Google Manager interview questions

Interview Details – Round 1: 1. Explain and Write KnapSack Algo with Memorization 2. Given a undirected graph, clone it. Now if the undirected graph has the neighbors with the nodes as same data - how do you make sure you create the exact same branches and also how do you make sure you don't run into loops for the exact node. He gave a empty directed graph and asked me write code after that. 3. Given two Btrees. these trees "may" have right and left branches swapped. Now compare it. Round 2: 1. Given a N different open and close braces in a string "( { [ } ] )". How do you check whether the string has matching braces. 2. Given a unsorted array. Create a balanced BTREE 3. Print a tree like (Parent ( leftchild (leftchild, rightchild), rightchild(leftchild,rightchild) ) ) Round 3: Given a kernal code in "0"th machine. How soon you can replicate the kernal across N machines. Now if the machines has upload and download bandwidth constraints, how can you impove the copy time. Round 4: 1. Design Short URL. 2. Given a List with duplicate Strings, how do you remove duplicate Strings Round 5: 1. How do you design a Maze and what kind of data structures you use for Maze. 2. Now print the shorted path from start to end point.

1st round - Phone interview with HR recruiter 2nd-4th rounds - In-person interviews with various Google employees, including some in the function/area of the position, as well with someone not in the same function/area of the company.