Interview Question

Software Engineering Intern Interview

-

Meta

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

AnswerAdd Tags

Interview Answers

16 Answers

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

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

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

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

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

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

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

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

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

0

That is similar to the question previous permutation

Jason on

0

#include #include #include #include #include using namespace std; int FindLargestSmallerNum (int n) { vector digits; int digit = 0; int new_num = n; while (n > 0) { digit = n % 10; digits.push_back(digit); n = (n - digit) / 10; } for (unsigned int i = 0; i < digits.size(); i++) { for (unsigned int k = i + 1; k < digits.size(); k++) { if (digits[i] < digits[k]) { new_num = 0; int tmp = digits[i]; digits[i] = digits[k]; digits[k] = tmp; for (unsigned int j = 0; j < digits.size(); j++) { new_num += pow(10, j) * digits[j]; } return new_num; } if (digits[i] == digits[k]) { break; } } } return new_num; } int main() { for (int n = 0; n < 481; n++) cout << "The Largest Smaller Num of: " << n << " Is: " << FindLargestSmallerNum(n) << "\n"; return 0; }

elad on

0

The key in generic questions like this, is to make sure to cover the fundamentals. There's usually a back-and-forth with the interviewer. Might be worth doing a mock interview with one of the Facebook Software Engineer Intern experts on Prepfully? Really helps to get some real-world practice and guidance. prepfully.com/practice-interviews

Anonymous on

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

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

0

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

david hurng on

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

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.