View All num of num See all Photos Facebook www.facebook.com Engaged Employer Overview Reviews Salaries Interviews Jobs Photos Benefits 927 Reviews 2.5k Salaries 1.4k Interviews 1.1k Jobs Follow Add Review or Salary Follow Add Review or Salary Interview Question Software Engineering Intern Interview Facebook Given a number n, find the largest number just smaller than n that can be formed using the same digits as n. Tags: See more , See less 8 Answer Add Tags Answer Interview Answer 2 Answers ▲ 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 ▲ 4 ▼ For this question you can keep an array of 0-9Start 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 10987598023start from 3A = [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 3So, 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 Interviews > Software Engineering Intern > Facebook Add Answers or Comments To comment on this, Sign In or Sign Up.