Google's Interview Questions For Software Engineers:

[davidthefat]

http://blog.seattleinterviewcoach.co...tware_engineer

Those that stood out to me were:

1.)What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?


2.)What is multithreaded programming? What is a deadlock?


3.)In Java, what is the difference between static, final, and const. (if you don't know Java they will ask something similar for C or C++).


Now there are some very hard questions for highschoolers but the above ones don't seem as complex.

Now I can only answer #2. A dead lock is when the 2 processes are dependent of each other so they are both waiting for each other to pass something but they won't pass it unless they get something... Pretty much that whole you step to the side and the guy in front of you do the same and you do that forever


Reading that list, even the lower programmers for Google are pretty hardcore. That just shows how long I have to go

[Chris27]

1) Mutexes and semaphores are used to control access to resources (such as variables) shared by many threads running concurrently. The order in which the threads run is unknown to the programmer and and funny things can happen if shared resources are not properly protected.

A classic is example of this is a simple program in which you initialize a simple counter variable (say int count = 0) and have two threads each run the following loop: ( for(int i = 0; i < 1000; i++) count++; ). If two threads run, we would expect that 'count' will have the value of 2000. However, this may very well not happen because of a "race condition." The statement count++ is not "atomic" i.e. it takes multiple steps to execute this command. More specifically, the value from count is read, incremented, and then this new value is stored back into count. However, say thread 1 reads the value 100 from count, but at this moment, the scheduler decides to preempt thread 1 and allow thread 2 to run for a while. In this time, thread 2 increments count to say, 200. Thread 2 is now stopped and thread 1 is allowed to run. It increments the value 100 it previously read to 101 and assigns this to the value of count (therefore count goes from the value 200 to 101). Notice we just lost 100 increments. This can be fixed by "locking" access to the count variable. Locking is often done with mutexes or semaphores.

A semaphore is effectively a counter that can be incremented/decremented atomically. Upon construction, it is given a max value it is allowed to take. Semaphores are commonly used in "producer-consumer models." An example of this is people queuing up for an amusement park ride. Say the ride can only accommodate 10 people, then it would be bad if more then 10 people tried to get on the ride at the same time. What we can do is have the riders increment a semaphore as they get on the ride, and decrement it as they get off the ride. If the semaphore is already at 10 when a rider wants to board, make them wait in line.

A mutex is effectively a key that allows a thread to use a resource. Consider a key to a door to a bathroom with a single stall. If you have the key, lock the door behind you, then another thread can't barge in when the bathroom is in use.

There is a also a notion of a "binary semaphore" which I think the Google question is alluding to. A binary semaphore is a semaphore that can take the values of either 0 or 1. I've heard mutexes described as being equivalent to a binary semaphore, which is wrong. I think this is really the heart of the Google question. A big differences is that mutexes have the concept of "ownership." Only the thread that owns the mutex (i.e. was the thread that originally claimed the mutex) can give it up. If another thread tries to free the mutex, this will cause an error. With semaphores, basically any thread is allowed to manipulate them.

I'd use a mutex to protect the increment operation.

2) I think I've already explained briefly what multithreaded programming is above. Deadlock (in multi-threaded programming) is the case where you have multiple threads, work still needs to be done, but the threads can't make any significant progress for some reason. Often the cause is improper locking. Say you have two threads (t1,t2), one resource (R), and two mutexes (m1, m2). Say in order that the tasks assigned to each thread require the resource R at some points and that for a thread to access R, it needs both the mutexes m1 and m2. Consider the case when t1 and t2 simultaneously want to access R, t1 claims m1 and t2 claims t2. They still need the other mutex so the wait for it to become available, except that it never will. We now have a case of deadlock.

Multi-threading is often quite hard to get right. It also can be quite hard to debug as the order of execution of threads is in essence quite random from the viewpoint of the programmer and maybe you have a bug that only shows up 1 in 100 times the program is executed.

3) As far as I know, Java doesn't have "const" (a C++ thing). Java's equivalent is final. A variable assigned the property of final must be initialized to some value and can't be changed by the program during runtime.

That being said, the style of questions I was asked for when I interviewed with Google were quite different then those that were in the list (I applied for both program manager and software engineer).

[RyanCahoon]

Originally Posted by davidthefat

Reading that list, even the lower programmers for Google are pretty hardcore. That just shows how long I have to go

Don't worry about it too much. I imagine even "lower programmers" at Google have at least a Bachelor's degree (at least new hires), and the synchronization questions were addressed in my intro to computer systems class, and static and final were talked about in my intro to programming class (the trick being that 'const' is a reserved word in java, but is actually unused in the language).

My point being in this being that don't worry if you don't feel qualified for Google yet; you still have at least 4 years of (fairly intense) schooling left before you'll have to worry about interview questions for a job (summer internships might present similar challenges, though). Seeing that these are all just factual/recall questions, I don't think that these are the most difficult questions on the list. If the interviewer is good at her job, these probably won't even be the most consequential questions. A question like

Let's say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi). How do you do the same?

seems a lot more interesting to me, as it touches on some open research topics.

--Ryan

[DonRotolo]

Originally Posted by davidthefat

Reading that list, even the lower programmers for Google are pretty hardcore.

For those of you not yet in the workforce, there is one truth you'll learn: Companies try to hire the best employees they can find.

They might not always succeed. You can probably fool a small company more easily than a large company (like Google), but in any company incompetence is obvious after a short while, and they'll have no qualms about "freeing you to seek other opportunities".

The point is, find something to get really good at, and get good at it. Then find someone who will pay you to do that. If you're not good at something, people will know.

As a course of study, make no mistake: Engineering is one of the more difficult ones. But it is worth it in a lifetime.

[ericzundel]

Google's interview process can be grueling, especially if you don't know what to expect. There are questions like this asked, but I wouldn't try to memorize answers to them. Of course, some of the questions require a direct answer and background knowledge. Usually questions like the synchronization question will be lead-ins to some sort of design or programming problem.

What I look for in a candidate is someone that can not just answer questions correctly, but talk through the process of solving a problem - discussing places where there are design decisions to be made. Someone that considers many solutions and evaluates them out loud during the interview makes a better impression than someone that knows the "best" solution right away.

If you are interested in applying for an internship with Google or another company that has a similar interview process, it would be helpful to practice a bit to get comfortable with the format. Take some of these questions and try answering them cold with someone else in the field who has had time to work through the problem ahead of time. Give yourself a time limit of 30-45 minutes for each session.

[davidthefat]

I am currently looking for internship opportunities for the summer, Google does not do highschool internships, so that's a bummer. I am focusing on the SpaceSHIP at JPL. Its less than 5 minutes away from my house, I am very interested in actually working there when I grow up, so why not?