Engaged Employer

Interview

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

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

3

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
5

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)

Srikant Aggarwal on Oct 24, 2014
0

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

Himanshu Sharma on Apr 23, 2015
0

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