Bloomberg LP Interview Question for Financial Software Developers


Country: United States
Interview Type: In-Person




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

There is an easier solution:
void 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

- Anonymous October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good one!

- Laxman October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

like this one. nice and neat!

- Anonymous February 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Jose November 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Jose November 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why the statement

if (k%10 == 0) return;

- Viraj January 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- evi March 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

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

- James October 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I like this one. You are hired :D

- iuliua October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

this code outputs 11 before 100 --- this is not correct

- Oleg January 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you give an example

- senthil1216 October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I've edited the question to provide an example.

- Abhi October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- siva October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

* As per my understanding

- siva October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The only thing I can think is divide numbers by multiples of 10 and then compare each result by implementing some kind of compareTO

- Uriel Rodriguez October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- siva October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

~

- maillist.danielyin October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The algo will be like this:

Step 1: find out the no of digits(say n)

Step 2:
for i=1 to n and digit is 1
a. i=1, print 1
b. i=2, print 10-19(next 10)
c. i=3, print 100-199(next 10^(i-1))..

step 3: repeat the step 2 for digit 2 to 9 as well..
This will give us the proper result.

- meiftikaralam October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def print_numbers(k, N):
    for i in range (0, 10):
        if (k+i)>N:
            break
        print (k+i)
        print_numbers((k+i)*10, N)

if __name__ == "__main__":
    try:
        N=int(raw_input('N = '))
    except ValueError:
        print "Not a number"

    for k in range (1, 10):
        if k>N:
            break
        print k
        print_numbers(k*10, N)

- In Python... October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var limit = N;
var lexi = function(input)
{
	for (var i = 0; i< (input == 1 ? 9 : 10); i++)
	{
		var output = input + i;
		
		if (output <= limit)
		{
			console.log(output):
			lexi(output * 10);
		}
	}
}
lexi(1);

- redseiko October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- arunachalam.t October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

MSD radix sort.

- tsarapin October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

}

- snigda October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C#:

private static void recurse(int value)
        {
            int max;
            if ((n - value) >= 9)
                max = ((value / 10) * 10) + 9;
            else
                max = ((value / 10) * 10) + n - value;

            for(int i = value; i <= max; i++){
                Console.WriteLine("{0}",i);

                if (i * 10 <= n && i != 0)
                {
                    recurse(i * 10);
                }
            }
        }

- brennahan October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ""

- Alpha October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Psycho October 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// I just write the solution in JavaScript
function list(n, m) {
var i;
for (i = n; i <= m && i < Math.floor((n + 10) / 10) * 10; i++) {
console.log(i);
if (i <= m) {
list(i * 10, m);
}
}
}
list(1, 25);

- Ahmad Masykur October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Subby October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void numsInLexOrder( int limit, int sofar = 0 )
{
	for ( int d=(sofar ? 0 : 1); d<=9; d++ )
	{
		int next = sofar * 10 + d;
		if ( next <= limit )
		{
			cout << next << "\n";
			numsInLexOrder( limit, next );
		}
		else
			break;
	}
}

- md October 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}






}
}

- Aman Mahajan October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code works but the code complexity is O(n^2)

- Alex October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- pagalguy October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Call this function func(1,N) and it should print all numbers in lexicographic order
bool func(int prn, int max)
{
	if(prn>max)
	{
		return false;
	}
	cout<<prn;
	for(int i = 0; i <= 9; i++)
	{
		if(!func(prn*10+i, max))
		{
			break;
		}
	}
	return true;
}

- Harsh October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use radix from msd to lsd and with each radix, put bucket according to the msd recently sorted.

- Anonymous October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- usca80 October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A very easy Solution:

Can be used for general case
For N=25:

void printLexi(int N)
{
int i=1,j=0,k=10;
while(k<N)
{
cout<<i;
j++;
while(k/10 == i){cout<<k; j++ ; k++; }
i++;
}
}

- Birbal October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A comparer for std::sort... Just call std::sort with it.

bool cmp(int a, int b) {
	double x = a, y = b;
	/* align x and y */
	while(x / 10 >= 1)
		x /= 10;
	while(y / 10 >= 1)
		y /= 10;
	/* distinguish N, N0 and N00... */
	if(x == y)
		return a < b ? true : false;
	return x < y ? true : false;
}

