Solving Interview Question

Question

Write an algorithm to find the kth number such that only prime factors are 3,5 and 7.

This question seems very simple but there is one interesting solution that I am going to explain below:

Solution

Let’s maintain 3 queues such that:
Q3: Has previously unseen multiples of 3
Q5: Has previously unseen multiples of 5
Q7: Has previously unseen multiples of 7

To find the minimum we only need to look at the fronts of each queue:
y=min(Q3.head(),Q5.head(),Q7.head())

Once we compute y, we need to insert 3y into Q3, 5y into Q5, 7y into Q7. And we only need to insert those elements that are not already into the other lists.

Let’s see how one number can be available in another list.
y is pulled from Q7 and we want to insert it into Q3. But y=7x(because Q7 has multiples of 7).
And we pulled y(=7x), meaning that it was the smallest value at the moment. It also means that we might have already seen 3x earlier.
At the moment we saw 3x we already inserted 7*3x into the queue.
7 * 3x=7x * 3

Let’s understand more clearly.
If we pull an element from Q7, it will be like 7 * suffix, and we know we have already handled 3*suffix and 5*suffix. In handling 3 * suffix, we inserted 7 * 3 * suffix into Q7. And in handling 5 * suffix, we know we inserted 7 * 5 * suffix into Q7. The only value remaining is 7 * 7 * suffix, so we only insert 7 * 7 * suffix into Q7.

Example

initialize:
Q3=3
Q5=5
Q7=7

remove min=3.
insert 3*3 into Q3, 5*3 into Q5 and 7*3 into Q7
Q3=3*3
Q5=5, 5*3
Q7=7, 7*3

reomove min=5.
3*5 is a duplicate, insert 5*5 into Q5 and 7*5 into Q7
Q3=3*3
Q5=5*3, 5*5
Q7=7, 7*3, 7*5

remove min=7.
3*7 and 5*7 are duplicates, insert 7*7 into Q7
Q3=3*3
Q5=5*3, 5*5
Q7=7*3, 7*5, 7*7

remove min = 3*3 = 9.
insert 3*3*3 in Q3, 3*3*5 into Q5, 3*3*7 into Q7
Q3=3*3*3
Q5=5*3, 5*5, 5*3*3
Q7=7*3, 7*5, 7*7,7*3*3

Pseudocode:

1. initialize array and queues Q3, Q5 and Q7
2. insert 1 into array
3. insert 1*3 in Q3, 1*5 in Q5 and 1*7 in Q7
4. let x be minimum element in Q3, Q5 and Q7.
5. if x was found in
   Q3 -> append 3*x, 5*x and 7*x in Q3, Q5 and Q7, remove x from Q3
   Q5 -> append 5*x and 7*x in Q5 and Q7, remove x from Q5
   Q7 -> append 7*x in Q7, remove x from Q7
6. repeat 4–6 until we’ve found k elements

For more such questions, refer to:

Cracking the Coding Interview (Indian Edition)

Google L3 Interview Experience

Goldman Sachs Interview Experience

Amazon SDE1 Interview Experience

Zeta(Directi) Interview Experience

Flipkart SDE1 Interview Experience