## Yahoo Interview Question

• 0

Country: -

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

let a[] be d array...where v have 2 store the number.
let i point's to 0th loc of a[] and j point's to last index(last index is nothing but d last index of given array.)
check if func returns 1 then store that number at ith loc and increment i by 1.
if func returns 0 then store that number at jth loc and decrement j by 1.
finally array a[] wil have required result.

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

clear & correct

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

THERE WILL BE NO ANOTHER ARRAY a[] i think so.....YOU SHOULD ARRANGE THEM IN THE MAIN ARRAY ITSELF

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

instead of using another array use 2 pointers i and j such that i=0 and j=last index
now traverse the array with k pointer and if i==k do no-op and if k=j end the loop else if arr[k] returns 0 swap with a[i] and i++ and if it returns 1 swap with arr[j] and j-- .
space complexity O(1) and time complexity O(n)

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

It's not entirely clear, but it sounds like your algo would require O(N) space. This problem is solvable in O(1) space and O(N) time as per Anonymous' comment and my post.

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

Dutch national flag once again. (2 colours, though).

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

Can any1 explain how to solve this

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

msankith, I posted working code. You can also check out the wikipedia article on the Dutch National Flag problem.

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

Counting sort will do this in O(N + 2), but it will also require O(N + 2) extra space.

if (1<<N > UINT_MAX) then, below procedure can be followed.

``````void arrange(int Arr[], int Arr_len)
{
unsigned int chk = 0;
for (int i=0; i<Arr_len; i++)
{
chk = chk | 1<<i;
}

int a = 0;
int b = 0;

while(1)
{
if(chk&(1<<a)<1)
{
a++;
}
if(chk&(1<<b)>1)
{
b++;
}
if(a>=Arr_len && b>=Arr_len) break;

swap(Arr[a], Arr[b]);
chk = chk | 1<<b;
}
}``````

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

(1<<N > UINT_MAX) should be (1<<N <= UINT_MAX)

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

Since no one has actually posted code for it, here is a solution using a 2 color Dutch National Flag algorithm. O(N) time, O(1) space

``````public class YahooPartitionArray {

public static void main(String[] args) {
int a[] = new int[] {4,5,2,4,3,9,8,1};
partition(a, new SomeInterface() {
@Override
public int someFunction(int i) {
if (i % 2 == 0) {
return 1;
}
else {
return 0;
}
}
});
System.out.println(Arrays.toString(a));
}

interface SomeInterface {
public int someFunction(int i);
}

// Use Dutch National Flag algorithm with 2 colors.
//
// O(N) time, O(1) space
static void partition(int a[], SomeInterface s) {
int i = 0, j = a.length - 1;
while (i < j) {
int result = s.someFunction(a[i]);
if (result == 0) {
i++;
}
else {
swap(a, i, j--);
}
}
}

static void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}``````

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

int run()
{

int A[] = {4, 2, 5, 8, 1, 7, 9, 4, 6};

int N = sizeof(A) / sizeof(A) - 1;

print_v(A, sizeof(A) / sizeof(A));

for(int i = 0; i <= N; i ++) {

if(f(A[i])) continue;

else {int t = A[i]; A[i] = A[N]; A[N] = t; N --; i --;}

}

print_v(A, sizeof(A) / sizeof(A));

return 0;
}

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

int run()
{
int A[] = {4, 2, 5, 8, 1, 7, 9, 4, 6};
int N = sizeof(A) / sizeof(A) - 1;
print_v(A, sizeof(A) / sizeof(A));
for(int i = 0; i <= N; i ++) {
if(f(A[i])) continue;
else {int t = A[i]; A[i] = A[N]; A[N] = t; N --; i --;}
}
print_v(A, sizeof(A) / sizeof(A));
return 0;
}

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

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

We can update the values in the same input array only. Let assume a condition of number is even/odd and the function returns 1 if that is odd else 0. Now start traversing array from the 0th index and check util it reached to endIndex. Keep all the even on the left side and odd values to the right side. If the number is even , just increment startIndex and proceed else swap the values and decrement endIndex and proceed.

``````// odd or even
bool isOdd(int n)
{
return (n % 2 == 0 ? 0: 1);
}

// Arrange element of the array
void arrangeArray(int * A, int size )
{
// Start from left
int startIndex = 0; // start index
int endIndex = size -1; // end index

int temp = 0;
while ( startIndex <= endIndex)
{
if ( isOdd(A[startIndex]))
{   // Store odd number at the end , decrement end index
temp = A[endIndex];
A[endIndex] = A[startIndex];
A[startIndex] = temp;
endIndex--;
}
else{
startIndex++;
}
}
}``````

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

int func(int num)
{
return num&1;
}

void storeNum(int *arr, int nLength)
{
if (NULL == arr)
return;

int i = 0,j = nLength-1;
while (i <= j)
{
if (!func(arr[i]))
{
while (i <= j)
{
if (leftNum(arr[j]))
break;
j--;
}
if (j < i)
break;
swap(arr+i,arr+j);
}
i++;
}
}

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

#include<stdio.h>
int main()
{
int arr={7,6,4,3,2,9,0,1,5,8};
int i=0,j=9;
while(i<j)
{

if(!func(arr[i]) || func(arr[j]))
{

if(!func(arr[i]) && func(arr[j]))
{
swapper(arr,i,j);
i++;
j--;
}
else if (!func(arr[i]))
{
j--;
}
else
{
i++;
}
}
else
{
i++;j--;
}
}
int k;
for(k=0;k<10;k++)
printf("%d ",arr[k]);
}

int func(int a)
{
return a%2;
}

void swapper(int arr[],int i,int j)
{
int temp;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}

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

One can use two index i and j and move them in opp direction till
I and j cross each other. Similar to quick sort

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

public class Solution
{
public static void main(String arg[])
{
int array[]={45,43,12,78,12,15,14};
int i=0;
int j=array.length-1;
while(i<j)
{
while(func(array[i])==1)
i++;
while(func(array[j])==0)
j--;
if(i<j)
{
int temp=array[j];
array[j]=array[i];
array[i]=temp;
}
}
for(int num : array)
{
System.out.print(num + " ");
}
}
public static int func(int array)
{
System.out.println(array%2);
return (array%2);
}
}

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

Use Insertion sort properties i.e if function return 1 insert it into the place after number whose return is 1 otherwise leave at its own place.

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

its complexity will be O(n2)

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

take two pointers say i and j. at starting i is pointing to a , and traverse the array with the pointer j. if fun(a[j])==1 ,then then replace a[j] with a[i] and increment both pointer i.e. i++ and j++. time complexity O(n).

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

If we see the values of what each functions return we will be able to see that it is only 0 and 1.
Assuming we are allowed this we can apply a quick sort on these values such that each swapping is reflected on the actual array as well.

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.