Google Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
37
of 41 vote

public static void main(String[] args) {
		for(int i=1;i<10;i++)
		printRec(""+i, 1000);
	}
static void printRec(String str, int n){
		if(Integer.parseInt(str) > n)
			return;
		System.out.println(str);
		for(int i=0;i<10;i++)
			printRec(str+i,n);
	}

- Phoenix July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good, very clean

- John July 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Logic is outstanding... though the logic fails if N = 0. But thats a small change.

- Saurabh July 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not very clear on the question itself. Could anyone please elaborate more?

- Ran July 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good logic. it can be enhanced further with a return status on printRec to reduce some unnecessary traversing

- lz July 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

I tried this in javascript code, doesn't work-- i dont see any difference in my code:
function printTopN_inStringComparisonORder(n) {
var printNum = function(str, n) {
if (parseInt(str) > n) return
console.log(str)
for (j=0;j<10;j++) {
printNum(str + j, n)
}
}
for(var i=1; i<10; i++) {
printNum(""+i, 1000);
}
}

- Larry July 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

void recur(string s, int N) {
	if(s!="") {
		if(stoi(s)>N)
			return;
		cout<<s<<"\n";
	}
	for(int i=0;i<=9;i++) {
		if(s=="" && i==0)
			continue;
		s.push_back('0'+i);
		recur(s,N);
		s.pop_back();
	}
}

- hugakkahuga January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
9
of 9 vote

DFS comes to our rescue.
if you observe a little you can find out that there is a nice pattern
Start with a char 1-9 in that order (9 iterations).
Add a 0-9 to right of string one at a time and recursively do dfs.
if value<=n print it.
recursively keep on adding char to the right.
when value>n. return from dfs call.

Here is the fully working code in C++

#include<stdio.h>
#include<stdlib.h>
using namespace std;
char s[8]="";
int n;
void dfs(int i)//i is the position of null character. initially null is at 0
{
	s[i+1]='\0';
	for(int j=48;j<=57;j++)//ascii 48 to 57 is '0' to '9'
	{
		s[i]=j;
		if(atoi(s)<=n)
		{
			printf("%s ",s);
			dfs(i+1);//add characters to the right
		}
		else
			break;
	}
	s[i]='\0';
}
int main()
{
	scanf("%d",&n);
	s[1]='\0';
	for(int j=49;j<=57;j++)//ascii for char '1' to '9'
	{
		s[0]=j;
		if(atoi(s)<=n)
		{
			printf("%s ",s);
			dfs(1);			
		}
		else
			break;
	}
	return 0;
}

- neerajlakhotia08 July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same idea but just try to avoid over-generate the sequence and atoi in every loop

int s[10];
int digit[10];
int nDigit;
int N = 123;
int count = 0;

void Convert(int N, int *digit, int &nDigit)
{
	nDigit = 0;
	while (N > 0)
	{
		digit[++nDigit] = N % 10;
		N /= 10;
	}
}

void Print(int length)
{
	count++;
	if (count > 50) return;

	for (int i = 1; i <= length; i++)
		cout << s[i];
	cout << endl;	
}


void Generate(int pos, bool f1, bool f2)
{
	int l = (pos == 1) ? 1 : 0;
	int h = 9;
	if (pos == nDigit)
		if (f1)	
			return;
		else if (f2)
			h = digit[1];
	for (int i = l; i <= h; i++)
	{
		s[pos] = i;
		Print(pos);
		if (pos < nDigit)
			Generate(pos+1, f1 | (s[pos] > digit[nDigit-pos+1]), f2 && (s[pos] == digit[nDigit-pos+1]));	
	}
}

int main()
{
	Convert(N, digit, nDigit);
	Generate(1, false, true);
}

- Anonymous July 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
8
of 8 vote

An iterative solution that doesn't use strings, so there's no dynamic memory allocation behind the scenes (except, possibly, for printing on the screen).

#include <iostream>
int main() {
    int N = 1000;
    int n = 1;
    do {
        std::cout << n << '\n';
        if (10 * n <= N)
            n = 10 * n;
        else {
            if (++n > N)
                n = (n - 1) / 10 + 1;
            while (n % 10 == 0)
                n = n / 10;
        }
    } while (n != 1);
}

- cassio.neri July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
5
of 5 vote

Can you please elaborate your question ?
When N=1000, why you selected only these number and only that sequence ?
1, 10, 100, 1000, 101, 102, ... 109, 11, 110,

