I interviewed at Google for a L4 testing position. This interview is similar to the regular Software Engineering interview, but with some more emphasis on testing questions. Of the five interviews I had, one was a “soft” interview about leadership and social wisdom. The other four were very similar: write an algorithm, determine the runtime complexity, and create some test cases for it.

For testing specific questions, I was asked how I would test the online google calculator. I was also asked what instances in my career Ive experienced flaky test cases. I mentioned a few instances, but somehow forgot to mention selenium tests which can be notoriously flaky.

I dont have an offer yet, but the recruiter told me unofficially I’ll get one.

Algorithm 1 [Medium+]:

Given a 2-dimensional array of characters of which the values are all “x”, “y”, “0”, find the shortest distance between any x and any y. (Horizontal movements only, not diagonal movements, so an X at [0][0] and a Y at [1][1] are 2 apart.

This is the question I did the weakest on. I was going about it a bit slowly and considering brute force solutions first and my interviewer interrupted me to tell me to store all the Xs and Ys in 2 separate lists. It got confusing from there. I would probably have tried some modified BFS if left to my own devices.

Algorithm 2 [Medium]:

```
class someObject {
char c;
int a;
}
```

Given two arrays of these objects, match all objects in the opposite array by the character value. Multiply the integer together for each matching object and add it to a running total which is to be returned. i.e…

[{ c: ‘a’, a: 5 }, {c: ‘b’, a: 6}]

[{ c: ‘b’, a: 4}, {c: ‘a’, a:2}]

The "a"s and the "b"s match up to form 5 * 2 + 6 * 4 = 34

NOTE: this question was intentionally asked obtusely, you are supposed to ask what happens if there are multiple object in one array with the same character, or no matching character in the other array.

Algorithm 3 [Medium]

Given binary trees where the leaf nodes have a string representation of a mathematical variable and the non-leaf nodes have strings of a plus sign “+” where the whole tree represents a mathematical addition of many variables, determine if two such trees are mathematically equivalent. This is all a rather fancy way of asking if the count of all the values of the leaf nodes of the two trees are identical.

Algorithm 4 [Easy]

Return true or false for this modified substring matching. Given string = “axxxxxbxxxxcxxx” and substr=“abc” return true, because that substring exists in the search string in order (although there are some nonmatching characters between)

Algorithm 5 [Easy+]

Same interviewer as (4) asked me a 2nd algorithm question because (4) is pretty easy and I finished it quickly.

Write a “git bisect” implementation where the inputs are an array of code revisions and you have some external function you can call to run tests on a chosen revision.