Interviewed in March at Google (Mountain View offices) for a Software Engineer, Tools & Infrastructure (SETI) position.
About myself: recent MSCS graduate.
Here’s how the day went:
Took place in the buildings Google dedicates to interviewing candidates (a 5-10 min walk from the main campus).
4 45-minutes interviews:
- 2 in the morning, then lunch with a Google engineer (who do not write feedback for the committee, hence this is a good time to ask all of your questions), followed by the last 2 interviews.
- All interviews were technical and I did not get system design questions. 3 of these interviews were focused on data structures & algorithms (i.e. Leetcode-like), but one of them was conducted by a SETI engineer, and thus more dedicated to tests (i.e. “how would you test your algorithm? What type of inputs and what specific conditions would you specify?”)
Here are the questions I faced:
Round 1:
Given an array of n integers, return the result of all possible equations you can generate by adding the following operators in-between the numbers: +, -, *, /, () (for prioritization).
Examples:
[4, 2]: Can generate 4 + 2 = 6, 4 - 2 = 2, 4 * 2 = 8, 4 / 2 = 2 -> Return [6,2,8,2]
[4, 2, 3]: Can generate: 4 + 2 + 3, 4 + 2 - 3, 4 + 2 * 3, 4 + 2 / 3
4 - 2 + 3, 4 - 2 - 3, 4 - 2 * 3, 4 - 2 / 3
Etc.
But we can prioritize operations as well: 4 + (2 * 3) = 10 != (4 + 2) * 3 = 18
Remarks:
The equations must use all elements of the array,
Do not permute the elements of the array, i.e. respect their order,
The order of the results in the returned array does not matter. i.e. for [4, 2], [6,2,8,2], [6,2,2,8], [8,6,2,2] etc. will be accepted,
If different equations lead to the same results, include all of them (i.e. no need to remove the duplicates),
Divide by Zero errors should be handled.
Hints:
The output size will be combinatorial in the number of elements,
Don’t forget the cases where the parenthesis for prioritization are set in the middle of the array. E.g. for [4,2,1,3], one possible equation would be 4 / ((2 - 1) / 3) = 12.
Round 2:
Given a string, which may contain substrings constituted of 3 or more occurrences of the same character, remove all these substrings, including the initial ones (present in the initial string), and the ones created by removing a first substring.
Examples:
- "abcdddf" -> "abcf"
- "eegdhhhouweppp" -> "eegdouwe"
- "aabbccdddcba" -> "aabbcccba" -> "aabbba" -> "aaa" -> ""
Return the modified substring.
Round 3:
Consider a n-ary tree (i.e. each parent node has at least one children (except the leafs) and up to n).
Some children nodes may be missing, i.e. a parent node could have only n/2 children.
The order of the children nodes matters here and, referring to them with their index i, a parent node with a child at index i is different than a parent node without a child at index i.
That is, the missing children nodes can be positioned anywhere between the index 0 and n - 1, and are represented by None values innode.children.
Write a recursive, in-place function which moves all missing children (i.e. the None values) to the right of the children list, and consequently, the valid children to the left.
Don’t return anything, write an in-place function.
Examples:
Suppose we consider 5-ary trees.
1 - A root node with the following list of children: [NodeA, Null, Null, NodeB, NodeC]would see its list of children changed to [NodeA, NodeB, NodeC, Null, Null].
2 - This needs to be done for every parent node in the tree which have a non-empty list of children. Hence, supposing NodeAhas the following list of children: [Null, Null, Null, Null, NodeD], this list would be thus changed to [NodeD, Null, Null, Null, Null].
Round 4:
https://leetcode.com/problems/binary-tree-maximum-path-sum
Define a path in a binary tree as a contiguous sequence of edges going from node A to node B.
The path is not oriented, i.e. it can start from a leaf, go through the root and end up at another leaf, but it cannot go through the same node twice.
Define the value of a path as the sum of the nodes’ value it goes through.
Return the maximum value obtained when considering all possible paths.
Hint:
It may not be the value of the longest path as the nodes’ value can be negative.
Miscellaneous remarks:
I was proposed a chromebook for coding during the interviews (but no possibility of compilation / execution). It appears that Google is extending this choice now.
All interviewers introduced themselves prior to the technical portion, and ensured some time would be left at the end of the interview for asking questions, which is always welcome.
Q1. LeetCode - The World's Leading Online Programming Learning Platform
Q2. LeetCode - The World's Leading Online Programming Learning Platform
Q4. LeetCode - The World's Leading Online Programming Learning Platform
Q1: Given an array of n integers, return the result of all possible equations you can generate by adding the following operators in-between the numbers: +, -, *, /, () (for prioritization).
Java solution https://leetcode.com/playground/9WPVeH84
Based on LeetCode - The World's Leading Online Programming Learning Platform
Q2: Given a string, which may contain substrings constituted of 3 or more occurrences of the same character, remove all these substrings, including the initial ones (present in the initial string), and the ones created by removing a first substring.
Java solution https://leetcode.com/playground/E2Zi83eA
Time complexity: O(n) .
Space complexity: O(n) .