Facebook Interview Question: Given a number n, find the la... | Glassdoor

Interview Question

Software Engineering Intern Interview

Given a number n, find the largest number just smaller than

  n that can be formed using the same digits as n.
Answer

Interview Answer

17 Answers

5

I gave the obvious solution of generating all permutations of the number n and ordering them, find the one that occurs before n.
Then I figured out that if I sort the digits from a certain point onwards into increasing order, it can help me build up to the solution. I proposed my algorithm and we began doing some really sort of pseudofunctional java code that solved the problem. After the end of that, I analyzed my solution and found it to run in O(n^2) time utilizing a bucket sort for the sorting operation. This was a big improvement from O(n!) but still not optimum. He explained the optimum solution found a pivot at which point it sorted the digits, running in O(n).

Interview Candidate on Apr 17, 2014

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

2

package interview;

import java.util.Arrays;
import java.util.Scanner;

public class LargestNumberBeforN {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String a = sc.next();

        for (int i = a.length() - 1; i > 0; i--) {
            if (a.charAt(i) = 0; i--) {
            b = b + String.valueOf(a[i]);
        }
        return b;
    }
}

Himanshu Sharma on Apr 23, 2015
1

put each digit into a vector of ints. iterating from the back, if the character at the index is smaller than any numbers preceding it, swap. this would be O(digits in the number ^ 2) but because integer size is limited to a constant, this is O(1)

Mitch Gildenberg on Aug 25, 2015
0

i dont understand how you guys are getting char and substring from input int n?

david hurng on Oct 6, 2015
1

Here is an actual implementation based on Srikant Aggarwal's description.

'''
QUESTION:
Given a number n, find the largest number just smaller than
n that can be formed using the same digits as n.

SOLUTION APPROACH:
* Find a part that can actually be rearranged into smaller number
    * 1123 can't be, because each number is in dictionary order
    * 8123 could be, and you do so by replacing the largest number with the next largest number,
        then the rest of the numbers in descending order from the left e.g. 3821
* Look for a chunk to arrange from the right since it'll have the least impact
'''

def find_next_largest(n):
    buckets = [0 for i in range(10)] #where index is the digit and the value is the number of occurrences
    num_str = str(n)
    for index in range(len(num_str)-1, -1, -1): #start from the right
        digit = int(num_str[index]) #get the a digit from the right
        buckets[digit] += 1 #tally the digit's occurrence

        #check if there are smaller digits
        for i in range(digit-1,-1,-1):
            if buckets[i] != 0: #if there is one, then get ready for the transformation
                buckets[digit] -=1 #update the occurrences
                buckets[i] -= 1
                chunk = str(i) + str(digit) #first two character of chunk
                while i > -1:
                    if buckets[i] != 0:
                        chunk += str(i)*buckets[i]
                    i -= 1
                return num_str[:index] + chunk
    return None

print find_next_largest('10987593820')

Victor Lin on Feb 6, 2016
3

Approach. Traverse from the last till u get a number that is greater than previous number..
Put last digit before this new number and the rest of digits in reverse order after this greater number.

#include
#include
using namespace std;
int main()
{
        int n,newN,newNumber=0,old=9;
        cin>>n;
        int numberToAdd=n%10;
        int i=0;
        n=n/10;
        while(n>0)
        {
                newN=n%10;
                if(old

Anonymous on Mar 3, 2016
0

In the above program for the edge case we put flag=0 initially and print Cannot get smaller number in case there is no smaller number.
Also instead of old= , initially old = numberToAdd.

Anonymous on Mar 3, 2016
0

I used recursion:

    public static int smaller(int n){
        if(n d0) return n / 100 * 100 + d0 * 10 + d1;
        return smaller(n2) * 10 + d0;
    }

Chenqian Lin on Oct 1, 2016
1

My answer did not show properly:

    public static int smaller(int n){
        if(n less than 10) return n;
        int d0 = n % 10, n2 = n / 10, d1 = n2 % 10;
        if(d1 greater than d0) return n / 100 * 100 + d0 * 10 + d1;
        return smaller(n2) * 10 + d0;
    }

Chenqian Lin on Oct 1, 2016
0

It doesn't work, please ignore it

This one works:

    public static int smaller(int n){
        int i = 1;
        int result = 0;
        while(i <= n / 10 && n / i / 10 % 10<= n / i % 10)
            i *= 10;
        if(i > n / 10) return n;
        int d = n / i / 10 % 10;
        int j, x;
        for(j = 1; (x = n / j % 10) >= d; j *= 10)
            result = result * 10 + x;
        result += j * x;
        result = result * 10 + d;
        for(j *= 10; j <= i; j *= 10)
            result = result * 10 + n / j % 10;
        return result + n / i / 100 * i * 100;
    }

Chenqian Lin on Oct 1, 2016
0

# Python implementation

def getSmallerNumWithSameDigits(num):

    strNum = list(str(num))
    endI = len(strNum)-1
    endDigit = strNum[endI]

    # Walk backwards through digits
    for i in range(len(strNum) - 1, -1, -1):
        digit = strNum[i]

        # If the digit is greater than the end
        if digit > endDigit:

            # Swap them
            strNum[endI], strNum[i] = strNum[i], strNum[endI]
            break

    # Put back into int form
    return int(''.join(strNum))

print getSmallerNumWithSameDigits(912345678)

Josh on Dec 7, 2016
0

Python solution: I followed my first instinct, which was to use strings. It may be a bit weird, but it gets the job done in O(n) time, I think.

def findLargestSameDigits(num):
    str_num = str(num)
    ret_str = ""
    for i in range(len(str_num)-1, 0, -1):
        if int(str_num[i]) < int(str_num[i-1]):
            ret_str = "".join([str_num[0:i-1], str_num[i], str_num[i-1], str_num[i+1:]])
            return int(ret_str)
    return None

Anonymous on Jan 19, 2017
0

Ok, this one is correct. It is in O(n^2) time, so not optimal. Sorry about the above one!

def findLargestSameDigits(num):
    str_num = list(str(num))
    for i in range(len(str_num)-1, 0, -1):
        for j in range(i-1, -1, -1):
            if int(str_num[i]) < int(str_num[j]):
                str_num[i], str_num[j] = str_num[j], str_num[i]
                str_num = str_num[:j+1] + sorted(str_num[j+1:], reverse=True)
                return int("".join(str_num))
    return None

Anonymous on Jan 19, 2017
1

Check the analysis: https://goo.gl/un8Jl1

jim on Jan 19, 2017
0

n=15424679

a=[int(x) for x in str(n)]
for i in range(len(a)-1,0,-1):
    if(a[i]

Suthagar on Mar 6, 2017
0

That is similar to the question previous permutation

Jason on Mar 8, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.