I wondered about that too, but decided (without measuring) that it is no
better. A deque allows us to append and pop elements from both ends, but
the question didn't require that, it only needed from one end, which a
list provides at O(1).
On 6/8/2017 03:30, Simon Hayward wrote:
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
--
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
