tested.candidate
 1of 1 vote
AnswersGiven an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).
 tested.candidate in Switzerland Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswersFind a duplicates in an array of length n. The values are positive integers in the range between 1 .. n1
 tested.candidate in Switzerland Report Duplicate  Flag
Google Software Engineer Algorithm  0of 0 votes
AnswersYou have an array of integers. Each integer in the array should be listed three times in the array. Find the integer which does not comply to that rule.
 tested.candidate in Switzerland Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersCount triangles in an undirected graph where a triangle is a unique set of three vertices connected to one another.
 tested.candidate in Switzerland Report Duplicate  Flag
Google Software Developer Algorithm  0of 0 votes
AnswersIn 5 minutes write a code which checks if a given number is a power of two.
 tested.candidate in Switzerland Report Duplicate  Flag
Google Software Engineer Algorithm  0of 0 votes
AnswersCheck if two given words are anagrams of each other.
 tested.candidate in Switzerland Report Duplicate  Flag
Google Software Engineer Algorithm  3of 3 votes
AnswersGiven two sorted arrays find the element which would be Nth in their merged and sorted combination.
 tested.candidate in Switzerland Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswersGiven a BST with unique values find in a given tree a value closest to a given value X.
 tested.candidate in Poland Report Duplicate  Flag
Google Software Engineer Algorithm  0of 0 votes
AnswersGiven a dependency list of libraries (where an item is: library X depends on library Y) generate a list describing the order in which libraries should be loaded.
 tested.candidate in UK
Additional request: detect circular dependencies. Report Duplicate  Flag
Amazon Senior Software Development Engineer Algorithm  1of 1 vote
AnswersDesign the (content) search autocomplete feature on Kindle
 tested.candidate in UK Report Duplicate  Flag
Amazon Senior Software Development Engineer System Design  1of 1 vote
AnswersHow would you store the relations in a social network like Facebook and implement a feature where one user receives notifications when their friends like the same things as they do?
 tested.candidate in Switzerland Report Duplicate  Flag
Google Software Engineer System Design  2of 2 votes
AnswersDesign Facebook Messenger backend
 tested.candidate in UK Report Duplicate  Flag
Facebook Software Engineer System Design  0of 0 votes
AnswersHow would you design the feature in LinkedIn where it computes how many hops there are between you and another person?
 tested.candidate in UK Report Duplicate  Flag
Amazon Software Engineer / Developer System Design  1of 1 vote
AnswerArchitect a worldwide video distribution system
 tested.candidate in UK Report Duplicate  Flag
Amazon Software Engineer / Developer System Design  0of 0 votes
AnswersDesign Google Search
 tested.candidate in UK Report Duplicate  Flag
Amazon Software Engineer / Developer System Design  0of 0 votes
AnswerDesign a keyvalue store
 tested.candidate in UK Report Duplicate  Flag
Amazon Software Engineer / Developer System Design  0of 0 votes
AnswersDesign a clientserver application which allows people to play chess and checkers with one another.
 tested.candidate in UK Report Duplicate  Flag
Amazon Software Engineer / Developer Object Oriented Design  1of 1 vote
AnswersDesign the front end of Google Calendar
 tested.candidate in United States Report Duplicate  Flag
Google Software Engineer System Design  0of 0 votes
AnswersDesign YouTube viewcounting feature
 tested.candidate in United States Report Duplicate  Flag
Google Software Engineer System Design  0of 0 votes
AnswerDesign Google Suggest
 tested.candidate in United States Report Duplicate  Flag
Google Software Engineer System Design  1of 1 vote
AnswersDesign Gmail backend (data storage and API)
 tested.candidate in United States Report Duplicate  Flag
Google Software Engineer System Design  2of 2 votes
AnswersYou are given printouts from an algorithm which ran over an unsorted binary tree. One printout is from an inorder run and another from a preorder run. Can you reconstruct the tree? If so, then write an algorithm.
 tested.candidate in UK Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswersYou are given printouts from an algorithm which ran over a sorted binary tree. One printout is from an inorder run and another from a preorder run. Can you reconstruct the tree? If so, then write an algorithm.
 tested.candidate in UK Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersYou have N points on a 2D surface. List K points at a shortest distance to the point (0, 0).
 tested.candidate in UK Report Duplicate  Flag
Google Software Engineer Algorithm  0of 2 votes
AnswersThere is a company with 250 employees. Its records contain: EmployeeID, ManagerID (which is a reference to the EmployeeID of the manager).
 tested.candidate in UK
Part 1. List directly reporting employees for a given ID
Part 2. List all (also indirectly) reporting employees to a given ID Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswersYou are given a monochrome bitmap as a byte array (together with its width and height). Draw a horizontal line.
 tested.candidate in UK Report Duplicate  Flag
