Interview Question
Software Engineering Intern Interview

MetaGiven 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(i1, 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 backandforth 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 realworld practice and guidance. prepfully.com/practiceinterviews
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[i1]): ret_str = "".join([str_num[0:i1], str_num[i], str_num[i1], 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.