Lin Quan - Top 10 coding interview problems asked in Google with solutions: Algorithmic Approach

2014 Lin Quan. All Rights Reserved.

This book is written for helping people prepare forGoogle Coding Interview. It contains top 10 programming problemsfrequently asked @Google with detailed worked-out solutions bothin pseudo-code and C++(and C++11).It came out as a result of numerous requests received from codersacross the Globe, primarily from Google aspirants. Author has avast collection of algorithmic problems since 20 years includingexperience in preparing computer science students for participationin programming contests like TopCoder, ACM ICPC and others.For suggestions, feedback and comments, the author can becontacted at : lin.quan.20@gmail.com

Lin Quan
Retired Professor(Computer Science)
March 7, 2014

* * There is a bag full of n nuts and n bolts, each of distinct sizes, such that there is one-to-one correspondence between the nuts and the bolts, i.e., for every nut, there is a bolt and vice verse. Nuts cannot be compared to nuts and bolts cannot be compared to bolts directly, but nuts can be compared to bolts by trying to fit one into the other. Design and implement an optimal algorithm for fitting all nuts to bolts. By optimal we mean to minimize the number of comparisons involved in the algorithm.

The same problem can be posed to a computer scientist asfollows:

Given two sets B : { b , ,b n } and N : { n , ,n n } , where B is a set of n distinct real numbers (representing the sizes of the bolts) and N is a permutation of B , we wish to find efficiently the unique permutation N n so that b i = n ( i ) i , based on queries of the form compare b i and n j . The answer to each such query is either

1. b i > n j or
2. b i = n j or
3. b i < n j

Since there are n! possibilities for , the obvious information theoreticlower bound shows that any bounded degree decision tree thatsolves the problem has depth at least log ( n !).

Using Sterlings approximation :

log ( n !) ( n log n )

Similar to comparison-based sorting, it can be analyzed usingdecision tree. Please note that we can model any algorithm formatching nuts and bolts as a decision tree.

The tree will be a ternary tree , since every comparison has three possible outcomes:

1. less than ,
2. equal , or
3. greater than

The height of such a tree corresponds to the worst-case number ofcomparisons made by the algorithm it represents, which in turn is alower bound on the running time of that algorithm. We thereforewant a lower bound of ( n log n ) on the height, H , of any decisiontree that solves nuts n bolts problem mentioned in earliersection.

To begin with, note that the number of leaves L in any ternarytree must satisfy L 3 H . Next, consider the following class ofinputs.

Let the input array of nuts N be fixed and consist of n nuts inincreasing sorted order, and consider one potential input for everypermutation of the bolts. In order to match the nuts and bolts,our algorithm must in this case essentially sort the array ofbolts.

In our decision tree, if two different inputs of this typewere mapped to the same leaf node, our algorithm wouldattempt to apply to both of these the same permutation ofbolts with respect to nuts, and it follows that the algorithmcould not compute a matching correctly for both of theseinputs.

Therefore, we must map every one of these n! different inputs toa distinct leaf node, i.e.

L n !3 H n ! H log n H = ( n log n )

Please note that base of logarithm doesnt matter in complexity,it is a kind of constant, so we will ignore this too.

In particular, at least ( n log n ) comparisons are needed. This isa lower bound for the expected number of comparisons in anyrandomized algorithm for the problem as well.

A simple modification of Randomized Quicksort shows thatthere are simple randomized algorithms whose expected number ofcomparisons (and running time) are O ( n log n ):

• pick a random bolt
• compare it to all the nuts
• find its matching nut, thus splitting the nuts into three parts:
  1. nuts smaller for the bolt
  2. nuts exactly fit with the bolt
  3. nuts bigger for the bolt
• compare the matching nut found above to rest of the remaining n - 1 bolts, thus splitting the bolts into three parts:
  1. bolts looser for the nut
  2. bolt exactly fit to the nut
  3. bolts tighter for the nut
• thus splitting the problem into two problems, one consisting of the nuts and bolts smaller than the matched pair and one consisting of the larger ones.

This pair of partitioning operations can easily implemented in( n ) time, and it leaves the nuts and bolts nicely partitioned sothat the pivot nut and bolt are aligned with each-other and allother nuts and bolts are on the correct side of these pivots:

• smaller nuts and bolts precede the pivots, and
• larger nuts and bolts follow the pivots.

This algorithm then finishes by recursively applying itself to thesubarrays to the left and right of the pivot position to match theseremaining nuts and bolts. We can assume by induction on n that these recursive calls will properly match the remainingbolts.

To analyze the running time of this algorithm, we can use thesame analysis as that of randomized quicksort . We are performinga partition operation in ( n ) time that splits our probleminto two subproblems whose sizes are randomly distributedexactly as would be the subproblems resulting from a partitionin randomized quicksort. Therefore, applying the analysisfrom quicksort, the expected running time of our algorithm is( n log n ).

This problem provides a striking example of how randomizationcan help simplify the task of algorithm design.

Rawlins [] posed this problem as :

We wish to sort a bag of n nuts and n bolts by size in the dark. We can compare the sizes of a nut and a bolt by attempting to screw one into the other. This operation tells us that either the nut is bigger than the bolt; the bolt is bigger than the nut; or they are the same size (and so fit together). Because it is dark we are not allowed to compare nuts directly or bolts directly. How many fitting operations do we need to sort the nuts and bolts in the worst case?