On 13/06/2017 16:29, Jonathan Hartley wrote:
On 06/13/2017 09:04 AM, Mark Lawrence via python-uk wrote:
On 07/06/2017 18:50, Jonathan Hartley 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 sol
On 06/13/2017 09:04 AM, Mark Lawrence via python-uk wrote:
On 07/06/2017 18:50, Jonathan Hartley 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 o
On 07/06/2017 18:50, Jonathan Hartley 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 las
Very interesting! Thanks for digging deeper and sharing.
I was thinking about horrible complicated structures like storing the
'add_to_first_n' params in parallel to the stack, to apply them at 'pop'
time, which doesn't work at all. As is so often the case with these
things, your solution of
You are right, when popping an empty stack I should probably raise.
On 2017-06-08 13:06, Samuel F wrote:
It may have failed for a different reason, (hard to say without the
original question and answer).
In the case where the stack is empty, you are returning None, was that
the requirement? (
I was able to get about a 20% speed up over Steve's solution, on some
benchmark data I created, by:
* converting LOAD_GLOBAL to LOAD_FAST for __builtins__
* eliminating the conditional in each loop in favour of a conditional on
pop only
* eliminating string comparison for the operation in favour o
Apologies, In my previous email, I meant 'insert a marker', rather than
'push a marker'
On Thu, Jun 8, 2017 at 7:17 PM Stestagg wrote:
> I tracked down the challenge on the site, and have a working solution (I
> won't share for obvious reasons). Basically the timeouts were being caused
> by 'add
I tracked down the challenge on the site, and have a working solution (I
won't share for obvious reasons). Basically the timeouts were being caused
by 'add_to_first_n' being called in horrible ways in the test cases.
Because add_to_first_n alters the bottom of the stack, you can just push a
marker
It may have failed for a different reason, (hard to say without the
original question and answer).
In the case where the stack is empty, you are returning None, was that the
requirement? (Likely to have been -1)
Sam
On Thu, 8 Jun 2017 at 17:27, Jonathan Hartley wrote:
> Yep, that's a great el
Yep, that's a great elimination of the suspicious small overheads.
line_profiler is beautiful, I'll definitely be adding it to my toolbox,
thanks for that!
I tried a variant of accumulating the output and printing it all as a
single string, but of course this didn't help, printing is already
If it's who I think it is, then I'm not entirely surprised, this particular
implementation is quite taxing for python in particular, and they don't do
much in the way of catering to more modern languages in general (not a
criticism, but most problems/samples are stated in a very 'traditional' way
t
Good point. FWIW, my submission was running Python 3.
On 6/8/2017 04:33, Toby Dickenson wrote:
In python 2, your use of range() without checking for a very large
parameter n might cause either a MemoryError exception, or trigger a
huge memory allocation just for the range list. Not a problem in
I cannot be sure. It is certainly used by many people. They are
competent in that it is a comprehensive online framework, allowing
candidates to submit solutions using an online editor, in any one of
about ten different languages. They are so large that there was no
obvious way to talk to anyon
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
In python 2, your use of range() without checking for a very large
parameter n might cause either a MemoryError exception, or trigger a
huge memory allocation just for the range list. Not a problem in
python 3 of course.
On 8 June 2017 at 09:54, Stestagg wrote:
> I honestly can't see a way to im
I honestly can't see a way to improve this in python. My best solution is:
def main(lines):
stack = []
sa = stack.append
sp = stack.pop
si = stack.__getitem__
for line in lines:
meth = line[:3]
if meth == b'pus':
sa(int(line[5:]))
elif meth
Are you sure that their test infrastructure was behaving correctly?
Is it widely used, day in day out, by thousands, and known to be
reliable? Did your colleagues all brag "no problem"? Or is it
possible that the whole execution framework threw a momentary wobbly
while trying to load up some larg
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 wi
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 inp
Algorithms questions are always fun. Quick time to answer before other
people!
You might be hitting problems with the "amortized part" if their code
didn't run for large enough n or used dumb special cases or bounds. They
may have (inadvertantly?) meant "realtime constant" (python lists
occasional
On 7 June 2017 at 18:50, Jonathan Hartley wrote:
> 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.
To put some numbers out there, eliminating the slice is not always a
win. On Python
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 fi
22 matches
Mail list logo
