<html>
  <head>
    <meta content="text/html; charset=windows-1252"
      http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <p>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).</p>
    <br>
    <div class="moz-cite-prefix">On 6/8/2017 03:30, Simon Hayward wrote:<br>
    </div>
    <blockquote
cite="mid:1496910650.2278421.1002665608.5049EA9A@webmail.messagingengine.com"
      type="cite">
      <pre wrap="">Rather than using a list, aren't deques more appropriate as a data
structure for stack like behaviour.

<a class="moz-txt-link-freetext" href="https://docs.python.org/3.6/library/collections.html#collections.deque">https://docs.python.org/3.6/library/collections.html#collections.deque</a>


Regards
Simon


On Wed, 7 Jun 2017, at 19:33, Jonathan Hartley wrote:
</pre>
      <blockquote type="cite">
        <pre wrap="">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:
</pre>
        <blockquote type="cite">
          <pre wrap="">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 <<a class="moz-txt-link-abbreviated" href="mailto:tartley@tartley.com">tartley@tartley.com</a> 
<a class="moz-txt-link-rfc2396E" href="mailto:tartley@tartley.com"><mailto:tartley@tartley.com></a>> 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 <a class="moz-txt-link-abbreviated" href="mailto:Hartleytartley@tartley.com">Hartleytartley@tartley.com</a> <a class="moz-txt-link-rfc2396E" href="mailto:tartley@tartley.com"><mailto:tartley@tartley.com></a>     <a class="moz-txt-link-freetext" href="http://tartley.com">http://tartley.com</a>
    Made out of meat.+1 507-513-1101 <a class="moz-txt-link-rfc2396E" href="tel:%28507%29%20513-1101"><tel:%28507%29%20513-1101></a>         twitter/skype: tartley

    _______________________________________________
    python-uk mailing list
    <a class="moz-txt-link-abbreviated" href="mailto:python-uk@python.org">python-uk@python.org</a> <a class="moz-txt-link-rfc2396E" href="mailto:python-uk@python.org"><mailto:python-uk@python.org></a>
    <a class="moz-txt-link-freetext" href="https://mail.python.org/mailman/listinfo/python-uk">https://mail.python.org/mailman/listinfo/python-uk</a>



_______________________________________________
python-uk mailing list
<a class="moz-txt-link-abbreviated" href="mailto:python-uk@python.org">python-uk@python.org</a>
<a class="moz-txt-link-freetext" href="https://mail.python.org/mailman/listinfo/python-uk">https://mail.python.org/mailman/listinfo/python-uk</a>
</pre>
        </blockquote>
        <pre wrap="">
-- 
Jonathan Hartley    <a class="moz-txt-link-abbreviated" href="mailto:tartley@tartley.com">tartley@tartley.com</a>    <a class="moz-txt-link-freetext" href="http://tartley.com">http://tartley.com</a>
Made out of meat.   +1 507-513-1101        twitter/skype: tartley

_______________________________________________
python-uk mailing list
<a class="moz-txt-link-abbreviated" href="mailto:python-uk@python.org">python-uk@python.org</a>
<a class="moz-txt-link-freetext" href="https://mail.python.org/mailman/listinfo/python-uk">https://mail.python.org/mailman/listinfo/python-uk</a>
</pre>
      </blockquote>
      <pre wrap="">

</pre>
    </blockquote>
    <br>
    <pre class="moz-signature" cols="72">-- 
Jonathan Hartley    <a class="moz-txt-link-abbreviated" href="mailto:tartley@tartley.com">tartley@tartley.com</a>    <a class="moz-txt-link-freetext" href="http://tartley.com">http://tartley.com</a>
Made out of meat.   +1 507-513-1101        twitter/skype: tartley

</pre>
  </body>
</html>