Yahoo Interview Question for Applications Developers


Country: United States
Interview Type: Written Test




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

We don't need to generate permutations. We can do it in O(nlgn). Observe that if all the digits are in non-decreasing order from right to left then the input itself is the biggest. So, if we can detect the position where the non-decreasing sequence in disrupted then we can simply work on the part of the array.

For example: N = 8234961

1) Detect the longest increasing (non-decreasing) sequence y from right to left and split the input into N=xy. This is O(n). Let a = the element where the increasing sequence disrupted. Also keep track of minimum even (say m) digit in y.

N = 8234 | 961, y=961, x=8234. a=4, m = 6;

Here, we might have a special case if y doesn't contain an even digit. In this case extend x to left the point where we have found an even on the left.

For example: N = 425731; x=425, y = 731, a=5, m=Integer.MIN. Then we extend y. Now, with extended y:

N = 425731; x=42, y = 5731, a=2, m=Integer.MIN.

2) Let, b = smallest element in y greater than a.

a=4. So, b=6.

3) swap (a,b);

N = 8236 | 941; x=8236, y=941. This is O(1).

4) Find max even in Y. This is O(n).

N= 8236 | 941; X=8234, Y=941, Max even = 4.

4) swap max even with the right most digit. This is O(1).

After swapping: N= 8236 | 914; X=8234, Y=914.

Special case: After swapping it may happen that there is no even in y. So, we need to constantly satisfy that y contains an even after swapping X[a] with the Y[b]. So, keeping this constraint true we will extend y to more left until we find an even. Consider this example: 125831

5) Now, sort y in decreasing order from right to left leaving rightmost digit unchanged. This is O(nlgn) in worst case.

N= 8236 | 91 | 4 --after sort --> 8236 | 19 | 4;

That's it, now N=xy is the desired solution. N = 8236194. Total complexity = O(nlgn)

- zahidbuet106 May 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

Here is the O(nlgn) code:

public static void swap(final int[] a, final int i, final int j) {
    if (i == j || i < 0 || j < 0 || i > a.length - 1 || j > a.length - 1) {
        return;
    }
    a[i] ^= a[j];
    a[j] ^= a[i];
    a[i] ^= a[j];
}

public static int[] nextEven(final int[] digits) {
    int y = digits.length - 1;
    boolean evenFound = digits[y] % 2 == 0;
    // find longest increasing subarray from right to left
    for (int i = digits.length - 2; i >= 0; i--) {
        if (digits[i] >= digits[i + 1]) {
            evenFound |= digits[i] % 2 == 0;
            y = i;
        } else {
            break;
        }
    }

    // if y doesn’t contain an even then extend y to left until an even found
    while (!evenFound && y - 1 >= 0 && digits[y - 1] % 2 != 0) {
        y--;
    }

    // input is already the largest permutation
    if (y <= 0) {
        return digits[digits.length - 1] % 2 == 0 ? digits : null;
    }

 //try to extend Y such that y contains an even after swapping X[a] with the Y[b]
 while(y -1 >= 0){
    // now X = digits[0..y-1], and Y = digits[y..digits.length-1]
    // a is the rightmost element of x, i.e. a = y-1;
    // find b = min of y greater than a
    final int a = y - 1;
    int b = -1;
    for (int i = y; i < digits.length; i++) {
        b = digits[i] > digits[a] && (b == -1 || (digits[i] < digits[b])) ? i : b;
    }

    // input is already the largest permutation
    if (b == -1) {
        return digits[digits.length - 1] % 2 == 0 ? digits : null;
    }
    // swap a and b
    swap(digits, a, b);

    // update max even in y
    int maxEven = -1;
    for (int i = y; i < digits.length; i++) {
        maxEven = digits[i] % 2 == 0 && (maxEven == -1 || (maxEven != -1 && digits[i] > digits[maxEven])) ? i
                : maxEven;
    }
   if (maxEven == -1) {
        y--;
   }
   else{
      break;
    }
}

    // input is already the largest permutation
    if (maxEven == -1) {
        return digits[digits.length - 1] % 2 == 0 ? digits : null;
    }

    // swap max even with rightmost position
    swap(digits, maxEven, digits.length - 1);
    // sort y leaving rightmost position unchanged
    Arrays.sort(digits, y, digits.length - 1);

    return digits;
}

