## Amazon Interview Question for Applications Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Use a LinkedHashMap which will retain the insertion order:

int[] a = {5,7,8,9,2,3,5,2,7,0};
for(int n : a){
m.put(n, m.containsKey(n));
}

for (Entry<Integer, Boolean> e : m.entrySet()) {
if(!e.getValue()){
System.out.println(e.getKey());
return;
}
}

Comment hidden because of low score. Click to expand.
0

Just for an explanation as to why we should use a LinkedHashMap instead of a regular HashMap:
LinkedHashMap maintains the insertion order, whereas a regular hashmap cannot guarantee the insertion order. Since the question specifies the 'first' non-duplicate, order matters. Just a tidbit.
Also, I'm not sure if LinkedHashMap is available in all modern languages; this is a Java implementation.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Assuming int array

public int firstNonRepeat(int[] input){
for(int i = 0; i < input.length; i++) {
boolean foundDuplicate = false;

for(int j = 1; j < input.length && !foundDuplicate; j++) {
foundDuplicate = input[j] == input[i];
}

if(!foundDuplicate)
return input[i];
}
}

Comment hidden because of low score. Click to expand.
0

return -1; outside of outer for loop

Comment hidden because of low score. Click to expand.
0

The inner for loop should not check equality for the i-th element. That is, it should not be checking equality on the same index as well. I think you missed that.

if(i != j )
foundDuplicate = input[j] == input[i];

Is that correct?

Comment hidden because of low score. Click to expand.
0

Inner loop should run from j = i +1 to length. Why would you want to look elements before ith element again. If they were similar, they would've been caught earlier itself. Also if array modification is allowed, delete subsequent matches if found one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

static int FirstNonRepeated(IEnumerable<int> iArr)
{
Dictionary<int, int> dict = new Dictionary<int,int>();
int count = 0;

int firstNumber = -1;

foreach (int i in iArr)
{
if (dict.ContainsKey(i))
{
dict.TryGetValue(i, out count);
dict[i] = count++;
}
else
{
}

}

foreach (KeyValuePair<int, int> kp in dict)
{
if (kp.Value.Equals(1))
{
firstNumber = kp.Key;
break;
}

}

return firstNumber;
}

Comment hidden because of low score. Click to expand.
0

Not sure is correct this approach because the Dictionary store the values according the hash value, not the way they are added, so not guarantee the first 1 value is the first not repeated element.

Comment hidden because of low score. Click to expand.
0

@hnatsu is correct. Use a LinkedHashMap (to guarantee insertion order) and you should be good to go.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumption, You know the range of values.

