interviews be like...

bipartite_matching.js

class Graph {
  constructor(edgesArray) {
    this.V = new Set();
    this.E = {};

    if(edgesArray.length === 0) {
      return this;
    }

    edgesArray.forEach(edge => {
      const [a, b] = edge.split('->');
      this.V.add(a);
      this.V.add(b);
      this.E[a] = (this.E[a] || new Set()).add(b);
    });
  }

  isBipartite() {
    const colors = new Map();
    for(let node of this.V) {
      if(colors.has(node)) {
        continue;
      }

      const queue = [node];
      colors.set(node, 1);

      while(queue.length > 0) {
        const current = queue.shift();
        const currentColor = colors.get(current);
        const neighborColor = -1 * currentColor;
        // console.log(node, queue, colors, currentColor, neighborColor, current, this.E[current]);
        const neighbors = this.E[current] || new Set();
        for(const neighbor of neighbors) {
          if(!colors.has(neighbor)) {
            colors.set(neighbor, neighborColor);
            queue.push(neighbor);
          } else {
            if(neighborColor === currentColor) {
              return false;
            } else {
              continue;
            }
          }
        }
      }
    }
    return true;
  }

  cardinality() {
    const matchRights = {};
    let count = 0;
    for(let vertex of this.V) {
      const visited = new Set();
      if(this.findPath(vertex, visited, matchRights)) {
        count++;
      }
    }
    return count;
  }

  findPath(vertex, visited, matchRights) {
    if(visited.has(vertex) || !this.E[vertex]) {
      return false;
    }
    visited.add(vertex);
    const neighbors = this.E[vertex];
    if(!neighbors) {
      return false;
    }
    for(const neighbor of neighbors) {
      const candidate = matchRights[neighbor];
      const isNotMatched = candidate === undefined;
      const canBeRematched = this.findPath(candidate, visited, matchRights);
      if(isNotMatched || canBeRematched) {
        matchRights[neighbor] = vertex;
        return true;
      }
    }
    return false;
  }
}

function BipartiteMatching(strArr) { 
  if(strArr.length === 0) {
    return 0;
  }
  const g = new Graph(strArr);
  if(!g.isBipartite()) {
    return 0;
  }

  return g.cardinality(); 

}

   
// keep this function call here 
console.log(BipartiteMatching(readline()));

dijkstra shortest path algorithm.md

Dijkstra's shortest path algorithm is not able to account for graphs with negative weight edges. The algorithm assumes that all edge weights are non-negative so that the shortest path between any two nodes can be progressively built up by adding the nearest node not yet considered to the path in each step. When a graph contains negative weight edges, adding a node to the path could lead to a situation where a previously considered path is no longer the shortest, which violates the algorithm's assumptions.

Here's a basic implementation of Dijkstra's algorithm in JavaScript. This implementation assumes the graph is represented as an adjacency list where each node maps to a list of its neighbors along with the corresponding edge weights:

function dijkstra(graph, start) {
    const distances = {}; // Distance from start to node
    const previous = {}; // Previous node in optimal path from source
    const visited = new Set(); // Nodes that have been visited
    const queue = new PriorityQueue(); // Priority queue of all nodes in the graph

    // Initialize distances to infinity and queue with all nodes
    for (const node in graph) {
        distances[node] = Infinity;
        queue.enqueue(node, Infinity);
        previous[node] = null;
    }

    // Set the distance for the start node to 0
    distances[start] = 0;
    queue.enqueue(start, 0);

    while (!queue.isEmpty()) {
        let smallest = queue.dequeue().element; // Node with the smallest distance
        
        if (visited.has(smallest)) continue; // Skip if already visited
        visited.add(smallest);

        for (const neighbor in graph[smallest]) {
            let alt = distances[smallest] + graph[smallest][neighbor];
            if (alt < distances[neighbor]) {
                distances[neighbor] = alt;
                previous[neighbor] = smallest;
                queue.enqueue(neighbor, distances[neighbor]);
            }
        }
    }

    return { distances, previous };
}

class PriorityQueue {
    constructor() {
        this.collection = [];
    }

    enqueue(element, priority) {
        let contains = false;
        for (let i = 0; i < this.collection.length; i++) {
            if (this.collection[i].priority > priority) {
                this.collection.splice(i, 0, { element, priority });
                contains = true;
                break;
            }
        }
        if (!contains) {
            this.collection.push({ element, priority });
        }
    }

    dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        return this.collection.shift();
    }

    isEmpty() {
        return this.collection.length === 0;
    }
}

// Example usage
const graph = {
    a: { b: 2, c: 1 },
    b: { a: 2, d: 1, e: 3 },
    c: { a: 1, d: 4 },
    d: { b: 1, c: 4, e: 1 },
    e: { b: 3, d: 1 }
};

console.log(dijkstra(graph, 'a'));

first step in heap sort.md

The first step in Heap Sort is to build a heap from the given array. Heap Sort uses a binary heap data structure to sort elements, and the process can be divided into two main phases:

1. Building a Heap from the Array

• A binary heap can be a max heap or a min heap. In a max heap, each parent node is greater than or equal to the values of its children, while in a min heap, each parent node is less than or equal to the values of its children.
• To sort an array in ascending order, you build a max heap. For descending order, you build a min heap.
• The idea is to treat the input array as a nearly complete binary tree, where each element of the array corresponds to a node in the tree. The tree structure is maintained in the array in level order, where the parent at index i has its children at indices 2i + 1 and 2i + 2.
• Starting from the last non-leaf node all the way up to the root node, you apply the heapify process. The last non-leaf node is found at index n/2 - 1 (assuming the first index is 0, where n is the total number of elements in the array).
• The heapify process adjusts the subtree rooted at the given node to satisfy the heap property. For a max heap, this means the root of the subtree has the maximum value of all nodes in the subtree. The heapify process is applied recursively to build the heap in a bottom-up manner.

2. Sorting the Array

After the heap is built, the array elements are not sorted yet. The sorting is done in the second phase:

• Swap the root of the heap (the largest element in a max heap) with the last element of the heap, effectively moving the maximum element to its correct sorted position at the end of the array.
• Reduce the heap size by one (excluding the last element which is now in its correct position).
• Apply the heapify process on the root of the now reduced heap, ensuring the top of the heap is again the largest element among the remaining unsorted elements.
• Repeat this process until all elements are sorted.

Here's a brief illustration of the first step in code:

