Google Interview Hacks

10 most common problems Dynamic Programming? 1. Longest Common Subsequence 2. Longest Increasing Subsequence 3. Edit Distance 4. Minimum Partition 5. Ways to Cover a Distance 6. Longest Path In Matrix 7. Subset Sum Problem 8. Optimal Strategy for a Game 9. 0-1 Knapsack Problem 10. Boolean Parenthesization Problem Longest Common Subsequence? 1) Optimal Substructure: Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]). If last characters of both sequences match (or X[m-1] == Y[n-1]) then L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2]) If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]) 2. Longest Increasing Subsequence? There is a recursive way, dynamic programming with brut...

Topological Sorting vs Depth First Traversal (DFS)? In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices.

Explain Boggle (Find all possible words in a board of characters) The idea is to consider every character as a starting character and find all words starting with it. All words starting from a character can be found using Depth First Traversal. We do depth first traversal starting from every cell. We keep track of visited cells to make sure that a cell is considered only once in a word.

Explain Topological Sort? In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don't print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

Explain Minimum Spanning tree *Kruskal* ? 1. Sort all the edges in non-decreasing order of their weight. 2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. 3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Explain does Minimum Spanning tree *Prim* ? 1) Create a set mstSet that keeps track of vertices already included in MST. 2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first. 3) While mstSet doesn't include all vertices ....a) Pick a vertex u which is not there in mstSet and has minimum key value. ....b) Include u to mstSet. ....c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v

How To detect cycle in a Graph *Union Find*? Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. Note that we have discussed an algorithm to detect cycle. This is another method based on Union-Find. This method assumes that graph doesn't contain any self-loops

Shortest Path from every vertex to every other vertex *Floyd Warshall? We initialize the solution matrix same as the input graph matrix as a first step. Then we update the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and update all shortest paths which include the picked vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every pair (i, j) of source and destination vertices respectively, there are two possible cases. 1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is. 2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j].

Explain Shortest Path from source to all vertices *Dijkstra* algorithm? is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. Mark all nodes unvisited. 1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty. 2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first. 3) While sptSet doesn't include all vertices ....a) Pick a vertex u which is not there in sptSetand has minimum distance value. ....b) Include u to sptSet. ....c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight o...

Explain Depth First Search (DFS)? Pick a starting node and push all its adjacent nodes into a stack. Pop a node from stack to select the next node to visit and push all its adjacent nodes into a stack. Repeat this process until the stack is empty. However, ensure that the nodes that are visited are marked. This will prevent you from visiting the same node more than once. If you do not mark the nodes that are visited and you visit the same node more than once, you may end up in an infinite loop.

Explain Breadth First Search (BFS)? First move horizontally and visit all the nodes of the current layer Move to the next layer. To avoid processing a node more than once, we use a boolean visited array.

Top 10 graph problems? 1. Breadth First Search (BFS) 2. Depth First Search (DFS) 3. Shortest Path from source to all vertices *Dijkstra* 4. Shortest Path from every vertex to every other vertex *Floyd Warshall* 5. To detect cycle in a Graph *Union Find* 6. Minimum Spanning tree *Prim* 7. Minimum Spanning tree *Kruskal* 8. Topological Sort 9. Boggle (Find all possible words in a board of characters) 10. Bridges in a Graph

How to check if a given Binary Tree is BST or not? If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false. See A program to check if a binary tree is BST or not for more details.

Which Data Structure Should be used for implementing LRU cache? We use two data structures to implement an LRU Cache. Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).The most recently used pages will be near front end and least recently pages will be near rear end. A Hash with page number as key and address of the corresponding queue node as value. See How to implement LRU caching scheme? What data structures should be used?

How to implement a queue using stack? A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways: Method 1 (By making enQueue operation costly) Method 2 (By making deQueue operation costly) See Implement Queue using Stacks

How to implement a stack using queue? A stack can be implemented using two queues. Let stack to be implemented be 's' and queues used to implement be 'q1' and 'q2'. Stack 's' can be implemented in two ways: Method 1 (By making push operation costly) Method 2 (By making pop operation costly) See Implement Stack using Queues

Can doubly linked be implemented using a single pointer variable in every node? Doubly linked list can be implemented using a single pointer. See XOR Linked List - A Memory Efficient Doubly Linked List

Which data structures are used for BFS and DFS of a graph? Queue is used for BFS Stack is used for DFS. DFS can also be implemented using recursion (Note that recursion also uses function call stack).

What is a Linked List and What are its types? A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items - the data and a reference to the next node.Types of Linked List : Singly Linked List : In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL. For example 1->2->3->4->NULL Doubly Linked List : Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node. Eg. NULL<-1<->2<->3->NULL Circular Linked List : Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first] ...

What are Infix, prefix, Postfix notations? Infix notation: X + Y - Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D Postfix notation (also known as "Reverse Polish notation"): X Y + Operators are written after their operands. The infix expression given above is equivalent to A B C + * D/ Prefix notation (also known as "Polish notation"): + X Y Operators are written before their operands. The expressions given above are equivalent to / * A + B C D