7 ms·

linked list is not complex for christ sake.

base698 10y ago
I think the original intent of the linked list question was to see if the candidate knew pointers. Implementing in a non pointer language would be trivial and definitely not complex.
- Apocryphon 10y ago
  Are linked lists even a difficult example of pointer use? You don't exactly have to do fancy pointer arithmetic with them. You just have to be a little bit careful when inserting or deleting nodes.
  - gpderetta 10y ago
    You do need to understand the difference between an object and a refrence to it. Seems trivial bit surprising many programmers seem not to understand it.
buserror 10y ago
No, AND they are actually useful for any sort of problem, like, reading a records from a file and that sort of stuff. Heck, I wrote one last week [0] because it's quick to implement and does the job. Same applies for the double-linked kind (slightly less so but still nice) and queues. One of my favourite linux kernel header is lists.h! [0]: https://github.com/buserror/rf_bridge/blob/master/src/rf_bridge_linux.c#L414 https://github.com/buserror/rf_bridge/blob/master/src/rf_bri...
yunolisten 10y ago
> linked list is not complex for christ sake. There are many people for whom this is complex, you're assuming a foundation that not everyone has. There are also many people for whom nothing is complex, they assume they can understand everything, while they don't currently, they assume they'll be able to learn it without issue. Dealing with new starts who are straight out of education is often like reading posts from 4chan.org/b, at first you don't know if they're joking. It's not all doom and gloom, occasional I'm pleasantly surprised by the calibre of those beginning their career/hobby, but this is the exception.
- latch 10y ago
  But there's also nothing crazy about a company saying: for this role, we expect the candidate know linked lists. It's not esoteric and I think a lot of us would consider normal programmers who have had to write linked lists (and other data structures) for one reason or another.
  - yunolisten 10y ago
    Personally I agree, however I know people employed to code PHP who have no concept of this. Some apprentices who have left college have joined our company who don't know this.
- deleted 10y ago
  [deleted]
mankyd 10y ago
Tell that to the 1000's of people who can't implement them. I agree, its not that hard, but that's all the more reason to avoid giving attitude about the question. Answer it quickly and move on. If you can't answer it quickly, maybe it _is_ that complex. A lot of interviewers have a short time window in which to conduct their 1-on-1. Sometimes they ask easy questions for a reason. Often, I start with a soft ball that I intend on building on - turn a linked list into a doubly linked list; a circular list; can you improve the lookup time; can you make it generic; what are the space constraints; what are the time constraints. And if they can't answer the simple question, we just leave it at that. A simple question can easily be built upon. "I'd Google it" can not.
golergka 10y ago
Have you ever hired developers? FizzBuzz is still a very effective filter.
- scarface74 10y ago
  At my last job, we asked two simple questions and many "senior developers" couldn't get them: 1. Write a function that determines if a number is prime. If they didn't know what a prime number was, we would tell them. 2. A simple problem that required designing a database schema and sql query that involved a left outer join. There were a lot of developers who couldn't do it. On the other hand, there was one developer who was just learning c#, who had spent most of his time doing VB.net, couldn't answer a lot of the technical questions but we could tell by his thought process and how he explained real world problems he solved that he would be a great asset to the company. We fought for him over more "senior" developers. When I have a chance to hire again, I'm going to fight to get him -- even though he sucks at interviewing and i might have to do a little convincing.
  - flukus 10y ago
    > Write a function that determines if a number is prime. If they didn't know what a prime number was, we would tell them. Did you also give them an algorithm to implement or was a brute force method good enough?
    - scarface74 10y ago
      First the brute force algorithm. Then we would ask them how could they optimize it. A lot of people couldn't even get to the brute force algorithm. 1st level optimization: skip even numbers. 2nd level optimization that I was the only person to get when I had to interview for the company: loop starting at 2, and go the square root of the argument.
