Two-Part Interview Question
December 18, 2015
For the first problem, our strategy is to create a dictionary with element as the key and position as the value. Then scan the input. If the element is not in the dictionary, add it. If the element is present in the dictionary, change the value from the input position to #f. After all the input has been read, scan the dictionary for elements with a value and report the element with the lowest value. We’ll represent the dictionary in an a-list, for simplicity:
(define (first-unique xs)
(let loop ((dict (list)) (xs xs) (idx 0))
(cond ((null? xs)
(car (apply maximum-by (lambda (x y) (> (cdr x) (cdr y)))
(filter (lambda (x) (cdr x)) dict))))
((assoc (car xs) dict)
(loop (alist! (car xs) #f dict) (cdr xs) (+ idx 1)))
(else (loop (cons (cons (car xs) idx) dict) (cdr xs) (+ idx 1))))))
The first cond clause is activated at the end of the input; it filters only those dictionary items with an index in the value, then takes the minimum (maximum using a > comparison) index. The second cond clause marks an element as previously seen. The third cond clause adds a new element. The alist! function modifies the value of an existing dictionary entry:
(define (alist! key val xs)
(let loop ((xs xs) (seen (list)))
(cond ((null? xs) seen)
((eq? (caar xs) key)
(append (cons (cons key val) (cdr xs)) seen))
(else (loop (cdr xs) (cons (car xs) seen))))))
Here is an example:
> (first-unique '(3 5 3 2 1)) 5
The second problem is similar. We keep two dictionaries, one for evens and one for odds, and twiddle elements between them as we scan the input:
(define (first-even xs)
(let loop ((evens (list)) (odds (list)) (xs xs) (idx 0))
(cond ((null? xs)
(car (apply maximum-by (lambda (x y) (> (cdr x) (cdr y)))
(filter (lambda (x) (cdr x)) evens))))
((assoc (car xs) evens)
(loop (alist-remove (car xs) evens)
(cons (assoc (car xs) evens) odds)
(cdr xs) (+ idx 1)))
((assoc (car xs) odds)
(loop (cons (assoc (car xs) odds) evens)
(alist-remove (car xs) odds)
(cdr xs) (+ idx 1)))
(else (loop evens (cons (cons (car xs) idx) odds) (cdr xs) (+ idx 1))))))
Again, we need an auxiliary function for the alist processing:
(define (alist-remove key xs)
(let loop ((xs xs) (seen (list)))
(cond ((null? xs) seen)
((eq? (caar xs) key)
(append (cdr xs) seen))
(else (loop (cdr xs) (cons (car xs) seen))))))
And here is an example:
> (first-even (5 3 5 1 5 1 3))
3
We used maximum-by from the Standard Prelude. You can run the program at http://ideone.com/NaTA1Q.
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