Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 4 vote

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION

public void output(int N) {
        Set<Integer> set = new HashSet<>();
        set.add(1);
        for(int num = 2; num <= N; num++) {
            if((num % 2 == 0 && set.contains(num / 2)) || (num % 5 == 0 && set.contains(num / 5))) {
                set.add(num);
                System.out.println(num);
            }
        }
    }

    //What if factors (such as 5 and 2) are not known numbers?
    //print all possible numbers by factor1^i * factor2^j * factor3^k * ...
    public void outputK(int[] a, int N) { //an array of factors are given
        Set<Integer> set = new HashSet<>();
        set.add(1);
        for(int num = 2; num <= N; num++) {
            for(int i = 0; i < a.length; i++) {
                if ((num % a[i] == 0 && set.contains(num / a[i]))) {
                    set.add(num);
                    System.out.println(num);
                    break;
                }
            }
        }
    }

- aonecoding March 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
def findPowers(N):
minHeap = [(1, 0, 0)]
seen = set()
res = []

while minHeap:
product, i, j = heapq.heappop(minHeap)
seen.add((i, j))
res.append(product)
nextIndices = [(i + 1, j), (i, j + 1)]

for nextI, nextJ in nextIndices:
if (nextI, nextJ) not in seen:
nextProduct = product * 2 if nextI > i else product * 5
if nextProduct <= N:
heapq.heappush(minHeap, (nextProduct, i + 1, j))
return res
}}

- pipedpiper March 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a minheap to keep track of the lowest product so far:

def findPowers(N):
    minHeap = [(1, 0, 0)]
    seen = set()
    res = []

    while minHeap:
        product, i, j = heapq.heappop(minHeap)
        seen.add((i, j))
        res.append(product)
        nextIndices = [(i + 1, j), (i, j + 1)]

        for nextI, nextJ in nextIndices:
            if (nextI, nextJ) not in seen:
                nextProduct = product * 2 if nextI > i else product * 5
                if nextProduct <= N:
                    heapq.heappush(minHeap, (nextProduct, i + 1, j))
    return res

- pipedpiper March 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 
aonecode's complexity is O(n) always.
That is kind of ok, because we can make the complexity much smaller.
The factors are 2,5, and thus suppose:
l2 = floor ( log(N,2) )
l5 = floor ( log(N,5) )
Then, all possible 2^i * 5^j are nothing but tuples from 
[0:l2] * [0:l5]
which would be significatly less. Try putting 1 million as N.
(zoomba)log(1000000,2)
19.931568569324174 // Double
(zoomba)log(1000000,5)
8.584059348440359 // Real
(zoomba)
Thus, the operations over loop will be 19 * 8.
It can be well argued that the computation to generate the number 2^i * 5^j 
will be great. Or will it be? We can always compose the number as simply 
of the form ( 10^a * 2^i ) or ( 10^a * 5^j ) , which clearly can be  
string manipulation of padding up powers of 2 or 5 padded with 0's.
This is something that I am not planning to do now. But of course we can 
pre compute it, based on these l2,l5 numbers.

Finally, can we avoid the set? Probably. But do we want to?
A simpler solution is using a sorted set, where we simply add the 
results of teh tuple selected from the ranges [0:l2] * [0:l5]
which, then are already sorted.

It is obvius that we can eliminate sets, by simply 
sorting the result in a list, which, given they are integers and prone to be binary,
can be radix sorted in base 10 in O( l2 * l3 * 10 ) time yielding 
a final complexity : O( log(N,2) * log(N,5) ), 
significantly less than that of O(N).
Space complexity is same in both the cases
Of course we can optimize a bit more, but we rememebr Knuth, 
and stop optimisation before we become evil. 
*/