- Kaushik Lele July 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

void print(int N) {
    for (int i = 1; i < 10; i++)
        printRec(i, N);
}

void printRec(int base, int N) {
    if (base > N)
        return;
    printf("%d\n", base);
    for (int i = 0; i < 10; i++)
        printRec(base * 10 + i, N);
}

- zprogd August 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Nice one with no strings involved!

- cassio.neri August 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

improved version with less calls:
void PrintRec(int base, int N)
{
printf("%d\n", base);
for (int i = 0; i < 10; i++)
{
int newBase = base * 10 + i;
if(newBase <= N)
PrintRec(newBase, N);
else
break;

}
}

void Print(int N)
{
for (int i = 1; i < 10; i++)
PrintRec(i, N);
}

- marina.gupshpun May 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

# To change this template, choose Tools | Templates
# and open the template in the editor.
# code is written in ruby language
class Number 
  @@number = "";
  def test(i)   
    for k in 0..9
      @@number = @@number.insert(i, k.to_s)
      if(@@number.to_i <= 1000)              
        puts @@number
        test(i+1)
      else
        break
      end
    end
    @@number = @@number[0, i-1];
  end
  
  def test2
    for j in 1..9 
      @@number.insert(0, j.to_s)
      puts @@number
      test(1)
    end
end
end

@number = Number.new
@number.test2

- Ankit jain(ankitjain50000@gmail.com) July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <sstream>
#include <algorithm>

struct Comp
{
    bool operator()(const int &i, const int& j)
    {
        ostringstream o1;
        ostringstream o2;

        o1 << i;
        o2 << j;

        return (o1.str() < o2.str());
    }
};


void PrintLex(int N)
{
    vector<int> V;
    Comp mycomp;

    for (int i = 1; i <= N; ++i)
    {
        V.push_back(i);
    }

    std::sort(V.begin(), V.end(), mycomp);

    for (auto iter = V.begin(); iter != V.end(); ++iter)
    {
        cout << *iter << "   ";
    }
}

- John Dope July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void MainFunc()
        {       
            string str = "1";
            while (str!=null)
            {
                Console.Write(str+", ");
                str = GetNext(str); 
            }

        }

        static string GetNext(string cur)
        {
            if(cur == "999") return null;

            if (cur.Length < 3)
            {
                cur += "0";
                return cur;
            }

            int tmp = int.Parse(cur);
            if(tmp==100)
            {
                return "1000";
            }

            if (tmp == 1000)
            {
                return "101";
            }

            tmp += 1;
            if (tmp % 100 == 0)
            {
                return ((int)(tmp / 100)).ToString();
            }
            else if (tmp % 10 == 0)
            {
                return ((int)(tmp / 10)).ToString();
            }
            else
            {
                return tmp.ToString();
            }
        }

- jiangok2006 July 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To make DFS more understandable just think about a tree with root 1. Root 1 has children 10,11,...,19. 10 has children 100,101,102,...,109. 11 has children 110,111,...,119. Do a DFS and if the node value is under given threshold print it.

public static void print(int root, int N){
		System.out.println(root);
		for(int i=0;i<=9;++i){
			int newNum = root*10+i;
			if(newNum>N)break;
			else print(newNum, N);
		}
	}
	public static void print(int N){
		print(1, N);
	}

- Chunming He July 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

static
void
printStringOrder(
    int n,
    int seed);

int main()
{
    int n = 0;

    printf ("Enter a maximum number:\t");
    scanf ("%d", &n);

    printStringOrder (n, 0);

    printf ("\n");

    return 0;
}

static
void
printStringOrder(
    int n,
    int seed
    )
{
    int j = seed;
    int k = 0;

    if (seed == n)
    {
        printf ("%d ", n);
        return;
    }

    if (seed > n)
    {
        return;
    }
    if (n>0)
    {
        while (j <= seed+9 && j <=n)
        {
            if (j)
            {
              k = j;
              printf ("%d ", j);
              k *=10;

              printStringOrder(n,k);
            }

            j++;
        }
    }
}

- aishu_oospno July 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python solution

def string_ord_nums(n):
    """Generate all number less than `n` in alphabetical order

    Example:
    >>> from itertools import islice
    >>> take = lambda n, xs: list(islice(xs, n))
    >>> take(10, string_ord_nums(100))
    [1, 10, 100, 11, 12, 13, 14, 15, 16, 17]
    >>> take(15, string_ord_nums(1000))
    [1, 10, 100, 1000, 101, 102, 103, 104, 105, 106, 107, 108, 109, 11, 110]
    """
    def nums(v):
        for i in range(10):
            vn = v * 10 + i
            if 0 < vn <= n:
                yield vn
                for vi in nums(vn):
                    yield vi
    return nums(0)

