## Google Interview Question for Software Engineers

• 3

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<>();
for(int num = 2; num <= N; num++) {
if((num % 2 == 0 && set.contains(num / 2)) || (num % 5 == 0 && set.contains(num / 5))) {
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<>();
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]))) {
System.out.println(num);
break;
}
}
}
}``````

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)
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
}}

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)
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``````

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]

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 )``````

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

``````static void PrintNumbers(int N)
{
var list = new List<int>();
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);
}
}``````

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;
}
}
}``````

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;
}
}``````

}

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<>();
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) {
}
}
int newValue = value * 5;
if (newValue <= n && newValue >= 0) {
}
}
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;
}
}``````

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;

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();
}
}
}``````

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]));
}

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]));
}``````

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]));
}``````

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]));
}``````

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

``````public static void print(int N){
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;
}
}
}
prev = num;
modif++;
}
if(modif==0)
break;
else
i++;
}

System.out.print("[ ");
for(Double d:notPrinted)
System.out.printf("%.0f ", d);
System.out.println(" ]");``````

}

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?

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;
while (true) {
Entry item = pq.poll();
if (item.value > N) break;
System.out.println(item.value);
if (item.i == 0) {
}
}
}
}``````

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;
while (true) {
Entry item = pq.poll();
if (item.value > N) break;
System.out.println(item.value);
if (item.i == 0) {
}
}
}
}``````

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

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.

### 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.