Amazon Interview Question Software Engineer / Developers
Team: Kindle
Country: India
Interview Type: In-Person
Here s1 and s2 are sets . union also should be a set .. means all the elements in set should be unique.
two disjoint sets means separate as mentioned in the question. The ans is perfectly acceptable compared to urs.
It does in O(1) unlike urs.
I suspect that tail works in O(N) where N is the size of the list. So in turn the above code should be O(N) not O(1) .. what you say?
@subrahmanyam Agree with your point. Since it is a dynamic link list, we can assume that we always have head and tail pointer of the list
public MyCircularDoubleLinkedList union(MyCircularDoubleLinkedList list1,MyCircularDoubleLinkedList list2){
MyCircularDoubleLinkedListNode temp1,temp2,temp3;
temp1=list1.headNode.prev;
//System.out.println("\n temp1 value"+temp1.getValue());
temp2=list2.headNode.prev;
//System.out.println("\n temp2 value"+temp2.getValue());
//System.out.println("\n head2s next value"+list2.headNode.getNext().getValue());
temp3=list2.headNode.next;
//System.out.println("\n temp3 value"+temp3.getValue());
temp1.next=temp3;
temp3.prev=temp1;
temp2.next=list1.headNode;
list1.headNode.prev=temp2;
return list1;
}
maintain 2 hashmaps on each set. when ever a element comes from set s1, check whether the element already exists in s2, if not keep in union set.
By assuming S1 and S2 are two Dynamic Link List. Append Tail S1 with head of S2. Which is of O(1).
- SRB December 10, 2012Node * Union(Node *S1, Node *S2) { TS1 = S1.Tail(); TS1->Next = S2; S1.tail = S2.tail; return S1; }