- zahidbuet106 May 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

had similar approach. good explanation.

- byteattack May 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why find the smallest even number in y? I think it should be biggest, and swap the biggest even number with right most digit.

- tonylibra1018 June 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes u r right..should be max even in y. typo. Fixed now.

- zahidbuet106 June 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

very nice solution.

- razib.nu June 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent solution and explanation.

- dhs.du.08 June 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice explanation and solution but had a question about it if somone can help. If the input is: 125831 it returns: 128531. I think the correct answer should be: 131258. Please let me know if I am wrong.

- Anon December 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anon, good catch, yes... we need one to constantly make sure that the partition satisfy a constraint : y contains an even after swapping X[a] with the Y[b]

I modified the code a little bit to resolve this case.

- zahidbuet106 January 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Hi ravio, I agree but don't think the problem is very interesting if you use an stl algo :)

I am thinking that you can reduce the number of permutations but walking incrementing the number of digits in the permutations being considered on at a time. So...

For example given : N = 8234961
--> Start with right most 2 digits = 61
Even Permutations : 16. (but this isn't > 61)
--> Move to rightmost 3 digits = 961
Even Permutations: 916, 196 (neither are > 961)
--> Move to rightmost 4 digits = 4961
Even Permutations > 4961 : 9614,9164, 6914, 6194, 9146, 9416
Get smallest from this set = 6194
Answer : E = 8236194

Algo is still O(n2) worst case, but in practical terms should be optimized with the reduced right-left generation of smallest permutations first.

- johny418 April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

We don't need to generate permutations. We can do it in O(nlgn). Observe that if all the digits are in non-decreasing order from right to left then the input itself is the biggest. So, if we can detect the position where the non-decreasing sequence in disrupted then we can simply work on the part of the array.

For example: N = 8234961

1) Detect the longest increasing (non-decreasing) sequence y from right to left and split the input into N=xy. This is O(n). Let a = the element where the increasing sequence disrupted. Also keep track of minimum even (say m) digit in y.

N = 8234 | 961, y=961, x=8234. a=4, m = 6;

Here, we might have a special case if y doesn't contain an even digit. In this case extend x to left the point where we have found an even on the left.

For example: N = 425731; x=425, y = 731, a=5, m=Integer.MIN. Then we extend y. Now, with extended y:

N = 425731; x=42, y = 5731, a=2, m=Integer.MIN.

2) Let, b = smallest element in y greater than a. Also update minimum even accordingly i.e. m = min{m, a}. This is O(n).
a=4. So, b=6. m = min{6, 4} = 4.

3) swap (a,b); N = 8236 | 941; x=8236, y=941. This is O(1).

4) swap minimum even , m with the right most digit. This is O(1)

N= 8236 | 914; x=8234, y=914.

5) Now, sort y in decreasing order from right to left leaving rightmost digit unchanged. This is O(nlgn) in worst case.

N= 8236 | 91 | 4 --after sort --> 8236 | 19 | 4;

That's it, now N=xy is the desired solution. N = 8236194. Total complexity = O(nlgn)

- zahidbuet106 May 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Here is the O(nlgn) code:

