## Interview Question

## Interview Answer

4 Answers

For this question you can keep an array of 0-9 Start traversing from back, if any bucket before that is fill that is you encountered an element smaller than it then put that element in current position and place all remaning elements in decreasing order. For example say the no is 10987598023 start from 3 A = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] array after 3 becomes [0, 0, 0, 1, 0,..] then when u see 2, you see that no smaller element. Array becomes [0, 0, 1, 1, 0,...] now when u reach at 0, again no smaller element, so array becomes [1, 0, 1, 1, 0, ...] Now when u reach 8 the just smaller element is 3 So, replace 8 with 3 and the array becomes [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0] So the number just smaller is 10987593820. O(n)

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) < a.charAt(i - 1)) { System.out.println(a.substring(0, i - 1) + getVal(a.substring(i - 1, a.length()))); return; } else { continue; } } } private static String getVal(String substring) { if (substring.length() == 1) { return substring; } char last = substring.charAt(substring.length() - 1); String b = "" + last; char[] a = substring.substring(0, substring.length() - 1).toCharArray(); Arrays.sort(a); for (int i = a.length - 1; i >= 0; i--) { b = b + String.valueOf(a[i]); } return b; } }

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)

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

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