Google Interview Question
Software Engineer / DevelopersCountry: United States
good logic. it can be enhanced further with a return status on printRec to reduce some unnecessary traversing
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);
}
}
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;
}
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);
}
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);
}
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);
}
# 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
#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 << " ";
}
}
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();
}
}
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);
}
#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++;
}
}
}
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)
#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;
}
/*
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;
}
// 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;
}
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);
}
}
}
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);
}
}
}
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++;
}
}
}
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;
}
- Phoenix July 15, 2014