5 ms·

> implement an algorithm that finds the value of the element in the middle of a linked list I'm struggling to think of the last time I had to use a linked list

> implement an algorithm that finds the value of the element in the middle of a linked list I'm struggling to think of the last time I had to use a linked list for anything. I'd be tempted to give the troll answer: put the elements into a List<T> already, divide list.Count by 2.... Sure if it's doubly linked then you can walk it from both ends and meet in the middle, then think about how to handle the case where there are an even number of elements, but do you really want a serious answer about linked lists in .Net?

DrJokepu 15y ago
That's not the point, the question is about understanding fundamental, abstract computer science concepts and being able to craft simple algorithms. Even if we don't manipulate these data structures directly these days in code, there are "real world" concepts that are very similar to these fundamental data structures such as HTTP redirection chains, various stages of a workflow and so forth. It is due to the very nature of computers that a good developer has to be able to find abstractions in real world patterns and solve problems using these abstract ideas. A linked list (or a binary tree) is a very simple abstract idea and it's a good device for measuring the candidate's skill at solving abstract problems. Additionally, my view and experience is that unless we're trying to hire a specialist in a niche, domain knowledge (in this case, .NET) is considerably less important than general programming skills and abilities; a good developer with limited .NET skills would still write excellent .NET code, a developer who's very familiar with the .NET Framework but who's poor programming skills would be a liability for the company.
- StrawberryFrog 15y ago
  > Even if we don't manipulate these data structures directly these days in code We don't manipulate them indirectly either; .Net or Java lists aren't implemented like that.