public void swap(int[] a, int i, int j)
	{
		a[i]^=a[j];
		a[j]^=a[i];
		a[i]^=a[j];
	}
	
	public int[] nextEven(int[] digits)
	{		
		int y = digits.length-1;
		int m = digits[y]%2 == 0 ? y : -1;			
		//find longest increasing subarray from right to left
		for (int i=digits.length-2; i>=0; i--){
			if(digits[i] >= digits[i+1]){							
				m = digits[i]%2 == 0 && (m == -1 || (m!=-1 && digits[i] > digits[m]))? i : m;
				y=i;
			}
			else break;
		}
		
		//if y doesn’t contain an even then extend y to left until an even found
		while(m==-1 && y-1>=0 && digits[y-1]%2 != 0)
			y--;			

		// input is already the largest permutation
		if (y <=0) return digits[digits.length-1]%2 == 0? digits : null;
			
		//now X = digits[0..y-1], and Y = digits[y..digits.length-1]
		//a is the rightmost element of x, i.e. a = y-1;
		//find b = min of y greater than a
		int a = y-1;
		int b = y;
		int minb = digits[b];
		
		for(int i=y; i<digits.length; i++)	
			b = digits[i] > digits[a] && digits[i] < minb ? i : b;	
		//swap a and b
		swap(digits, a, b);
		//update max even in y
		m = digits[b]%2 == 0 && (m == -1 || (m!=-1 && digits[b] > digits[m]))? b : m;
		
		//swap min even with rightmost position
		swap(digits, m, digits.length-1);
		//sort y leaving rightmost position unchanged
		Arrays.sort(digits, y, digits.length-1);

		return digits;	
	}

- zahidbuet106 May 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach is same as the top answer,

1) find the smallest non increasing subinteger (from right to left)
2) find the smallest ( but larger than most significant digit of the above subinteger) integer in the above subinteger
3) Swap
4) Find the smallest number you can achieve with the above subinteger's digits - 1 ie
if above integer is 4921 then find smallest using 921 - ie 129
so 4921 becomes 4129
5) find the first even number starting from the right and replace it with number[0]

public class NextLargestEventNumber {
    public int findNextLargestEventNumber(int input) {
        int len = String.toInteger(input).length();
        if len == 0 {
            return input;
        }
        int[] numarray int[len]
        int next_largest = find_next_largest(input)
        for (int i = len - 1; i >= 0; i--) {
            numarray[i] = next_largest % 10
        }
        for (int i = 0; i < len; i ++) {
            if numarray[i] % 2 == 0 {
                swap(numarray[i], numarray[0]);
                break;
            }
        }
        return arrayToInt(numarray);
    }
    
    private int[] find_smallest(int[] input, begin_index) {
        if begin_index == 0 {
            return input
        }
        int min = input[0]
        int minindex = 0
        for (int i = 0; i <= begin_index; i++) {
            if (min < input[i]) {
                min = input[i]
                minindex = i
            }
        }
        swap(numarray[begin_index], numarray[minindex])
        find_smallest(numarray, begin_index - 1)
        return numarray
    }
    
    private int find_nex_largest(int input) {
        int len = String.toIntege(input).length() == 0
        int[] numarray = int[len]
        for (int i = len - 1; i >= 0; i--) {
            numarray[i] = input % 10
        }
        if len == 0 {
            return input
        }
        int max = numarray[0]
        for (int i = 0; i < len; i++) {
            lsg = numarray[i]
            if lsg > max {
                max = lsg
            }
            if (lsg < max) {
                int min_diff = 0
                int swapint = 0
                for (int j = 0; j < i; j++) {
                    if numarray[i] > numarray[j] {
                        int diff = numarray[j] - numarray[i]
                        if diff < min_diff {
                            min_diff = diff
                            swapint = j
                        }
                    }
                }
                swap(numarray[i], numarray[j])
                find_smallest(numarray, i)
                break;
            }
        
        return array_to_int(numarray)
    }
}

- byteattack May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok i found a flaw i replace the first even number with array[0]
it should be smallest even number in the subarray

- byteattack May 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I just realized my find smallest is actually doing sorting... that can be replaced by quicksort.

- byteattack May 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Find all the permutations of the given number by converting it into the string. Few cases before finding the permutations, check if the given number has at least one even digit (2, 4 ,6 ,8 ,0) in the given number. While finding the permutations we can easily reduce the number of permutations to have by checking the last digit of the permutation not an even digit.

- Deepak Rosario Pancras April 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Simple approach.
1)Generate all permutations for the number
2 ) Store each permutation in a Set
3)For each element E in set. Check if(E%2==0 && E>N)
print
4)else print None.