- Pavel Aslanov July 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

#define f(i,n) for(int i=0;i<n;i++)

string to_string(int a)
{
    char s[1000];
    itoa(a,s,10);
    return string(s);
}

bool cmp(string a, string b)
{
    int i=0;
    while(i<a.length() && i<b.length())
    {
        if(a[i]<b[i]) return 1;
        else if (a[i]>b[i]) return 0;
        i++;
    }
    return (a.length()<b.length())?1:0;
}

int main()
{
    int n;
    cin>>n;
    vector<string> numbers;
    f(i,n) numbers.push_back(to_string(i+1));
    sort(numbers.begin(), numbers.end(), cmp);
    f(i,n) cout<<numbers[i]<<" ";
    cout<<endl;
    return 0;
}

- suri July 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Output top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...
*/

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric>
#include <sstream>
#include <stack>
#include <string>

using namespace std;

struct Node
{
Node( int nValue )
{
this->m_nValue = nValue;
memset( this->m_SubTree, 0, sizeof( Node * ) * 10 );
}

int m_nValue;
Node * m_SubTree[10];
};

class Solution
{
public:
static void AddToTree( int nValue, Node * & pTree)
{
vector<int> vecTreePath;
int nValueCopy = nValue;
while ( nValueCopy > 0 )
{
vecTreePath.push_back( nValueCopy % 10 );
nValueCopy /= 10;
}

Node * pParent = pTree;
{
for ( size_t i = vecTreePath.size() - 1; i > 0; i -- )
pParent = pParent->m_SubTree[ vecTreePath[i] ];
}

pParent->m_SubTree[ vecTreePath[0] ] = new Node(nValue);
}

static void CreateTree( int nValue, Node * & pTree )
{
if ( nValue <= 0 )
return;
pTree = new Node( 0 );
for ( int i = 1; i <= nValue; i ++ )
AddToTree( i, pTree );
}

static void PrintTreeInDFS( Node * pTree )
{
if ( !pTree )
return;

// skip zero
if ( pTree->m_nValue )
printf( "%d ", pTree->m_nValue);

for ( int ii = 0; ii < 10; ii ++ )
{
if ( pTree->m_SubTree[ ii ])
PrintTreeInDFS( pTree->m_SubTree[ ii ] );
}
}

static void DeleteTree( Node * & pTree )
{
for ( int i = 0; i < 10; i ++ )
{
if ( pTree->m_SubTree[i] )
DeleteTree( pTree->m_SubTree[i]);
}
delete pTree;
pTree = NULL;
}
};


int _tmain(int argc, _TCHAR* argv[])
{
Node * pTree = NULL;

Solution::CreateTree( 1000, pTree );
Solution::PrintTreeInDFS( pTree );
Solution::DeleteTree( pTree );

_getch();

return 0;
}

- slfeng July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// RePaste

/*
Output top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below: 
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...
*/

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric> 
#include <sstream>
#include <stack>
#include <string>

using namespace std;

struct Node
{
	Node( int nValue )
	{
		this->m_nValue = nValue;
		memset( this->m_SubTree, 0, sizeof( Node * ) * 10 );
	}

	int m_nValue;
	Node * m_SubTree[10];
};

class Solution
{
public:
	static void AddToTree( int nValue, Node * & pTree)
	{
		vector<int> vecTreePath;
		int nValueCopy = nValue;
		while ( nValueCopy > 0 )
		{
			vecTreePath.push_back( nValueCopy % 10 );
			nValueCopy /= 10;
		}

		Node * pParent = pTree;
		{
			for ( size_t i = vecTreePath.size() - 1; i > 0; i -- )
				pParent = pParent->m_SubTree[ vecTreePath[i] ];			
		}

		pParent->m_SubTree[ vecTreePath[0] ] = new Node(nValue);
	}

	static void CreateTree( int nValue, Node * & pTree )
	{
		if ( nValue <= 0 )
			return;
		pTree = new Node( 0 );
		for ( int i = 1; i <= nValue; i ++ )
			AddToTree( i, pTree );
	}

