Yahoo Interview Question
Applications DevelopersCountry: United States
Interview Type: Written Test
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;
}
Why find the smallest even number in y? I think it should be biggest, and swap the biggest even number with right most digit.
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.
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.
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)
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;
}
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)
}
}
ok i found a flaw i replace the first even number with array[0]
it should be smallest even number in the subarray
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.
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.
}
}
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.
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
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?
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.
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
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;
}
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));
}
}
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");
}
}
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.
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.
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;
}
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.
- zahidbuet106 May 25, 2014For 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)