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
Hoy me he levantado con ganas de poner un post de estos inútiles. Por ejemplo: cosas de Londres que no vienen en los libros, pero que uno se da cuenta estando aquí. Sin ir más lejos, aquí dejo tres:
- En las paradas de metro no hay papeleras (sorprendente, verdad?) pero si las hay en las salidas
- Puedes determinar si alguien es un londinense “de pura cepa” con solo escuchar como pronuncia “leicester square” y “cheers!”
- Cuando vas a comprar batido y ves los típicos rosa, marrón y amarillo, leete las etiquetas! el rosa es de fresa y el marrón de chocolate, pero el amarillo suele ser de plátano, y no de vainilla! };P
Alguien se anima a dejarme alguna otra perla de conocimiento semi-inútil extraída de sus experiencias y aventuras en London?
actualización (22 Mayo): mi amiga Louise, en su infinita sapiencia, me comenta que lo de las papeleras es para evitar que la gente ponga bombas en ellas (pura lógica, vamos };P)
Yup, not joking! This is not another catchy header to get your attention, it is really one of the new thingies that have been presented at JavaOne in San Francisco… sounds weird, doesn’t it?
Well, apart of the oddity, there are a lot of interesting things coming in the next version of Java that are definitely worth a look! Check the roadmap for the Java Technologies in the keynote slides and find more in the rest of the sessions or watching the webcasts.
It’s in the news! (but not in Slashdot or Barrapunto, how strange!) Google is going to launch the CodeJam competition in Europe too!
Read more about European CodeJam 2006 here!
I think everybody should give this a try and here are my reasons why:
- First, it is a cool event, and you get to meet and compete with some interesting people all around Europe
- Second, it might give you extra reasons for sharpening your coding skills, review those data structures basics or algorithms or get that extra notch of excellence in your language of choice (Java, C++ or C#)
- Third, prizes are good, and finalists will get the opportunity to travel to Google Dublin for the finals
- And last but not least: I’m going to be in Dublin interviewing the finalists, so apart from a good prize, you might end up with a job offer from Google! };P
Registration is already opened, so start warming up in the TopCoder arena and… good luck!
Today, reading some past mailing lists items, I’ve come to this link of a Rob Pike’s talk about software and how it hasn’t changed much in the last years:
http://herpolhode.com/rob/utah2000.pdf
I think it’s worth to give a good read (also has some references to Linux and Microsoft, so it’s good material for worthless discussions };D) and also to consider it was written in 2000, and things haven’t really changed that much… at least not yet };P
P.S. did you know that Rob Pike works in Google? I didn’t! (but was happy to find so!)
