Amazon Interview Question for SDE1s


Team: AWS Auto Scaling
Country: United States
Interview Type: Phone Interview




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

Use a LinkedList and a HashMap<Id, ListNode<T>>

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

- guilhebl May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't we just use a LinkedHashSet<Object> set instead ?
1. For ever insert : check if set.contains(o1)
=> if true : remove it (since it is no longer unique now).
=> if false : add to the set using set.add(o1)
2. To get first unique , Iterator i = set.iterator; print(i.next())

- Mayank Jain September 24, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.)
=====

- NoOne June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- ali.kheam June 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
			
		}
	
	}

}

- divm01986 June 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- lostintranslation June 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about using a deque?

deque<int> v;

void insert_unique(int i){
    if(v.size()>0 && i == v.front())
    {
        v.pop_front();
    }else{
        v.push_back(i);
    }
}
int get_unique()
{
    return v.size()>0 ? v.front() : -1;
}

- neo2005 June 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about using a deque?

deque<int> v;

void insert_unique(int i){
    if(v.size()>0 && i == v.front())
    {
        v.pop_front();
    }else{
        v.push_back(i);
    }
}
int get_unique()
{
    return v.size()>0 ? v.front() : -1;
}

- ddddneo2006 June 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

deque<int> v;

void insert_unique(int i){
    if(v.size()>0 && i == v.front())
    {
        v.pop_front();
    }else{
        v.push_back(i);
    }
}
int get_unique()
{
    return v.size()>0 ? v.front() : -1;
}

- ddddneo2006 June 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about using a deque?

deque<int> v;

void insert_unique(int i){
    if(v.size()>0 && i == v.front())
    {
        v.pop_front();
    }else{
        v.push_back(i);
    }
}
int get_unique()
{
    return v.size()>0 ? v.front() : -1;
}

- neo2006 June 27, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More