Amazon Interview Question Applications Developers
Country: United States
Interview Type: In-Person
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.
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];
}
}
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?
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
{
dict.Add(i, 1);
}
}
foreach (KeyValuePair<int, int> kp in dict)
{
if (kp.Value.Equals(1))
{
firstNumber = kp.Key;
break;
}
}
return firstNumber;
}
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.
{
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;
}
}
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
}
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
}
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))
{
dic.Add(item, 1);
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;
}
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;
}
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;
}
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
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;
}
// 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
{
distinct.Add(arr[i]);
}
}
if (distinct.Count > 0)
{
Console.WriteLine("First Non Repeating: " + distinct[0]);
}
else
{
Console.WriteLine("No Non Repeating Numbers.");
}
}
Use a LinkedHashMap which will retain the insertion order:
- mariovalentim December 16, 2015int[] a = {5,7,8,9,2,3,5,2,7,0}; LinkedHashMap<Integer, Boolean> m = new LinkedHashMap<>(); 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; } }