One of the cool things about big software companies, such as Microsoft or Google, is the interview process. Interviews are done by actual engineering people (along with HR) and candidates are asked direct engineering, problem solving and coding questions. For people who are really into hands-on coding and who like problem solving, this is great. Plus, it gives you an exact idea about the candidates ability. A lot of the things you need to know about how you code can be easily seen in front of a blackboard. (If you’re really interested in how this works, I will reccomend getting a copy of “Programming interviews exposed”)
So, I was thinking about posting a couple of the interview questions I use here at Google… BUT that would put it way too easy for some of the people I’ll interview next month during the European CodeJam finals so… let’s see if this one suits you anyway.
Important: normally interview questions have several “levels of complexity” just to give a better idea of how the candidate’s “expertise”. This means that normally there are several ways of solving them, and that in many cases it’s not expected from you to get all the question up to the end…
Go on and give this one a try! And post your solutions and questions in the comments! I promise to give feedback in all of them! }:D
Balloons and bullets
Step 1: I have N balloons and a bullet in 3-D space. Write some code to determine if the bullet is inside of any balloon, if yes, which balloons. Balloons may overlap. For simplicity, assume all balloons are spheres of radius 1 and the bullet is a point.
Step 2: Now I have K bullets, can you enhance the algorithm so the complexity is better than O(NK)?
Step 3: Now the balloons have different radius. How does the solution change?
Step 4: Now I have only one bullet but it’s a tracing bullet that can change direction, and it’s moving through K positions. I want to know if the bullet hit any balloons. How does the solution change?
Tips: Step 1 is what is expected from a college hire. Step 2 is for a good college hire. Step 3 is expected from a good coder with knowledge of some advanced data structures. Step 4 is for people who actually have good mathematical/geometry skills.
a 2d version of our problem: Pang! };D
From my (limited) experience, I can’t say I’ve ever found a bullet inside a balloon unless the ballon was lying on the ground deflated (which would actually simplify the problem by a whole dimension) ;P
I’ll get something working when I get home - these are fun! (is it possible to do it faster than O(log n)?)
hallo Lera, you’re right… assume the balloons have not gone boom just yet };P
And for the other issue: I can’t think of a solution that is better than O(log n) (in the first case)… (if somebody else can, please let us know!)