Ebay Interview Question
SDE-2sTeam: Traffic
Country: United States
Interview Type: In-Person
public static int[] adjust(int[] ar) {
if(ar == null || ar.length < 2)
return ar;
int read;
int write;
for(read = 1, write = 0; read < ar.length; ) {
if (ar[read] == ar[write]) {
read++;
continue;
} else {
write++;
int temp = ar[write];
ar[write] = ar[read];
ar[read] = temp;
read++;
}
}
return ar;
}
We do this by using a hash map.
//Given an array of sorted elements, move the distinct values to the top
var arr = [1,1,2,2,3,4,5];
function moveDistinct(arr){
var indexMap = {};
//Mark the duplicates
for(var i = 0; i < arr.length; i++){
var value = arr[i];
if(indexMap[value] > 0){
indexMap[value]++;
}
else{
indexMap[value] = 1;
}
}
//replace front values of array with distinct values
var count = 0;
for(var key in indexMap){
if(indexMap.hasOwnProperty(key)){
if(indexMap[key] === 1){
arr[count] = parseInt(key);
count++;
}
}
}
//add the duplicate values back in
for(var key in indexMap){
if(indexMap.hasOwnProperty(key)){
if(indexMap[key] > 1){
// add each occurrence to the array after the last distinct value
while(indexMap[key] > 0){
arr[count] = parseInt(key);
count++;
indexMap[key]--;
}
}
}
}
};
public class Duplicates {
public void moveDistinctFront(int[] a) {
int tail = 0 ;
for(int i = 1 ; i < a.length ; i++) {
if ( (a[i] != a[i-1]) && (a[i] != a[tail])) {
if (i > tail + 1) {
++tail ;
int tmp = a[tail] ;
a[tail] = a[i] ;
a[i] = tmp ;
} else if (i == tail +1) {
++tail ;
}
}
}
}
public static void main(String args[]) {
int[] a = {1,1,2,2,3,4,4,5,5,5} ;
Duplicates d = new Duplicates() ;
d.moveDistinctFront(a);
for(int i : a) {
System.out.print(i);
System.out.print(',');
}
}
}
- Vir Pratap Uttam April 12, 2015