Hacker News Reader

Comment by fideloper | Hacker News Reader

A majority of my career has been CRUD (occasionally "advanced" CRUD). Ive worked in (and coded non-trivial things) in PHP, Python, node (lol) & Golang. I've learned a ton of server management.

I've literally coded a linked list once, years ago, when reviewing an algorithms book (never played in anything more advanced). I don't have a CS degree.

Am I a programmer in the eyes of these interviewsers? It feels an awful lot like the answer is "no". And "hope you never get an intense technical interview!"

What do y'all think?

View on HN

The worst part about these interviewers is that they assume that because you don't know their area that you don't know how to code.

Anyone who has cut their teeth on crud apps and server management should be able to figure out how to make a linked list _given specifications_. If a candidate doesn't know the terminology, it should be explained what it does and then I think it's fair to say that someone can build it. They're probably built something related/similar and never realized it. This is a great place for discussion about code! It's an opportunity more than anything.

Discounting candidates because they don't know a subset of the vast amount of knowledge we can have in this field is an _interviewer fail_. I think it says everything about the company culture and very little about the candidate.

Well it kind of depends, doesn't it? Linked Lists are a good introduction to the types of structures you'll use in any sort of graph-related problems. If the work you're interviewing for is going to involve a lot of manipulations of node trees and graphs and lists, then you'd want someone who either knows that stuff or seems capable of understanding it.

Certainly not knowing it doesn't disqualify you from being "a real programmer" or whatever. If you never use one, then there's no shame in not knowing it. (Though it's good to learn things you haven't used because maybe there are better ways to do what you're doing.) But it's not a flaw of the interviewer to ask questions related to the work the candidate will be expected to do, either.

I use lists a lot. That's because I program in Lisp most of the time. Lists are a very flexible data structure. But I wouldn't use them in a language if I had to implement them from scratch, such as C, or in a language where the functional style is unnatural, such as Java or Python, even though both those languages have basic support for them. I'd use vectors and hash tables instead. They're less flexible than lists, but good enough for most purposes (and they might even be faster).

The only time I can remember implementing lists is when writing a Lisp interpreter or virtual machine. And that uses a fixed length array of cons cells, so no dynamic heap allocation is necessary.

I've been asked list-related questions at interviews several times, e.g. how to destructively reverse one, and how to tell if a list is circular. If it's just to check that I really have implemented Lisp, then they're reasonable questions, but I suspect all the candidates for the same job were asked those questions.

A linked list is probably literally the simplest data structure in all of CS. No, you'll probably never need to write one in real life because most modern languages come with one, but exactly because it's so simple and so ubiquitous, it speaks quite loudly about the level of abstraction at which you operate if you can't implement one quite quickly.

Is there a problem with operating at that level of abstraction? Are we here to serve our egos, or business needs?

I'm sure I could implement one, but it'd require googling. If that ever kept me from a position, they could gladly keep it.

A linked list is so simple that you should know how to implement one off the top of your head.

It's literally:

    struct list_node {
        struct list_node *next;
        ...
    };

There, you know how linked lists work :)

That's what I came up with in my head, but my issue is, in an interview I'd not be confident with that kind of an answer. I've never done that before, I've never had a reason to do that before. I've contributed to Rails, graphing libraries, written docs for complex JS projects, implemented caching solutions, written authentication and authorization backends- but this here is like asking an architect to cut down a tree.

Sure, he can figure it out, but he's gonna look stupid for the first few minutes.

The figuring it out is entirely the point of the interview. When I interview someone, I need to work on a problem with them. The simpler the problem we can work on together, the more likely that I'll learn what they're like to work with, not whether or not they've memorized some trivia like how to implement quicksort in 10 lines of Python.

That's fair, and a totally valid way of going about it. But if I'd been devving for a few years and hadn't heard the term "linked list", and the interviewer scoffed at having to answer the question of what it was, I get uninterested real fast.

Sure, if what you're doing is trivial, and remains trivial, you can get by with low skills, that's tautological. It's just that people rarely really know the limit of their skills, and end up doing things they think are trivial, but aren't, and boom, you have a seemingly trivial screen in your app that takes 45 seconds once there are 2000 row in some table, and you have no idea why.

There are pretty simple things that will blow up in your face performance-wise even at rather modest scale if you don't know what's going on under the hood.

Do you know why you're not supposed to concate strings, especially at scale/in loops? Do you know what the N+1 performance problem is? I've seen simple webapps take out beefy servers at modest load because a dev didn't.

So yeah, we're here to serve business needs, and for that we need devs who can reason at the most basic level of abstraction about what's going on under the hood.

The N+1 issue is one that everyone ends up learning and understanding on the job fairly quickly. It doesn't require anything abstract to understand- "You're constantly hitting it over and over instead of doing things in one or two passes."

Modern programming generally has you approaching any obscure issues like this the same way: You profile your code, figure out where something is going horribly wrong, then try to look up answers for why. If I noticed that my string concatenation was taking an inordinate amount of time, it'd probably take me under 5 minutes to figure out why via Google alone.

Hell, I'd significantly wonder what someone was doing if they were concatenating strings enough to cause performance issues. I can't imagine any business need, for anyone, that could be brought together by that.

I happen to have a BSc in this field and of course we learned the linked list. Teachers love to teach it as much as US interviewers seems to love asking about it in interviews. (Around here they seem to be to dumb to know about it or to smart to ask for it, I suspect the latter.)

That said I think gp's point is that if you ask for a doubly-linked list then you basically filter by having learned programming in school or not, or iow, if you told them how it was supposed to work instead of just saying the magic name then more of them would pass.

I think you're responding to someone other than OP? Certainly, demanding a CS degree is BS. Demanding you memorize the exact sequence of operations for rebalancing a red-black tree is BS. But OP isn't talking about that, just about having the basic skill to write a simple program, which presumably you do have.

Would you say you would be able to code a simple linked list, with `add`, `get` and `remove` support if asked on an interview?

The post is talking about people who cannot implement fizzbuzz. I think you're safe.

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!

Btw, 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.

Here'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, ()))))

Shouldn'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:]

# 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.

But 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.

You are mistaken. In Lisp, lists are constructed out of NIL and dotted pairs, so,

(1 . (2 . (3 . NIL))) = (1 2 3)

I chose to implement lists in Python in the same way, out of () and 2-element tuples. So

(1 2 3) = (1 . (2 . (3 . NIL))) in Lisp which becomes (1, (2, (3, ())) in Python.

(cdr '(1 2 3)) = (2 3) = (2 . (3 . NIL)) which should therefore be (2, (3, ())) in Python, i.e. the second element of the 2-element tuple (1, (2, (3, ())), NOT the 1-element tuple ((2, (3, ())),) obtained by removing the first element.

I should point out that there is one difference, in case anyone else spots it: tuples in Python are immutable, whereas dotted pairs in Lisp are not, so my implementation won't allow rplaca and rplacd.

Reply on news.ycombinator.com