Google Software Engineer Bit Manipulation  2of 2 votes
AnswersPart 1: You are given a computer #1 with array Foo, a computer #2 with array Bar and a spare computer #3. You need to apply a function F to corresponding/matching elements of the two arrays. How would you do that?
 tested.candidate in UK
Part 2: Once you scale up, how would you balance the number of machines sorting with the machines applying the function?
Part 3: What if the master (which is distributing the work) dies and never recovers? Report Duplicate  Flag
Google Software Engineer Distributed Computing  1of 1 vote
AnswersYou are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering.
 tested.candidate in Switzerland
*** SPOILER ALERT ***
The question was pusposefully underspecified  upon questioning it was revealed that the string O might not necessarily include all characters used in string T  the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order). Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersYou are given two arrays  A & B. The length of the arrays is the same  N. The values in the arrays are integers from 0 to N  1 in random order and no number is repeated. You need to list a sequence of twoelement swaps required to reorder the array A into the order of the array B. Additionally, at each step of the sequence you are allowed to swap two elements only if one of them is 0.
 tested.candidate in UK Report Duplicate  Flag
Google Software Engineer Algorithm
Because all integers are positive and the array is long enough we can exploit the sign of the integer to mark which integer was encountered before:
private static int findDuplicated(int[] array) {
if (array == null  array.length < 1) {
return 1;
}
int result = 1;
for (int i = 0; i < array.length; i++) {
if (Math.abs(array[i]) < 1  array.length  1 < Math.abs(array[i])) {
result = 1;
break;
}
if (array[Math.abs(array[i])] >= 0) {
array[Math.abs(array[i])] = array[Math.abs(array[i])];
} else {
result = Math.abs(array[i]);
}
}
// Undo
for (int i = 0; i < array.length; i++) {
array[i] = Math.abs(array[i]);
}
return result;
}

tested.candidate
July 14, 2015 One way is to create a hash table with frequency of each integer and then search though it to find the noncompliant integer:
private static int find(int[] array) {
HashMap<Integer, Integer> frequencies = new HashMap<>();
for (int value : array) {
Integer frequency = frequencies.get(value);
if (frequency == null) {
frequencies.put(value, 1);
} else {
if (frequency == 3) {
return value;
}
frequencies.put(value, 1 + frequency);
}
}
for (int value : frequencies.keySet()) {
if (frequencies.get(value) != 3) {
return value;
}
}
return 0;
}

tested.candidate
July 14, 2015 Simple solution counting the number of bits set:
private static boolean slow(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if ((n & 1) == 1) {
count++;
}
n >>= 1;
}
return count == 1;
}
Better solution exploiting the properties of two's complement representation of and integer:
private static boolean fast(int n) {
return ((n & n) == n);
}

tested.candidate
July 14, 2015 If the strings are character arrays one can sort both  O(n log n)  and compare the result:
private static boolean check(String a, String b) {
char[] aa = a.toCharArray();
char[] bb = b.toCharArray();
Arrays.sort(aa);
Arrays.sort(bb);
return Arrays.equals(aa, bb);
}

tested.candidate
July 14, 2015 public class NthOfSortedArrays {
private static int nth(int[] a, int a1, int a2, int[] b, int b1, int b2, int n) {
if (a2 < a1) {
return b[b1 + n];
}
if (b2 < b1) {
return a[a1 + n];
}
int midA = (a1 + a2) / 2;
int midB = (b1 + b2) / 2;
if (midA  a1 + midB  b1 < n) {
// Middle is too little to reach n
// Get rid of the quarter which is surely smaller  it can't contain nth
if (a[midA] > b[midB]) {
// Lower b values are certainly below nth
return nth(a, a1, a2, b, midB + 1, b2, n  (midB  b1 + 1));
} else {
// Lower a values are certainly below nth
return nth(a, midA + 1, a2, b, b1, b2, n  (midA  a1 + 1));
}
} else {
// Middle is enough to reach n
// Get rid of the quarter which is surely bigger  it can't contain nth
if (a[midA] > b[midB]) {
// Upper a values are certainly above nth
return nth(a, a1, midA  1, b, b1, b2, n);
} else {
// Upper b values are certainly above nth
return nth(a, a1, a2, b, b1, midB  1, n);
}
}
}
private static int nth(int[] a, int[] b, int n) {
return nth(a, 0, a.length  1, b, 0, b.length  1, n);
}
public static int[] random() {
Random random = new Random();
int[] array = new int[1 + Math.abs(random.nextInt()) % 9];
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt();
}
Arrays.sort(array);
return array;
}
private static int[] join(int[] a, int[] b) {
int[] joined = new int[a.length + b.length];
System.arraycopy(a, 0, joined, 0, a.length);
System.arraycopy(b, 0, joined, a.length, b.length);
Arrays.sort(joined);
return joined;
}
public static void main(String[] arguments) {
int[] a = random();
int[] b = random();
Random random = new Random();
int n = 1 + Math.abs(random.nextInt()) % (a.length + b.length  2);
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(b));
System.out.println(Arrays.toString(join(a, b)));
System.out.println(n);
System.out.println(nth(a, b, n));
}
}

