Adobe Interview Question Member Technical Staffs
Country: India
Interview Type: In-Person
Please correct me if I am wrong - nice solu bt I feel a minor mistake, shudn't it be this way?
for( low = mid = 0, high = len-1; mid <= high; ) {
a[mid] == 0 ? swap(a[low++], a[mid++]) : a[mid] == 1 ? mid++ : ( swap(a[mid],a[high--]) );
}
Change is in last swap a[mid] instead of a[low].
Consider three ranges in the array at any instant :
0 to low-1 => contains 0
low to mid-1 => contains 1
mid to high => values to process
high+1 to len-1 => contains 2
for( low = mid = 0, high = len-1; mid <= high; ) {
a[mid] == 0 ? swap(a[low++], a[mid++]) : a[mid] == 1 ? mid++ : ( swap(a[mid],a[high--]) );
}
It is similar, consider 5 ranges :
0 to r0-1 => contains 0
r0 to r1-1=> contains 1
r1 to r2-1 => contains 2
r2 to r3 => values to process
r3+1 to len-1 => contains 3
You just have to make sure these conditions are satisfied after each iteration.
r0 = r1 = r2 = 0;
r3 = size-1;
while( r2 <= r3 ) {
if( a[r2] == 0 ) {
swap( a[r0], a[r2] );
if( r1 <= r0 ) {
r1++;
r2++;
}
r0++;
} else if( a[r2] == 1 ) {
swap( a[r1++], a[r2++] );
} else if( a[r2] == 2 ) {
r2++;
} else {
swap( a[r2], a[r3--] );
}
}
I think this can be extended to any number of colors but those nested if conditions ( like that in first if() ) will become very complex and it will be difficult to write accurate solution for large number of colors in single pass of array.
Moreover the constant factor involved in such complex linear time solution will be so large that normal (NlogN)sorting or bucket sort will outperform it.
Please correct me if I am wrong - nice solu bt I feel a minor mistake, shudn't it be this way?
for( low = mid = 0, high = len-1; mid <= high; ) {
a[mid] == 0 ? swap(a[low++], a[mid++]) : a[mid] == 1 ? mid++ : ( swap(a[mid],a[high--]) );
}
Change is in last swap a[mid] instead of a[low].
import java.util.Scanner;
public class ReArrange012 {
String inputArray[];
/**
* @param args
*/
public static void main(String[] args) {
System.out.println("Enter the array ..");
Scanner sc = new Scanner (System.in);
String s = sc.nextLine();
ReArrange012 obj = new ReArrange012();
obj.inputArray = s.split(" ");
obj.rearrange();
System.out.println("Rearranged Array");
for(int i = 0 ;i <obj.inputArray.length ; i++)
{
System.out.println(obj.inputArray[i] + " ");
}
}
//0, 1, 1 ,0, 2, 2, 1, 0 ,1, 2, 1,0 }
//to be converted into
//{0, 0, 0, 0, 1, 1, 1, 1, 1 ,2 ,2 ,2}
private void rearrange() {
int Firstocc_0_index = -1;
int Firstocc_1_index = -1;
int Firstocc_2_index = -1;
for(int i =0; i < this.inputArray.length ; i ++)
{
if(i==0)
{
if (Integer.parseInt(this.inputArray[i]) == 0)
{
Firstocc_0_index = i;
}
else if (Integer.parseInt(this.inputArray[i]) == 1)
{
Firstocc_1_index = i;
}
else if (Integer.parseInt(this.inputArray[i]) == 2)
{
Firstocc_2_index = i;
}
}
//to be converted into
//{0, 0, 0, 0, 1, 1, 1, 1, 1 ,2 ,2 ,2}
else
{
if((Integer.parseInt(this.inputArray[i]) > (Integer.parseInt(this.inputArray[i-1]))))
{
if (Integer.parseInt(this.inputArray[i]) == 1)
{
Firstocc_1_index = i;
}
else if (Integer.parseInt(this.inputArray[i]) == 2)
{
Firstocc_2_index = i;
}
}
else if((Integer.parseInt(this.inputArray[i]) < (Integer.parseInt(this.inputArray[i-1]))))
{
String temp = "";
if((Integer.parseInt(this.inputArray[i]) == 1))
{
temp = this.inputArray[i];
this.inputArray[i] = this.inputArray[Firstocc_2_index];
this.inputArray[Firstocc_2_index] = temp;
if(Firstocc_1_index == -1)
{
Firstocc_1_index = Firstocc_2_index ;
}
Firstocc_2_index++;
}
else if (Integer.parseInt(this.inputArray[i]) == 0)
{
Firstocc_0_index = 0;
if ( (Firstocc_1_index != -1))
{
temp = this.inputArray[i];
this.inputArray[i] = this.inputArray[Firstocc_1_index];
this.inputArray[Firstocc_1_index] = temp;
Firstocc_1_index++;
if((Integer.parseInt(this.inputArray[i-1]) == 2))
{
temp = this.inputArray[i];
this.inputArray[i] = this.inputArray[Firstocc_2_index];
this.inputArray[Firstocc_2_index] = temp;
Firstocc_2_index++;
}
}
else if (Firstocc_1_index == -1 )
{
temp = this.inputArray[i];
this.inputArray[i] = this.inputArray[Firstocc_2_index];
this.inputArray[Firstocc_2_index] = temp;
Firstocc_2_index++;
}
}
}
}
}
//0, 1, 1 ,0, 2, 2, 1, 0 ,1, 2, 1,0 }
//0, 0, 0, 0 , 1 ,1, 1, 1 , 1 ,2 , 2,2
}
}
@Vitlay - was it asked in tech interview ??
I hv given written of Adobe for MTS on 25th Aug. Still got no result of that. Mailed them twice. One out of office reply came from HR mentioning "University recruiting is keeping me busy. Please expect a delay in reply."
Do Adobe informs about result, if candidate could not clear it ??
@nittin,
mine written was latter, but i get the call. anyway i was out in first round itself :)
#include<stdio.h>
main()
{
int a[] = {0,1,1,0,2,2,1,0,1,2,1,0},i,j,k,temp,x;
i=0; j=0; k=11;
printf("Before : ");
for(x=0;x<12;x++)
printf("%d ",a[x]);
printf("\nAfter :");
while(j<k)
{
if(a[j] == 1)
j++;
else if(a[j] == 0)
{
temp = a[j]; a[j] = a[i]; a[i] = temp;
i++; j++;
}
else if(a[j] == 2)
{
temp = a[j]; a[j] = a[k]; a[k] = temp;
k--;
}
}
for(x=0;x<12;x++)
printf("%d ",a[x]);
printf("\n");
}
Apply Dutch national flag algo for 3 colors. Link below:
- pavi.8081 September 14, 2012