Meena Chaudhary
BAN USERnext() and previous() ca be easily done with two stacks as shown above. But addLast() can be achieved in O(1) only if the last element is always at the top of the stack(which comes with a cost of popping elements back to the first stack). Using a pair of two stacks for maintaining the head and tail of the list is not a good idea because if we add element to one pair of stacks the same should be added to the second pair of stacks too. And that will cost O(n) which is not good. Two pair of stacks solution is feasible but not efficient.
- Meena Chaudhary February 13, 2015we can achieve O(logN) time complexity for getNumber() and requestNumber(Number) using BST for storing unassigned numbers and Set for assigned numbers.
getNumber(){
number = BST.remove
Set.add(number)
}
requestNumber(number){
if(!Set.contains(number)){
BST.remove(number)
Set.add(number)
return true;
} else {
return false;
}
}
How about a Bipartite graph where we have two sets. One of patients and other of problems. An edge exists between a node in patient set and a node in problem set if that patient has that problem. That way picking a problem from the set we can easily find out any 3 nodes it is connected to in patient set.
- Meena Chaudhary February 13, 2015