Two-Part Interview Question

December 18, 2015

Today we have a two-part interview question from Amazon:

First, find the first non-repeated element in an unsorted array. For instance, in the array [3, 5, 3, 2, 1], element 3 is repeated, elements 5, 2, and 1 are non-repeated, and the first of those is 5. Second, find the first element that appears an even number of times in an unsorted array. For instance, in the array [5, 3, 5, 1, 5, 1, 3], elements 1 and 3 appear an even number of times, and the first of those is 3.

Your task is to write programs that find the first non-repeated element and the first even-appearance elements in an unsorted input array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

10 Responses to “Two-Part Interview Question”

  1. This is a tad convoluted – so I’ve merged the counting/position logic into a single method, which takes as a parameter the “function” used to say whether the entry is the one we want, followed by the list of numbers…

    use strict;
    
    print v( sub { $_[0] == 1; },
             qw(3 5 3 2 1) ),"\n";
    print v(
             sub { !($_[0]%2); }, qw(5 3 5 1 5 1 3) ),"\n";
    
    sub v {
      my( $f, @a ) = @_;
      my ($i, %c, %x );
      $c{$_}++        foreach @a;
      $x{$_} ||= $i++ foreach @a;
      return [
        sort {$x{$a} <=> $x{$b}}
        grep { &{$f}($c{$_}) }
        keys %x
      ]->[0];
    }
    
  2. Paul said

    In Python.

    from collections import Counter, OrderedDict
    
    class OrderedCounter(Counter, OrderedDict):
        pass
    
    def first_non_dup(seq):
        cnt = OrderedCounter(seq)
        return next((v for v, n in cnt.items() if n == 1), None)
    
    def first_even(seq):
        cnt = OrderedCounter(seq)
        return next((v for v, n in cnt.items() if not n % 2), None)
    
  3. matthew said

    Here’s another Python solution. This one makes a list of indices, sorts them according to the input list, then scans the sorted list counting occurrences of each element. When doing this, we copy each new element index down the list, but only include it in the final result if the count for that element satisfies the desired predicate. The end result is that the first j elements of b are the indices of the first occurrence of exactly those items in the input list that we want and we just need to take the minimum of b[:j] to find the earliest overall (Python’s sort is stable it seems). We could do the same sort of thing with itertools, but this way seems pretty neat:

    def test(a,pred):
        b = sorted(range(len(a)), key = lambda i: a[i])
        j = 0; count = 1
        for i in range(1,len(a)):
            if a[b[j]] == a[b[i]]:
                count += 1
            else:
                if pred(count): j += 1
                count = 1; b[j] = b[i]
        if pred(count): j += 1
        if j == 0: return None
        else: return a[min(b[:j])]
    
    pred1 = lambda n: n == 1
    pred2 = lambda n: n%2 == 0
    print(test ([3,5,3,2,1], pred1))
    print(test ([5,3,5,1,5,1,3], pred2))
    print(test ([2,3,1,7,3,4,5,3,2,1,5], pred1))
    print(test ([2,3,1,7,3,4,5,3,2,1,5], pred2))
    
  4. Globules said

    Here’s a Haskell version. I believe it gives the “convoluted” Python version a run for its money! (This is mostly due to the function passed to Q.alter.) My first version was similar to the ones above, so rather than repeat them I decided to look for a solution that made a single pass over the input and (ideally) didn’t need to retain the entire list in memory.

    The core of the code is a priority search queue, which allows us to efficiently look up elements as well as keep them ordered by priority (the first element satisfying some criteria). It would probably be most suitable for a large amount of streamed data whose elements come from a fairly small set of values.

    import Data.List (foldl')
    import qualified Data.OrdPSQ as Q
    
    -- Return just the "least" element of a list, if one exists, otherwise nothing.
    -- 
    -- Associated with each element is a pair (b, i), where b is a boolean value and
    -- i is its index in the list.  We consider the least element to be the one with
    -- the smallest i among those with b == False.  If there are no such elements
    -- then there is no "least" value.
    --
    -- The init argument is the initial b value, set for the first occurrence of an
    -- element.  The function sub produces subsequent b values given the current
    -- one.
    -- 
    -- The function uses a "priority search queue" whose keys are the list elements
    -- and whose priorities are the pairs (b, i).  For our purposes we don't need to
    -- associate any value with a key, so we use ().
    -- 
    -- The space used is O(d), where d is the number of distinct values.  The
    -- runtime is O(n * log d) where n is the length of the input.
    -- 
    leastBy :: Ord a => Bool -> (Bool -> Bool) -> [a] -> Maybe a
    leastBy initB nextB xs = case Q.findMin (psqFrom xs) of
        Just (k, (False, _), _) -> Just k
        _                       -> Nothing
      where psqFrom = foldl' step Q.empty . zip [0 :: Int ..]
            step q (n, x) = snd $ Q.alter (upd n) x q
            upd i  Nothing           = ((), Just ((initB,   i), ()))
            upd _ (Just ((b, i), _)) = ((), Just ((nextB b, i), ()))
    
    -- Return just the first non-repeating value in the list, or nothing if there is
    -- none.
    fstNonRep :: Ord a => [a] -> Maybe a
    fstNonRep = leastBy False (const True)
    
    -- Return just the first value in the list whose number of occurrences has even
    -- parity, or nothing if none do.
    fstEvenParity :: Ord a => [a] -> Maybe a
    fstEvenParity = leastBy True not
    
    main :: IO ()
    main = do
      putStrLn "First non-repeating values:"
      print $ fstNonRep [3, 5, 3, 2, 1]
      print $ fstNonRep [3, 5, 3, 2, 1, 5]
      print $ fstNonRep [3, 5, 3, 2, 1, 5, 2]
      print $ fstNonRep [3, 5, 3, 2, 1, 5, 2, 1]
    
      putStrLn "\nFirst values with even parity:"
      print $ fstEvenParity [5, 3, 5, 1, 5, 1, 3]
      print $ fstEvenParity [5, 3, 5, 1, 5, 1, 3, 3]
      print $ fstEvenParity [5, 3, 5, 1, 5, 1, 3, 3, 1]
    
    $ ./nonrep 
    First non-repeating values:
    Just 5
    Just 2
    Just 1
    Nothing
    
    First values with even parity:
    Just 3
    Just 1
    Nothing
    
  5. Khushboo said

    from collections import OrderedDict
    def nonrepeated_evennum(list1):
    element_count ={}
    element_count = OrderedDict()
    for element in list1:
    if element not in element_count:
    element_count[element]= 1
    else:
    element_count[element]= element_count[element]+1
    # for first non repeated
    for value in element_count:
    if element_count[value] == 1:
    print (value)
    break
    # for first character repeated even number of times
    for value in element_count:
    if element_count[value] % 2 == 0:
    print (value)
    break

    list1= [3, 5, 2, 1, 1, 5, 5, 2]
    nonrepeated_evennum(list1)

  6. david said

    // Here is a simple greedy approach in java

    import java.util.Iterator;
    import java.util.LinkedHashMap;

    public class ArrayProblem {
    public static void main(String[] args){
    ArrayProblem instance = new ArrayProblem();
    int[] unsortedArray1 = new int[]{3,5,3,2,1};
    int[] unsortedArray2 = new int[]{5,3,5,1,5,1,3};
    instance.solveFirstNoneRepeated(unsortedArray1);
    instance.solveFirstEvenNumberAppearance(unsortedArray2);
    }

    public void solveFirstNoneRepeated(int[] array){
    LinkedHashMap map = new LinkedHashMap();
    for(int i: array){
    if(map.containsKey(i)){
    boolean repeated = true;
    map.put(i, repeated);
    } else {
    map.put(i, false);
    }
    }
    // find the first is then simply:
    Iterator it = map.keySet().iterator();
    while(it.hasNext()){
    int key = (int) it.next();
    if(map.get(key) == false){
    System.out.println(“first item that is not repeated is: ” + key);
    return;
    }
    }
    }

    public void solveFirstEvenNumberAppearance(int[] array){
    LinkedHashMap map = new LinkedHashMap();
    for(int i: array){
    if(map.containsKey(i)){
    int count = map.get(i);
    count++;
    map.put(i, count);
    } else {
    map.put(i, 1);
    }
    }
    // find the first is then simply:
    Iterator it = map.keySet().iterator();
    while(it.hasNext()){
    int key = (int) it.next();
    if(isEven(map.get(key))){
    System.out.println(“first item that appears an even number of times: ” + key);
    return;
    }
    }
    }

    public boolean isEven(int value){
    return ((value % 2) == 0);
    }
    }

  7. Chris Azzara said

    A little late but here are my solutions in python!

    numz =  [4,5,6,7,6,2,5,4,3,7,3]
    count_dict = {}
    
    for i in numz:
        if i in count_dict:
            count_dict[i] += 1
        else:
            count_dict[i] = 1
    assert len(count_dict) > 1, 'List only has one unique number'
    assert 1 in count_dict.values() , 'List has no non-repeating elements'
    
    pos = len(numz)-1
    for num in count_dict.keys():
        if count_dict[num] == 1 and numz.index(num) < pos:
            pos = numz.index(num)
    print numz[pos]
    
    

    And the program for part 2

    numz =  [5,5,5,5,5]
    count_dict = {}
    
    for i in numz:
        if i in count_dict:
            count_dict[i] += 1
        else:
            count_dict[i] = 1
    assert len(count_dict) > 1, 'List only has one unique number'
    
    
    pos = len(numz)-1
    for key in count_dict:
        if count_dict[key] % 2 == 0 and numz.index(key) < pos:
            pos = numz.index(key)
    print numz[pos]
            
    
    
  8. # check first non-repeating element from array
    arr = [1,200,1,200,3,4,5]
    res = Array.new
    arr.detect{|e| res < 1) }
    puts “First non-repeated element in Array”+arr.to_s+” is : “+ res.first.to_s

    # check even times repeating elements in array
    a = [5, 3, 5, 1, 5, 1, 3]
    res_arr = Array.new
    a.select{|e| res_arr << e if a.count(e).even? }
    res_arr.uniq!
    p "even times repeating elements in Array"+a.to_s+" are: "+res_arr.to_s

  9. Yuri said

    Java Script:

    var array = [7, 5, 3, 5, 1, 5, 1, 3];
    document.write("Unsorted array: [" + array+ "] <BR/>");
    document.write("First repeated number: "+ first(array)+ "<BR/>");
    document.write("First item that appears an even number of times: "+ firstEven(array));
    
    function first(array){
    	for (i=0;i<array.length; i++){
    		for (j=i+1; j<array.length; j++){
    			if (array[i]== array[j]){return array[i]};
    		};
    	};
    }; //end of function 1
    
    function firstEven(array) {
    var counter = 1;
    	for (i=0;i < array.length; i++){
    		for (j=i+1; j < array.length; j++){if (array[i]== array[j]){ counter += 1};
    		};
    			if ((counter > 1) && (counter % 2 === 0)) { return array[i]};
    	};
    }; //end of function 2
    

    ===========================================
    Result on screen:

    Unsorted array: [7,5,3,5,1,5,1,3]
    First repeated number: 5
    First item that appears an even number of times: 3

  10. Yuri said

    Corrected logic in the first part. Java Script

    var array = [7, 5, 3, 5, 3, 5, 9, 0];
    document.write("Unsorted array: [" + array+ "] <BR/>");
    document.write("First non-repeated number: "+ first(array)+ "<BR/>");
    document.write("First item that appears an even number of times: "+ firstEven(array));
    
    function first(array){
    var counter = 0;
    	for (i=0;i<array.length; i++){
    		for (j=i+1; j<array.length; j++){
    		if (array[i]== array[j]){counter=1};
    		};
    		if (counter == 0){return array[i]};
    	};
    }; //end of function 1
    
    function firstEven(array) {
    var counter = 1;
    	for (i=0;i < array.length; i++){
    		for (j=i+1; j < array.length; j++){if (array[i]== array[j]){ counter += 1};
    		};
    		if ((counter > 1) && (counter % 2 === 0)) { return array[i]};
    	};
    }; //end of function 2
    

    ==================================
    Result

    Unsorted array: [7,5,3,5,3,5,9,0]
    First non-repeated number: 7
    First item that appears an even number of times: 3

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: