4 ms·
I am not a Python programmer -- but since you are (at least you've coded non-trivial things in it) -- I've chosen it for this (brief) exercise. During the exerc
by sulam 10y ago
I am not a Python programmer -- but since you are (at least you've coded non-trivial things in it) -- I've chosen it for this (brief) exercise. During the exercise I had to 1) type this post. 2) Google how to write a Python class. 3) Write down some code. 4) test it quickly in a REPL. I started at 11:30am local time. I am on shitty coffee-house wifi so googling was pretty slow by any standard. I finished at 11:45 -- which includes the testing (and at least one silly mistake)...
[GCC 4.2.1 Compatible Apple LLVM 7.0.0 (clang-700.0.59.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> class LinkedList(object):
... def __init__(self, value):
... self.value = value
... self.next = None
... def insert(self, value):
... el = LinkedList(value)
... el.next = self
... return el
...
>>> list = LinkedList("baz")
>>> list = list.insert("bar")
>>> list = list.insert("foo")
>>> list.value
'foo'
>>> list.value.next.value
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'str' object has no attribute 'next'
>>> list.next.value
'bar'
>>> list.next.next.value
'baz'
>>>
I do not have a CS background (I've never taken a CS class in my life). I also think this is shitty code! Some immediate things I would talk about with the interviewer include:
1) list.insert is awkward, fixing it would require the notion of a head pointer, but I didn't want to waste the memory for what is meant to be a simple example and keeping the API convenient would require the introduction of another type I think.
2) Despite having semantics that look mildly immutable on their face, it's not immutable, and probably not thread safe (I don't know Python's memory model).
3) I haven't written any tests. I don't know how to write a Python unit test, but if I did it would take about 60s to write one.
I could probably have a good conversation with them about this code a similar implementation in Golang (another language I don't know, with strict types but no generics, so the implementation would either be less general or <handwave about Go interfaces>).
Do you really think you couldn't produce this code when asked? The point I'm trying to make here is not that you're dumb, or that I'm some sort of super genius (hopefully that's obviously not true!) but that writing a linked list is truly trivial!
- sulam 10y agoBtw, the self.next in the __init__ block was a little unexpected and probably consumed the majority of the time writing the code not counting writing the text of the post.
- DonaldFisk 10y agoHere's my implementation, using tuples. But bear in mind that for almost everything Python's used for, Python lists (i.e. vectors) are good enough. def cons(x, y): return (x, y) def car(x): return x if x == () else x[0] def cdr(x): return x if x == () else x[1] def append(x, y): return y if x == () else cons(car(x), append(cdr(x), y)) def rev(x, y): return y if x == () else rev(cdr(x), cons(car(x), y)) def reverse(x): return rev(x, ()) def null(x): return x == () def list(*tuple): if len(tuple) < 1: return () else: x = () for i in reversed(range(len(tuple))): x = cons(tuple[i], x) return x def mapcar(fn, x): return () if x == () else cons(apply(fn, (car(x),)), mapcar(fn, cdr(x))) ---------------------- >>> import sexpr >>> print sexpr.cons(1, 2) (1, 2) >>> x = sexpr.list(1, 2, 3, 4) >>> print x (1, (2, (3, (4, ())))) >>> print sexpr.reverse(x) (4, (3, (2, (1, ())))) >>> print x (1, (2, (3, (4, ())))) >>> print sexpr.append(x, sexpr.cdr(sexpr.reverse(x))) (1, (2, (3, (4, (3, (2, (1, ()))))))) >>> print sexpr.mapcar(lambda y : y ∗ y, x) (1, (4, (9, (16, ()))))
- sn9 10y agoShouldn't cdr be changed so that it gives the list that doesn't contain the first element? def cdr(x): return x if x == () else x[1:]
- DonaldFisk 10y ago# No. x = sexpr.list(1, 2, 3, 4) >>> print x (1, (2, (3, (4, ())))) >>> print sexpr.cdr(x) (2, (3, (4, ()))) # which is what you want. >>> def cdr2(x): return x if x == () else x[1:] ... >>> print cdr2(x) ((2, (3, (4, ()))),) # which is wrong.
- sn9 10y agoBut that's how it's used in Lisp, which is where car and cdr are used. (car x) is the first sexp in x and (cdr x) is x without the first sexp.
- 10y ago