tested.candidate
July 14, 2015 private static class Tree {
public Tree left;
public double value;
public Tree right;
public Tree(Tree left, double value, Tree right) {
this.left = left;
this.value = value;
this.right = right;
}
}
public static double closest(Tree root, double value) {
double delta = Math.abs(root.value  value);
if (value < root.value && root.left != null) {
double left = closest(root.left, value);
if (Math.abs(left  value) < delta) {
return left;
}
}
if (root.value < value && root.right != null) {
double right = closest(root.right, value);
if (Math.abs(right  value) < delta) {
return right;
}
}
return root.value;
}

tested.candidate
July 14, 2015 I'm not trying to achieve anything, just posting the questions I was asked during onsites (I tried couple times with Google, once at Facebook and Amazon).
I also collected questions from a few friends who went (successfully) through their round of interviews.
And, yes, the folks at Google do ask open ended questions as part of the System Design interview
@eng.ahmed.moustafa  I can't remember exactly anymore but I think I asked the same question and got reply to assume the elements are distinct. It's a good question though.
@guilhebl  the trick is that the order of the listing determines that  elements in the "before" lists go to the left, elements in the "after" lists go to the right (i.e. it was still assumed that the in/preorder take the left child first)
Came up with the same algorithm, here's the code in Python:
DECREASING = 0
INCREASING = 1
def prepare(A, function, direction):
Z = [0] * len(A)
Y = [None] * len(A)
indices = range(len(A))
if DECREASING == direction:
indices.reverse()
first = 2
second = 1
seed = len(A)  1
delta = 1
elif INCREASING == direction:
first = 1
second = 2
seed = 0
delta = 1
for i in indices:
if i == indices[0]:
Z[i] = A[i]
Y[i] = (A[i], seed, seed)
else:
previous = i + delta
Z[i] = function(A[i], Z[previous] + A[i])
if Z[i] == A[i]:
start = i
else:
start = Y[previous][first]
result = function(Y[previous][0], Z[i])
if result == Z[i]:
stop = i
else:
stop = Y[previous][second]
Y[i] = [result, 0, 0]
Y[i][first] = start
Y[i][second] = stop
return Y
def check(U, V):
for i in range(len(U)  1):
diff = abs(U[i + 1][0]  V[i][0])
if i == 0:
maximum = diff
index = 0
elif diff > maximum:
maximum = diff
index = i
return (maximum, index)
def find(A):
C = prepare(A, min, INCREASING)
B = prepare(A, max, DECREASING)
(maximum1, index1) = check(B, C)
D = prepare(A, max, INCREASING)
E = prepare(A, min, DECREASING)
(maximum2, index2) = check(E, D)
if maximum1 < maximum2:
print('From %d to %d' % (D[index2][1], D[index2][2]))
print('From %d to %d' % (E[index2 + 1][1], E[index2 + 1][2]))
else:
print('From %d to %d' % (C[index1][1], C[index1][2]))
print('From %d to %d' % (B[index1 + 1][1], B[index1 + 1][2]))
A = [2, 1, 2, 1, 4, 2, 8]
find(A)
A = [2, 2, 2, 2, 1, 1, 1, 1]
find(A)