StringBuffer sb= new StringBuffer(); //global
Set<String> set= new HashSet<String>();
boolean [] used;
private String permuteString;
 
public void printNextgreatestEven(int num)
{
if(num<0)
print "Error";
Set <String> s= getPermutations(num);
Iterator it = s.iterator();
boolean hasPrined=false;
while(it.hasNext())
{
int E=it.getValue();// permutation of N
if(N>E && E%2==0 && !hasPrinted)
{print(E);
hasPrinted=true;
return;
}
}
if(!hasPrinted)
{
print ("None");
return;
}
}
 
 
Set<String> getPermutations (int in)
{
String s=""+in;/// convert to String;
Set<String> set= new HashSet<String>();
if( s.length==1)
{
set.add(s);
return set;
}
permuteString=s;
used= new boolean[s.length];// set globals for perumutation.
set= Permutations();
return set;
}
Set<String> Permutations();
{ // base case
if(in.length==sb.length)
{
set.add(in);
}
for(int i=0;i<in.length;i++)
{
if(used[i])
continue;
sb.append(in[i]);
Permutations();
used[i]= false; // to reuse the character for next permutation.
}
}

- Noobcoder April 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It is too computationally intensive. You should use the algorithm to generate next_permutaion instead of generating all permuations. For example you can use the STL algorithm "next_permutataion" in C++ to generate next_permutation and judge if it is even.

- ravio April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Giving a complex solution is better than providing a solution from library...
may be you can tell the interviewer abt the lib function and then can give your solution

- arsragavan April 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is the Approach I used:
lets say a list stores all the digits. first number at index 0, second at index 1 ...
From right to left, check if last number in list is greater than the rest of the number. If yes, then swap. Store the index of the swap in pos. Break
Now from pos+1 to list.size-1, find the largest even number and swap it with the last number in list. Lets store the largest number in variable called "large".
Then, sort the list in increasing order from pos+1 to list.size-2
Last step is to combine, list.get(0) .....+ list.get(pos) ....list.(size-2) + large

- programmerLeNoob April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Continuation...
For example,
Number = 34722641
Check if 1>4 || 1>6 || 1>2 || 1>2 || 1>7 || 1>4 || 1>3 ==> False
Check if 4>6 || 4>2 ==>True
Swap 4 at position 6 and 2 at position 4 ?(Swapping 4 and 2)
Number = 34724621
Find Largest even number after position 4. largest Number = 6 (6,2,1)
Swap it with last number:
Number = 34724126
Sort list from position 5 to position list.size-1. Sort(1,2) ==>Already sorted
Number: 34724126

I am not sure if my thinking is correct. It works for the above examples. Let me know what you think?

- programmerLeNoob April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

just briefly looking at your logic I don't think it is right because for a first pass you check the 1 > each digit the whole way to the end of the number. If the number were 14764242, your arrive at comparing 2 > 1 as true as then presume that the 2 needs to be in that position? You have to consider all the smallest possibilities first, so in this case it would swapping the 242 to be 422, resulting in 14764422. I didn't play out your whole algo with this number, just that it didn't make sense to me that you would be looking across the whole span of digits with the first number.

- johny418 April 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

As For example, we will take the same number
Number = 34722641

Assuming a[0] =1
a[1] =4 and so on...

Compare a[i] & a[i+1] and loop through until a[i] < a[i+1]

i=0;
 while( a[i] < a[i+1])
	{
		i++;
	}

Once we come out of the loop, we know where a[i] > a[i+1]

so the number to swap is a[i+1] and the number which is between j=0 to i-1 and it should the smallest number which is greater than a[i+1]

so the below code does that ,

num = a[i+1];
j=0;
curMin = INT_MAX;//some random max number
while(j<i)
{
	if( a[j] > num && a[j] <curMin)
	{
		curMin = a[j];
		minIndex = j;
	}
      j++;
}

//Now swap a[i+1 ] and a[minIndex]