def sorted_list_till( N ){
  l2 = int( log(N,2) )
  l5 = int( log(N,5) )
  s = sset() // sorted set 
  join ( [0:l2] , [0:l5] ) where {  
    x = ( 2 ** $.0 )  * ( 5 ** $.1 )
    continue ( x > N )
    s += x 
    false // do not add to list  
  }
  println( s )
}
// to prove some point...
sorted_list_till( 100000000 )

- NoOne March 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void PrintNumbers(int N)
        {
            var list = new List<int>();
            list.Add(1);
            Console.WriteLine(1);

            var i = 0;
            var j = 0;

            while (true)
            {
                var tmp = 0;
                var a = list[i] * 2;
                var b = list[j] * 5;

                if (a < b)
                {
                    tmp = a;
                    i++;
                }
                else if (a > b)
                {
                    tmp = b;
                    j++;
                }
                else if (a == b)
                {
                    i++;
                    continue;
                }

                if (tmp > N) break;
                Console.WriteLine(tmp);
                list.Add(tmp);
            }
        }

- anon March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printnum(int n) {
    int i=0,j=0;
    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            if(pow(2,i)*pow(5,j)<n) {
                int val = pow(2,i)*pow(5,j);
                printf(" %d,",val);
            }
            else {
                break;
            }
        }
        if(pow(2,(i+1))>=n) {
            return;
        }
    }
}

- Anonymous March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printnum(int n) {
    int i=0,j=0;
    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            if(pow(2,i)*pow(5,j)<n) {
                int val = pow(2,i)*pow(5,j);
                printf(" %d,",val);
            }
            else {
                break;
            }
        }
        if(pow(2,(i+1))>=n) {
            return;
        }
    }

}

- Anonymous March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printNumbers(int n) {
        if (n <= 0) return;
        PriorityQueue<Pair> pq= new PriorityQueue<>();
        pq.add(new Pair(1, 2));
        while (pq.isEmpty() == false) {
            Pair popped = pq.remove();
            int value = popped.value;
            int multiplier = popped.multiplier;
            System.out.print(value + " ");
            if (multiplier == 2) {
                int newValue = value * 2;
                if (newValue <= n && newValue >= 0) {
                    pq.add(new Pair(newValue, 2));
                }
            }
            int newValue = value * 5;
            if (newValue <= n && newValue >= 0) {
                pq.add(new Pair(newValue, 5));
            }
        }
        System.out.println();
    }
    public static class Pair implements Comparable<Pair>{
        int value;
        int multiplier;
        Pair(int v, int m) {
            value = v;
            multiplier = m;
        }
        public int compareTo(Pair p) {
            if (value > p.value) return 1;
            if (value < p.value) return -1;
            return 0;
        }
    }

- Aim_Google March 29, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TwoPowerFivePower {

    public static void main (String[] args)
    {

        List<Entry> res = new TwoPowerFivePower().calculate(50);
        for (Entry e: res)
            System.out.println(e.getValue());
    }

    List<Entry> calculate(int N)
    {
        List<Entry> res = new ArrayList<>();
        Queue<Entry> q = new PriorityQueue<>();
        q.offer(new Entry(0,0));

        while(true)
        {
            Entry current = q.poll();
            if (current.getValue() > N)
                break;
            res.add(current);

            Entry e1 = new Entry(current.i + 1, current.j);
            if (!q.contains(e1))
                q.offer(e1);

            Entry e2 = new Entry(current.i, current.j+1);
            if (!q.contains(e2))
                q.offer(e2);
        }

        return res;
    }

    public static class Entry implements Comparable<Entry>
    {
        public int i;
        public int j;
        public Entry(int i, int j)
        {
            this.i = i;
            this.j = j;
        }

        public int getValue()
        {
            return (int)Math.pow(2,i) * (int)Math.pow(5, j);
        }

        @Override
        public boolean equals(Object o)
        {
            Entry e = (Entry)o;
            return i == e.i && j == e.j;
        }

        @Override
        public int compareTo(Entry o) {
            return getValue() - o.getValue();
        }
    }
}

