Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Created a Dictionary to hold key/value for elements that occur only once, with the value being their index in the list which we need to determine which one is the first occurrence. The hashtable holds the elements that occur more than once and we ignore those. Algo goes 1x through the list ignoring a string that is in the Hashtable (multiple) already, inserting into to the Dictionary (single) if not present, and moving from single to multiple if this is a first repeat. Result is Dictionary of unique elements whose values are their indexes. Loop through the resulting dictionary returning the key for the smallest value.
Since the hashtable and dictionary lookups are 0(1), I think this algo is 0(2n) where n is the number of elements in the list. Would happily except correction here if my big O performance assessment is wrong :)
protected string GetFirstUnique(List<string> baseList)
{
Dictionary<string,int> single = new Dictionary<string,int>();
Hashtable multiple = new Hashtable();
string retVal = null;
int minIndex = int.MaxValue;
for (int index = 0; index < baseList.Count; index++)
{
string str = baseList[index];
if (!multiple.ContainsKey(str))
{
if (single.ContainsKey(str))
{
single.Remove(str);
multiple.Add(str, 0);
}
else
{
single.Add(str, index);
}
}
}
foreach (var e in single)
{
if (e.Value < minIndex)
retVal = e.Key;
}
return retVal;
}
There is a sample of doing this with integers, and you xor all the values together, and it spits out the one unique value. If you could encode these to big integers, xor them all, and then reverse the encoding, the same concept would apply.
You could do this with a hashing function (say, CRC or MD5 for simplicity), but you'd need to maintain a table of hash->value. You'd have O(N) storage, and O(N) for processing (keeping elements in a hashtable)
Pseudocode:
sum = bigint()
map = hashmap()
for element in list:
h = hash(element)
map[h] = element
sum ^= h
print map[sum]
>>> a=['a','b','c','b','a','d']
>>> b=list(set(a))
>>> for i in b:
... count=0
... for j in a:
... if i==j:
... count=count+1
... if count==2:
... break
... if count==1:
... print i
...
c
d
Here is a HashMap Based solution
public String findDuplicate(String[] inputStrings){
Map<String,Integer> inputMap = new HashMap<>();
int count;
String uniqueString="";
for(String input : inputStrings){
if(inputMap.containsKey(input)){
count = inputMap.get(input).intValue();
count++;
inputMap.put(input, count);
}else{
inputMap.put(input, 1);
}
}
for(String input : inputStrings){
if(inputMap.containsKey(input) && inputMap.get(input).intValue() ==1){
uniqueString = input;
break;
}
}
return uniqueString;
}
package com.collection2;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class UniqueElement {
public static List<String> value;
public static Map<String, Integer> MappedValues = new HashMap<String, Integer>();
public static String uniqueval = null;
public static String str = "";
public UniqueElement() {
value = new ArrayList<String>();
value.add("BH");
value.add("BH");
value.add("F");
value.add("AL");
value.add("HJ");
value.add("AL");
value.add("HJ");
value.add("PK");
System.out.println(value);
}
protected String myVal(List<String> val) {
for (int i = 0; i < val.size(); i++) {
int count = 0;
str = val.get(i);
for (String key : val) {
if (key == str) {
count++;
MappedValues.put(str, count);
}
MappedValues.put(str, count);
}
}
for (String uniq : val) {
if (MappedValues.containsKey(uniq)
&& MappedValues.get(uniq).intValue() == 1) {
uniqueval = uniq;
break;
}
}
return uniqueval;
}
public static void main(String[] args) {
UniqueElement a = new UniqueElement();
a.myVal(value);
System.out.println(MappedValues);
System.out.println(uniqueval);
}
}
I would do it in the following way....
Step 1: Iterate through all the elements in the list
Step 2: Insert each element in a set if its not there, else remove from the set.
Step 3: once end of list occurs, Iterate through the set and print if any element, else "print no unique element"
Well the person who down flagged it please be courteous enough to drop the reason for the same. Also this solution works as I have tried and tested it using JAVA
@Madhur do u think set can have duplicate into it?
Given a list with duplicate values find the first unique elements in it.
and From Ex : BH BH F AL HJ AL HJ PK
according to ur logic the O/P should be F PK
how u will decide which one is First Unique element?
I need the first unique element
my solution is :
1. Insert the elements of the list into hashmap as Key and a count as value.
2. Before insert check the key into hashmap
if the key is present make the value as negative
else insert into the hashmap and increase the count value
3. After iterating the whole list,search for the key whose value is least +ve value
and that is the answer.
geeksforgeeks.org/find-first-non-repeating-character-stream-characters/
- Nitin April 03, 2014Use hashmap to uniquely identify keys in place of repeated array.