onion2k 10y ago
linked list is not complex for christ sake That depends on the language. If you're using something without pointers or references it's quite hard.
- ldarcyftw 10y ago
  Hmm, which (general) language has no pointers or references?
  - falcolas 10y ago
    Python. Ruby. Javascript. Lisp. Haskel (IIRC). They all use them internally, but don't tend to make them available to the programmer (usually because they aren't needed).
    - gpderetta 10y ago
      They have references (at least python, lisp that I know of, likely the others as well), which is enough to implement linked lists.
      - falcolas 10y ago
        The ability to implement linked lists != pointers and references Behind the scene, yes, every Python variable is a reference to an object. It's not addressable, however, and in the case of immutable objects (like strings), you can't modify the underlying object and keep all references pointed at that updated object.
        gpderetta 10y ago
        If have references you can pretty much always implement lists. First all you do not need mutability, you can implement linked lists form immutable cons cells, second python has mutable references so implementing linked lists is trivial (the fact that some objects are in fact immutable is immaterial).
    - 10y ago
falcolas 10y ago
They can be. Doubly linked lists. Intrusively linked lists. Ring buffers. Linked Lists optimized for storage in CPU caches. B Trees (stretching the definition a bit). And so forth.
btschaegg 10y ago
> linked list is not complex for christ sake. ...unless you need them for lock-free programming. There was a nice C++ talk by Herb Sutter on that, with the apt title "Juggling Razor Blades". That pretty much says it all. From a practical standpoint, the question "what is a linked list good for?" really might be more interesting. Does anyone know of potential use cases besides kernel design, lock free programming or Clojure-style immutable datastructures? I'd guess CPU caches to have erradicated most of them...
StreamBright 10y ago
No it is not. However, it is totally irrelevant for 99% of jobs require programming skills. Being 15 years in this business I haven't seen linked lists being used for any particular problem, but I understand that when you work in the right industry it is invaluable. If I had to implement it I would probably use a library and I would educate myself on the subject. I usually find programmers running into many other issues that don't show up during interviews. Few questions I usually ask: - How can you make sure that your Java application runs on the server not only on your laptop? (I take any answers: containers, single JAR, etc.) - What is printed out def add_list(val, list=[]): list.append(val) return list print add_list(10) print add_list(20) print add_list(123,[]) - Explain recursion Funny to see how a non-trivial amount of programmers fail to answer these questions.

I think the original intent of the linked list question was to see if the candidate knew pointers. Implementing in a non pointer language would be trivial and definitely not complex.

Apocryphon 10y ago
Are linked lists even a difficult example of pointer use? You don't exactly have to do fancy pointer arithmetic with them. You just have to be a little bit careful when inserting or deleting nodes.
- gpderetta 10y ago
  You do need to understand the difference between an object and a refrence to it. Seems trivial bit surprising many programmers seem not to understand it.

buserror 10y ago

No, AND they are actually useful for any sort of problem, like, reading a records from a file and that sort of stuff. Heck, I wrote one last week [0] because it's quick to implement and does the job. Same applies for the double-linked kind (slightly less so but still nice) and queues. One of my favourite linux kernel header is lists.h! [0]: https://github.com/buserror/rf_bridge/blob/master/src/rf_bridge_linux.c#L414 https://github.com/buserror/rf_bridge/blob/master/src/rf_bri...

yunolisten 10y ago

> linked list is not complex for christ sake. There are many people for whom this is complex, you're assuming a foundation that not everyone has. There are also many people for whom nothing is complex, they assume they can understand everything, while they don't currently, they assume they'll be able to learn it without issue. Dealing with new starts who are straight out of education is often like reading posts from 4chan.org/b, at first you don't know if they're joking. It's not all doom and gloom, occasional I'm pleasantly surprised by the calibre of those beginning their career/hobby, but this is the exception.

latch 10y ago
But there's also nothing crazy about a company saying: for this role, we expect the candidate know linked lists. It's not esoteric and I think a lot of us would consider normal programmers who have had to write linked lists (and other data structures) for one reason or another.
- yunolisten 10y ago
  Personally I agree, however I know people employed to code PHP who have no concept of this. Some apprentices who have left college have joined our company who don't know this.
deleted 10y ago
[deleted]

mankyd 10y ago

