Technical phone screen (45 min):
You are given an array A of distinct integers, you have to return another array B which transforms the first array such that the minimum element in the new array is 1 and all the other elements maintain their relative ordering i.e. if A[i] > A[j] then it should also be that B[i] > B[j] and similarly for other elements. Better explanation of this question can be found here.
Input: [4, 2, 3, 7]
Output: [3, 1, 2, 4]
Input: [-4, -2, -3, -7]
Output: [2, 4, 3, 1]
Follow ups:
What if the elements are not distinct?
Second question: You have to perform the same operation on a 2D array of distinct elements.
What if the matrix has duplicates?
Input:
1 5 6
4 3 2
8 7 9
Output:
1 3 4
3 2 1
5 4 6
Onsite (5 rounds):
Round 1 - Googleyness & Leadership (Behaviourial)
I was asked about my past leadership roles, how I meet my deadlines, how I would lead a team etc. The interviewer built up questions from my responses itself.
Round 2 - Techinical
Given an N-ary tree, if a water drop is dropped at the root of the tree and it flows down throughout the tree, find out how much time will it take to wet the entire tree. The time to travel each edge is given.
Given an input string and a list of valid words, find if the input can be transformed into a valid word by 0 or 1 replacement i.e. at max only 1 character can be replaced to another character.
Input: “applo” , [“apple”, “apply”, “cat”, “dog”]
Output: True
Explanation:
“applo” can be made into “apple” or “apply” by replacing o with e/y.
Optimize for -
multiple such input queries are there
character set is huge
Round 3 - Technical
Given a complete binary tree such that the nodes are filled in a level-wise manner starting from 0 to n. Given a number find if it exists in the tree.
0
/ \
1 2
/ \ / \
3 4 5 6
/
7
find(7)
find(8)
find(4)
Round 4 - Technical
Given two strings a and b, find if a can be subsequence of b or by concatenating b.
Input:
a = jaja
b = baj
Output:
True
Explanation:
baj | baj | baj
“baj” can be concatenated three times to get “jaja”.
Follow-up:
Find the minimum number of concatenations. Optimize it further from O(n * m)
Given an array of elements. We have 3 functions -
get(index) - return value at given index
set(index, val) - set value at given index
setAllElements(val) - set all elements as the given value
All of these should be in O(1).
Round 5 - Technical
Given two expression in the form of a binary tree, find if both the expressions are equivalent.
exp1 = a + b + c + a
exp2 = a + a + b + c
+
/ \
+ +
/ \ / \
a b c a
+
/ \
+ +
/ \ / \
a a b c
You are given root of the two trees. There are only lowercase english alphabets and only addition operator.
**Follow up - **
Subtract operator is also there. How will you evaluate that.
exp1 = (a + b) + (c - a)
exp2 = (a + b) - (c - a)
Follow up -
Multiplication operator is also there.
exp1 = (a + b)*(c + d)
exp2 = ac + db + cb + bd
Result
I was told I performed good on 3 interviews but received mixed reviews for 2 therefore it was difficult to make a strong case for me. I didn’t perfomr quite well in Round 3. The second mixed review would probably be for Round 2 because I wasn’t able to optimize the second question further.