## 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.

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…

In Python.

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:

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.

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!

And the program for part 2

# 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:

===========================================

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

==================================

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