bool[] flagArray = new bool[range]; // default value is false
for(i=0;i<arr.length;i++)
{
var value = arr[i];
if(!flagArray[value])
{
flagArray[value] = true;
}
else
{
Console.Wrilteline("Duplicate ", arr[i]);
break;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
int firstNonrepeatedNumber(int[] array) {
Map<Integer, Boolean> map = new LinkedHashMap<>();
for(int i: array) {
if(map.containsKey(i)) {
map.put(i,true);
} else {
map.put(i,false);
}
}
//Iterate on map to get first key with false value
Set<Integer> set = map.keySet();
int res = -1;
for(int i: set) {
if(map.get(i) == false) {
res = i;
break;
}
}
return res;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int firstNonRepeatElemInUnsortedArr(int arr[], int size)
{
int repeatFlag = 0;
map <int, int> ElemWithElemCount;
for(int i=0; i < size; i++)
{
repeatFlag = 0;
for(int j = i+1; j < size; j++)
{
if(!ElemWithElemCount.count(arr[i]) >0 )
ElemWithElemCount[arr[i]] = 1;
if(arr[i] == arr[j])
{
ElemWithElemCount[arr[i]] = ElemWithElemCount[arr[i]] + 1;
repeatFlag = 1;
break;
}
}
if(repeatFlag == 0 && ElemWithElemCount[arr[i]] ==1)
return arr[i];
}
return -1; //If no repeat element found
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int firstNonRepeatElemInUnsortedArr(int arr[], int size)
{
int repeatFlag = 0;
map <int, int> ElemWithElemCount;
for(int i=0; i < size; i++)
{
repeatFlag = 0;
for(int j = i+1; j < size; j++)
{
if(!ElemWithElemCount.count(arr[i]) >0 )
ElemWithElemCount[arr[i]] = 1;
if(arr[i] == arr[j])
{
ElemWithElemCount[arr[i]] = ElemWithElemCount[arr[i]] + 1;
repeatFlag = 1;
break;
}
}
if(repeatFlag == 0 && ElemWithElemCount[arr[i]] ==1)
return arr[i];
}
return -1; //If no rrepeat element found
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int? FindFirstNorepeating(int[] values)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
Queue<int> queue = new Queue<int>();

foreach (var item in values)
{
if (!dic.ContainsKey(item))
{
queue.Enqueue(item);
continue;
}

dic[item] = dic[item] + 1;
if (queue.Count > 0 && item == queue.Peek())
{
while (queue.Count > 0)
{
var first = queue.Peek();
if (dic[first] == 1)
break;
queue.Dequeue();
}
}
}

return queue.Count > 0 ? (int?)queue.Peek() : null;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just to be clear....shouldnt the first element itself be the first non-repeated element

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;

/**
* Find first non repeated element from unsorted array.
*
* Time complexity:O(1) Space complexity:O(n), here n is number of elements in
* the array.
*
* @author dmpatel
*
*/
public class FindFirstNonRepeatedElement {

public static void main(String[] args) {
int a1[] = new int[] { 5, 7, 8, 9, 2, 3, 5, 2, 7, 0 };
int a2[] = new int[] { 5, 7, 8, -1, 0, 4 };
try {
int element = findFirstNonRepeatedElement(a1);
System.out.println("First Non Repeated Element=" + element);
} catch (InvalidInputException e) {
System.out.println(e.getMessage());
}
}

private static int findFirstNonRepeatedElement(int[] a)
throws InvalidInputException {
Integer element = null;
if (null == a || a.length == 0) {
throw new InvalidInputException("Invalid input");
}
int aLength = a.length;
Map<Integer, Boolean> map = new HashMap<Integer, Boolean>(aLength);
int aElement = 0;
for (int i = 0; i < aLength; i++) {
aElement = a[i];
if (!map.containsKey(aElement)) {
map.put(aElement, true);
} else {
map.put(aElement, false);
}
}
for (int i = 0; i < aLength; i++) {
aElement = a[i];
if (!map.get(aElement)) {
element = aElement;
break;
}
}
if (null == element) {
throw new InvalidInputException("Invalid input");
}
return element;
}
}

class InvalidInputException extends Exception {

public InvalidInputException(String message) {
super(message);
}

/**
* Generated serial version id.
*/
private static final long serialVersionUID = 5890758270469708368L;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;

/**
* Find first non repeated element from unsorted array.
*
* Time complexity:O(1) Space complexity:O(n), here n is number of elements in
* the array.
*
* @author dmpatel
*
*/
public class FindFirstNonRepeatedElement {

public static void main(String[] args) {
int a1[] = new int[] { 5, 7, 8, 9, 2, 3, 5, 2, 7, 0 };
int a2[] = new int[] { 5, 7, 8, -1, 0, 4 };
try {
int element = findFirstNonRepeatedElement(a1);
System.out.println("First Non Repeated Element=" + element);
} catch (InvalidInputException e) {
System.out.println(e.getMessage());
}
}

private static int findFirstNonRepeatedElement(int[] a)
throws InvalidInputException {
Integer element = null;
if (null == a || a.length == 0) {
throw new InvalidInputException("Invalid input");
}
int aLength = a.length;
Map<Integer, Boolean> map = new HashMap<Integer, Boolean>(aLength);
int aElement = 0;
for (int i = 0; i < aLength; i++) {
aElement = a[i];
if (!map.containsKey(aElement)) {
map.put(aElement, true);
} else {
map.put(aElement, false);
}
}
for (int i = 0; i < aLength; i++) {
aElement = a[i];
if (!map.get(aElement)) {
element = aElement;
break;
}
}
if (null == element) {
throw new InvalidInputException("Invalid input");
}
return element;
}
}

class InvalidInputException extends Exception {

public InvalidInputException(String message) {
super(message);
}

/**
* Generated serial version id.
*/
private static final long serialVersionUID = 5890758270469708368L;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple O(n) solution in Python.

def first_non_repeated(lst):
d = {}
for i in lst:
d[i] = d.get(i, 0) + 1
for i in lst:
if d[i] == 1:
return i

Comment hidden because of low score. Click to expand.
0

This is not O(n)..

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findNonRepeatedElement(int[] array){
int firstNum = -1;
Map<Integer, Boolean> map = new LinkedHashMap<>();
for(int index = 0;index<array.length;index++){
if(!map.containsKey(array[index])){
map.put(array[index], false);
}
else
map.put(array[index], true);
}
for(Entry<Integer, Boolean> e: map.entrySet()){
if(!e.getValue()){
firstNum = e.getKey();
break;
}
}
return firstNum;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

// C# version without dictionary

public static void FindFirstNotRepeated()
{
var arr = new int[] { 5, 7, 8, 9, 2, 3, 5, 2, 7, 0 };
var distinct = new List<int>();

for (int i = 0; i < arr.Length; i++)
{
if (distinct.Contains(arr[i]))
{
distinct.Remove(arr[i]);
}
else
{
}
}

if (distinct.Count > 0)
{
Console.WriteLine("First Non Repeating: " + distinct[0]);
}
else
{
Console.WriteLine("No Non Repeating Numbers.");
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.