Interview Question

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.

Interview Answer

2 Answers


@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

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, Sign In or Sign Up.