	static void PrintTreeInDFS( Node * pTree )
	{
		if ( !pTree )
			return;

		// skip zero
		if ( pTree->m_nValue )
			printf( "%d ", pTree->m_nValue);

		for ( int ii = 0; ii < 10; ii ++ )
		{
			if ( pTree->m_SubTree[ ii ])
				PrintTreeInDFS( pTree->m_SubTree[ ii ] );
		}
	}

	static void DeleteTree( Node * & pTree )
	{
		for ( int i = 0; i < 10; i ++ )
		{
			if ( pTree->m_SubTree[i] )
				DeleteTree( pTree->m_SubTree[i]);
		}
		delete pTree;
		pTree = NULL;
	}
};


int _tmain(int argc, _TCHAR* argv[])
{
	Node * pTree = NULL;

	Solution::CreateTree( 1000, pTree );
	Solution::PrintTreeInDFS( pTree );
	Solution::DeleteTree( pTree );

	_getch();

	return 0;
}

- slfeng July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

two files:

Data class contains the integer and compares like string:

public class Data implements Comparable{
    public int i;

	public int compareTo(Object other) {
		// TODO Auto-generated method stub
		Data o = (Data)other;
		
		String left = Integer.toString(this.i);
		String right = Integer.toString(o.i);
		return left.compareTo(right);
	}
	Data(int i)
	{
		this.i = i;
	}
}

----------------------------------------------------------------

Main function:

import java.util.ArrayList;


public class OutputNumbersByStringCompare {

	
	/*Output top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below: 
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...*/
	public static void main(String[] args) {
	 
		// TODO Auto-generated method stub
	  ArrayList<Data> list = new ArrayList<Data>();
      for ( int i = 1; i<= 1000; i++) 
      {
    	  Data d = new Data(i);
    	  list.add(d);
      }
      list.sort(null);
      for ( Data d : list)
      {
    	  System.out.println(d.i);
      }
	}
}

- Anonymous July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

String comparison done on the numbers will give the expected results.

public class PrintNumbers {
    public static void main(String[] args) {
        int N = 1000;

        List<String> list = new ArrayList<>();
        for(int i = 1 ; i <= N ;i++) {
            list.add(""+i);
        }
        Collections.sort(list);

        for(String s : list) {
            System.out.println(s);
        }
    }
}

- Anonymous August 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

convert the int to char using a 1000*4 char array, then do radix sort.

- Linnan August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int value = 1;

		int counter = 0;
		while (counter < N)
		{
			counter++;
			System.out.println(value);
			if (value * 10 <= N)
				value = value * 10;
			else
			{
				if (value + 1 > N)
					value = value / 10 + 1;
				else
				{
					if ((value + 1) % 10 == 0)
					{
						value++;
						while (value % 10 == 0)
							value = value / 10;
					}
					else
						value++;
				}
			}
		}

- Rick August 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple C++ solution.

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N;
    cin >> N;

    vector<string> V(N);

    for (int i = 0; i < N; i++){
        ostringstream oss;
        oss << i + 1;
        string s = oss.str();
        V[i] = s;
    }

    sort(V.begin(), V.end());

    for (int i = 0; i < N; i++){
        cout << V[i] << endl;
    }

    return 0;
}

- Inucoder August 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import bisect

def sort(n):
  s = []
  for i in range(1,1+n):
    bisect.insort(s, str(i))
  return s

print(digit_sort(1000))

- d.gabri3le September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def sort_numbers(n):
	l = [str(x) for x in range(1,n+1)]
	l.sort()
	return l

- Fede September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
    public ArrayList<String> topN(int n) {
        TreeSet<String> set = new TreeSet<String>();
        for (int i = 1; i <= n; i++) {
            set.add(String.valueOf(i));
        }
        return new ArrayList<String>(set);
    }
}

- Anonymous February 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can someone explain the question?

- jigili September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def output(n):
    if n > 0:
        return ' '.join(sorted([str(x) for x in range(1, n+1)])) # O(nlogn)
    return None

print (output(1000))

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

def output(n):
if n > 0:
return ' '.join(sorted([str(x) for x in range(1, n+1)])) # O(nlogn)
return None

print (output(1000))

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

return ' '.join(sorted([str(x) for x in range(1, n+1)])) # O(nlogn)

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

Here's my solution in five lines of Python:
O(1) space, O(n) time:

def f(n,s=''):
    if not s or int(s)<=n:
        print(s)
        for i in range(not s,10):
            f(n,s+str(i))

Example usage:

f(1000)

- ryancentralorg November 06, 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