tested.candidate
March 23, 2015 The answer is yes and the solution is:
1. Take the first element of the preorder list
2. Find that element in inorder list and split that list into two lists  inorder before and inorder after
3. Similarly, for the preorder list remove the first element and split it into two parts of the same length as in point 2  preorder before and preorder after
4. Apply this function recursively to "before" and "after" lists
The answer is yes and the solution is:
1. Take the first element of the preorder list
2. Find that element in inorder list and split that list into two lists  inorder before and inorder after
3. Similarly, for the preorder list remove the first element and split it into two parts of the same length as in point 2  preorder before and preorder after
4. Apply this function recursively to "before" and "after" lists
First step is to calculate the distance for each point = sqrt(x * x + y * y).
Next step is to fint the K points with the smallest distance.
One way is just to sort the points by their distance and list K first items in the resulting list  this would obviously have a complexity of O(N log N).
Another way would be to insert the points into a binary min heap of length K while calculating the distances  this would have a complexity of O(N log K) which might be beneficial (in terms of time and space) if K is much smaller than N.
Part 1 is easy  just go through all records and list the record if the ManagerID is equal to the given ID
Part 2  one solution is to build a (hierarchy) tree of all employees, search for the entry for employee with the given ID and then list its subtree depthfirst. This is no problem for 250 employees, but if there were more then we might want to explore different solution.
Let's assume that the organization of pixels is: a line of pixels (from left to right) is a consecutive sequence of bytes (each byte holding 8 pixels  bit 0 is the leftmost pixel, bit 7 the rightmost) and then lines are a consecutive sequence from top to bottom. It is important to ask the interviewer if this is the right assumption.
One can iterate pixelbypixel but this would potentially access the same byte multiple times. This can be improved by dividing drawing of the line into three parts: drawing the head  first byte of the line where only the high part of the bits is affected, then the body  the part of the line where a full bytes are affected, and finally the tail  last byte of the line where only the low part of the bits is affected.
import math
def blank(width, height):
return [0] * int(math.ceil(width * height / 8.0))
def line(bitmap, width, height, x1, x2, y):
a_full = width * y + x1
z_full = width * y + x2
a_head = a_full >> 3
a_bits = a_full & 0x7
a_body = a_head + (1 if 0 != a_bits else 0)
z_tail = z_full >> 3
z_bits = (z_full & 0x7) + 1
z_body = z_tail  (1 if 8 != z_bits else 0)
# Head
if a_head != a_body:
bitmap[a_head] = (0xFF << a_bits) & 0xFF
# Body
for i in range(a_body, z_body + 1):
bitmap[i] = 0xFF
# Tail
if z_tail != z_body:
bitmap[z_tail] = ~(0xFF << z_bits) & 0xFF
def hexed(bitmap):
return ''.join(['%02X' % byte for byte in bitmap])
width = 32
height = 3
bitmap = blank(width, height)
line(bitmap, width, height, 7, 22, 1)
print(hexed(bitmap))

tested.candidate
March 21, 2015 Nice catch, seems like a better solution. Good thing though that my solution was good enough to pass to the onsite
 tested.candidate March 21, 2015Part 1: The arrays need to be sorted first and then the function can be applied. This can be accomplished by splitting the sorting between the machines, then merging the results and then exchanging the parts of the arrays for application of the function (a form of a mapreduce algorithm). Heap sort would be particularly useful as it produces consecutive (and sorted) elements during sorting which could already be used for application of the function.
Part 2: Either run a small subset first to get an idea if it is linear distribution and then divide statically according to that or try to adapt during processing depending on the load of the machines.
Part 3: Use master election algorithms (gossip algorithms, etc.).
The solution to this question is a decoratesortundecorate algorithm. The characters of the string T are supposed to be decorated with values which are indices of those characters in the string O or value 1 if they are absent in string O. Since the order of the characters decorated with 1 is not important we are free to use any sorting algorithm (i.e. not necessarily a stable one).
def reorder(t, o):
# Build a decorating hash table
lut = {}
for i in range(len(o)):
lut[o[i]] = i
# Reorder
return ''.join(sorted(t, key=lambda character: lut[character] if lut.has_key(character) else 1))
print reorder('hello world', 'wrled')

tested.candidate
March 21, 2015 While iterating through A use a look up table to figure out the indices of the elements to be swapped.
Algorithm (pseudocode):
Build a look up table LUT from the array A mapping a value to its position in the array A
Iterate through the array A{
If value at current index I is misplaced then{
Find the index J of the element which should be placed at the current index I
If A[I] == 0 or A[J] == 0 then{
Do one swap between A[I] and A[J]
}Else{
Find the position of zero K
Do three swaps between A[I], A[J] & A[K]
}
Update the LUT
}
}
Code (Python):
def reorder(a, b):
# Check input
if len(a) != len(b):
print('Mismatched array length')
return
print('A = %s' % str(a))
print('B = %s' % str(b))
N = len(a)
# Building LUT
lut = N * [None]
for i in range(N):
lut[a[i]] = i
print('LUT = %s' % str(lut))
# Reordering
for i in range(N):
impostor = a[i]
expected = b[i]
if impostor != expected:
j = lut[expected]
if 0 in [expected, impostor]:
print('Swapping %d and %d' % (i, j))
else:
print('Swapping %d and %d through %d' % (i, j, lut[0]))
a[j] = impostor
a[i] = expected
lut[impostor] = j
lut[expected] = i
print('A = %s' % str(a))
reorder([1, 3, 2, 4, 0], [4, 0, 3, 2, 1])

tested.candidate
March 21, 2015 Open Chat in New Window
The answer is to traverse the tree (DFS or BFS) while keeping track of the number of nodes we've seen so far (with the first one indexed 1). Each time we see a new node pick a random number from 0 to index1. If the random number is equal to 0 then remember the node to be returned (replace the previous one if necessary).
 tested.candidate July 14, 2015