function heapify(arr, n, i) {
    let largest = i; // Initialize largest as root
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    
    // If left child is larger than root
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // If largest is not root
    if (largest !== i) {
        // Swap
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// Function to build a max heap
function buildHeap(arr) {
    const n = arr.length;
    // Index of the last non-leaf node
    const startIdx = Math.floor(n / 2) - 1;
    
    // Perform reverse level order traversal from last non-leaf node and heapify each node
    for (let i = startIdx; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

This code snippet defines the heapify function and shows how to build a heap from an array. The sorting phase would then proceed to sort the array by iteratively removing the largest element (root of the heap) and heapifying the remaining elements.

random.txt

A Solutions Architect is designing a critical business application with a relational database that runs on an EC2 instance.It requires a single EBS volume that can support up to 16, 000 IOPS. Which Amazon EBS volume type can meet the performance requirements of this application?
Provisioned IOPS SSD (io1/io2)

An application requires a highly available relational database with an initial storage capacity of 8 TB. The database will grow by 8 GB every day.To support expected traffic, at least eight read replicas will be required to handle database reads. Which option will meet these requirements?
Aurora

Status data will be exposed to the rest of the Android system via
Content Provider

What is an Android ContentProvider and what is it typically used for?
An Android ContentProvider is a component that manages access to a structured set of data. It encapsulates the data and provides mechanisms for defining data security. ContentProviders are typically used for sharing data between different applications, allowing one app to store data in a way that others can easily query or modify. This is particularly useful for common data types (such as contacts, calendar events) that many apps might need to access.

In Dart, how can you implement the Visitor design pattern?
By defining an abstract `accept` method in the base class and implementing it in derived classes to call the appropriate `visit` method.

In Flutter, how can you optimize the performance of a ListView with a large number of items?
By using the `ListView.builder` constructor to create a lazily loaded list.

What is the purpose of using `Zone` in Dart?
To provide a context for isolating the execution of asynchronous operations.

What are the four essential states of an activity in Android?
Active, Paused, Stopped, Destroyed.

What is the purpose of the `TickerProvider` mixin in Flutter?
To provide a ticker for driving animations that update with the frame rate.

How can you implement Dependency Injection in Dart?
By using the injectable package or creating a custom service locator class.

In Dart, how can you create a mixin that can only be applied to classes that implement a specific interface?
By using the on keyword followed by the interface name in the mixin declaration.

In Flutter, how can you handle platform-specific code?
By using `dart:io` to detect the platform and create separate code paths or by using platform channels to communicate with native code.

What is the purpose of `Isolate` in Dart?
To provide a way to run code in a separate thread-like environment to avoid blocking the main UI thread.

In Flutter, how can you create a custom implicit animation?
By extending the ImplicitlyAnimatedWidget class and implementing a custom Tween.

In Dart, how can you create an extension method for an existing class?
By using the `extension` keyword followed by the extension name, `on` keyword, and the target class name.

session state sotrage for stateless web server.txt

For a highly available web application using stateless web servers, storing session state data externally is crucial to ensure scalability and reliability. Two AWS services that are particularly suitable for this purpose are:

    Amazon DynamoDB:
        DynamoDB is a fully managed NoSQL database service that provides fast and predictable performance with seamless scalability. It's a good choice for storing session state because of its high availability and durability. DynamoDB can handle high request rates, making it suitable for applications with large amounts of session data. Its built-in redundancy across multiple availability zones ensures that the session state is preserved even in the case of infrastructure failures.

    Amazon ElastiCache:
        ElastiCache supports two popular in-memory data stores: Redis and Memcached. Both are excellent choices for session state caching due to their high performance and low-latency data access. ElastiCache is managed, reducing the administrative burden and ensuring that the caching layer is highly available. Redis, in particular, supports data persistence, making it a reliable choice for session state data that needs to be quickly accessible across multiple stateless web servers. Additionally, Redis offers data structures like strings, hashes, lists, sets, and sorted sets, which can be useful for complex session states.

Both services are designed to be highly available and scalable, fitting well into architectures that require stateless web servers while managing session states externally. The choice between DynamoDB and ElastiCache (Redis or Memcached) would depend on specific application requirements, such as the need for persistent storage, data structure complexity, and latency sensitivity.

store data for durability.md

Amazon S3 (Simple Storage Service) is a scalable object storage service that is designed for durability, availability, and scalability. By enabling versioning on an S3 bucket, you can preserve, retrieve, and restore every version of every object stored in the bucket. This means that even if a user accidentally deletes or overwrites a file, you can easily recover the previous version of that file. Versioning is a critical feature for protecting against the loss of important data due to human errors or application faults.

Here's why S3 with versioning is the best choice for this scenario:

Durability and Availability:

S3 provides high durability (99.999999999% or 11 9's) and availability, ensuring that your data is safe and accessible when needed.

Versioning:

Once enabled, every object in the bucket will have all of its versions stored indefinitely (or for a configured period), unless explicitly removed. This allows for easy recovery of previous versions of data.

Protection Against Deletion:

S3 also offers features like MFA Delete (Multi-Factor Authentication on delete operations) which can add an additional layer of security against accidental or malicious deletions. Lifecycle Policies: You can configure lifecycle policies to automate the transition of old versions to cheaper storage classes or even schedule deletion if necessary, helping manage costs while keeping your data protected.

The other options like EBS (Elastic Block Store), an EC2 instance, or simply using two S3 buckets without versioning do not inherently provide the same level of protection against accidental deletions or the ability to easily recover previous versions of the data.

Therefore, S3 with versioning is the most suitable and protective action for storing sales figures documents and safeguarding against unintended user actions.

string_reduction.js

const conversion_pairs = {
  a: { b: "c", c: "b" },
  b: { a: "c", c: "a" },
  c: { a: "b", b: "a" }
};

function convertPair(a, b) {
  return conversion_pairs[a][b];
}

function StringReduction(str) { 
  let countA = 0, countB = 0, countC = 0;
  const len = str.length;
  if(len < 2) {
    return len;
  }
  for(let i = 0; i < len; i++) {
    const ch = str[i];
    countA += ch === 'a' ? 1 : 0;
    countB += ch === 'b' ? 1 : 0;
    countC += ch === 'c' ? 1 : 0;
  }
  if(countA === 0 || countB === 0 || countC === 0) {
    return countA + countB + countC;
  }

  let newStr = "";
  for(let i = 0; i < len; i+=2) {
    newStr += convertPair(str[i], str[i+1]);
  }
  if(len % 2 === 1) {
    newStr += str[len -1];
  }

  return StringReduction(newStr);
}
   
// keep this function call here 
console.log(StringReduction(readline()));

All that in 90 minutes... chatGPT++