- Babao April 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int powi(int num, int expo)
{
int i=0;
int retVal = 1;
for(i=0;i<expo;i++){
retVal *= num;
}
return retVal;
}

int printNums(int maxAllowed)
{
int i;
int j;
int num;

int *hash;

if( (hash=(int*)malloc(maxAllowed*sizeof(int))) == 0){
printf("malloc failed\n");
return -1;
}
memset(hash, 0, maxAllowed*sizeof(int));

for(i = 0; powi(2,i) < maxAllowed ; i++) {
for(j = 0; ; j++) {
num = powi(2,i) * powi(5,j);
if( num > maxAllowed){
break;
}
hash[num]=1;
printf("i %d j %d num %d\n", i, j, num);
}
}

for(i = 0; i < maxAllowed ; i++) {
if(hash[i]){
printf("%d\n", i);
}
}
return 0;
}

int main(int argc, char* argv[])
{
printNums(atoi(argv[1]));
}

- SAMMY April 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int powi(int num, int expo)
{
	int i=0;
	int retVal = 1;
	for(i=0;i<expo;i++){
		retVal *= num; 
	}
	return retVal;
}

int printNums(int maxAllowed)
{
    int i;
    int j;
    int num;

    int *hash;

    if( (hash=(int*)malloc(maxAllowed*sizeof(int))) == 0){
	printf("malloc failed\n");
	return -1;
    }
    memset(hash, 0, maxAllowed*sizeof(int));

    for(i = 0; powi(2,i) < maxAllowed ; i++) {
    	for(j = 0; ; j++) {
		num = powi(2,i) * powi(5,j);
		if( num > maxAllowed){
			break;
		}
		hash[num]=1;
		printf("i %d j %d num %d\n", i, j, num);
	}
    }

    for(i = 0; i < maxAllowed ; i++) {
	if(hash[i]){
		printf("%d\n", i);
	}
    }
    return 0;
}

int main(int argc, char* argv[])
{
	printNums(atoi(argv[1]));
}

- SAMMY April 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int powi(int num, int expo)
{
	int i=0;
	int retVal = 1;
	for(i=0;i<expo;i++){
		retVal *= num; 
	}
	return retVal;
}

int printNums(int maxAllowed)
{
    int i;
    int j;
    int num;

    int *hash;

    if( (hash=(int*)malloc(maxAllowed*sizeof(int))) == 0){
	printf("malloc failed\n");
	return -1;
    }
    memset(hash, 0, maxAllowed*sizeof(int));

    for(i = 0; powi(2,i) < maxAllowed ; i++) {
    	for(j = 0; ; j++) {
		num = powi(2,i) * powi(5,j);
		if( num > maxAllowed){
			break;
		}
		hash[num]=1;
		printf("i %d j %d num %d\n", i, j, num);
	}
    }

    for(i = 0; i < maxAllowed ; i++) {
	if(hash[i]){
		printf("%d\n", i);
	}
    }
    return 0;
}

int main(int argc, char* argv[])
{
	printNums(atoi(argv[1]));
}

- SAMMY April 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int powi(int num, int expo)
{
	int i=0;
	int retVal = 1;
	for(i=0;i<expo;i++){
		retVal *= num; 
	}
	return retVal;
}

int printNums(int maxAllowed)
{
    int i;
    int j;
    int num;

    int *hash;

    if( (hash=(int*)malloc(maxAllowed*sizeof(int))) == 0){
	printf("malloc failed\n");
	return -1;
    }
    memset(hash, 0, maxAllowed*sizeof(int));

    for(i = 0; powi(2,i) < maxAllowed ; i++) {
    	for(j = 0; ; j++) {
		num = powi(2,i) * powi(5,j);
		if( num > maxAllowed){
			break;
		}
		hash[num]=1;
		printf("i %d j %d num %d\n", i, j, num);
	}
    }

    for(i = 0; i < maxAllowed ; i++) {
	if(hash[i]){
		printf("%d\n", i);
	}
    }
    return 0;
}

