Interview Question

Software Development Engineer Interview Seattle, WA

1. Find common elements between two arrays of integers

  . 2. Find cycles in a graph. 3. Efficiently find duplicate elements in an array of numbers with bounded entries (for example, elements are between 0 and 99). 4. Reverse word sequence in a string inplace. 5. Efficiently find all Pythogorean triplets in a given array of integers. 6. Find all anagrams in a list of words. 7. Set operations.
Answer

Interview Answer

2 Answers

0

@1: Can you first mergesort the two arrays, and then do the following? That'll be nlogn runtime? I haven't tested it out...

int i=0, j=0;
while ( i<sorted_array1_size && j<sorted_array2_size ){
   if( sorted_array1[i] < sorted_array2[j] ){
        i++;
    }else if ( sorted_array1[i] > sorted_array2[j] ){
        j++;
    } else { //must be equal
        printf("Common element: %d\n", sorted_array1[i]);
        i++; j++;
    }
}

kim on Jul 28, 2010
1

for #1 you just have to hash the first array and then if(contains) the hash table against each element of the second array

O(n) # of comparisons

D on Aug 19, 2010

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up