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

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