Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
@vgeek
I doubt the correctness of your algorithm. Could you please clarify if your procedure takes care of producing numbers that are multiples of a subset of powers of 2,3,5 & 7. For ex: will you algorithm be able to generate 2^2 * 3^2 * 5^2 * 7^2?
yes, this algo generating below cases
2^2 * 3^2 * 5^2 * 7^2 -> 44100
2^1 * 3^2 * 5^2 * 7^2 -> 22050
This is an ugly number problem, and vgeek's solution is better. Miguel Oliveira 's solution is very easy to understand, but waste of space for the numbers which are currently not used, and increased the corresponding time on PUSH operation.
1) it is very hard to argue about the correctness of this, because e.g.
the number 11 will be missing ;)
The key here is to use a heap (aka priority queue). Start with number 1 and add it to the heap. Then, do a loop
a) Pop the minimum value from the heap
b) Print this minimum
c) Add minimum*2, *3, *5 and *7 to the heap
If we want N numbers, the complexity will be O(N log N).
Note that since i,j,k,l >=0, the first number should be 1, not 2.
how to deal with when duplicate values arrives.. like 2*5,5*2,4*3,3*4.....?? also the series should be 2,3,4,5.....(4 is missing)
To deal with duplicates, you can use a hash table.
About the missing 4, it should be a mistake. 4 must be in the sequence (note that 8 is there)
Why 4^N? It's O(N), this is a sample implementation for small values. Note that we ignore repeated values and we could also ignore values to the heap when we already have N values in the heap.
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int primes[] = {2, 3, 5, 7};
char seen[1000000]; // for large values, use a hash table instead
int main() {
int N, i, j, next, minimum;
cin >> N;
priority_queue<int, vector<int>, greater<int> > heap;
heap.push(1);
for (i = 0; i < N; i++) {
minimum = heap.top();
heap.pop();
cout << minimum << endl;
for (j = 0; j < 4; j++) {
next = minimum * primes[j]; // careful with overflow
if (!seen[next]) { // for large values
seen[next] = 1;
heap.push(next);
}
}
}
return 0;
}
Although this solution is easier to understand, vgeek's solution is O(N), thus better than this one.
@Miguel: Using this solution we will never get 22, 44 etc.
But these numbers can be obtained from equation putting i = 11 and rest 0
This does not seem to be correct, according to this algorithm, the output will be:
1, 2, 3, 5, 7, 4, 6 10, 14, 9, 15 21...
instead of:
1, 2, 3, 4, 5, 6, 7, 8....
it's a heap (priority queue), not a queue. The heap will get the minimum value, not the FIFO order
As we need to remove duplicates, a BST could serve better than heap: no need for the additional hash table. And still O(N log N). On the other hand, BST uses pointers and can't be stored in an array like a heap.
Also, we can't stop when we have N items in the tree - e.g. say N=4, the tree would contain 2, 3, 5, 7 after the first round. We must keep adding until we output all N items.
explicitly avoid duplicate (according to the CTCI book)
*** 2, 3, 5, 7 factor sequence ****
from collections import deque
def min4(a, b, c, d):
l = [a, b, c, d]
return min(enumerate(l), key = lambda x: x[1])
# return first N numbers whose only prime factors are 2,3,5,7
def gen_2357_seq(N):
q2 = deque([2])
q3 = deque([3])
q5 = deque([5])
q7 = deque([7])
res = [1]
for i in range(1, N):
idx, m = min4(q2[0], q3[0], q5[0], q7[0])
res.append(m)
q7.append(7 * m)
if idx == 3:
q7.popleft()
continue
q5.append(5 * m)
if idx == 2:
q5.popleft()
continue
q3.append(3 * m)
if idx == 1:
q3.popleft()
continue
q2.append(2 * m)
q2.popleft()
return res
limit=10
print "looping for", limit ,"times"
numlist = ["0000"]
#-----------------------------------------
def generator(nlist,count):
for i in range(1,count):
nlist.append(str(i)+str(i-1)+str(i-1)+str(i-1))
nlist.append(str(i-1)+str(i)+str(i-1)+str(i-1))
nlist.append(str(i-1)+str(i-1)+str(i)+str(i-1))
nlist.append(str(i)+str(i)+str(i-1)+str(i-1))
nlist.append(str(i-1)+str(i-1)+str(i-1)+str(i))
nlist.append(str(i-1)+str(i)+str(i)+str(i-1))
nlist.append(str(i)+str(i)+str(i)+str(i-1))
nlist.append(str(i-1)+str(i-1)+str(i)+str(i))
nlist.append(str(i-1)+str(i)+str(i)+str(i))
nlist.append(str(i)+str(i)+str(i)+str(i))
#print numlist
#print count
#-----------------------------------------
generator(numlist,limit)
#print numlist
for item in numlist:
part = list(item)
#print part
calcOP = (2**int(part[0]))*(3**int(part[1]))*(5**int(part[2]))*(7**int(part[3]))
print calcOP
This should do it in python.
so in this question
2^i * 3^j * 5^k * 7^l
should mean 2 to the power of i multiplied by 3 to the power of j and so on..
thus
for i=1,j=1,k=1,l=1
shouldnt the first number be
2*3*5*7 = 210 ?
so even if exponents are 0, the first number would be 1 followed by 210 !! The sequence 2,3,5,6,7,8,9. seems incorrect to me !!
those 4 letters i,j,k and l mean that the exponents don't need to have the same value
2 = 2^1 * 3^0 * 5^0 * 7^0
3 = 2^0 * 3^1 * 5^0 * 7^0
4 = 2^2 * 3^0 * 5^0 * 7^0
etc
Rohit made some mistakes, 1 and 4 are missing from the sequence
this should print out all the nos. whose only prime factors are 2,3,5 or 7. We will print out 1 by default. We should try to reduce a number to 1 by dividing it with different powers of 2,3,5 and 7. if the number reduces to 1 then print it out.
std::cout << 1 << " ";
size_t n = 2;
void reduce( size_t& num, size_t divisor )
{
while( num % divisor == 0 )
num /= divisor;
}
int main()
{
std::cout << 1 << std::endl;
size_t num = 2;
while( true )
{
num = reduce( num, 2 );
num = reduce( num, 3 );
num = reduce( num, 5 );
num = reduce( num, 7 );
if( num == 1 )
std::cout << num << std::endl;
num++;
}
}
complexity: O(N)
Here's a dynamic programming approach that I think does it in O(n) with a memory space of ~N.
bool array[N+1];
for(int i = 0; i < N+1; i++)
{
array[i] = 0;
}
array[1] = true;
int j = 0;
while(j < N+1)
{
j += 2;
array[j] = true;
}
j = 0;
while(j < N+1)
{
j += 3;
array[j] = true;
}
j = 0;
while(j < N+1)
{
j += 5;
array[j] = true;
}
j = 0;
while(j < N+1)
{
j += 7;
array[j] = true;
}
for(int i = 0; i < N+1; i++)
{
if(array[i] == true)
{
print i;
}
}
you're mixing 2 different Ns: the n-th number we want and the magnitude (say M) of this number. While the above approaches state the time complexity in terms of "n". Your algorithm is O(M)
Miguel, you are right.
I'm a little hazy on big O notation, but with the constraints of the problem, I think it's still O(n).
To fix this solution, you could let M = 2*N (since 2 is one of the factors, it's not going to use more than 2*N space), then use M for the array length. At the end, you'd have to count how many numbers you had printed and stop when you'd printed the appropriate amount.
Because M is a fixed multiple of N, I believe you can still call it O(N).
My idea is same as Miguel Oliveira's, and the time complexity is O(nlogn), here is my code:
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
struct quadruple
{
int i, j, k, l;
int v;
quadruple( int i, int j, int k, int l ) : i(i), j(j), k(k), l(l),
v( static_cast<int>( pow( 2.0f, i ) * pow( 3.0f, j ) * pow( 5.0f, k ) * pow( 7.0f, l ) ) ) {}
bool operator!=( const quadruple& q )
{
return v != q.v;
}
};
struct quadruple_greater
{
bool operator()( const quadruple& p, const quadruple& q ) const
{
return p.v > q.v;
}
};
void number( int n ) // time complexity O(nlogn)
{
std::vector<quadruple> result;
result.reserve(n);
std::priority_queue< quadruple, std::vector<quadruple>, quadruple_greater > min_heap;
quadruple q( 0, 0, 0, 0 );
min_heap.push( q );
result.push_back(q);
while( !min_heap.empty() )
{
q = min_heap.top();
min_heap.pop();
if( result.back() != q ) result.push_back(q);
if( result.size() == n ) break;
min_heap.push( quadruple( q.i + 1, q.j, q.k, q.l ) );
min_heap.push( quadruple( q.i, q.j + 1, q.k, q.l ) );
min_heap.push( quadruple( q.i, q.j, q.k + 1, q.l ) );
min_heap.push( quadruple( q.i, q.j, q.k, q.l + 1 ) );
}
for( std::vector<quadruple>::iterator it = result.begin(); it != result.end(); ++it )
std::cout << it->v << " (" << it->i <<"," << it->j << "," << it->k << "," << it->l << ")" << std::endl;
}
int main( int argc, char* argv[] )
{
number(9);
return 0;
}
Not going in to time complexity, this is how i wrote the program.
public class PrimeFactors {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
for(int c=2;c<100;c++)
calculatePrimeFactors(c);
}
public static void calculatePrimeFactors(int num)
{
int i=num;
while(i>1 && i%7==0)
{
i=i/7;
}
while(i>1 && i%5==0)
{
i=i/5;
}
while(i>1 && i%3==0)
{
i=i/3;
}
while(i>1 && i%2==0)
{
i=i/2;
}
if(i==1)
{
System.out.println(num+"can be broken in to factrs of 2,3,5,7");
}
else
{
System.out.println(num+" cannot be broken in to factors of 2,3,5,7");
}
}
}
Any number that conforms to this formula is a number that is divisible by 2 or 3 or 5 or 7. So just loop over the integers and check if any is divisible by 2,3,5 or 7.
public void printNums(int N){
for(int i = 0; i < N; i++){
if(isdivisible(i,2) || isdivisible(i,3) || isdivisible(i,5) || isdivisible(i,7))
System.out.printlnt(i);
}
}
public class Solution{
public ArrayList<Integer> sortedOrder(int len){
PriorityQueue<Word> qe = new PriorityQueue<Word>(2*len , Word.com );
ArrayList<Integer> res = new ArrayList<Integer> ();
qe.add(new Word(2,2));
qe.add(new Word(3,3));
qe.add(new Word(5,5));
qe.add(new Word(7,7));
int k = 0;
while( k < len ){
k++;
Word t = qe.poll();
res.add(t.val);
switch( t.calss ){
case 2:
qe.add(new Word(2,2 * t.val));
qe.add(new Word(3,3* t.val));
qe.add(new Word(5,5* t.val));
qe.add(new Word(7,7* t.val));
break;
case 3:
qe.add(new Word(3,3* t.val));
qe.add(new Word(5,5* t.val));
qe.add(new Word(7,7* t.val));
break;
case 5:
qe.add(new Word(5,5* t.val));
qe.add(new Word(7,7* t.val));
break;
case 7:
qe.add(new Word(7,7* t.val));
break;
}
}
return res;
}
}
public class Word{
int class;
int val;
public Word(int cla, int v)
{
class = cla;
val = v;
}
public static Comparator<Word> com = new Comparator<Word>(){
@override
public int compare(Word a , Word b){
if(a.val > b.val ) return 1;
if(a.val < b.val ) return -1;
return 0;
}
}
}
why dont we simply take a loop over numbers and for any no see whether it is divisible by the combination of the given number. if it is then it can be generated else not..
I took this approach while caching the previous solutions. If the number you're testing is divisible by any of the bases, make that base one and the others 0. Then divide the number by that base, and add the exponents from the quotient (which you have cached). This works in linear time so it should be very fast.
think we should use four queues, initialy each queue has only one num 2,3,5,7,we name them q2,q3,q5and q7
then we compare the top of the four queues to get the min, and if min is from q2, then we add *2 to q2, and the *min to q3 q5andq7, if min is from q3, we only add *3 to q3 and the *min to q5 and q7, etc to avoid duplicates
for instance
2 2*2
3 3*2
5 5*2
7 7*2
then 3 is min so
2 2*2
3 3*2 3*3
5 5*2 5*3
7 7*2 7*3
then 4 from q2 is min so
2 2*2 4*2
3 3*2 3*3 3*4
5 5*2 5*3 5*4
7 7*2 7*3 7*4
etc
I worked on this problem independently and found that my solution is exactly the same as the one from vgeek, however my implementation is shorter and easier to read;
O(N) time O(N) space
void printSequence(int n)
{
vector<int> v(n);
v[0] = 1;
int p2 = 0, p3 = 0, p5 = 0, p7 = 0;
cout << 1 << endl;
for (int i = 1; i < n; i++) {
int n2 = v[p2] * 2;
int n3 = v[p3] * 3;
int n5 = v[p5] * 5;
int n7 = v[p7] * 7;
int next = min(min(n2,n3),min(n5,n7));
v[i] = next;
if (next == n2) p2++;
if (next == n3) p3++;
if (next == n5) p5++;
if (next == n7) p7++;
cout << next << endl;
}
}
Question is not clear. Can you please explain the intent with an example or "Miguel Oliveira" can you please help with a pseudo code and a simulation around it please.
I assume we should print number 1 as well. For large values, we should use a hash table and be careful with overflow in integers multiplication.
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int primes[] = {2, 3, 5, 7};
char seen[1000000]; // for large values, use a hash table instead
int main() {
int N, i, j, next, minimum;
cin >> N;
priority_queue<int, vector<int>, greater<int> > heap;
heap.push(1);
for (i = 0; i < N; i++) {
minimum = heap.top();
heap.pop();
cout << minimum << endl;
for (j = 0; j < 4; j++) {
next = minimum * primes[j]; // careful with overflow
if (!seen[next]) { // for large values
seen[next] = 1;
heap.push(next);
}
}
}
return 0;
}
Meh, going to have to heap it after all.
Coffee first, then code :(
vgeeks algorithm is the best I can come up with. Here it is in Python:
def printMultiples(n):
op = array.array('i')
i,j,k,l = 0,0,0,0
mi,mj,mk,ml = 2,3,5,7
op.append(1)
print op[0]
for x in range(1,n):
op.append(min(mi,mj,mk,ml))
print op[x]
if mi == op[x]:
i = i+1
mi = op[i]*2
if mj == op[x]:
j = j+1
mj = op[j]*3
if mk == op[x]:
k = k+1
mk = op[k]*5
if ml == op[x]:
l = l+1
ml = op[l]*7
These are basically referred to as ugly numbers . Here is the code for it:
a. Take variables for multiples of 2,3,5,7.
b. Everytime find a minimum of the multiple.
c. Store 1 in the first index as it is multiple of all.
d. Find the minimum of all the multiples of 2,3,5,7. Whenever that minimum is equal to any of the multiples. Store that multiple in the indexes assigned for 2,3,5,7 and also multiply that element with the number to get the next higher multiple in next iteration.
- vgeek July 29, 2013#include <stdio.h> #include <conio.h> #include <malloc.h> int min(int a,int b) { return (a<b?a:b); } int min(int a,int b,int c,int d) { return min(a,min(b,min(c,d))); } void printAllMultiples(int n) { unsigned *ugly=(unsigned *)malloc(sizeof(ugly)); unsigned next_multiple_2=2; unsigned next_multiple_3=3; unsigned next_multiple_5=5; unsigned next_multiple_7=7; unsigned i2=0,i3=0,i5=0,i7=0; ugly[0]=1; unsigned next_ugly_no; int i; printf(" %d ",ugly[0]); for(i=1;i<n;i++) { next_ugly_no=min(next_multiple_2,next_multiple_3,next_multiple_5, next_multiple_7); *(ugly+i)=next_ugly_no; printf(" %d ",next_ugly_no); if(next_ugly_no==next_multiple_2) { i2=i2+1; next_multiple_2=ugly[i2]*2; } if(next_ugly_no==next_multiple_3) { i3=i3+1; next_multiple_3=ugly[i3]*3; } if(next_ugly_no==next_multiple_5) { i5=i5+1; next_multiple_5=ugly[i5]*5; } if(next_ugly_no==next_multiple_7) { i7=i7+1; next_multiple_7=ugly[i7]*7; } } } int main() { printAllMultiples(20); }