<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hey.<br>
<br>
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.<br>
<br>
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.<br>
<br>
I converted to integers inside 'dispatch'. 'args' must have actually
been created with:<br>
<br>
<font face="Consolas" size="-2">args = [int(i) for i in tokens[<font
color="#993399">1</font>:]]</font><br>
<br>
Where len(tokens) is never going to be bigger than 3.<br>
<br>
Return values (from 'pop') were unused. <br>
<br>
<br>
<div class="moz-cite-prefix">On 6/7/2017 13:25, Stestagg wrote:<br>
</div>
<blockquote
cite="mid:CACFDE8ZpFN2YNBRe-bj1+RE_1iGOm63f8=5ferzxApONbnc1JQ@mail.gmail.com"
type="cite">
<div dir="ltr">Do you have any more context?
<div>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?
<div><br>
</div>
<div>I'm assuming that lines look like this:</div>
<div><br>
</div>
<div>push 1</div>
<div>push 2</div>
<div>add_to_first_n 2 10</div>
<div>pop</div>
<div>pop</div>
<div><br>
</div>
<div>with all arguments as integers, and the final value being
returned from main()?</div>
<div>How did you convert from string inputs to numeric values?</div>
<div>How did you manage return values?</div>
<div><br>
</div>
<div>:D</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr">On Wed, Jun 7, 2017 at 6:51 PM Jonathan Hartley
<<a moz-do-not-send="true"
href="mailto:tartley@tartley.com">tartley@tartley.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<p>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.</p>
<p> From memory, I think I had something pretty standard:</p>
<p><font face="Consolas" size="-2"><font color="#3333ff">class
</font>Stack:<br>
<br>
<font color="#3333ff">def </font>__init__(self):<br>
self.storage = []<br>
<br>
<font color="#3333ff">def </font>push(arg):<br>
self.storage.append(arg)<br>
<br>
<font color="#3333ff">def </font>pop():<br>
<font color="#3333ff">return </font>self.storage.pop()
if self.storage else None<br>
<br>
<font color="#3333ff">def </font>add_to_first_n(n,
amount):<br>
<font color="#3333ff">for </font>n <font
color="#3333ff">in </font><font color="#009900">range</font>(n):<br>
self.storage[n] += amount<br>
<br>
<font color="#3333ff">def </font>dispatch(self,
line)<br>
tokens = line.split()<br>
method = <font color="#009900">getattr</font>(self,
tokens[<font color="#993399">0</font>])<br>
args = tokens[<font color="#993399">1</font>:]<br>
method(*args)<br>
<br>
<font color="#3333ff">def </font>main(lines):<br>
stack = Stack()<br>
<font color="#3333ff">for </font>line <font
color="#3333ff">in </font>lines:<br>
stack.dispatch(line)</font><br>
</p>
<p><br>
</p>
<p>(will that formatting survive? Apologies if not)<br>
</p>
<p>Subsequent experiments have confirmed that appending to
and popping from the end of lists are O(1), amortized.</p>
So why is my solution too slow?<br>
<br>
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.)<br>
<br>
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?<br>
<br>
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.<br>
<br>
Thoughts welcome,<br>
<br>
Jonathan<br>
<pre class="m_-7825971627947445388moz-signature" cols="72">--
Jonathan Hartley <a moz-do-not-send="true" class="m_-7825971627947445388moz-txt-link-abbreviated" href="mailto:tartley@tartley.com" target="_blank">tartley@tartley.com</a> <a moz-do-not-send="true" class="m_-7825971627947445388moz-txt-link-freetext" href="http://tartley.com" target="_blank">http://tartley.com</a>
Made out of meat. <a moz-do-not-send="true" href="tel:%28507%29%20513-1101" value="+15075131101" target="_blank">+1 507-513-1101</a> twitter/skype: tartley
</pre>
</div>
_______________________________________________<br>
python-uk mailing list<br>
<a moz-do-not-send="true" href="mailto:python-uk@python.org"
target="_blank">python-uk@python.org</a><br>
<a moz-do-not-send="true"
href="https://mail.python.org/mailman/listinfo/python-uk"
rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/python-uk</a><br>
</blockquote>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
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>
<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>