Now again we need to check whether the element at a[0] is even , it it is even then we have arrived at the result

else

search for i =0 to n , and swap the first even number with a[0].

Regards,
Vinodh

- vino321 April 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This would have been so much more compact in Java 8 with lambdas. This is a more general function to provide the next higher permutation of digits. Filter it for even numbers or whatever you like...

public static long nextPermutation(long in) {
    // Break digits into array of integers
    int numOfDigits = Long.toString(in).length();
    int[] inDigits = new int[numOfDigits];
    long remainder = in;
    for (int i = numOfDigits - 1; i >=0; i--) {
      inDigits[i] = (int)(remainder % 10);
      remainder /= 10;
    }
    if (numOfDigits < 2) {
      return in;
    }

    // Find the digit where reordering can start
    for (int i = numOfDigits - 2; i >= 0; i--) {
      if (inDigits[i] < inDigits[i + 1]) {
        // Get the next highest digit to the right
        int nextHighestIndex = 0, nextHighestNumber = 10;
        for (int next = i + 1; next < numOfDigits; next++) {
          if ((inDigits[next] < nextHighestNumber) && (inDigits[next] > inDigits[i])) {
            nextHighestIndex = next;
            nextHighestNumber = inDigits[next];
          }
        }
        
        // Swap for that next highest digit
        int temp = inDigits[i];
        inDigits[i] = inDigits[nextHighestIndex];
        inDigits[nextHighestIndex] = temp;
          
        // Sort the remainder
        Arrays.sort(inDigits, i + 1, numOfDigits);
        
        // Build and return
        StringBuilder result = new StringBuilder();
        for (int d : inDigits) {
          result.append(Integer.toString(d, 10));
        }
        return Long.parseLong(result.toString());
      }
    }
    
    // No reordering found
    return in;
  }

- Sir CodesALot April 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you tell how to filter it for even number?

- Jiaxin April 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

package take2;
import java.util.*;
class o
{
	static int getNo(Vector<Integer> v)
	{
		int x = 0;
		for(int i = v.size()-1; i >= 0; i --)
		{
			x = 10* x + v.get(i);
		}
		return x;
	}
	static int minEven(int x)
	{
		Vector<Integer> v = new Vector<Integer>();
		int z = x;	
		while(z>0)
		{
			v.add(z % 10);
			z /= 10;
		}
		int f = 1;
		System.out.println(getNo(v));
		int gh = 0;
		int xf = x;
		Vector<Integer> vf = (Vector<Integer>)v.clone();
		while(true)
		{
			int edigits[] = new int[f];
			Vector<Integer> vt = (Vector<Integer>)v.clone();
			for(int j = 0; j < f; j++)
			{
				edigits[j] = vt.get(0);
				vt.remove(0);
			}
			System.out.println(Arrays.toString(edigits));
			
			for(int i = 1; i <= vt.size(); i++)
			{
				for(int j = 0; j < f; j++)
				{
					vt.add(i+j,edigits[j]);			
				}
				int no = getNo(vt);
				System.out.println(no + "   " + f);
				if( no > xf )
				{
					if ( no % 2 == 0)
						return no;
					else
					{
						f = 1;
						v = vt;
						xf = no;
						break;
					}
				}
				else
				{
					for(int j = 0; j < f; j++)
					{
						vt.remove(i);			
					}
					if( i == v.size() - 1)
					{	
						f++;
						v = vf;
					}
				}
			}
			if(f >= v.size())
				return -1;
			if(gh == 20)
				return -1;
			gh++;
		}
	}
	public static void main(String[] args) {
		System.out.println(minEven(8234961));
	}
}

- Anonymous April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here's one that uses a class that you an iterate through the permuations for any number of digits you want to check for. It can be optimized by keeping a table or hash for already computed values, but it works of for all good and bad combinations.

// class to get each permuation separately
public class Permute {
	Permute(int[] array, int len)
	{
		array_ = new int[len];
		array_ = array;
		len_ = len;
		current_ = -1;
		travel_ = len_-1;
		pos_ = len_;
		perm_ = new StringBuffer();
		// setup members for iteration
		haveNext();
		System.out.println("first group: " + perm_);
	}
	
