Expedia Interview Question
Software Engineer / DevelopersI've sent this:
int uniques(int * arr, int size)
{
if(size < 3) return size;
int i = 0;
int j = i + 1;
short do_swap = 0;
while(j < size) {
if(do_swap) {
if(arr[i] == arr[j]) {
j++;
} else if(arr[i] != arr[j]) {
i++;
// swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
j++;
}
} else {
if(arr[i] != arr[j]) {
i++;
j++;
} else {
do_swap = 1;
}
}
}
return (i + 1);
}
Here is the code:
int getUnq(int a[], int len)
{
if (len == 1)
return 1;
int i = 0;
int count = -1; // count of uniq element;
int unq = a[i];
bool skip = false;
do
{
i++;
if (unq != a[i])
{
if (!skip)
{
count++;
a[count]=unq; // save in a
printf("%d is unq!\n",unq);
}
unq = a[i]; // new element
skip = false;
if (i== len-1)// the last one
{
count++;
a[count] = unq;
printf("%d is the last unq!\n",unq);
}
}
else
skip=true;
} while (i< len -1);
return count+1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int sortArr[] = { 1, 2, 2, 3, 3, 4, 5, 5, 6};
int unqCount = getUnq(sortArr, 9);
printf("array has %d unqs!\n",unqCount);
for (int i=0; i< unqCount; i++)
printf(" %d, ",sortArr[i]);
printf("are the %d unqs in the sorted array. \n",unqCount);
getchar();
return 0;
}
public class UniqueElements{
public static void main(String args[]){
int [] sortArr = {1,1,2,2,3,4,4,5,5,6,7,8,9,9,10,12,12};
int length = sortArr.length;
int [] newArr= new int[sortArr.length];
for(int i=0,j=1;i<length;i++){
if(sortArr[i]==newArr[j-1])
;
else{
newArr[j]=sortArr[i];
j++;
}
}
for(int k=0;k<sortArr.length;k++)
System.out.print(newArr[k]+" ");
}
}
public static void findUniqueInts(int[] a) {
int duplicate = 0;
for (int i=0; i<a.length; i++) {
if (i == a.length-2) {
if (a[i] != a[i+1]) {
System.out.print(a[i+1] +" ");
}
break;
} else if (a[i] == 0 && a[i] != a[i+1]) {
System.out.print(0+" ");
} else if (a[i] != a[i+1] && a[i] != duplicate) {
System.out.print(a[i]+" ");
} else {
duplicate = a[i];
}
}
}
public static void findUniqueInts(int[] a) {
int duplicate = 0;
for (int i=0; i<a.length; i++) {
if (i == a.length-2) {
if (a[i] != a[i+1]) {
System.out.print(a[i+1] +" ");
}
break;
} else if (a[i] == 0 && a[i] != a[i+1]) {
System.out.print(0+" ");
} else if (a[i] != a[i+1] && a[i] != duplicate) {
System.out.print(a[i]+" ");
} else {
duplicate = a[i];
}
}
}
private static void findUniqueInts()
{
int[] a = { 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 10, 12, 12 };
int duplicate = 0;
for (int i = 0; i < a.Length; i++)
{
if (i == a.Length - 2)
break;
if (a[i] != a[i + 1] && a[i] != duplicate)
Console.WriteLine(a[i] + " ");
else
duplicate = a[i];
}
}
private static void findUniqueInts()
{
int[] a = { 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 10, 12, 12 };
int duplicate = 0;
for (int i = 0; i < a.Length; i++)
{
if (i == a.Length - 2)
break;
if (a[i] != a[i + 1] && a[i] != duplicate)
Console.WriteLine(a[i] + " ");
else
duplicate = a[i];
}
}
Hey bharath,
I think if the last element in the array is a unique element then your printUniqueElements method will not return that element.
eg, int[] a = { 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 10, 11, 12 ,13,};
13 will not be printed.
in order to get it printed it should like the below
public static void printUniqueElements(int[] a){
for(int i=0, j=1; j<a.length;i++,j++){
if((a[i] != a[j]) && ((j != a.length - 1) && (a[j] != a[j+1])))
System.out.println(a[j]);
if(a[i] != a[j] && j == a.length - 1){
System.out.println(a[j]);
}
}
}
public static void main(String args[]) {
uniqueTest u=new uniqueTest();
int[] a1 = { 1, 1, 1, 2, 2, 3 };
uniqueTest.printUniqueElements(a1);
for (int i = 0; i < a1.length; i++) {
if (i == 0) {
if (a1[i] != a1[i + 1]) {
System.out.println(a1[i]);
}
} else if (i < a1.length - 1) {
if (a1[i] != a1[i + 1] && a1[i] != a1[i - 1]) {
System.out.println(a1[i]);
}
} else {
if (a1[i] != a1[i - 1]) {
System.out.println(a1[i]);
}
}
}
}
public static void main(String args[]) {
int[] a1 = { 1, 1, 1, 2, 2, 3 };
for (int i = 0; i < a1.length; i++) {
if (i == 0) {
if (a1[i] != a1[i + 1]) {
System.out.println(a1[i]);
}
} else if (i < a1.length - 1) {
if (a1[i] != a1[i + 1] && a1[i] != a1[i - 1]) {
System.out.println(a1[i]);
}
} else {
if (a1[i] != a1[i - 1]) {
System.out.println(a1[i]);
}
}
}
}
#include <iostream>
void print_uniques(int a[], int len)
{
int i = 0;
int j = 1;
while (j < len)
{
if (a[i] != a[j])
{
i = j;
std::cout << a[j] << " ";
}
++j;
}
};
int main()
{
int arr[] = {INT_MAX, 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9, 9, 10, 11, 12 ,13};
int length = sizeof(arr) / sizeof(arr[0]);
print_uniques(arr, length);
return 0;
}
# Print unique elements of an array
arr=[0,0,0,0,0,0,0,0,1,2,2,4,5,6,7,8,9,9]
size=len(arr)
newArr=[0]*size
count=0
lastDuplicate=""
for i in arr:
if count<size-1 and arr[count] == arr[count + 1]:
lastDuplicate=arr[count]
if arr[count]==lastDuplicate:
lastDuplicate=arr[count]
else:
print arr[count]
count = count + 1
static void Main(string[] args)
{
int[] array = new int[]{1,1,1,2,2,3,3,3};
ExtractUnique(array, array.Length);
}
private static void ExtractUnique(int[] array, int length)
{
int i = 0;
int j = 1;
while (i < length && j < length)
{
if (array[i] != array[j])
{
Console.WriteLine(array[i].ToString());
j++;
i = j - 1;
}
else if (array[i] == array[j])
{
j++;
}
}
Console.WriteLine(array[i]);
Console.Read();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = { 1, 1, 2, 2, 4,4,8,9 };
printUniq(a);
}
public static void printUniq(int a[]) {
if (a != null) {
if (a.length == 2) {
if (a[0] != a[1]) {
//
}
} else {
int min = a[0];
int start = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] > min) {
min = a[i];
if (i == (start + 1)) {
System.out.println("unique elem at " + start
+ " value " + a[start]);
}
if (i == a.length - 1) {
System.out.println("unique elem at last " + i
+ " value " + a[i]);
}
start = i;
}
}
}
}
}
Asked to explain solution and sent code into email after phone interview
- zdmytriv March 10, 2008