- DumbMallard October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void LexNum(int n)
{
	bool em = false;
    for (int i = 1, i < 9; i++)
	{
		em =false;
	   k = i;
	   cout << k << " ";
	   while (k < n)
	   {
		k*=10;
		for (int j = 0; j < k-1, em != true; j++)
		{
			int m = k+j;
			if (m < n) cout << m << " ";
			else 
			{
			  em = true;
			}
		}
		if (em == true) 
			break;
	   }
	}
}

- Anonymous November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void Print(int p, int n){
if(p > n) return;
cout << p << endl;
for(int i = 0; i <= 9; ++i){
if(p*10 + i <= n) Print(p*10+i,n);
}
if(p < 9) Print(p+1,n);
}

- jeffnju November 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void PrintNumsInLexicographicOrder(int n)
        {
            int k;
            for (int i = 1; i <= 9; i++)
            {
                k = i;
                Console.WriteLine(k);
                if (k * 10 <= n)
                {
                    k *= 10;
                }
                else
                {
                    continue;
                }

                for (int j = 0; j <= 9; j++)
                {
                    if (k + j <= n)
                    {
                        Console.WriteLine(k + j);
                    }
                }
            }

}

- praveen December 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void PrintNumsInLexicographicOrder(int n)
        {
            int k;
            for (int i = 1; i <= 9; i++)
            {
                k = i;
                Console.WriteLine(k);
                if (k * 10 <= n)
                {
                    k *= 10;
                }
                else
                {
                    continue;
                }

                for (int j = 0; j <= 9; j++)
                {
                    if (k + j <= n)
                    {
                        Console.WriteLine(k + j);
                    }
                }
            }

}

- praveen December 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Deric December 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

GOOD ONE SIMPLE

- Roshan December 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Alok December 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh there is no need for that vector of vectors. I was trying something else earlier.
Apologies

- alok.theanomaly December 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops.

function printit(n,N)
{
	for(var i=n; i< n+10; i++)
	{
		if(i>N)return;
		console.log(i);
		printit(i*10, N);
		
	}
}
printit(1,25);

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

public static void printLexi(int n)
{
int x=0;
for(int i=1;i<=9;i++)
{
x=i;
System.out.println(x);
x *=10;
for(int z = 0;z<10;z++)
{
if((x<=n))
{
System.out.println(x);
x++;
}
else
break;
}
}
}

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

jh

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

void outVal(int target, int cur, vector<int>& res)
{
if(cur>target)
return;

res.push_back(cur);

for(int i=0; i<=9; i++)
outVal(target, cur*10+i, res);
}

vector<int> outVal(int target)
{
vector<int> res;

for(int i=1; i<9; i++)
outVal(target, i, res);

return res;
}

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

public class lexicographicOrdering {

	public static void main(String[] args) {
		int N = 25, i =0 , j =0;
		for(i=1;i<=(N/10);i++){
			System.out.println(i);
			for(j=10*i;(j<(10*(i+1)))&&j<=N;j++){
				System.out.println(j);
			}
		}
	}
}

- karpagaganesh March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Renato Parente March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function lex(n) {
function print(m) {
if (m > n) {
return;
}
console.log(m);
for (var i=0; i<=9; i++) {
print(+(m+''+i));
}
}
for (var i=1; i<=9; i++) {
print(i);
}
}
lex(120);

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

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

- vish1310 April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vish1310 April 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

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

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

}

- maxx March 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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

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

public static void printLexographicalOrder(int num, int n) {
if (n > num)
return;
else {
System.out.println(n);
printLexographicalOrder(num, n * 10);
if (( (n + 1) / 10) % 10 != (n / 10) % 10) {
return;
} else {
printLexographicalOrder(num, n + 1);
}
}
}

- Shivam Maharshi October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{ public static void printLexographicalOrder(int num, int n) {
if (n > num)
return;
else {
System.out.println(n);
printLexographicalOrder(num, n * 10);
if (( (n + 1) / 10) % 10 != (n / 10) % 10) {
return;
} else {
printLexographicalOrder(num, n + 1);
}
}
}
}

- Shivam Maharshi October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 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);
	}
}

- abhishek893.rai June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- abhishek893.rai June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sonesh April 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/* 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);
	}
}

- Jackmerius Tacktheritrix October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Jackmerius Tacktheritrix October 04, 2013 | Flag


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