	void swap(int i, int j)
	{
		//System.out.println("swap - i:" + i + ", j:" + j + ", before:" + perm_);
		char[] ci = new char[1];
		ci[0] = perm_.charAt(i);
		String str = new String(ci);
		char[] cj = new char[1];
		cj[0] = perm_.charAt(j);
		perm_.replace(j, j+1, str);
		String str2 = new String(cj);
		perm_.replace(i, i+1, str2);		
		//System.out.println("swap - i:" + i + ", j:" + j + ", after:" + perm_);
	}
	
	boolean haveNext()
	{
		if (current_ == len_ - 1 &&
			travel_ == len_ - 1 &&
			pos_ == len_)
			return false;

		//System.out.println("haveNext - current:" + current_ + ", travel:" + travel_ + ", pos:" + pos_);

		// if travel_ = len_-1, do next series;
		if (pos_ == len_ &&
			travel_ == len_ -1 )
		{
			current_++;
			travel_ = 0;
			pos_ = 0;
		
			Integer val = array_[current_];
			perm_.setLength(0);
			
			perm_.replace(0, 1, val.toString()); // make first
			int pos = 1;
			for(int i = 0; i < len_; i++)
			{
				if (i == current_)
					continue;
				val = array_[i];
				perm_.replace(pos++, pos, val.toString());
			}
			//System.out.println("haveNext - current:" + current_ + ", travel:" + travel_ + ", pos:" + pos_ + ", buf:" + perm_);
		}
		else if (pos_ == len_)
		{
			travel_++;
			pos_ = 0;
		}
		return true;
	}
	
	String getNext()
	{
		String str = "";
		if (!haveNext())
			return str;
		StringBuffer orig = new StringBuffer(perm_);
		swap(travel_, pos_);
		
		pos_++;
		
		StringBuffer save = new StringBuffer(perm_);
		perm_ = orig;
		
		save.reverse();
		return save.toString();
	}
	
	int[] array_;
	int len_;
	int current_; // the one to be at front
	int travel_; // the onoe to move around
	int pos_; // 
	StringBuffer buffer_; // buffer to build permutations with
	StringBuffer perm_;
}


 	public class CodeTest {

	public static void main(String[] args) {
		int test = 32359761; // if 3232461, then 3232614
							// if 3232561, then 3235612
							// if 32329581, then 32359218
							// if 35372763, then 35373672
							// if 1211, then fail
							// if 32359761, then 32379516
		if ((test & 1) == 0)
		{
			System.out.println("value is already even.");
			return;
		}

		int temp = test;
		int[] digits = new int[16]; // assuming that the number is at most 16 digits.
		int i = 0;
		// separate input into an array of ints
		for(; i < 16 && temp > 0; i++)
		{
			digits[i] = temp % 10; // get next digit
			temp /= 10;
			//System.out.println("digits[" + i + "] is " + digits[i]);
		}
		
		int cal = 0;
		int checkCount = 3; // never mind checking the first two digits, will never get larger number
		do {
			temp = test; // reset
			Permute per = new Permute(digits, checkCount);
			Double zeros = Math.pow(10, checkCount);
			cal = (temp / zeros.intValue()) * zeros.intValue(); // strip off n digits
			int stripped = temp % zeros.intValue();
			int min = zeros.intValue();
			while(per.haveNext())
			{
				String permutation = per.getNext();			
				System.out.println(permutation);
				int testFor = Integer.parseInt(permutation);
				if ( (testFor & 1) == 0 && // it's even
					testFor < min &&  // less than what we have so far
					testFor > stripped) // bigger than the target value we started with
					min = testFor;		// use this value	
			}

			if (min < zeros.intValue()) // found one that works
			{
				cal += min;
				System.out.println("Found on " + checkCount + " integer check with value:" + cal);
				return;
			}
			checkCount++; // increase # of digits to check for the correct value
		} while (checkCount <= i); // don't exceed number of digits to check
		System.out.println("could not find value");
	}
}

