CareerCup

Looking for help on interview preparation?
Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

Customized course covers
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. every aspect you need in a coding interview and Clean Coding)
Interview questions sorted by companies
Mock Interviews

Our members got into G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!


SOLUTION
The push, pop and inc can all take place in O(1) time
if there is an additional array to maintain the m incremented at each position n.

class Stack:
    def __init__(self):
        self.nums = []
        self.add = []
    
    def push(self,num):
        self.nums.append(num)
        self.add.append(0)
        print num," "
        
    def pop(self):
        try:
            number_to_add = self.add.pop()
            print self.nums.pop() + number_to_add
            if self.add:
                self.add[-1] += number_to_add
        except:
            print "can't pop from an empty stack"
            
    def inc(self, n, m):
        if not self.nums:
            print "empty"
        if n > 0:
            n = min(n, len(self.nums))
            self.add[n - 1] += m
        print self.nums[-1] + self.add[-1], " "

push(Integer i) {
	stack.push(i);
	size++;
	last_index = Math.min(m,size);
}

pop() {
	return null;
	if(size>m) {
	  return stack.pop();
	} else {
	   size--;
	   last_index = Math.min(m,size);
	   return stack.pop()+1;
	}
}

push(Integer i) {
stack.push(i);
size++;
last_index = Math.min(m,size);
}

pop() {
return null;
if(size>m) {
return stack.pop();
} else {
size--;
last_index = Math.min(m,size);
return stack.pop()+1;
}
}