Rather than using a list, aren't deques more appropriate as a data structure for stack like behaviour.
https://docs.python.org/3.6/library/collections.html#collections.deque Regards Simon On Wed, 7 Jun 2017, at 19:33, Jonathan Hartley wrote: > Hey. > > Thanks for engaging, but I can't help with the most important of those > questions - the large data sets on which my solution failed due to > timeout are hidden from candidates. Not unreasonable to assume that they > do exercise deep stacks, and large args to add_to_first_n, etc. > > Yes, the input looks exactly like your example. All args are integers. > The question asked for output corresponding to the top of the stack > after every operation. I omitted this print from inside the 'for' loop > in 'main', thinking it irrelevant. > > I converted to integers inside 'dispatch'. 'args' must have actually > been created with: > > args = [int(i) for i in tokens[1:]] > > Where len(tokens) is never going to be bigger than 3. > > Return values (from 'pop') were unused. > > > On 6/7/2017 13:25, Stestagg wrote: > > Do you have any more context? > > For example, is the add_to_first_n likely to be called with very large > > numbers, or very often? Does the stack get very deep, or stay shallow? > > > > I'm assuming that lines look like this: > > > > push 1 > > push 2 > > add_to_first_n 2 10 > > pop > > pop > > > > with all arguments as integers, and the final value being returned > > from main()? > > How did you convert from string inputs to numeric values? > > How did you manage return values? > > > > :D > > > > On Wed, Jun 7, 2017 at 6:51 PM Jonathan Hartley <tart...@tartley.com > > <mailto:tart...@tartley.com>> wrote: > > > > I recently submitted a solution to a coding challenge, in an > > employment context. One of the questions was to model a simple > > stack. I wrote a solution which appended and popped from the end > > of a list. This worked, but failed with timeouts on their last few > > automated tests with large (hidden) data sets. > > > > From memory, I think I had something pretty standard: > > > > class Stack: > > > > def __init__(self): > > self.storage = [] > > > > def push(arg): > > self.storage.append(arg) > > > > def pop(): > > return self.storage.pop() if self.storage else None > > > > def add_to_first_n(n, amount): > > for n in range(n): > > self.storage[n] += amount > > > > def dispatch(self, line) > > tokens = line.split() > > method = getattr(self, tokens[0]) > > args = tokens[1:] > > method(*args) > > > > def main(lines): > > stack = Stack() > > for line in lines: > > stack.dispatch(line) > > > > > > (will that formatting survive? Apologies if not) > > > > Subsequent experiments have confirmed that appending to and > > popping from the end of lists are O(1), amortized. > > > > So why is my solution too slow? > > > > This question was against the clock, 4th question of 4 in an hour. > > So I wasn't expecting to produce Cython or C optimised code in > > that timeframe (Besides, my submitted .py file runs on their > > servers, so the environment is limited.) > > > > So what am I missing, from a performance perspective? Are there > > other data structures in stdlib which are also O(1) but with a > > better constant? > > > > Ah. In writing this out, I have begun to suspect that my slicing > > of 'tokens' to produce 'args' in the dispatch is needlessly > > wasting time. Not much, but some. > > > > Thoughts welcome, > > > > Jonathan > > > > -- > > Jonathan hartleytart...@tartley.com <mailto:tart...@tartley.com> > > http://tartley.com > > Made out of meat.+1 507-513-1101 <tel:%28507%29%20513-1101> > > twitter/skype: tartley > > > > _______________________________________________ > > python-uk mailing list > > python-uk@python.org <mailto:python-uk@python.org> > > https://mail.python.org/mailman/listinfo/python-uk > > > > > > > > _______________________________________________ > > python-uk mailing list > > python-uk@python.org > > https://mail.python.org/mailman/listinfo/python-uk > > -- > Jonathan Hartley tart...@tartley.com http://tartley.com > Made out of meat. +1 507-513-1101 twitter/skype: tartley > > _______________________________________________ > python-uk mailing list > python-uk@python.org > https://mail.python.org/mailman/listinfo/python-uk -- Simon si...@fastmail.to _______________________________________________ python-uk mailing list python-uk@python.org https://mail.python.org/mailman/listinfo/python-uk