int main(int argc, char* argv[])
{
	printNums(atoi(argv[1]));
}

- SAMMY April 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void print(int N){
		LinkedList<Double> notPrinted = new LinkedList<>();
		ListIterator<Double> iter = notPrinted.listIterator();
		double prev = -1;
		int maxJ = Integer.MAX_VALUE;
		int modif = 0;
		
		int i = 0;
		while(true){ // i
			modif = 0;
			for(int j=0; j<maxJ; j++){
				double num = pow(2,i) + pow(5,j);
				if(num>N){
					if(i==0)
						maxJ = j;
					break;
				}
				if(num<prev){
				  while(iter.hasPrevious()){
					  prev = iter.previous();
					  if(prev<num){
						  iter.next();
						  break;
					  }
				  }
				}else{
				  while(iter.hasNext()){
					  prev = iter.next();
					  if(prev>num){
						  iter.previous();
						  break;
					  }
				  }
				}
				iter.add(num);
				prev = num;
				modif++;				
			}
			if(modif==0)
				break;
			else
				i++;
		}
		
		System.out.print("[ ");
		for(Double d:notPrinted)
			System.out.printf("%.0f ", d);
		System.out.println(" ]");

}

- lareinev April 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It looks like this will be adding one zero in each computation.
2^1 =2 5^1=5 2^i*5^i=10
2^2 =4 5^2=25 =100
2^3 =8 5^3=125 =1000
2^4 =16 5^4=625 =10000
2^5 =32 5^5=3125 =100000

do we simply run a loop N times for getting the right side value? Will this be accepted?

- Anonymous May 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.PriorityQueue;

public class Print2Power5Power {
	static class Entry implements Comparable<Entry> {
		public final int i;
		public final int j;
		public final long value;
		public Entry(int i, int j) {
			this.i = i;
			this.j = j;
			this.value = (long)(Math.pow(2,i)* Math.pow(5,j));
		}
		public int compareTo(Entry arg0) {
			long diff = value - arg0.value;
			if (diff < 0) return -1;
			else if(diff == 0) return 0;
			else return 1;
		}
	}

	public static void main(String[] args) {
		// The head of this queue is the least element with respect to the specified ordering.
		PriorityQueue<Entry> pq = new PriorityQueue<Entry>();
		long N = 12345678900000L;
		pq.add(new Entry(0,0));
		while (true) {
			Entry item = pq.poll();
			if (item.value > N) break;
			System.out.println(item.value);
			pq.add(new Entry(item.i+1, item.j));
			if (item.i == 0) {
				pq.add(new Entry(item.i, item.j+1));
			}
		}
	}
}

- danzhi May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.PriorityQueue;

public class Print2Power5Power {
	static class Entry implements Comparable<Entry> {
		public final int i;
		public final int j;
		public final long value;
		public Entry(int i, int j) {
			this.i = i;
			this.j = j;
			this.value = (long)(Math.pow(2,i)* Math.pow(5,j));
		}
		public int compareTo(Entry arg0) {
			long diff = value - arg0.value;
			if (diff < 0) return -1;
			else if(diff == 0) return 0;
			else return 1;
		}
	}

	public static void main(String[] args) {
		// The head of this queue is the least element with respect to the specified ordering.
		PriorityQueue<Entry> pq = new PriorityQueue<Entry>();
		long N = 12345678900000L;
		pq.add(new Entry(0,0));
		while (true) {
			Entry item = pq.poll();
			if (item.value > N) break;
			System.out.println(item.value);
			pq.add(new Entry(item.i+1, item.j));
			if (item.i == 0) {
				pq.add(new Entry(item.i, item.j+1));
			}
		}
	}
}

- danzhi May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why on earth ppl are doing all this shit instead of print just 1 10 100 1000 till n ?
since a^i*b^ = (a+b)^i

- Anonymous May 30, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More