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

Reply via email to