crpatino 15y ago
I am sorry, but I just cannot let that go! From a recruiting point of view, this kind of questions are indicators. They are easy to verify and they are correlated with some other, more relevant skills. First, knowing your 101 Data structures is correlated to your Computer Science general knowledge. What relevance does it have? It depends on the job description. There are jobs that merely require churning out bland CRUD application code, and it does not make much of a difference if you know this stuff. But, in general, for anything that has strong performance requirements, it might be a concern. By example, if you let me feed the troll, your solution shows a mix of cleverness, (potential) ignorance and unawareness of the high level goal.. that I might be concerned you would produce something like... class SortedList extends List{ //... add(E element){ parent.add(element); qsort(this); } //... } On the other hand, Linked lists also give you a hint of the ability of the candidate to manipulate pointers/references. This may or may not be relevant, again, depending on how often do expect to use this skill in your code base. A trivial solution would let you at least know that the person pays attention to detail and does not leave a mess behind. A more sophisticated approach gives you more information about actual expertise (like, if you know about cycle detection, this is a piece of cake).
- StrawberryFrog 15y ago
  > First, knowing your 101 Data structures is correlated to your Computer Science general knowledge. I can't quite shake the idea that what you're really testing is if the applicant has been to the same kind of school as yourself. > There are jobs that merely require churning out bland CRUD application code, and it does not make much of a difference if you know this stuff I've seen some really interesting (and performance-constrained) code done in .Net that didn't use pointers or linked lists in any way. It's not either "bland crud" or pointers, that's a false dichotomy. Of course, concepts like parse trees, A-B pruning or Hungarian method of optimization are things that are worth having a hold on. But "how often you expect to use the skill" of linked lists with pointers in many modern languages, Java and C# included, is effectively never. No idea where the crap java code for a sorted list came from, hope you're not trying to put those words in my mouth! In the .Net world, good companies do try to look out for "broader" developers who are aware of useful open-source software toolkits, and want to practice things like Dependency Injection, TDD, Continuous Integration etc. They generally make better coders.
  - crpatino 15y ago
    Yes, I am aware of the CS vs street smarts debate. Everybody has its own opinion, and I am sure neither of us is going to convince the other, so I'd rather not go there. At the end of day, you seem to miss my point altogether. Testing for the skill is not useful in itself. It is just an heuristic. The industry is choke full with people that seem fairly competent and accomplished, who is able to produce code that fulfills the specification, but who also come with a collection of vices, bad practices, and simply cannot make trade-offs intelligently. People like me wants to believe that, because CS foundations are not strictly needed for the task at hand, these people tend to ignore it for the same reason that they ignore other, more important, stuff that also is not strictly needed to complete the task at hand (but that will have a direct impact on the quality of your solution). I am fully aware that there are great developers that do not come from a CS background. I am also painfully aware that there's people who excels at the CS 101 questions but cannot perform in a real world environment. At the end of day, this does not provide a final go or no go answer. It is just an indicator of whom you want to bring in for a deeper, longer interview. > hope you're not trying to put those words in my mouth! Not at all. I was just going on with the troll thing. Hope I did not offend you.

DrJokepu 15y ago

That's not the point, the question is about understanding fundamental, abstract computer science concepts and being able to craft simple algorithms. Even if we don't manipulate these data structures directly these days in code, there are "real world" concepts that are very similar to these fundamental data structures such as HTTP redirection chains, various stages of a workflow and so forth. It is due to the very nature of computers that a good developer has to be able to find abstractions in real world patterns and solve problems using these abstract ideas. A linked list (or a binary tree) is a very simple abstract idea and it's a good device for measuring the candidate's skill at solving abstract problems. Additionally, my view and experience is that unless we're trying to hire a specialist in a niche, domain knowledge (in this case, .NET) is considerably less important than general programming skills and abilities; a good developer with limited .NET skills would still write excellent .NET code, a developer who's very familiar with the .NET Framework but who's poor programming skills would be a liability for the company.

StrawberryFrog 15y ago
> Even if we don't manipulate these data structures directly these days in code We don't manipulate them indirectly either; .Net or Java lists aren't implemented like that.

crpatino 15y ago

I am sorry, but I just cannot let that go! From a recruiting point of view, this kind of questions are indicators. They are easy to verify and they are correlated with some other, more relevant skills. First, knowing your 101 Data structures is correlated to your Computer Science general knowledge. What relevance does it have? It depends on the job description. There are jobs that merely require churning out bland CRUD application code, and it does not make much of a difference if you know this stuff. But, in general, for anything that has strong performance requirements, it might be a concern. By example, if you let me feed the troll, your solution shows a mix of cleverness, (potential) ignorance and unawareness of the high level goal.. that I might be concerned you would produce something like... class SortedList extends List{ //... add(E element){ parent.add(element); qsort(this); } //... } On the other hand, Linked lists also give you a hint of the ability of the candidate to manipulate pointers/references. This may or may not be relevant, again, depending on how often do expect to use this skill in your code base. A trivial solution would let you at least know that the person pays attention to detail and does not leave a mess behind. A more sophisticated approach gives you more information about actual expertise (like, if you know about cycle detection, this is a piece of cake).

StrawberryFrog 15y ago
> First, knowing your 101 Data structures is correlated to your Computer Science general knowledge. I can't quite shake the idea that what you're really testing is if the applicant has been to the same kind of school as yourself. > There are jobs that merely require churning out bland CRUD application code, and it does not make much of a difference if you know this stuff I've seen some really interesting (and performance-constrained) code done in .Net that didn't use pointers or linked lists in any way. It's not either "bland crud" or pointers, that's a false dichotomy. Of course, concepts like parse trees, A-B pruning or Hungarian method of optimization are things that are worth having a hold on. But "how often you expect to use the skill" of linked lists with pointers in many modern languages, Java and C# included, is effectively never. No idea where the crap java code for a sorted list came from, hope you're not trying to put those words in my mouth! In the .Net world, good companies do try to look out for "broader" developers who are aware of useful open-source software toolkits, and want to practice things like Dependency Injection, TDD, Continuous Integration etc. They generally make better coders.
- crpatino 15y ago
  Yes, I am aware of the CS vs street smarts debate. Everybody has its own opinion, and I am sure neither of us is going to convince the other, so I'd rather not go there. At the end of day, you seem to miss my point altogether. Testing for the skill is not useful in itself. It is just an heuristic. The industry is choke full with people that seem fairly competent and accomplished, who is able to produce code that fulfills the specification, but who also come with a collection of vices, bad practices, and simply cannot make trade-offs intelligently. People like me wants to believe that, because CS foundations are not strictly needed for the task at hand, these people tend to ignore it for the same reason that they ignore other, more important, stuff that also is not strictly needed to complete the task at hand (but that will have a direct impact on the quality of your solution). I am fully aware that there are great developers that do not come from a CS background. I am also painfully aware that there's people who excels at the CS 101 questions but cannot perform in a real world environment. At the end of day, this does not provide a final go or no go answer. It is just an indicator of whom you want to bring in for a deeper, longer interview. > hope you're not trying to put those words in my mouth! Not at all. I was just going on with the troll thing. Hope I did not offend you.