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.
Programming Praxis 
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]; }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)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))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]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)
// 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);
}
}
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]# 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
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
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