You don't need a continue in your 1st elif
You gotta draw the tree out. 7 is the parent node of 10 in that example. I got that testcase wrong in the contest too
For the second answer, I'd saw you're wrong. It's faster to use list binary search
Hardest part of this question is figuring out an efficient was to pop max. I originally was trying to do something similar to LFU cache with double linked lists, but couldn't figure out how to save the sequential maxes after popping the max. So right now I take the brute force approach of popping everything out from both stacks until we reach the max, and add the elements that were previously popped, back in.
class MaxStack(object): def __init__(self): """ initialize your data structure here. """ self.stk= self.maxstk= def push(self, x): """ :type x: int :rtype: void """ self.stk.append(x) if not self.maxstk: self.maxstk.append(x) else: self.maxstk.append(max(x,self.maxstk[-1])) def pop(self): """ :rtype: int """ self.maxstk.pop() return self.stk.pop() def top(self): """ :rtype: int """ return self.stk[-1] def peekMax(self): """ :rtype: int """ return self.maxstk[-1] def popMax(self): """ :rtype: int """ n=self.maxstk.pop() i=len(self.stk)-1 tmp= while n!=self.stk[-1]: tmp.append(self.pop()) ret=self.stk.pop() for i in xrange(len(tmp)-1,-1,-1): self.push(tmp[i]) return ret
@ztlevi What if your hash short_url is the same as another short_url in another machine? You did not discuss the case of duplicate short_urls from different machines. How would you handle this?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.