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:
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:
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.
insert 3*3 into Q3, 5*3 into Q5 and 7*3 into Q7
3*5 is a duplicate, insert 5*5 into Q5 and 7*5 into Q7
Q7=7, 7*3, 7*5
3*7 and 5*7 are duplicates, insert 7*7 into Q7
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
Q5=5*3, 5*5, 5*3*3
Q7=7*3, 7*5, 7*7,7*3*3
- initialize array and queues Q3, Q5 and Q7
- insert 1 into array
- insert 1*3 in Q3, 1*5 in Q5 and 1*7 in Q7
- let x be minimum element in Q3, Q5 and Q7.
- 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
- repeat 4–6 until we’ve found k elements
For more such questions, refer to:
Goldman Sachs Interview Experience
I interviewed with GS in January 2021 for the post of Java/Python Developer. There were 5 rounds in total.
Amazon SDE1 Interview Experience
I interviewed for Amazon in November 2020. I applied through a referral which helped in expediting the process.
Zeta(Directi) Interview Experience
I applied on LinkedIn for the SDE2 role. After a couple of weeks, I received a call from the recruiter that my profile…