## Google Interview Question for Software Engineer / Developers

Team: Knowledge Graph
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
12
of 12 vote

- Get digits of N in positional order
- Find first digit M that is not in ascending order (searching from right to left)
- If all digits are in ascending order from right to left, then return N
- Find the smallest digit P that is to the right of M and is also larger than M
- Swap positions of M and P
- Sort digits after original position of M in ascending order from left to right
- Build and return from digits

``````public int NextLargest(int n)
{
byte[] digits = new byte[10];

int length = 0;
while (n > 0)
{
digits[length++] = (byte)(n % 10);
n /= 10;
}

Array.Reverse(digits, 0, length);

int swapPos = -1;
for (int i = length - 2; (i >= 0) && (swapPos == -1); i--)
if (digits[i] < digits[i + 1]) swapPos = i;

if (swapPos == -1) return n;

int swapPos2 = -1;
int min = int.MaxValue;
for (int i = swapPos + 1; i < length; i++)
{
if ((digits[i] > digits[swapPos]) && (digits[i] < min))
{
min = digits[i];
swapPos2 = i;
}
}

byte bTemp = digits[swapPos];
digits[swapPos] = digits[swapPos2];
digits[swapPos2] = bTemp;

Array.Sort(digits, swapPos + 1, length - swapPos - 1);

for (int i = 0; i < length; i++)
n = n * 10 + digits[i];

return n;
}``````

Comment hidden because of low score. Click to expand.
5

Array.sort is O(nLogN). To keep the total time complexity linear, just reverse the remaining digits as they are already sorted in descending manner from left to right.

Comment hidden because of low score. Click to expand.
1
of 1 vote

And we don't have to search for minimum value on the right side of our found first_not_in_ascending_order digit. It would allways be rightmost digit. Because they are actually arranged in ascending order from right to left:)

Comment hidden because of low score. Click to expand.
0

I think the time complexity is O(log N)

Proof:
For Integer N , there are max of logN+1 digits , let K= log N
so,
1. For traversing over digits : O(K)
2. We know the digits range only from 0-9 , so we'll use bucket sort, radix sort algos instead of heap -r quick sort , hence for sorting O(K)

over all : O(K) => O(log N)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Do you really need this step "Sort digits after original position of M in ascending order from left to right " The numbers should already be sorted there

Comment hidden because of low score. Click to expand.
2
of 2 vote

