Amazon Interview Question
SDE1sTeam: AWS Auto Scaling
Country: United States
Interview Type: Phone Interview
In Java, you want to use a :
[ docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html ]
to maintain objects as keys and their count as values And you are good.
====
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)
=====
I have not used the linked list hashtable, as it is not available in c++. I just learned that there is also a mapped hashtable available in java.
Given not knowing this hashtable -->linked list datastructure. I initially thought of having two hashtables.
1) First hashtable has the entries which are seen just once
2) second hashtable has duplicate entries
process is like this.
a) for any new entry, do a look up into second table, if present Ignore the entry
b) if no entry in hashtable 2, look up into table 1
b1), if found in table 1, remove entry into the table 1 and insert into table 2.
b 2) else insert into table 1.
c) a and b will provide the separation of single vs multiple entries for O(1) access time,
d) to query the oldest first entry, we need look up into the table 1. In Table 1, we keep the entries as unordered_map<entry, time stamp> where the time stamp is the entry# (or any monotonically increasing number). Do the iteration of the table 1 and find the lower count .
e) The linked hashtable provide this facility
Hence I propose this solution
#include <iostream>
using namespace std;
#include <unordered_map>
#include <list>
#include <algorithm>
#include <functional>
struct entry {
entry(int i): id(i) {}
int id;
};
class hash_s {
public:
size_t operator() (const entry &e) const {
return std::hash<int>()(e.id);
}
};
class comp_s {
public:
bool operator() (const entry &l, const entry &r) const {
if (l.id == r.id ) {
return true;
}
return false;
}
};
class not_found_exception:std::exception {
string str_reason;
public:
not_found_exception(const char *input) : str_reason(input) {}
virtual const char *what() const throw() {
return str_reason.c_str();
}
};
class linked_hash {
unordered_map<entry, list<entry>::iterator, hash_s, comp_s> sobject;
list<entry> lobjects;
public:
void insert_object(int i) {
entry en(i);
unordered_map<entry, list<entry>::iterator, hash_s, comp_s>::iterator it =
sobject.find(en);
if (it != sobject.end()) {
// found it
if (it->second != lobjects.end()) {
// if this is more than the first time.
lobjects.erase(it->second);
it->second = lobjects.end();
}
return;
}
// first time
lobjects.push_front(en);
sobject.insert(pair<entry, list<entry>::iterator>(en, lobjects.begin()));
}
entry get_first_non_repeating() {
if (!lobjects.empty()) {
return lobjects.back();
}
throw not_found_exception("No non repeating element");
}
};
int main() {
// your code goes here
return 0;
}
//Assumptions: Object has a getId() method which generates a unique integer similar to hash code. All operations are O(1)
public class ObjectSvc{
private static class Node{
Object obj;
Node prev;
Node next;
Node(Object ob){
obj = ob;
}
}
Map<Integer,Node> mp;
Set<Integer> seen;
Node head;
Node tail;
public ObjectSvc(){
mp = new HashMap<Integer,Node>();
seen = new HashSet<Integer>();
}
public Object getUnique(){
if(head == null){
return null;
}
return head;
}
public void addObject(Object obj){
int id = obj.getId();//could be hash code.
if(mp.containsKey(id)){
Node n = mp.get(id);
mp.remove(id);
removeNode(n);
seen.add(id);
}else{
if(!seen.contains(id)){
Node n = new Node(obj);
mp.put(id,n);
addNode(n);
}
}
}
private void addNode(Node n){
if(head == null){
head = n;
tail = n;
}else{
tail.next = n;
n.prev = tail;
tail = tail.next;
}
}
private void removeNode(Node x){
if(head == x){
Node tmp = head.next;
if(tmp != null){
tmp.prev = null;
head.next = null;
head = tmp;
}else{
head = null;
tail = null;
}
}
else if(tail == x){
Node tmp = tail.prev;
tmp.next = null;
tail.prev = null;
tail = tmp;
}else{
x.prev.next = x.next;
x.next.prev = x.prev;
x.prev = null;
x.next = null;
}
}
}
We can use a linkedhashset(contains unique items) and hashset(contains repeated items) for the purpose. On reading an element if it is there in linkedhashset or hashset add it to hashset. Else if the item is not their on both linkedhashset and hashset add it to hashset. Whenever asked get the first element of linkedhashset.
Use a LinkedList and a HashMap<Id, ListNode<T>>
- guilhebl May 31, 2017LinkedList - preserve the order of first seen objects
HashMap - keep track of those already seen and keep a reference for the ListNode of all first time seen elements
for every element of stream:
1. if first time seen (element ID is not in Map): insert it on end of LinkedList also insert ListNode reference in Map
2. else if already seen (element exists in Map): get ListNode reference from Map and use it to find Prev and Next nodes of the Object's ListNode, make LIstNode.Prev->Next = Next (eliminate this node from linked list). Set Map Value to Null, so in Map it would be <Key = Obj.ID, Value = NULL> this way we can keep track of those already seen.
At the end of the stream, select HEAD element from LinkedList, if empty return Null.