Google Interview Questions - Part 9

Q1: How you would tweak bits in C to find out if a machine’s stack grows up or down in memory?

Q2: There are 8 stones which are similar except one which is heavier than the others. To find it, you are given a pan balance. What is the minimal number of weighing needed to find out the heaviest stone ?

Q3: N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?


Here are the answers:


A1: Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function's local is higher, the stack grows away from address location 0; if the function's local is lower, the stack grows towards address location 0.

A2: Divide the stones into sets like (3,3,2). Use pan to weigh (3,3). If the pan is remains balanced, the heavier is in the remaining (2). use pan again to find which is heavy from (2). (Total pan use 2) If the pan does not remain balanced when weighing (3,3), pick the set of stones that outweigh other. Divide it into (1,1,1). use pan to weigh first two. It it remains balanced, the remaining stone is the heavier, otherwise the one outweighing other is heavier(total pan use 2)

A3:

• Avoiding Deadlocks with Lock Leveling, each thread would have different level, thread with high level would be able to lock thread with lower level but not contrary.
• Avoid acquiring more then one lock at a time.
• Acquire the lock always in the same order.
• Shrink synchronized blocks.