- TomT April 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here's a Pseudocode. Although it might be complex to implement.

Number 34722641

Go from position of the last even digit to first digit decrementing by 1. (start from 4)
{
Take the number "just larger" than current digit from right side .
if there is no such number, decrement and continue, (decrement until reach 2)
If you reach first and nothing, print NONE
else
Make that a control number. and swap with this (34722641 -> 34724621)
arrange the right side in increasing order. (34724621 -> 34724126)

if last digit is not even, move the first even digit to the end and move the rest of the string left.
break;
}



8234961
-> 8236941 swap 4 with just larger digit
-> 8236149 increasing order right side of 6
-> 8236194 put 4 at end and move the rest ("9") to left.

- Jason April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Assumption: n is positive (a slightly modified similar approach should work for negative numbers as well).

1. Initialize a digits array (10 element int array) which would hold counters for all the digits we encountered while iterating - to 0 (all counters are 0).
2. Start iterating from the last digit of the input number. In each iteration:
2.1. Increment the digit counter of the current digit.
2.2. Divide n by 10
2.3. Use the digits array to check whether there exists a digit that's strictly bigger than the current digit and that the list of all the digits we encountered so far (including the current digit) minus this digit (the one that's greater than the current digit) contains at least one even digit. Because the digits array only has 10 elements, this can be done in O(1).
2.4. If we found an appropriate digit in step 2.3 that means that we can now construct the desired output number:
2.4.1. Put the digit we found in 2.3 as the last digit in n (remember that n was already divided by 10) and reduce its counter in the digits array by 1.
2.4.2. Use the digits array to find the maximum even digit whose counter is positive (such digit should exist according to 2.3), denote it by lastDigit and reduce its counter by 1.
2.4.3. Using the digits array again put the remaining digits whose counters are positive as last digits of n in an increasing order.
2.4.4. Put lastDigit as the last digit of n and return the number.
3. If a number wasn't returned during step 2 that means that no appropriate number exists.

Example (n=8234961):
Iteration 1 - encountered digits - {1}. The current digit is 1 and we have yet to encounter a digit greater than 1. n = 823496
Iteration 2 - encountered digits - {6,1}. The current digit is 6 and again we have yet to encounter a digit greater than 6. n = 82349
Iteration 3 - encountered digits {9,6,1}. The current digit is 9 and again we have yet to encounter a digit greater than 9. n = 8234
Iteration 4 - encountered digits {4,9,6,1}. The current digit is 4. We have encountered 2 digits greater than 4 - 9 and 6. Replacing the current digit (4) with either 6 or 9 is possible because in both cases we have at least 1 even digit remaining to serve as the last digit (for 9, we can choose either 4 or 6 as last digits and for 6 we only have 4 as a possible last digit). Because we want to return the minimum possible number, we'll choose the smaller between the 2 which is 6.
We put 6 as the current last digit (n=8236). The remaining digits to use are {1,4,9} - we choose the maximum even digit to serve as the last digit of the returned number - 4 (it's the only remaining even digit). The rest of the digits we put as last digits in an increasing order to n (n=823619). Finally, we add the chosen even digit (4) to the end of n (n=8236194) and return n.

Code: pastebin.com/k4NgZFfG

Complexity: O(logn) worst-case (because the digits array is of constant size and the sum of all its counters cannot be greater than the total number of digits in n).


It seems to work but I haven't tested it too thoroughly.

- IvgenyNovo April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is a simple solution: Let me know what you guys think.

private static int findNextSmallestEven(int num) {
		char[] input = Integer.toString(num).toCharArray();
		Arrays.sort(input);
		while(true){
			if(num%2==0)
				num += 2;
			else
				num += 1;
			char[] output = Integer.toString(num).toCharArray();
			Arrays.sort(output);
			if(Arrays.equals(input, output)){
				break;
			}
		}
		return num;
	}

- Aniks May 08, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More