Subscribe to Its not a bug, It's a feature

## Google Interview Questions

I'd like to start off by thanking everyone that gave me advice, links, and reading materials to study up on for my Google interview last week. It went pretty well, even though there were a few technical difficulties. Google docs were not working, so no live coding. But I'm happy to announce that they want to do another interview with me. (Stupidly enough I scheduled the interview for release day for Guildwars 2, but oh well). Either way I'd thought I'd share the questions I was asked, in case anyone is curious.

The interview started with a few simple questions about trees. Given some arbitrary non-balanced tree, whats the big oh to determine if its uni-value (all elements are same value). We also talked about different edge cases of the tree structure. What if its balanced, what if its linear, which would cause worst big-oh.

Which lead to Programming Problem No. 1: Write a program to count the number of uni-value sub-trees in a given tree. Explain reasoning, and implementation decisions.

Here is what I wrote:
Spoiler

Programming Question No.2: You are given some number, in String format, create a method public static String increment( String someInt), where you add 1 to the input string, and return the new number.

The quick answer would be
```(String.parseInt( someInt ) + 1) + ""
```
so after I answered that they asked what if the input is insanely huge (Bigger than BigInt).

Here is what I wrote:
Spoiler

And lastly, Programming Question No. 3 given 2 different arrays of values 'a' and 'b', determine if there is a combination of some element in 'a' and some element in 'b' that sums to a given value 'c'. private static boolean slowFindSum(int[] a, int[] b, int c).

The first question was, whats the simple way, and the Big-Oh?
Spoiler

Part two, and admittedly I struggled a bit on this. How do do you improve it? Then write the code. Took me a while to get it, so i need practice there but I think I came up with a good solution. They did give me a hint. Consider the importance of difference between c and some element in b.

Heres what I came up with:
Spoiler

Good luck if you try these problems yourself, and I'll let you know how the next one goes.

### 11 Comments On This Entry

Page 1 of 1

#### mostyfriedman

21 August 2012 - 08:46 PM
For the last question the first idea that came to mind was to sort the second array. Then for every element in array a, search for c-a in b using binary search, Big-oh = (nlgn)
0

#### CarDriver

21 August 2012 - 09:28 PM
Cool, good luck on your next interview! I'll be wasting my life on Guild Wars 2

If you don't mind me asking, what kind of background (educational or otherwise) does Google look for when hiring? And did they ask you any ridiculously difficult problem like "how many ping pong balls can fit in a school bus?" just to see your thought process, or was all of this done through programming problems?
0

#### mostyfriedman

21 August 2012 - 09:31 PM

AVReidy, on 22 August 2012 - 07:28 AM, said:

Cool, good luck on your next interview! I'll be wasting my life on Guild Wars 2 :P

If you don't mind me asking, what kind of background (educational or otherwise) does Google look for when hiring? And did they ask you any ridiculously difficult problem like "how many ping pong balls can fit in a school bus?" just to see your thought process, or was all of this done through programming problems?

I think they stopped asking open-ended questions like the ping pong thing.
0

#### SwiftStriker00

21 August 2012 - 10:19 PM

AVReidy, on 22 August 2012 - 12:28 AM, said:

Cool, good luck on your next interview! I'll be wasting my life on Guild Wars 2 :P

If you don't mind me asking, what kind of background (educational or otherwise) does Google look for when hiring? And did they ask you any ridiculously difficult problem like "how many ping pong balls can fit in a school bus?" just to see your thought process, or was all of this done through programming problems?

I don't know what their criteria is for looking for potential candidates. In fact I don't know what I did to stand out. what I can tell you is this: I have a B.S. in Computer Science, i'm active in a programming community, and I code in my free time. it helps to maintain a LinkedIn page and a personal website that has an up to date resume.

Unfortunately there were no "impossible" or thought process questions. it's a shame since i find those questions fun, maybe next interview. there was more than just the three programming questions, but it was more of a discussion that mostly consisted about trees and bigOh of them when doing different operations.
2

#### SwiftStriker00

21 August 2012 - 10:24 PM

mostyfriedman, on 21 August 2012 - 11:46 PM, said:

For the last question the first idea that came to mind was to sort the second array. Then for every element in array a, search for c-a in b using binary search, Big-oh = (nlgn)

Yeah nice solution. that's much simpler than mine.
0

#### mostyfriedman

21 August 2012 - 11:16 PM
The use of hashmaps was nice though, I can expand on my idea with that to make it O(n)
0

#### mostyfriedman

21 August 2012 - 11:19 PM
using HashSet though. But anyway good luck with your next interview
0

#### Nikitin

21 August 2012 - 11:21 PM
Google doesn't ask those mind-bending questions anymore. Expect algorithms and design questions only. The criteria to get a phone screen is nothing out of the ordinary - be a programmer who has demonstrated an ability and interest to learn. If you have that, you are a potential candidate.

You're still on the phone interviews stage, right? Good luck, real fun are the on-site interviews.
0

#### Jstall

22 August 2012 - 07:02 AM
Sounds interesting and challenging , good luck in the next step!
0

#### CarDriver

22 August 2012 - 11:42 AM
Doesn't Google ask for your SAT score? Rumor has it you need a 1400+
0

#### blackcompe

22 August 2012 - 07:06 PM
Those questions aren't so bad. I'm kind of surprised actually! I figured Google would be asking some really tough stuff.

Quote

Which lead to Programming Problem No. 1: Write a program to count the number of uni-value sub-trees in a given tree. Explain reasoning, and implementation decisions.

Does uni-value refer to the values (not keys) in a key-value node tree? Should be linear in the worst case.

Quote

Programming Question No.2: You are given some number, in String format, create a method public static String increment( String someInt), where you add 1 to the input string, and return the new number.

Assuming BigInt, is the equivalent of BigInteger in Java, which represents arbitrarily long integers, it's pretty much the same thing. However, if BigInteger didn't exist, you could write an array-based implementation.

Quote

The use of hashmaps was nice though, I can expand on my idea with that to make it O(n)

Right.

Let a be an array of size n, and b be an array of size m.

• Throw both arrays into separate maps: Theta(2(n+m))
• Iterate through either of the two, and for each element, x, subtract it from c, and see if that value is in the other map: Theta(n+m)+Theta(1)
0
Page 1 of 1

### Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

S M T W T F S
1234567
891011121314
1516171819 20 21
22232425262728
2930