Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
Interview Type: In-Person
Do you think this version is better or worse?
void Lexi2(int N, int k=1)
{
for(int i = 0; i<10 && k+i<N && (k!=1||i!=9); i++)
{
std::cout<<k+i<<", ";
Lexi2(N, (k+i)*10);
}
}
void Lexi2(int N, int k=1)
{
for(int i = 0; i<10 && k+i<N && (k!=1||i!=9); i++)
{
std::cout<<k+i<<", ";
Lexi2(N, (k+i)*10);
}
}
@Viraj
the statement
if (k%10 == 0) return;
is to handle the case k == 1 in the very beginning. Because when k == 1, only need to go from 1 to 9 not from 0 - 9.
The codes can be written like this as well:
#include<iostream>
using namespace std;
void outputCore(long long v, int N){
if(v > N) return;
int upper = (v == 1 ? 9 : 10);
for(int i = 0; i < upper && v <= N; ++i){
cout << v << endl;
outputCore(v*10, N);
++v;
}
}
int main(){
outputCore(1, 520);
return 0;
}
A very good recursion question.
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
void printHelper(int i, int range){
if (i>range) return;
if (i != 0){
std::cout<<i<<std::endl;
}
int next = i*10;
if (next <=range){
for (int k = 0;k<=9 & (next+k<=range);k++){
printHelper(next+k,range);
}
}
}
void printNumber(int N){
for (int i = 1;i<10;i++){
printHelper(i,N);
}
}
int main(){
int N;
std::cin>>N;
printNumber(N);
}
~
void Print(int n)
{
for(int i = 1; i <= 9; i ++){
int j = 1;
while( j <= n){
for(int m = 0; m < j ; ++ m){
if(m + j * i <= n){
cout << m + j * i << endl;
}
}
j *= 10;
}
}
}
As my understanding the lexicographic order / dictionary order of numbers for the range 0 to 20 is
0 1 10 11 12 13 14 15 16 17 18 19 2 20 3 4 5 6 7 8 9
Correct me if I'm wrong...
After lot of math and paper work here is the code in C# with inline comments
O(n) time and O(1) space complexity
public void PrintNumbersInDictionaryOrder(int N)
{
// straight forward
if (N < 9)
{
for (int i = 1; i <= N; i++)
{
Console.WriteLine(i);
}
return;
}
int startingDigit, multiplyingFactor, loopCount, max;
// dangerous code with lot of math :-)
for (int index = 1; index <= 9; index++)
{
// prints single digit numbers
startingDigit = index;
Console.WriteLine(startingDigit);
// reset variables
multiplyingFactor = 1;
loopCount = 1;
while (startingDigit * 10 < N)
{
// 10, 100, 1000 and so on
// 20, 200, 2000 and so on
startingDigit = startingDigit * (int)Math.Pow(10, 1);
// 9, 99, 999, 9999 and so on
max = 9 * multiplyingFactor;
// max value depends on N
// for example, if N is 25 then max will become 5 instead of 9
// another example, if N is 256 then max will become 56 instead of 99
if (N - startingDigit < Math.Pow(10, loopCount))
{
max = N - startingDigit;
}
// prints 10 - 19, 100 - 199 and so on
for (int j = 0; j <= max; j++)
{
Console.WriteLine(startingDigit + j);
}
// 1, 11, 111, 1111 and so on
multiplyingFactor = (multiplyingFactor * 10) + 1;
loopCount++;
}
// corner case to print
// for example, if N = 10/100/1000 while loop fails to print the number
if (startingDigit * 10 == N)
{
Console.WriteLine(N);
}
}
}
The above code gives you just the idea and it can be refactored more to reduce some Math.
Use Recursion to Print it out. The idea is before printing the next number, exhaust all the number with the current prefix. The solution will be simple like the following one.
Also the search should blindly start from 0 and end at 9. Because if you were asked for numbers from 15 to 999, the very first number to appear will be 100 which will be missed if we start from 15 to 99.
for(int i = 0; i < 10; i ++)
{
PrintLexicographicOrder(i, endValue);
}
void PrintLexicographicOrder(int number, int endValue)
{
if(number >= startValue && number <= endValue)
print number;
int nextNumber = number * 10;
if(nextNumber == 0 || nextNumber > endValue)
return;
for(int i = 0; i < 10; i ++)
{
PrintLexicographicOrder(nextNumber+i, endValue);
}
}
public class PrintLexNumbers {
public static int LIMIT = 100;
/**
* @param args
*/
public static void main(String[] args) {
boolean[] result = new boolean[LIMIT];
printLex(100, 1, result);
}
public static void printLex(int limit, int n, boolean[] result){
if(n>limit || result[n])
return;
else{
result[n]=true;
System.out.println(n);
printLex(limit, n*10, result);
}
if(n <10 || n%10 == 0){
for(int i=1;i<10;i++){
printLex(limit, n+i, result);
}
}
}
}
Another solution: the idea is to simply write a "lexicographic comparator" for integers and just pass that to the language's built-in sort function (code is F#)
// Given N, print 1 .. N in lexicographic order
// integer lexicographic comparator
let lexicographic_compare num1 num2 =
let inline ( ** ) b p = pown b p
let inline len_minus1 num1 = (num1 |> float |> log10 |> floor |> int)
let inline compare_digits d1 d2 =
if d1 < d2 then -1
elif d1 = d2 then 0
else 1
let rec compare_nums num1 num2 index result =
if result <> 0 || index < 0 then result
else
let d1 = num1 / (10 ** index)
let d2 = num2 / (10 ** index)
let _result = compare_digits d1 d2
let _num1 = num1 - d1 * (10 ** index)
let _num2 = num2 - d2 * (10 ** index)
compare_nums _num1 _num2 (index - 1) _result
let len1 = len_minus1 num1
let len2 = len_minus1 num2
if len1 = len2 then compare_nums num1 num2 len1 0
elif len1 < len2 then
let _num2 = num2 / (10 ** (len2 - len1))
let cmp = compare_nums num1 _num2 len1 0
if cmp = 0 then -1
else cmp
else // len1 > len2
let _num1 = num1 / (10 ** (len1 - len2))
let cmp = compare_nums _num1 num2 len2 0
if cmp = 0 then 1
else cmp
// test module
let print_in_lexicographic_order n =
[|1 .. n|]
|> Array.sortWith lexicographic_compare
|> Array.iter (printf "%d ")
printfn ""
You asked for lexicographic order and don't want to convert it to character strings.
But according to lexicographic order your example shows "one -> ten -> eleven and so on".
Please edit your question : "Lexicographic order" seems pretty misleading. Your example tells what is the question.
Here is the complete and simplest solution in O(n log n) time and O(n) space.
1. Generate all the numbers from 1 to n.
2. Sort the numbers, use lexicographic order while comparing.
3. Print the sorted list.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
public class PrintLexoList {
public void printList(int N){
if(N <= 0)
return;
MyComparator myComp = new MyComparator();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i =1 ; i<N; i++){
list.add(i);
}
Collections.sort(list, myComp);
System.out.println(list.toString());
}
class MyComparator implements Comparator<Integer>{
@Override
public int compare(Integer num1, Integer num2) {
int digitCount1 = getNumDigits(num1);
int digitCount2 = getNumDigits(num2);
if (digitCount1 > digitCount2){
num2 = (int) ((int)num2* Math.pow(10, digitCount1 - digitCount2));
}
else{
num1 = (int) ((int)num1* Math.pow(10, digitCount2 - digitCount1));
}
if(num1 > num2)
return 1;
else if(num1 < num2)
return -1;
else if(digitCount1 > digitCount2)
return 1;
return -1;
}
private int getNumDigits(int number){
int digitCount = 0;
while(number > 0){
number = number/10;
digitCount++;
}
return digitCount;
}
}
public static void main(String[] args) {
System.out.println("Enter a number");
Scanner scanner = new Scanner(System.in);
new PrintLexoList().printList(scanner.nextInt());
}
}
void PrintValuesLexicographically(int n)
{
if(n<=0)
return;
int val, cnt=0;
while(cnt<=n/10)
{
if(cnt==0)
printf("%d\t",cnt);
else
{
printf("%d\t",cnt);
val=cnt*10;
for(int i=1;i<=10;i++)
{
printf("%d\t",val);
val+=1;
}
}
cnt++;
}
printf("\n");
}
There's a part missing the above code. I am sorry for the mistake. Here's the correct version:
while(cnt<=n/10)
{
if(cnt==0)
printf("%d\t",cnt);
else
{
printf("%d\t",cnt);
val=cnt*10;
while(val<n)
{
for(int i=1;i<=10;i++)
{
printf("%d\t",val);
val+=1;
}
val=(val/10 -1)*10;
val=val*10;
}
}
cnt++;
}
import java.util.ArrayList;
public class LexiSort {
public static void main(String[] args){
ArrayList<Integer> al = new ArrayList<Integer>();
int[] a = {};
for(int j=1;j<=9;j++){
for(int k=1;k<25;k++)
{
if(k%10 == j && k/10 == 0){
al.add(k);
}
else if(k/10 == j){
al.add(k);
}
}
}
//System.out.print(al.size());
for(int i=0;i<al.size();i++){
System.out.println(al.get(i));
}
}
}
void printLexico(vector<char> ch, int idx, int len)
{
if(idx == len)
{
print(ch);
return;
}
bool flag = true;
for(int i=0; i<=9; i++)
{
if(i==0 && idx == 0)
continue;
if(flag)
{
print(ch);
flag=false;
}
ch.push_back(i+'0');
printLexico(ch, idx+1, len);
ch.erase(ch.begin() + (int)ch.size()-1);
}
}
int main()
{
vector<char> ch;
printLexico(ch, 0, 2);
return 0;
}
Use DFS
#include <iostream>
using namespace std;
void dfs(int seed, int n){
if(seed > n) return;
cout<<seed<<endl;
for(int i=0; i<=9; i++){
int newseed = seed * 10 + i;
dfs(newseed, n);
}
}
void printlexico(int n){
if(n < 1) return;
for(int i=1; i<=9; i++){
dfs(i, n);
}
}
int main()
{
printlexico(25);
return 0;
}
Use DFS
#include <iostream>
using namespace std;
void dfs(int seed, int n){
if(seed > n) return;
cout<<seed<<endl;
for(int i=0; i<=9; i++){
int newseed = seed * 10 + i;
dfs(newseed, n);
}
}
void printlexico(int n){
if(n < 1) return;
for(int i=1; i<=9; i++){
dfs(i, n);
}
}
int main()
{
printlexico(25);
return 0;
}
private void PrintLexicographicOrder1(int N, int i)
{
if (i <= 0) return;
for (int j = 0; j < 10 && i + j <= N; j++)
{
Console.WriteLine(i+j);
PrintLexicographicOrder1(N, (i + j) * 10);
}
}
public void PrintLexicographicOrder(int N)
{
for (int i = 1; i < 10 && i < N; i++)
{
Console.WriteLine(i);
PrintLexicographicOrder1(N, i * 10);
}
for(int i=1;i<=n;i++)
{ k=i;
printf("%d",i);
while(k<n)
{
k = k*10;
if(k>n) break;
for(m=k;m<10*(i+1);m++)
{
if(m<n)
printf(" %d",m)
else break;
}
break;
}
}
Here's my version
void printLexicOrder(int n)
{
if (n<=0)
return;
std::vector< vector<int> > buckets(10);
int counter = 1;
int jumpVariable=0;
if (n<=9)
{
for (int i = 1; i<=n;++i)
{
cout<<i<<endl;
}
}
else
{
for(int i =1 ; i<=9;++i)
{
cout<<i<<endl;
jumpVariable = i*pow(10,counter);
while(jumpVariable <= n)
{
cout<<jumpVariable++<<endl;
if (jumpVariable%10 == 0)
{
counter+=1;
jumpVariable=i*pow(10,counter);
}
}
counter =1;
}
}
}
in javascript
function printit(n,N)
{
for(var i=n+1; i< n+10; i++)
{
if(i>N)return;
console.log(i);
printit(i*10, N);
}
}
printit(0,25);
What I would do is pretty simple: put those numbers into an array and sort it, but, instead of having the common order operator to make the swap, I'd do my own, which would be like these:
Given two number, X and Y, we will find the smallests 10^powerX > X and 10^powerY > Y. After that, we would lower each of its 'power_i' to check each digit (coming from above back to 1) and check whether the actual value of every digit is the same; if it's not, we already find a difference, and only check who's bigger. If any of the numbers 'end' (by 'end' I mean we have arrived at the units) and we had no answer yet, we simply check who's greater, X or Y. I've done a code to explain better what I wanted.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct DigitSort {
int val;
DigitSort(int N = 0): val(N) {}
bool operator < (const DigitSort &digitSort) const {
int X = val;
int Y = digitSort.val;
long long powerX = 1;
long long powerY = 1;
while (powerX < X) {
powerX *= 10;
}
while (powerY < Y) {
powerY *= 10;
}
powerX /= 10, powerY /= 10;
while (powerX > 0 and powerY > 0) {
int digitX = (X / powerX) % 10;
int digitY = (Y / powerY) % 10;
if (digitX != digitY) {
return digitX < digitY;
}
powerX /= 10;
powerY /= 10;
}
return X < Y;
}
};
void build(int N) {
vector<DigitSort> orderedDigits(N);
for (int i = 1; i <= N; i++) {
orderedDigits[i - 1].val = i;
}
sort(orderedDigits.begin(), orderedDigits.end());
for (int i = 0; i < N; i++) {
printf("%d\n", orderedDigits[i].val);
}
}
int main() {
int N;
scanf("%d", &N);
build(N);
return 0;
}
public class printLexiOrder
{
public static void main(String args[])
{
for(int i=1;i<10;i++)
lexi(i,25);
}
public static void lexi(int x, int num)
{
if(x>num)
return;
System.out.println(x);
for(int i=0;i<9;i++)
{
lexi((x*10+i), num);
}
}
some modification to above cod
public class printLexiOrder
{
public static void main(String args[])
{
int num = 151;
for(int i=1;i<10;i++)
{
System.out.println(i);
lexi(i,num);
}
}
public static void lexi(int x, int num)
{
if(x>num)
return;
for(int i=0;i<9;i++)
{
if((x*10+i)<= num)
System.out.println((x*10+i));
}
lexi((x*10), num);
}
}
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
bool lexicComp(int i, int j)
{
int no_digit_i = log10(i);
int no_digit_j = log10(j);
bool isLess = i < j;
if (no_digit_i > no_digit_j)
{
j = j * pow(10, (no_digit_i - no_digit_j));
if (i == j)
isLess = false;
else
isLess = i < j;
}
else if (no_digit_i < no_digit_j)
{
i = i * pow(10, (no_digit_j - no_digit_i));
if (i == j)
isLess = true;
else
isLess = i < j;
}
return isLess;
}
int main()
{
int maxLimit = 1200;
vector<int> theSet;
for (int i = 0; i < maxLimit; ++i)
{
theSet.push_back(maxLimit - i);
}
sort(theSet.begin(), theSet.end(), lexicComp);
copy(theSet.begin(), theSet.end(), ostream_iterator<int>(cout, " "));
return 0;
}
#include<iostream>
#include<deque>
using namespace std;
int main(){
int upper = 130;
int temp, temp2,temp3;
deque<int> sol;
for (int i = 1; i<10; i++){
cout<<i<<endl;
temp = i*10;
while(temp<upper){
for(int j =0; j<(temp/i); j++){
temp3 = temp+j;
if(temp3>upper) break;
cout<<temp3<<endl;
}
temp *= 10;
};
}
}
#include<iostream>
#include<deque>
using namespace std;
int main(){
int upper = 130;
int temp, temp2,temp3;
deque<int> sol;
for (int i = 1; i<10; i++){
cout<<i<<endl;
temp = i*10;
while(temp<upper){
for(int j =0; j<(temp/i); j++){
temp3 = temp+j;
if(temp3>upper) break;
cout<<temp3<<endl;
}
temp *= 10;
};
}
}
#Run in python 2.7
# break down the number to it digits: units digit, tens digit, hundreds digits and so on.
# From the tens digits, it actually just tens digit multiple by ten for each digit after that.
def printlexicographic(N = 25):
if N == 0:
print N
if N < 10:
for i in range(N):
print N
else:
digit = N//10
r = N%(digit*10)
for i in range(1,digit +1):
print i
for j in xrange(10):
if (i == digit and j == r+1):
break
print i*10 + j
for i in xrange(i+1,10):
print i
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void printt(int i, int n ){
if( i > n ) return;
for( int j = 0; j<10;++j){
if( i <= n)
System.out.print(i + " ");
printt(i*10,n);
if( i + 1 == 10)
break;
++i;
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
printt(1,25);
}
}
import math
def sigfig(n, offset):
return (n / 10 ** (int(math.log(n)/math.log(10))-offset)) % 10
def sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
less, more = [], []
for i in range(len(arr)-1):
#less, default, more = -1, 0, 1
state = 0
n = 0
while state == 0:
result = sigfig(pivot, n) - sigfig(arr[i], n)
if result > 0:
state = -1
elif result < 0:
state = 1
else:
if arr[i] < pivot:
state = -1
elif arr[i] > pivot:
state = 1
n += 1
if state == -1:
less.append(arr[i])
else:
more.append(arr[i])
return sort(less) + [arr[-1]] + sort(more)
print sort([25, 1, 2, 13, 10, 11, 65, 22])
what about this one
using System;
namespace Helloworld
{
class Program
{
static void Main(string[] args)
{
int N = 250;
PrintLexicographicRes(1,N);
}
public static void PrintLexicographicRes(int i, int N)
{
Console.WriteLine(i);
if(i*10 <= N)
{
PrintLexicographicRes(i*10, N);
}
int j = i + 1;
if(j <= N && j%10 != 0)
{
PrintLexicographicRes(j, N);
}
}
}
}
Complexity of this is O(N) + O(1).
Here is a simple solution using depth first traversal of this generic tree..
import java.util.*;
public class LexicographicalSort {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
for (int i = 1; i <= 9; i++) {
dfs(i, n);
}
}
public static void dfs(int i, int n) {
if (i > n) {
return;
}
System.out.println(i);
for (int j = 0; j < 10; j++) {
dfs((i * 10) + j, n);
}
}
}
/* I cheated by using a map and a list. There's probably a more efficient way to do this, but I ain't a genius to figure that sh*t out. */
static void printLexicographicOrder(int n){
Map<Integer, ArrayList<Integer>> map = new LinkedHashMap<Integer, ArrayList<Integer>>();
int divisor = 10;
int key;
ArrayList<Integer> value;
for(int i = 1; i <= n; i++){
if( (i / divisor) > 9){
divisor *= 10;
}
if( (i % divisor) == i){
key = i;
value = new ArrayList<Integer>();
} else {
key = i / divisor;
value = map.get(key);
}
value.add(i);
map.put(key, value);
}
for(int i = 1; i <= map.size(); i++){
value = map.get(i);
for(Integer k: value)
System.out.println(k);
}
}
Goddamnit. I just realized that you can just initialize the divisor to 1 and the map before the main loop. So this little refactor will get rid of the if-else in the main loop.
int divisor = 1;
// initialize map
for(int i = 1; i <= n; i++){
value = new ArrayList<Integer>();
map.put(i, value);
}
for(int i = 1; i <= n; i++){
if( (i / divisor) > 9){
divisor *= 10;
}
key = i / divisor;
value = map.get(key);
value.add(i);
map.put(key, value);
}
There is an easier solution:
- Anonymous October 04, 2013void Test(int N, int k)
{
if (k > N) {return;}
for(int i = 0; i<10; i++)
{
if (k <= N)
{
cout<<k<<endl;
k *= 10;
Test(N, k);
k /= 10;
k++;
if (k%10 == 0) return;
}
}
}
To call this use Test(25, 1), for example