very similar to leetcode Next Permutation

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````public class Solution {

public static int nextHigherPermutation(int number) {
int[] num = numberToArray(number);
nextPermutation(num);
int nextPermNumber = arrayToNumber(num);

return Math.max(number, nextPermNumber);

}

private static int arrayToNumber(int[] num) {
int number = 0;
int p = 10;

for (int i = 0; i < num.length; i++) {
number = number * p + num[i];
}

return number;
}

private static int[] numberToArray(int number) {
String numberString = String.valueOf(number);
int digits = numberString.length();
int[] num = new int[digits];

int i = 0;

for (char digit: numberString.toCharArray()){
num[i] = digit - '0';
i++;
}

return num;
}

public static void nextPermutation(int[] num) {

int i = num.length - 2;
boolean permFound = false;

while (i >= 0) {

int j = i + 1;
while (j < num.length) {
if (num[i] < num[j]) {
swap(num, i, j);
permFound = true;
break;
}
j++;
}

if (permFound)
break;

rotateLeft(num, i);
i--;
}

}

private static void rotateLeft(int[] num, int from) {

int temp = num[from];

for (int i = from; i < num.length - 1; i++) {
num[i] = num[i + 1];
}

num[num.length - 1] = temp;

}

private static void swap(int[] num, int indxi, int indxj) {
int temp = num[indxi];
num[indxi] = num[indxj];
num[indxj] = temp;
}

/**
* Example 1 : if num = 25468, o/p = 25486
* Example 2 : if num = 21765, o/p = 25167
* Example 3 : If num = 54321, o/p = 54321
*
* @param args
*/
public static void main(String[] args) {
System.out.println(nextHigherPermutation(25468));
System.out.println(nextHigherPermutation(21765));
System.out.println(nextHigherPermutation(54321));
}

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

//O(n) time complexity

``````public int nextHighNumber(int number){
int[] num = numberToArray(number);
int i = 0;
for(i = 0 ; i < num.length-1; i++){
if(num[i] > num[i+1]) break;
}
if(i == num.length-1) {
System.out.println("No number can be formed");
return 0;
}
int numi = num[i+1];
num[i+1] = num[0];
int temp = 0;
for(int j = 0; j <= i/2; j++){
temp = num[j];
num[j]=num[i-j];
num[i-j] = temp;
}
num[i]=numi;
return arrayToNumber(num);
}``````

``````public int[] numberToArray(int number){
System.out.println("Original number: " + number);
int[] num = new int[getNumberLength(number)];
int i = 0;
while(number > 0){
num[i] = number % 10;
number = number / 10;
System.out.print(num[i]);
i++;
}
System.out.println("\n" + "Converted number to array");
return num;
}

public int arrayToNumber(int[] num){
int number = 0;
for(int i = 0; i < num.length; i++){
number = number + num[i] * (int) Math.pow(10, i);
}
System.out.println("\n" + "Converted Array to number");
return number;
}

public int getNumberLength(int number){
int length = 0;
while(number > 0){
length++;
number = number / 10;
}
System.out.println("The length of number is: " + length);
return length;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution:
# @param num, a list of integer
# @return a list of integer
def nextPermutation(self, num):
length = len(num)
if not num:
return []
i = length - 1

# find the last item which has at least one
# item that is greate than it and behind it.
# the item is num[j], the item that greater than
# it and behind it is mun[i]
max_j = -1
max_j_i = None
while i >= 0:
j = i - 1
while j >= 0:
if num[j] < num[i]:
if j > max_j:
max_j = j
max_j_i = i
break
j -= 1
i -= 1

j = max_j
i = max_j_i
if max_j != -1:
# it is not a descending array
num[i], num[j] = num[j], num[i]
for k in range(j + 1, length):
for l in range(k, length):
if num[k] > num[l]:
num[k], num[l] = num[l], num[k]
else:
# it is a descending array
return num

return num``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class getNextHigherNumber {

public static void main(String args[])throws IOException

{
try{
Scanner sc = new Scanner(System.in);
int number = sc.nextInt();
getHigher(number);
}
catch(java.util.InputMismatchException e)
{
System.out.println("Value is too big: "+ e.getMessage());
}

}

public static void getHigher(int number)
{
int num=number;
int len=0;
while(num>0)
{
len++;
num= num/10;
}
num=number;
int[] a = new int[len];
for(int i=a.length-1; i>=0; i--)
{
a[i]=num%10;
num=num/10;
}
int[] secondHalf = new int[a.length];
secondHalf[a.length-1]=a[a.length-1];
int i;
for(i=a.length-2; i>=0; i--)
{
if(a[i]>secondHalf[i+1]) //insert in the array
{
secondHalf[i]=a[i];
Arrays.sort(secondHalf);

}
else
{
secondHalf[i]=a[i];
int t = secondHalf[i];
secondHalf[i] = secondHalf[i+1];
secondHalf[i+1] = t;
break;
}
}
if(i-1>=0){
for(int j=i-1; j>=0; j--)
{
secondHalf[j]=a[j];
}
}
for(int j=0; j<secondHalf.length; j++)
{
System.out.print(secondHalf[j]); //print the next higher number
}
System.out.println();
}

}``````

Comment hidden because of low score. Click to expand.
0

Come on, dude. 1. you use additional space; 2, the complexity is log linear, because no need to sort for every descending order!

Comment hidden because of low score. Click to expand.
0
of 0 vote

integer to array, then scan from the last digit, if a[i] < a[i + 1] continue, until you find a pos to stop, if not found, then return the original number (cannot swap), else do:

let the number to be swapped is x = a[i + 1] (which is smaller than a[i])
find the position that a[p] > x (p is from 0 to i - 1, use binary search)
swap the a[p + 1] and x;
reverse the order of elements from 0 to i;
convert the array to integer and return it.

``````int* toarray(int x, int& size)
{
int n = x;
int l = 0;
while (n > 0)
{
n /= 10;
++l;
}

int* a = new int[l];
int p = 0;
n = x;
while (n > 0)
{
a[p] = n % 10;
n /= 10;
++p;
}
size = l;

return a;
}

int find(int x, int* a, int s, int e)
{
if (s == e)
{
if (a[s] < x)
return s;
else
return s - 1;
}

int mid = (s + e) / 2;

if (a[mid] > x)
return find(x, a, 0, mid - 1);
else
return find(x, a, mid + 1, e);
}

int toint(int* a, int p, int size)
{
int result = 0;

for (int i = size - 1; i > p; --i)
{
result = result * 10 + a[i];
}

for (int i = 0; i <= p; ++i)
{
result = result * 10 + a[i];
}

return result;
}

int nextbig(int n)
{
int size;
int *a = toarray(n, size);

for (int i = 0; i < size - 1; ++i)
{
if (a[i] > a[i + 1])
{
// swap a[i + 1] to the proper position
int pos = find(a[i + 1], a, 0, i) + 1;
a[i + 1] ^= a[pos];
a[pos] ^= a[i + 1];
a[i + 1] ^= a[pos];
}
}
return n;
}

int _tmain(int argc, _TCHAR* argv[])
{
int x = 54321;
std::cout << nextbig(x) << "\n";
getchar();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>

int main()
{
int n,i,j,k,ar[5],num,key,p;
printf("Enter no.: ");
scanf("%d",&n);
i=0;
p=n;
while(n>0) //seperating each digit
{ //and storing it in array.
ar[i]=n%10;
n=n/10;
i++;
}
num=ar[i-1]; //using last digit in num bcz num must be started with same digit i.e.
for(j=1;j<i-1;j++) //if number is 21567 then higher will be started from 2 and will be 25167
{
key=ar[j]; //appplying insertion sort on digits stored in array except last digit
k=j-1;
while((k>=0)&&ar[k]>key)
{
ar[k+1]=ar[k];
k=k-1;
ar[k+1]=key;
}
}
for(k=0;k<i-1;k++) //finding the smallest larger number from last digit
{ //i.e larger no than 2 in our example is 5 which is smallest
if(ar[k]>num) //of all larger no's.
{
j=k;
key=ar[k];
break;
}
}
num=num*10+key; //converting digits in number
k=0;
while(k<i-1)
{
if(k==j) //we need not to take that digit which is already has been used
{ //so if that location comes, just increment in k location
k++;
}
num=num*10+ar[k];
k++;
}
printf("\nThe next higher number of %d is %d",p,num);
getch();
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NextHighestNumber {

public static void main(String args[]) {
System.out.println(nextHighestNumber(25468));
System.out.println(nextHighestNumber(21765));
System.out.println(nextHighestNumber(54321));
}

public static int nextHighestNumber(int number) {
List<Integer> result = new ArrayList<Integer>();
createPermutations("", String.valueOf(number), result);
Collections.sort(result);
int index = result.indexOf(number);
return result.get(index == result.size() - 1 ? index : index + 1);
}

public static void createPermutations(String prefix, String str,
List<Integer> result) {
if (str.length() == 0) {
}
for (int i = 0; i < str.length(); i++) {
createPermutations(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1), result);
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````1)Break the number into an array of digits
2)Start using insertion sort from right to left
3)When you insert a digit(using insertion sort) if there is a digit on its right, put it in the original position of the digit that was being inserted. Stop
4)Recombine the digits to the number``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class FindNumber {

public static void main(String argv[]) {
System.out.println(findGreater(25468));
System.out.println(findGreater(21765));
System.out.println(findGreater(54321));
}

private static int findGreater(int i) {
ArrayList<Integer> digits = new ArrayList<Integer>(); //Contains digits in the ascending order

//Break number into digits.
while (i > 0) {
i /= 10;
}

for (int candidateDigit = 1; candidateDigit < digits.size(); candidateDigit++) {
if (digits.get(candidateDigit) < digits.get(candidateDigit - 1)) {

//We found digits[candidateDigit] breaks the ascending order.
//Swap it with smallest possible digit in the tail array [0, candidateDigit],
//in such way so after that, the tail array will be still in ascending order
for (int toSwap = 0; i < candidateDigit; i++) {
if (digits.get(toSwap) > digits.get(candidateDigit)) {
//digits[toSwap+1]>=digits[candidateDigit]>= digits[toSwap-1],
// so array is still in order
swap(digits, candidateDigit, toSwap);
break;
}
}

//Reverse the tail array
for (int index1 = 0; ; index1++) {
int index2 = candidateDigit - 1 - index1;
if (index1 < index2) swap(digits, index1, index2);
else break; //We are done reversing, indexes crossed
}

//We are done modifying the number, break out of the cycle
break;
}
}

//Assemble the number back
int result = 0;
for (int c = digits.size() - 1; c >= 0; c--) {
result *= 10;
result += digits.get(c);
}

return result;
}

private static void swap(ArrayList<Integer> digits, int index1, int index2) {
Integer swap = digits.get(index1);
digits.set(index1, digits.get(index2));
digits.set(index2, swap);
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Pretty sure some simple thing like this in Ruby would work.

``````ARGV.each do |a|
nums = a.to_s.chars.map(&:to_i)
i = nums.length - 1
last = nums.last
nums.reverse_each {|n| (last > n) ? break : i-=1 }
nums[-1] = nums[i]
nums[i] = last
nums = nums[0..i] + nums[i+1..-1].sort unless i == -1
puts nums.map(&:to_s).join.to_i
end``````

Comment hidden because of low score. Click to expand.
0

And a slightly longer version in Python

``````import sys

for arg in sys.argv[1:]:
nums = map(int,list(str(arg)))
i = len(nums) - 1
last = nums[-1]
for n in reversed(nums):
if last > n:
break
i-=1
nums[-1] = nums[i]
nums[i] = last
if not i == -1:
nums = nums[:i+1] + sorted(nums[i+1:])
print ''.join(map(str,nums))``````

Comment hidden because of low score. Click to expand.
0

And finally a kind of ridiculous one line ruby script with no semi-colons

``ARGV.each {|a| lambda {|b| puts b.reverse.each_with_index.inject([]){|ary, (elem, idx)| b.last > elem && ary.length < b.length ? (ary[0] = elem) && ary.sort!.reverse! && ary << b.last && ary+=b[0..b.length-idx-2].reverse : ary.length < b.length ? ary << elem : ary }.reverse.map(&:to_s).join("")}.call(a.to_s.chars.map(&:to_i))}``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.*;

public class Qs4869907900530688 {
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);

int length = number.length();
if (length > 0) {
char ch = number.charAt(length-1);
int exchangePosition = -1;
for (int i = length-2; i >= 0; --i) {
if (ch > number.charAt(i)) {
exchangePosition = i;
break;
}
}
if (exchangePosition == -1)
out.println(number);
else {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < exchangePosition; ++i)
sb.append(number.charAt(i));
sb.append(ch);
sb.append(number.charAt(exchangePosition));
for (int i = length-2; i > exchangePosition; --i)
sb.append(number.charAt(i));
out.println(sb.toString());
}
}

out.flush();
out.close();

System.exit(0);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int nextPermutation(int n){
int result, size, prev, next;
string number;
stringstream ss;
string::iterator itr;

// Converts n to char array (string)
ss << n;
ss >> number;

// Clears stream for next use
ss.str("");
ss.clear();

next = number.length()-1;
prev = next; 			  // Starting point, usually equals next-1
itr = number.end();

while(next > -1){

// Sorts the right half
sort(itr, number.end());
itr--;

if(number[next] < number[prev]){

// Swaps numbers
number[prev] = number[prev] ^ number[next];
number[next] = number[prev] ^ number[next];
number[prev] = number[prev] ^ number[next];

// Converts back to int
ss << number;
ss >> result;

return result;
}
else{
prev = next;
next--;
}
}

return n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int nNextHigher( int N )
{
assert( N >= 0 );

// Count # of digits
int nDigitCount = 0;
for( int nTemp = N; nTemp > 0; ++nDigitCount )
{
nTemp /= 10;
}

// Return current if 0/1 digit
if( nDigitCount <= 1 )
{
return N;
}

// Decompose into digits
vector<int> digits( nDigitCount, 0 );
for( int i = 0, nTemp = N; nTemp > 0; ++i, nTemp /= 10 )
{
digits[nDigitCount -1 - i] = nTemp % 10;
}

// Find first inverted digit
int nToggleIndex = -1;
for( int i = nDigitCount -2; i >= 0; --i )
{
if( digits[i] < digits[i+1] )
{
nToggleIndex = i;
break;
}
}

// If none found, return original N
int nNextHighestValue = N;
if( nToggleIndex != -1 )
{
// Build up set of all digits to the right of inverted index
multiset<int> nToggleDigits;
for( int i = nToggleIndex; i < nDigitCount; ++i )
{
nToggleDigits.emplace(digits[i]);
}

// Find the first value above the current value
int nCurrentDigit = digits[nToggleIndex];
auto minGreaterThanIter = nToggleDigits.upper_bound(nCurrentDigit);
assert( minGreaterThanIter != end(nToggleDigits) );
assert( *minGreaterThanIter > nCurrentDigit );

// Replace the current digit and remove from the toggle digit set
digits[nToggleIndex] = *minGreaterThanIter;
nToggleDigits.erase(minGreaterThanIter);

// For the remaining digits, just choose the min
for( int i = nToggleIndex + 1; i < nDigitCount; ++i )
{
assert( !nToggleDigits.empty() );
auto minDigitIter = begin(nToggleDigits);
digits[i] = *minDigitIter;
nToggleDigits.erase(minDigitIter);
}

// Build the integer back up
nNextHighestValue = 0;
for( int i = nDigitCount -1, nPow10 = 1; i >= 0; --i, nPow10 *= 10 )
{
nNextHighestValue += digits[i] * nPow10;
}
}

return nNextHighestValue;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

That ought to do it:

``````unsigned next_largest(unsigned x)
{
std::vector<unsigned short> l;
unsigned p;

do l.push_back(x % 10); while (x/=10);
for (p=0; p+1!=l.size() && l[p]<l[p+1]; ++p);

std::sort(&l[0], &l[p+1]);
std::reverse(&l[0], &l[p+1]);
std::swap(l[p+1], l[p]);

for (unsigned i=l.size(); i-->0; x*=10, x+=l[i]);
return x;
}``````

Comment hidden because of low score. Click to expand.
0

You can fix it with (at most) one line extra... I'll leave that as an exercise ;)

Comment hidden because of low score. Click to expand.
0

Should this compile? Breaks on second for() in Xcode 5.1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in python:

``````def next_higher(number):
stringified_number = list(str(number))
n = len(stringified_number)
j = n - 2

for i in reversed(xrange(n)):
for j in reversed(xrange(i)):
if int(stringified_number[j]) < int(stringified_number[i]):
stringified_number[j], stringified_number[i] = stringified_number[i], stringified_number[j]
return int("".join(stringified_number[:j+1])+ "".join(sorted(stringified_number[j+1:])))
return number

assert(next_higher(25468) == 25486)
assert(next_higher(21765) == 25167)
assert(next_higher(54321) == 54321)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;

public class NextHighestNumberWithSameDigits {

public static void main(final String[] args) {
// TODO Auto-generated method stub
final Scanner sc = new Scanner(System.in);
System.out.println("Enter a number:");
final String digit = sc.next();
final char[] ch = digit.toCharArray();
final int j = digit.length() - 1;
int k = -1;
for (int i = j - 1; i >= 0; i--) {
if (ch[i] < ch[j]) {
final char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
k = i;
break;
}
}
if (k == -1) {
System.out.println(digit);
} else {
for (int i = k + 1; i < j; i++) {
if (ch[i] > ch[j]) {
final char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
System.out.println("next biggest digit:" + String.valueOf(ch));
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. We scan the no from the Least significant digit and store it
2. The scan continues unitl we find a digit lesser than the previous digit
3. If the order is in ascending from least significant digit to the most then return the same number
4. Else the found digit is swapped with the least significant digit and the rest digits are sorted in ascending order and the final number is made

#include<iostream>
#include<math.h>
//#include<algorithm>

using namespace std;
int get_length(int n)
{
int temp=0;
while(n)
{
n=n/10;
temp++;
}
cout<<"in get_length ="<<temp<<endl;
return temp;
}
void sortRest(int arr[],int i)
{
int j,k,temp;
for(j=0;j<=i-1;j++)
{
for(k=j+1;k<=i;k++)
{
if(arr[j]>arr[k])
{
temp=arr[k];
arr[k]=arr[j];
arr[j]=temp;
}

}

}
cout<<"after sorting\n";
for(j=0;j<=i;j++)
cout<<arr[j];
cout<<endl;
}
double swap(int arr[], int i, double n)
{
int j=i;
//int temp = arr[0];
//arr[0] = arr[i];
//arr[i]= temp;
cout<<"0,i= "<<arr[0]<<arr[i]<<endl;
sortRest(arr+1, i-1);
cout<<"0,i= "<<arr[0]<<arr[i]<<endl;
while(j>=0)
{ cout<<"in swap n="<<n<<" i="<<i<<endl;
n=n*10+arr[i-j];
j--;
}
return n;
}
int main()
{
int n,num,len,i=0,ans=-1;
cout<<"enter n\n";
cin>>n;num=n;
len=get_length(n);
int arr[len];
while(n)
{
arr[i]=n%10;cout<<"arr["<<i<<"]="<<arr[i]<<endl;
n=n/10;cout<<"n="<<n<<endl;
if(i!=0)
{
if(arr[i]<arr[i-1])
{
ans=swap(arr, i, n);
break;
}
}
i++;
}
if(ans!=-1)
cout<<ans<<endl;
else
cout<<num<<endl;
return ans;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Goal is to swap 2 digits such that it results in bigger number, i.e before swap left digit should be greater than right digit. If we swap the 2 right most digits where this is possible, we will get next biggest number.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey everyone. My solution is the same as the majority of you. Here is my implementation in C++, using priority_queue class in STL. Note that, we should push (-1 * value) in the pqueue, because we want to have a min-heap but the priority_queue class implements a max-heap.

``````#include <iostream>
#include <queue>
#include <string>

using namespace std;

string findnexthighest(string ipt)
{
priority_queue <char> pq;
int swplace = -1;
for (int i = ipt.size() - 1; i > 0; i--)
{
pq.push(-1 * ipt[i]);
if (ipt[i] > ipt[i - 1])
{
swplace = i - 1;
break;
}
}
if (swplace < 0)
return ipt;
pq.push(-1 * ipt[swplace]);
int curplace = swplace + 1;
int cur;
while (true)
{
cur = -1 * pq.top();
pq.pop();
if (cur>ipt[swplace])
{
ipt[swplace] = cur;
break;
}
ipt[curplace++] = cur;
}
while (!pq.empty())
{
cur = -1 * pq.top();
pq.pop();
ipt[curplace++] = cur;
}
return ipt;
}``````

The running time of the algorithm is proportional to running time of the sorting algorithm used. Note that we have only digits here, so we can use counting sort to have a linear running time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static ArrayList<Integer> convertToList(int a) {
ArrayList<Integer> l = new ArrayList();
int num = a;
while (num > 0) {
num /= 10;

}
return l;
}

public static int convertToInt(ArrayList<Integer> num) {
int a = 0;
int unit = 1;
for (int i = num.size(); i > 0; i--) {
a += num.get(i - 1) * unit;
unit *= 10;
}
return a;
}

public static int findNextMax(int a) {

ArrayList<Integer> num = convertToList(a);
boolean found = false;
for (int j = num.size(); j > 0; j--) {
int last = num.get(j - 1);
for (int i = j; i > 0; i--) {
if (last > num.get(i - 1)) {
num.remove(j );
found = true;
break;
}
}
if(found){break;}
}
return convertToInt(num);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.test.util;

public class NextHigherNumber {
static int numArr[];
public static void main(String[] arg)
{
int n=123456789;
int num=n;
int numLen=0;
while(n!=0)
{
n=n/10;
numLen++;
}
numArr=new int[numLen];
n=num;
for(int i=numLen-1;i>=0;i--)
{
numArr[i]=n%10;
n=n/10;
}
for(int i : numArr)
System.out.println("i : "+i);

outer : for(int i=numLen-2;i>=0;i--)
{
inner : for(int j=i+1;j<numLen;j++)
{
if(numArr[i]>=numArr[j])
{
System.out.println("1st cond>>>>>i : "+i+" j : "+j+" numArr[i]="+numArr[i]+" numArr[j]="+numArr[j]);
continue inner;
}

else
{
System.out.println("2nd cond>>>>>i : "+i+" j : "+j+" numArr[i]="+numArr[i]+" numArr[j]="+numArr[j]);
int temp=numArr[numLen-1];
numArr[numLen-1]=numArr[i];
numArr[i]=temp;
System.out.println("Swapping>>>>>i : "+i+" numLen-1 : "+(numLen-1)+" numArr[i]="+numArr[i]+" numArr[numLen-1]="+numArr[numLen-1]);
sort(i+1,numLen-1);
break outer;
}
}
}
int newNum=0;
for(int i=numLen-1;i>=0;i--)
{
newNum=newNum+(int) (Math.pow(10, i)*numArr[numLen-1-i]);
}
System.out.println("New Number : "+newNum);
}

public static void sort(int frmIndex,int toIndex)
{
for(int i=frmIndex;i<=toIndex;i++)
System.out.println(i+" Before : "+numArr[i]);
for(int i=frmIndex;i<=toIndex;i++)
{
for(int j=i+1;j<=toIndex;j++)
{
if(numArr[i]>numArr[j])
{
int temp=numArr[i];
numArr[i]=numArr[j];
numArr[j]=temp;
}
}
}
for(int i=0;i<=toIndex;i++)
System.out.println(i+" After : "+numArr[i]);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def next_higher(a):
a = [int(i) for i in str(a)]
length = len(a)
index = -1
for i in range(length-1, -1, -1):
if a[i] < a[length-1]:
index = i
break
b = a[0:index]
b.append(a[length-1])
c=a[index:length-1]
c.sort()
b.extend(c)
return reduce(lambda a, b: a*10+b, b)

print next_higher(25468), next_higher(21765), next_higher(54321)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* find the next higher number with the same digits
*/

public static int findNextHigerNum(int num){

int[] arr = num2arr(num);
if(arr.length<=1) return num;
if(num<0) return -1 * findNextLower(arr);
return findNextHiger(arr);

}
private static int[] num2arr(int num){
if(num<0) num *= -1;
int count = 0;
int temp = num;
while(temp>0){
temp /= 10;
count++;
}
//use an array to store the num digit by digit
int[] arr = new int[count];
for(int i=0; i<count; i++){
arr[i] = num%10;
num /= 10;
}
return arr;
}
private static int findNextHiger(int[] arr){

int i = 0, j = 0;
while(arr[i]<=arr[i+1]&&i<arr.length-1){
i++;
if(i==arr.length-1) return arr2num(arr);//meaning this number is the largest possible
}

int value = arr[i+1];
while(arr[j]<=value) j++;
swap(arr, i+1, j);
//now place the the remaining part in descending order, this just need a reverse operation
reverse(arr, 0, i);
return arr2num(arr);
}

private static int findNextLower(int[] arr){

int i = 0, j = 0;
while(arr[i]>=arr[i+1]&&i<arr.length-1){
i++;
if(i==arr.length-1) return arr2num(arr);
}

int value = arr[i+1];
while(arr[j]>=value) j++;
swap(arr, i+1, j);
reverse(arr, 0, i);
return arr2num(arr);
}

private static int arr2num(int[] arr){
int poly = 1;
int value = 0;
for(int i=0; i<arr.length; i++){
value += arr[i] * poly;
poly *= 10;
}
return value;
}
private static void reverse(int[] arr, int start, int end){
while(start<end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

c++ solution

``````#include<bits/stdc++.h>
using namespace std;
int main()
{	int i,j,l,hash[10];
char s[1000001],max;//using string to store number.. no precision issues atleast for a 1000000 digits!!!
scanf("%s",s);
for(i=0;i<10;i++)
hash[i]=0;//initially count of 0..9 digits is 0 in the number
l=strlen(s);
i=l-1;
max='0';
while(i>=0)//from right to left until we find a smaller digit than present max digit found.
{
if(s[i]>max)//update max if greater digit found
max=s[i];
else if(s[i]<max)//end loop if smaller digit found
break;
i--;
}
if(i<0)//if number has digits in non increasing order from left to right i.e.no greater no. possible
{
puts(s);
return 0;
}
//i currently holds the position of leftmost digit to be changed
j=s[i]-48+1;
while(hash[j]==0)
j++;
s[i]=48+j;//use digit which is just greater than digit at ith position
hash[j]--;
i++;
j=0;
for(;i<l;i++)//update all digits to the right of the previous digit
{
while(hash[j]==0)
j++;
s[i]=48+j;
hash[j]--;
}
puts(s);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>

void sort(int *number, int size, int last);

void leastBiggerNumberWithSameDigits(int *number, int size);

void print(int *number, int size);

int main(void)
{

int number[] = {2, 1, 7, 6, 5};

print(number, 5);

leastBiggerNumberWithSameDigits(number, 5);

print(number, 5);

return 0;

}

void sort(int *number, int size, int last)
{

for(int i = last + 1; i < size - 1; i++)
{

for(int j = i + 1; j < size; j++)
{

if(number[i] > number[j])
{
int temp = number[i];
number[i] = number[j];
number[j] = temp;
}

}

}

}

void leastBiggerNumberWithSameDigits(int *number, int size)
{

// first make the smallest swap

int last;

for(last = size - 2; last >= 0; last--)
{
if(number[last] < number[last + 1])
{
//printf("-%d-", number[last]);
break;
}
}

if(last == 0)
{
return;
}

bool swapped = false;

for(int i = last + 1; i < size; i++)
{

if(number[i] < number[last])
{

int temp = number[i-1];
number[i-1] = number[last];
number[last] = temp;

sort(number, size, last);

swapped = true;

break;

}

}

if(!swapped)
{

int temp = number[size - 1];
number[size - 1] = number[last];
number[last] = temp;

sort(number, size, last);

}

}

void print(int *number, int size)
{

for(int i = 0; i < size; i++)
{
printf("%d, ", number[i]);
}

printf("\n");

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

similar to leetcode nextPermutation

``````class Solution {
public:
void nextPermutation(vector<int> &num) {
int i = num.size()-1;
int j = 0;
while (i>0 && num[i-1] >= num[i]) {
i--;
}
if (i==0)
sort(num.begin(), num.end()); // 321 to 123
else {
j = i+1;
while (num[j] > num[i-1] && j<num.size()) {
j++;
}
swap(num[j-1], num[i-1]);
sort(num.begin()+i,num.end());
}
}
};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class NextHigh {
public static int makeNumber(int a[])
{
int ans=0;
for(int i=a.length-1;i>=0;i--)
{

ans=a[i]+ans*10;
}
return ans;
}
public static int func(int b[])
{
int a[]=new int[b.length];
a=Arrays.copyOf(b, b.length);
int n=a.length,ans=makeNumber(b);
int i,t;
boolean found=false;
int f,s;
for(i=0;i<n-1;i++)
{
f=makeNumber(a);
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
s=makeNumber(a);
if(s>f)
{
found=true;
break;
}
else
a=Arrays.copyOf(b, b.length);
}
if(found)
ans=makeNumber(a);
return ans;
}
public static void main(String args[])
{
int n=11;
int t=n;
int len=0;
while(t>0)
{
len++;
t=t/10;
}
int a[]=new int[len];
t=n;
for(int i=0;i<len;i++)
{
a[i]=t%10;
t=t/10;
}
System.out.println(makeNumber(a));
System.out.println(func(a));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

pseudo code:

``````lsb = len(digit)
msb = 0
done = false
from x= lsb to x = msb+1:
from y = x-1 to msb:
if (y < x) :
swapdigits(y,x)
sort the digits from y+1 to lsb``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// Working c code

/*
* File:   main.c
* Author: Sandeep Srivastava
*
* Created on May 11, 2014, 11:30 AM
*/

#include <stdio.h>
#include <stdlib.h>

void sortArray(int arr[],int s,int e)
{
int i,j;
for (i = s; i < e; ++i)
{
for (j = i + 1; j < e; ++j)
{
if (arr[i] > arr[j])
{
int a =  arr[i];
arr[i] = arr[j];
arr[j] = a;
}
}
}
}
void swap(int arr[],int i,int pos)
{
int temp=arr[i];
arr[i]=arr[pos];
arr[pos]=temp;
}
int findMin(int arr[],int s,int e)
{
int pos=s;
while(s<e)
{
if(arr[pos]>arr[s])
pos=s;
s++;
}
return pos;
}

int findDigit(int n)
{
int count=0;
while(n)
{
n=n/10;
count++;
}
return count;
}
int findNext(int n,int d)
{
int tn=n; // storing n in tn
int arr[d]; // array of length equal to number of digit
int i;

for(i=d-1;i>=0;i--)
{
arr[i]=n%10; // storing each digit of number in array
n=n/10;
}
int temp= arr[d-1];
i=d-1;
while(temp<=arr[i] && i>=0)
{
temp=arr[i];
i--;
}
if(i==-1)
return tn;
else
{
int pos= findMin(arr,i+1,d);
swap(arr,i,pos);

sortArray(arr,i+1,d);
for(i=0;i<d;i++)
{
n=n*10+arr[i];
}
}
return n ;

}
int main() {

int digit =findDigit(21765); // find the number of digit
printf("input is: %d and output is: %d \n",21765, findNext(21765,digit));

digit =findDigit(25468);
printf("input is: %d and output is: %d \n",25468, findNext(25468,digit));

digit =findDigit(54321);
printf("input is: %d and output is: %d \n",54321, findNext(54321,digit));
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
int n;
cin >> n;
vector<int> digits;
if (n <= 0) return -1;
else{
while(n){
digits.push_back(n%10);
n/=10;
}
reverse(digits.begin(), digits.end());
if (digits.size() == 1) return -1;
int i;
for (i = digits.size()-2; i >= 0; i--){
if (digits[i] < digits[i+1]){
int j = i+1;
while(j < digits.size() && digits[j] > digits[i]) j++;
j--;
swap(digits[i], digits[j]);
sort(digits.begin()+i+1, digits.end());
break;
}
}
if (i == -1) return -1;
else{
for (int i = 0; i < digits.size(); i++)
cout << digits[i];
cout << endl;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
int n;
cin >> n;
vector<int> digits;
if (n <= 0) return -1;
else{
while(n){
digits.push_back(n%10);
n/=10;
}
reverse(digits.begin(), digits.end());
if (digits.size() == 1) return -1;
int i;
for (i = digits.size()-2; i >= 0; i--){
if (digits[i] < digits[i+1]){
int j = i+1;
while(j < digits.size() && digits[j] > digits[i]) j++;
j--;
swap(digits[i], digits[j]);
sort(digits.begin()+i+1, digits.end());
break;
}
}
if (i == -1) return -1;
else{
for (int i = 0; i < digits.size(); i++)
cout << digits[i];
cout << endl;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def highest_number_same_digits(n):
s = list(str(n))
i = len(s)-1
min = s[i]
k = i
while i >= 1 and s[i-1] >= s[i]:
if min > s[i-1]:
min = s[i-1]
k = i-1
i -=1
if i > 1:
s[i-1], s[k] = s[k], s[i-1]

return int(''.join(s[:i] + sorted(s[i:])))
else:
return n``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.*;
public class Main {

public static void main(String args[]){
int num  = 18715;
String nums = String.valueOf(num);

int min = Integer.parseInt(nums.substring(nums.length()-1));
int minIndex = nums.length()-1;
int i = nums.length()-2;
int a = Integer.parseInt(nums.substring(i+1,i+2));
int b= Integer.parseInt(nums.substring(i,i+1));

while(a<b){
System.out.println(i);
i--;
if(i==-1){
System.out.println("No min next Possible");
break;
}

a = Integer.parseInt(nums.substring(i+1,i+2));
b= Integer.parseInt(nums.substring(i,i+1));

}
int newnum=0;
if(i!=-1){
for(int j=0;j<nums.length()-1;j++){
if(j==i){
newnum=newnum*10 + Integer.parseInt(nums.substring(nums.length()-1, nums.length()));
}
else{
newnum=newnum*10 + Integer.parseInt(nums.substring(j,j+1));
}
}
newnum=newnum*10 + Integer.parseInt(nums.substring(i,i+1));
System.out.println(newnum);
}

}``````

}

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1
of 1 vote

FUCK YOU.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

THIS GUY IS USING SOCK PUPPETS TO UPVOTE HIS QUESTIONS AND ANSWERS. FUCK THIS GUY.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

FUCK YOU RAMESH.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Guys even if he is publicizing his blog, atleast the question he posts are good. When the question quality is down then we can criticize him.

Comment hidden because of low score. Click to expand.
0

No, don't encourage people to make this their own advertising space. Broken windows theory (see wikipedia) applies here. Plus, the questions are not necessarily first-hand interview questions, even though they might be interesting/good. I can give you plenty of interesting questions which will only lower your chances of getting a job.

He can post to the forum all he wants. Is it really hard for folks to understand that? GAWD. The IQ level on this site is sickening.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.