Tell that to the 1000's of people who can't implement them. I agree, its not that hard, but that's all the more reason to avoid giving attitude about the question. Answer it quickly and move on. If you can't answer it quickly, maybe it _is_ that complex. A lot of interviewers have a short time window in which to conduct their 1-on-1. Sometimes they ask easy questions for a reason. Often, I start with a soft ball that I intend on building on - turn a linked list into a doubly linked list; a circular list; can you improve the lookup time; can you make it generic; what are the space constraints; what are the time constraints. And if they can't answer the simple question, we just leave it at that. A simple question can easily be built upon. "I'd Google it" can not.

golergka 10y ago

Have you ever hired developers? FizzBuzz is still a very effective filter.

scarface74 10y ago
At my last job, we asked two simple questions and many "senior developers" couldn't get them: 1. Write a function that determines if a number is prime. If they didn't know what a prime number was, we would tell them. 2. A simple problem that required designing a database schema and sql query that involved a left outer join. There were a lot of developers who couldn't do it. On the other hand, there was one developer who was just learning c#, who had spent most of his time doing VB.net, couldn't answer a lot of the technical questions but we could tell by his thought process and how he explained real world problems he solved that he would be a great asset to the company. We fought for him over more "senior" developers. When I have a chance to hire again, I'm going to fight to get him -- even though he sucks at interviewing and i might have to do a little convincing.
- flukus 10y ago
  > Write a function that determines if a number is prime. If they didn't know what a prime number was, we would tell them. Did you also give them an algorithm to implement or was a brute force method good enough?
  - scarface74 10y ago
    First the brute force algorithm. Then we would ask them how could they optimize it. A lot of people couldn't even get to the brute force algorithm. 1st level optimization: skip even numbers. 2nd level optimization that I was the only person to get when I had to interview for the company: loop starting at 2, and go the square root of the argument.

onion2k 10y ago

linked list is not complex for christ sake That depends on the language. If you're using something without pointers or references it's quite hard.

ldarcyftw 10y ago
Hmm, which (general) language has no pointers or references?
- falcolas 10y ago
  Python. Ruby. Javascript. Lisp. Haskel (IIRC). They all use them internally, but don't tend to make them available to the programmer (usually because they aren't needed).
  - gpderetta 10y ago
    They have references (at least python, lisp that I know of, likely the others as well), which is enough to implement linked lists.
    - falcolas 10y ago
      The ability to implement linked lists != pointers and references Behind the scene, yes, every Python variable is a reference to an object. It's not addressable, however, and in the case of immutable objects (like strings), you can't modify the underlying object and keep all references pointed at that updated object.
      - gpderetta 10y ago
        If have references you can pretty much always implement lists. First all you do not need mutability, you can implement linked lists form immutable cons cells, second python has mutable references so implementing linked lists is trivial (the fact that some objects are in fact immutable is immaterial).
  - 10y ago

falcolas 10y ago

They can be. Doubly linked lists. Intrusively linked lists. Ring buffers. Linked Lists optimized for storage in CPU caches. B Trees (stretching the definition a bit). And so forth.

btschaegg 10y ago

> linked list is not complex for christ sake. ...unless you need them for lock-free programming. There was a nice C++ talk by Herb Sutter on that, with the apt title "Juggling Razor Blades". That pretty much says it all. From a practical standpoint, the question "what is a linked list good for?" really might be more interesting. Does anyone know of potential use cases besides kernel design, lock free programming or Clojure-style immutable datastructures? I'd guess CPU caches to have erradicated most of them...

StreamBright 10y ago

No it is not. However, it is totally irrelevant for 99% of jobs require programming skills. Being 15 years in this business I haven't seen linked lists being used for any particular problem, but I understand that when you work in the right industry it is invaluable. If I had to implement it I would probably use a library and I would educate myself on the subject. I usually find programmers running into many other issues that don't show up during interviews. Few questions I usually ask: - How can you make sure that your Java application runs on the server not only on your laptop? (I take any answers: containers, single JAR, etc.) - What is printed out def add_list(val, list=[]): list.append(val) return list print add_list(10) print add_list(20) print add_list(123,[]) - Explain recursion Funny to see how a non-trivial amount of programmers fail to answer these questions.