Google Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Gud one!!
But I guess in the if condition check you have to handle the equality separately and increment both count_2 and count_5 in case arr[count_2] and arr[count_5] are equal.
can u point out the mistake in the solution instead of general statement. that will do more good to u and others
Good one and simple, but Small correction. Start i with 1 istead of 0, and increment i only once. you did twice
#include<iostream>
using namespace std;
int main()
{
int tpc = 0;
int count;
cin>>count;
unsigned long int curr = 1;
int mtp = 1, mpowt = 0;
while(count>0)
{
while(tpc >= 0)
{
cout<<curr<<" ";
count--;
if (count == 0)
break;
if (tpc >= 2)
{
curr = curr*5/4;
}
tpc -= 2;
}
mtp *= 2;
tpc = ++mpowt;
curr = mtp;
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
int* createIncreasingOrder (int limit) {
int *result, i, index2 = 0, index5 = 0 ;
result = (int *) malloc (sizeof(int) * limit) ;
result[0] = 1 ;
for ( i = 1 ; i < limit ; i ++ ) {
/* Check which one is better multiplied by 2 or 5 specified by their indices */
if ( (result[index2]<<1) > (result[index5]*5) )
result[i] = result[index5++] * 5 ;
else if ( (result[index2]<<1) < (result[index5]*5) )
result[i] = result[index2++] << 1 ;
else {
result[i] = result[index2] << 1 ;
index2 ++ ;
index5 ++ ;
}
}
return result ;
}
void printList (int *list, int size) {
int i ;
printf ( "\n" ) ;
for ( i = 0 ; i < size ; i ++ )
printf ( "%d ", list[i] ) ;
}
int main () {
int limit = 20 ;
printList (createIncreasingOrder(limit),limit) ;
return 0;
}
I think the original idea is still good, although it has a bug.
The following is my Java implmentation with a simple test.
The scenario 'values[index2] * 2 == values[index5] * 5' is also considered.
import java.util.*;
class G216
{
public static void main(String[] args) {printIncreasing(50);}
public static void printIncreasing(int length)
{
long[] values = new long[length];
values[0] = 1;
int index2 = 0;
int index5 = 0;
for (int i = 0; i < length; i++)
{
System.out.println(values[i] + "");
if (i < (length - 1))
{
if (values[index2] * 2 == values[index5] * 5)
{
values[i + 1] = values[index2] * 2;
index2++;
index5++;
}
else if (values[index2] * 2 < values[index5] * 5)
{
values[i + 1] = values[index2] * 2;
index2++;
}
else
{
values[i + 1] = values[index5] * 5;
index5++;
}
}
}
}
}
Have 2 queues - one for powers of 2, another for powers of 5.
Start with X = 1
Push 2*X and 5*X to both queues.
Pick the number from that queue which gives a smaller number.
If the number came from Q(2), push x*2 in to Q(2), push x*5 into Q(5) remove x from Q(2)
if the number came from Q(5), push x*2 into Q(5), remove x from Q(5)
If the number came from Q(2), push x*2 in to Q(2), push x*5 into Q(5) remove x from Q(2)
If the number came from Q(5), push x*2 in to Q(2), push x*5 into Q(5) remove x from Q(2)
If the number came from both i.e equal , push x*2 in to Q(2), push x*5 into Q(5) remove x from Q(1), Q(2)
void print_series(int n)
{
Queue q1,q2;
int count = 0,x = 1;
while(count < n){
cout<< x << "\t";
q1.enqueue(2*x);
q2.enqueue(5*x);
if(q1.first() < q2.first())
x = q1.dequeue();
else if(q1.first() > q2.first())
x = q2.dequeue();
else{
q1.dequeue();
x = q2.dequeue();
}
count++;
}
}
If the number came from Q(5), push x*2 in to Q(2), push x*5 into Q(5) remove x from Q(2)
//Not sure I understand the request fully. Here's a shot at it I pieced together:
#include <iostream>
using namespace std;
void MultiplyIncrement(long long *multipliedNumber, int *increment, int base)
{
(*increment)++;
(*multipliedNumber)*=base;
}
int numPrinted = 0;
void PrintMultiplyIncrement(long long *printableNumber, int *increment, int base)
{
printf("\n%3d: %llu - base %d", numPrinted++, *printableNumber, base);
MultiplyIncrement(printableNumber, increment, base);
}
int main(int argc, char *argv[])
{
int i=0;
int imax = 63;//let's try *not* overflowing the long int
//also, the final bit "inverts" the gt-lt comparison below, so we can't use
//the 64th bit in this case.
int ibase = 2;
long long ii = 1;
int j=0;
int jmax = 28;//try to avoid overflow for this algorithm; a double can be used for a larger number.
int jbase = 5;
long long jjjjj = 1; //jjjjj - worst variable name ever? perhaps
for (int k=0; k<100; k++)
{
if (!(i<imax)&& !(j<jmax)){
printf("\nprinted as many of ii and jjjjj as we wanted without overflow");
break; //that's as high as we want to print for now for both
}
if (ii < jjjjj)
{
if (i<imax)
{
//printf("\n%llu < %llu",ii, jjjjj);
PrintMultiplyIncrement(&ii, &i, ibase);
}
else
{
printf("\nalready reached imax last time");
ii=LONG_LONG_MAX; // keep loop from coming to ii again
k--; // try again, this time going to j
continue;
}
}
else if(ii > jjjjj)
{
if (j<jmax)
{
PrintMultiplyIncrement(&jjjjj, &j, jbase);
}
else
{
printf("\nalready reached jmax last time");
jjjjj=LONG_LONG_MAX;
k--;
continue;
}
}
else if (ii == jjjjj) //not less-than and not greater-than... the comparison in the if-clause is not necessary
{//note: 5^j will never be equivalent to a power of two aside from 5^0; so, this is
//mostly unnecessary here, although it might be more useful for a different set of base numbers.
PrintMultiplyIncrement(&jjjjj, &j, jbase);
MultiplyIncrement(&ii, &i, ibase);
}
}
putchar('\n');
system("PAUSE");
return EXIT_SUCCESS;
}
/* output from program:
0: 1 - base 5
1: 2 - base 2
2: 4 - base 2
3: 5 - base 5
4: 8 - base 2
5: 16 - base 2
6: 25 - base 5
7: 32 - base 2
8: 64 - base 2
9: 125 - base 5
10: 128 - base 2
11: 256 - base 2
... [truncated] ...
85: 1152921504606846976 - base 2
86: 1490116119384765625 - base 5
87: 2305843009213693952 - base 2
88: 4611686018427387904 - base 2
already reached imax last time
89: 7450580596923828125 - base 5
printed as many of ii and jjjjj as we wanted without overflow
Press any key to continue . . .
*/
Here's a very simple solution. Just to keep in mind is that multiplying any number with 2 or 4 will always result in a number less than multiplying it with 5. Now what u need to do take two counters i=0, j;
a[i]=1;
a[++i] = 2;
for(j=1;i<n;j++) //first n numbers of the sequence need to be printed
{
a[++i] = a[j]*4;
if (i == n)
break;
a[++i] = a[j]*5;
}
that's it. :-)
<pre lang="" line="1" title="CodeMonkey10275" class="run-this">Simple brute force would be to keep all the previous solutions and then iterate over
them to find the minimal one that multiplied by 2 or 5 gives the number greater
then the current element. History search should start at the latest number and continue by decreasing solutions until the first one found and multiplied by 5 is lesser then current element. Complexity is linear space, ant time is certainly better than O(n^2) but one should prove that limited history search is better than O(n) (and it is).
void GetElementsSimple(int n){
list<int> solutions;
int curSolution;
int bestNext;
solutions.push_back(1);
while(n){
curSolution=solutions.back();
cout<<solutions.back()<<" ";
bestNext=curSolution*2;
for(list<int>::reverse_iterator i=solutions.rbegin();
i!=solutions.rend()&& (*i)*5>curSolution;
i++){
if(((*i)*5>curSolution)&&((*i)*5<bestNext)) bestNext=(*i)*5;
if(((*i)*2>curSolution)&&((*i)*2<bestNext)) bestNext=(*i)*2;
}
solutions.push_back(bestNext);
n--;
}
}
Additionally one may try to exercise O(n) solution that takes a numeber 2^i*5^j
and tries to create 2 exchanges. First is to convert a subset of 2^i to 2^(i-n)*5^n. The second is to convert 5^j to 2^m*5^(j-m). Conversion that gets smaller solution must be used.
Optimal conversion for all parameters i and j can be precomputed. This leads to provable O(n) time after precomputation.
</pre><pre title="CodeMonkey10275" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey41749" class="run-this">import java.util.PriorityQueue;
/**
* @author jk
* Print the numbers of form 2^i.5^j in increasing order. For eg:
* 1, 2, 4, 5, 8, 10, 16, 20
*/
public class G65IncreasingOrderSameFactors {
static class TwoFactorNumber implements Comparable<TwoFactorNumber> {
int p2;
int p5;
public TwoFactorNumber(int p2, int p5) {
this.p2 = p2;
this.p5 = p5;
}
int numberValue() {
return (int) (Math.pow(2, this.p2) * Math.pow(5, this.p5));
}
public int compareTo(TwoFactorNumber o) {
return this.numberValue() - o.numberValue();
}
}
final static int MAX_SIZE = 30;
static TwoFactorNumber[] a = new TwoFactorNumber[MAX_SIZE];
public static void printTheNumbers(int index) {
if (index >= MAX_SIZE)
return;
if (index == 0) {
a[0] = new TwoFactorNumber(0, 0);
System.out.printf("%d ", a[0].numberValue());
printTheNumbers(index + 1);
} else {
a[index] = getNextNumber(index - 1);
System.out.printf("%d ", a[index].numberValue());
printTheNumbers(index + 1);
}
}
/**
* @param size
* @returns the next number having factor prime 2 and 5
* Solution is to find the next bigger number as the last element in the array a
*/
private static TwoFactorNumber getNextNumber(int size) {
TwoFactorNumber cLast = a[size];
PriorityQueue<TwoFactorNumber> pq = new PriorityQueue<TwoFactorNumber>();
for(int i = 0; i <= size; i++){
TwoFactorNumber n2 = new TwoFactorNumber(a[i].p2+1, a[i].p5);
TwoFactorNumber n5 = new TwoFactorNumber(a[i].p2, a[i].p5+1);
if(n2.compareTo(cLast) > 0){
pq.add(n2);
}
if(n5.compareTo(cLast) > 0){
pq.add(n5);
}
}
return pq.poll();
}
/**
* @param args
*/
public static void main(String[] args) {
printTheNumbers(0);
}
}
</pre><pre title="CodeMonkey41749" input="yes">
</pre>
Note that log(2^i * 5^j) = i*log(2) + j*log(5).
let n = floor(log(5)/log(2)).
Start with i = 0, j = 0
At each step, print 2^i * 5^j
Continue by incrementing i from 1 to n.
When i = n, reset i = 0 and increment j by one.
Start your set with [1] and j=1
1. Start multiplying 2 with each element in the set
-> if it is less than 5^j then insert it into the array
-> greater then insert 5^j into the array, increment j, insert the multiplied result in the array and repeat Step 1.
Ex:
[1]
insert 2*1 : [1,2]
insert 2*2 : [1,2,4]
since 2*4 is greater than 5^1, insert 5 ; increment j; and insert 2*4 : [1,2,4,5,8]
insert 2*5 : [1,2,4,5,8,10]
insert 2*8 : [1,2,4,5,8,10,16]
insert 2*10 : [1,2,4,5,8,10,16,20]
since 2*16 is greater than 5^2, insert 5^2 ; increment j; and insert 2*16 : [1,2,4,5,8,10,16,20,25,32]
insert 2*20: [1,2,4,5,8,10,16,20,25,32,40]
insert 2*25: [1,2,4,5,8,10,16,20,25,32,40,50]
insert 2*32: [1,2,4,5,8,10,16,20,25,32,40,50,64]
insert 2*40: [1,2,4,5,8,10,16,20,25,32,40,50,64,80]
.... and so on
<pre lang="" line="1" title="CodeMonkey61410" class="run-this">void printIncreatNum()
{
int twoIndex = 0;
int fiveIndex = 0;
vector<int> outNum;
outNum.push_back(1);
while (1)
{
printf("%d\n",outNum.back());
int two = 2*outNum[twoIndex];
int five = 5*outNum[fiveIndex];
if (two < five)
{
outNum.push_back(two);
twoIndex++;
}
else if (two == five)
{
outNum.push_back(two);
twoIndex++;
fiveIndex++;
}
else
{
outNum.push_back(five);
fiveIndex++;
}
i++;
}
}
</pre><pre title="CodeMonkey61410" input="yes">
</pre>
int main()
{
int two,five;
int i,j;
i = 0; j=0; two=1; five = 1;
while (i < 10 || j < 10 )
{
if( five == two ) /* same -- bump up both */
{
printf("%i\n", five);
i++; j++;
two *= 2;
five *= 5;
}
else if(five < two ) /* print five */
{
printf("%i\n", five);
five *= 5;
j++;
}
else
{
printf("%i\n", two);
two *= 2;
i++;
}
}
return 0;
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package Arrarys;
/**
*
* @author swapnil
*/
public class powers2i5j {
public static void main(String[] args) {
int[] ans = new int[100];
ans[0] = 1;
int m = 0; //2
int n = 0; //5
int i = 1;
for (int j = 1; j < 100; j++) {
int n5 = ans[n] * 5;
int m2 = ans[m] * 2;
if (n5 < m2) {
ans[i] = n5;
i++;
System.out.print(n5 + ", ");
n++;
} else if (n5 > m2) {
ans[i] = m2;
i++;
System.out.print(m2 + ", ");
m++;
} else {
ans[i] = n5;
i++;
System.out.print(m2 + ", ");
m++;
n++;
}
}
}
}
<pre lang="" line="1" title="CodeMonkey12416" class="run-this"> public static void computeIncreasingOrder() {
int i = 0;
int smaller = 0;
int twoMultiple = (int) Math.pow(2, 0);
int fiveMultiple = (int) Math.pow(5, 0);
for (i = 1; i < 10; i++) {
if (twoMultiple < fiveMultiple) {
smaller = twoMultiple;
twoMultiple *= 2;
} else if (twoMultiple > fiveMultiple) {
smaller = fiveMultiple;
fiveMultiple *= 5;
} else {
smaller = fiveMultiple;
fiveMultiple *= 5;
twoMultiple *= 2;
}
System.out.println(smaller);
}
}</pre><pre title="CodeMonkey12416" input="yes">
</pre>
public void printNumbers2i5j() {
long i = 0;
long j = 0;
long base2N = 1;
long base5N = 1;
do {
if (base2N == base5N) {
System.out.println(base2N);
base2N = (long) Math.pow(2, ++i);
base5N = (long) Math.pow(5, ++j);
} else if (base2N < base5N) {
System.out.println(base2N);
base2N = (long) Math.pow(2, ++i);
} else if (base2N > base5N) {
System.out.println(base5N);
base5N = (long) Math.pow(5, ++j);
}
} while (i < 60);
}
Solution written in Python.
Complexity: O(n)(lg2(n)+lg5(n)).
def onlytwofive(data):
val = data
while val % 2 == 0:
val /= 2
while val % 5 == 0:
val /= 5
if val == 1:
return True
else:
return False
def twofive(max_value):
val = 1
while val < max_value:
if onlytwofive(val):
print val
val += 1
we dunt need to use extra data structure;
steps are:-
1st:- divide range in power of 5 ,like p = 5^i, q= 5^(i+1);
2nd:- find 2's power in the range of 2^(i-1)*p to 2^i*p ,which will always less than q.Print all,
ex :- let p =5 and q =25(for p = 1 to q =5 ,do same)
so first division is 5 to 2^1*5 and number would be 8 so it will print 8,10;
for next iteration it would be 2^1*5 to 2^2*5(still less than q)
so number would be 16,20
so for 5 to 25 all numbers are (5,8,10,16,20,25)
note the pattern in the following sequence. in the first column, the exponent of 2 goes from 0 to m (assume m is given). in each row, the exponent of 2 decreases by 2 and the exponent of 5 goes from 0 and increments by 1.
[2^0]*5^0,
[2^1]*5^0,
[2^2]*5^0, 2^0*5^1,
[2^3]*5^0, 2^1*5^1,
[2^4]*5^0, 2^2*5^1, 2^0*5^2,
[2^5]*5^0, 2^3*5^1, 2^1*5^2,
[2^6]*5^0, 2^4*5^1, 2^2*5^2, 2^0*5^3,
[2^7]*5^0, 2^5*5^1, 2^3,5^2, 2^1*5^4
code:
void genSequence(int m) //m is the largest exponent of 2 to generate
{
for (int k = 0; k < m; ++k)
{
for (int i = k, j = 0; i >= 0; i = i - 2, ++j)
cout << pow(2,i)*pow(5,j) << " ";
}
}
#include<stdio.h>
int main()
{
int a[10]={0};
a[0]=1;
int n2,n5;
int i,i2,i5;
n2=2;
n5=5;
i2=0;i5=0;
for(i=1;i<10;i++)
{
int next=n2<n5?n2:n5;
a[i]=next;
if(next==n2)
{
i2++;
n2=a[i2]*2;
}
if(next==n5)
{
i5++;
n5=a[i5]*5;
}
// printf("%d ",a[i]);
}
for(i=0;i<10;i++)
printf("%d ",a[i]);
getchar();
return 0;
}
public class Test
{
public static void main(String[] args)
{
printAll(13);
// Outputs
// ================
// 1
// 2
// 4
// 5
// 8
// 16
// 25
// 32
// 64
// 125
// 128
// 256
// 512
}
private static void printAll(int numberOfElement)
{
int i = 0, j = 0;
int count = 0;
while (count < numberOfElement)
{
//Since 2 and 5 are prime numbers, 1 needs exceptional handler
if(count == 0)
{
System.out.println(1);
count++;
i++;
j++;
}
int pow2i = (int) Math.pow(2, i);
int pow5j = (int) Math.pow(5, j);
if (pow2i < pow5j)
{
System.out.println(pow2i);
i++;
}
else
{
System.out.println(pow5j);
j++;
}
count++;
}
}
}
thought this would be a simple solution - check it out
Point to be considered from the question :
1) 2^1<2^2<5^1.
2) split the problem as small as possible.
2.1) Take a previous value from the arr and multiply by 2^1 put it in the top of the array.
2.2) then multiply the prev value by 2^2 put it in the top of the array.
2.3) then multiply the prev value by 5^1 put it in the top of the array.
3) Now move on to the next value in the array. perform the 2nd point.
public static void main(String[] args) {
int n=20;
int[] a=new int[n];
int ind=0, top=0;
a[top]=1;
generateSequence(a, n, top, ind);
System.out.println(Arrays.toString(a));
}
public static void generateSequence(int[] a, int n, int top, int ind){
if(top>=n-1)
return;
if(a[ind]*2>a[top]&&top<n){
a[++top]=a[ind]*2;
}
if(a[ind]*4>a[top]&&top<n){
a[++top]=a[ind]*4;
}
if(a[ind]*5>a[top]&&top<n){
a[++top]=a[ind]*5;
}
generateSequence(a, n, top, ++ind);
}
output : [1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125, 128, 160, 200, 250]
Here is my coding,and is it right?
#include<stdio.h>
#define N 10
int main()
{
int a[N];
int count2=0,count5=0,i;
a[0]=1;
for(i=1;i<N;i++)
{
if(a[count2]*2<a[count5]*5)
{
a[i]=a[count2]*2;
count2=i;
}
else
{
a[i]=a[count5]*5;
count5=i;
}
}
for(i=0;i<N;i++)
printf("%d ",a[i]);
return 0;
}
Notice a simple fact. For a number N = n*2*2 in the sequence, a higher number can be obtained by dividing by 4 and multiplying by 5 (i.e. next = n*5). This has a recursive nature. For example, if N = n*2*2*2*2, two higher numbers in the sequence are n*2*2*5 and n*5*5. The following algorithm is based off this idea.
#include <iostream>
#include <vector>
#include <algorithm>
void log(long d)
{
// application specific logic here
std::cout << d << std::endl;
}
void print_enumeration_two_five_powers()
{
std::cout << "1\n2" << std::endl;
// some init
long curr = 2;
long power_2 = 1; // power of 2 in the prime factorization of curr
bool times_2 = true;
std::vector<long> remains;
while (true)
{
if (times_2)
{// print the next power of 2
curr *= 2;
++power_2;
log(curr);
}
else
{// find out all powers of 5 that can be brought in..
// for every 4 that is slashed bring in a 5
long curr_cp = curr;
long power_2_cp = power_2;
long div = 4, mul = 5;
while (power_2_cp > 1)
{
power_2_cp -= 2;
curr_cp /= div;
curr_cp *= mul;
remains.push_back(curr_cp);
}
// since (5/4)^k will eventually exceed 2
// we need to stop printing these values currently
// and hold them on for later
std::sort(remains.begin(), remains.end(), std::greater<long>()); // can be made a little smarter
for (int i = remains.size() - 1; i >= 0; --i)
{
if (remains[i] < curr*2)
{
log(remains[i]);
remains.pop_back();
}
else
{
break;
}
}
}
// toggle
times_2 = !times_2;
}
}
int main()
{
print_enumeration_two_five_powers();
return 0;
}
Motivated by the fact that if N = n*2*2, then (N/4)*5 comes later on (not necessarily immediately after) in the sequence. And for any N, N*2 comes later on in the sequence.
#include <iostream>
#include <vector>
#include <algorithm>
void log(long d)
{
// application specific logic here
std::cout << d << std::endl;
}
void print_enumeration_two_five_powers()
{
std::cout << "1\n2" << std::endl;
// some init
long curr = 2;
long power_2 = 1; // power of 2 in the prime factorization of curr
bool times_2 = true;
std::vector<long> remains;
while (true)
{
if (times_2)
{// print the next power of 2
curr *= 2;
++power_2;
log(curr);
}
else
{// find out all powers of 5 that can be brought in..
// for every 4 that is slashed bring in a 5
long curr_cp = curr;
long power_2_cp = power_2;
long div = 4, mul = 5;
while (power_2_cp > 1)
{
power_2_cp -= 2;
curr_cp /= div;
curr_cp *= mul;
remains.push_back(curr_cp);
}
// since (5/4)^k will eventually exceed 2
// we need to stop printing these values currently
// and hold them on for later
std::sort(remains.begin(), remains.end(), std::greater<long>()); // can be made a little smarter
for (int i = remains.size() - 1; i >= 0; --i)
{
if (remains[i] < curr*2)
{
log(remains[i]);
remains.pop_back();
}
else
{
break;
}
}
}
// toggle
times_2 = !times_2;
}
}
int main()
{
print_enumeration_two_five_powers();
return 0;
}
Compute_Increasing_Order() {
- Google Aspirant September 18, 2011arr[0]= 1
count_2 = 0
count_5 = 0
for(int i = 0; ; i++)
{
if(2 * arr[count_2] <= 5 * arr[count_5])
{
arr[i] = 2 * arr[count_2];
count_2 ++;
} else {
arr[i] = 5 * arr[count_5];
count_5 ++;
}
print arr[i];
i++;
}
}