Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am a newbie into the corporate world recently graduated in computers. I am a java/groovy developer. I am a quick learner and I can learn new frameworks, APIs or even programming languages within considerably short amount of time. Albeit that, I must confess that I was not so strong in data structures when I graduated out of college. Through out the campus placements during my graduation, I've witnessed that most of the biggie tech companies like Amazon, Microsoft etc focused mainly on data structures. It appears as if data structures is the only thing that they expect from a graduate. Adding to this, I see that there is this general perspective that a good programmer is necessarily a one with good knowledge about data structures.

To be honest, I felt bad about that. I write good code. I follow standard design patterns of coding, I do use data structures but at the superficial level as in java exposed APIs like ArrayLists, LinkedLists etc. But the companies usually focused on the intricate aspects of Data Structures like pointer based memory manipulation and time complexities. Probably because of my java-ish background, Back then, I understood code efficiency and logic only when talked in terms of Object Oriented Programming like Objects, instances, etc but I never drilled down into the level of bits and bytes. I did not want people to look down upon me for this knowledge deficit of mine in Data Structures.

So really why all this emphasis on Data Structures? Does, Not having knowledge in Data Structures really effect one's career in programming? Or is the knowledge in this subject really a sufficient basis to differentiate a good and a bad programmer?

share|improve this question
34  
I don't really get your question. You say "I write good code" -- how can data structures be not part of good code. And, I doubt any sincere interviewer would be excessively obsessed with them. –  good_computer Aug 18 '11 at 12:38
4  
@greengit: There's a difference between implementing a hash map, and using its API. What I would value in an interview is if they'd describe an application for me, then asked me to build up the central data structures, and explain my choices. –  György Andrasek Aug 18 '11 at 15:37
7  
What would you prefer to be asked? –  temptar Aug 18 '11 at 16:00
12  
@Jurily - To understand when to use a container library, it helps to have some knowledge of how the underlying data structure works. It's hard to accept that you know about efficiency of code if you don't know the time and space complexities of the libraries you are using - just because it works well on small test datasets doesn't mean it'll scale well to larger datasets in the real world. IMO, understanding the time and space complexities is as much a part of understanding the API as knowing the class and method names - perhaps more so, as intellisense won't tell you the complexities. –  Steve314 Aug 18 '11 at 22:10
2  
A good data structure give clean, simple code. A bad data structure give complex code. It is important to get right. –  user1249 Apr 17 '12 at 6:29
show 4 more comments

24 Answers 24

up vote 102 down vote accepted

most of the biggie tech companies like Microsoft focus mainly on data structures. It appears as if data structures is the only thing that they expect from a graduate.

No, there's more. For example, we also expect that you be a quick learner who can learn new frameworks, APIs or even programming languages within a short amount of time. That's a bare minimum bar. Someone who takes a long time to learn a new framework, API or language will not be a successful developer on most teams at Microsoft.

And of course there are many more aspects that we focus on in interviews other than just raw knowledge of data structures. Ability to deal with ambiguous specifications, for example, or ability to recognize coding patterns that produce insecure code, or a dozen other things. But ability to understand data structures certainly is a very big one.

It is particularly the case that interviews are biased towards testing knowledge of data structures for recent CS graduates. Recent graduates, most of whom do not have a lot of real-world experience, are not expected to be good at the same sorts of things that someone with fifteen years of industry experience would be good at.

I must confess that I was not so strong in data structures

It's good that you know that about yourself. If you're unable or unwilling to change that about yourself then my recommendation is that you don't apply for a job that requires facility with data structures.

there is this general perspective that a good programmer is necessarily a one with good knowledge about data structures.

It's tautological that a good programmer is a programmer who is good at building the sorts of programs that need to be built. Lots of programmers work on tasks that do not require deep knowledge of data structures. Some of them work on tasks that require a deep knowledge of user interface design, for example. Or database normalization. Or whatever. Those people can still be "good programmers" in their domains.

why all this emphasis on Data Structures?

I ask interview questions about data structures because on my team the developers design, implement and manipulate complex data structures all day every day. Yesterday we had four hours of meetings in which a half-dozen developers argued the pros and cons of adding single Boolean field to a particular tree node. There is probably no skill on my team more important than ability to understand data structures at a deep level. It would be foolish to not ask interview questions about it, since that's what we do.

Does not having knowledge in Data Structures really affect one's career in programming?

Well it certainly will prevent you from getting a job on my team. But like I said before, programming is a huge field. There are lots of kinds of computer programming that don't require knowledge of data structures.

is the knowledge in this subject really a sufficient basis to differentiate a good and a bad programmer?

No. But it is almost always sufficient to detect developers who are unlikely to be successful at Microsoft. Since that is what I am primarily interested in detecting, knowledge of data structures is one of the factors I test for in interviews.

share|improve this answer
9  
Thanks a tonne Eric! This is the least demotivating answer that I've got for my question. :-) –  Vamsi Emani Aug 18 '11 at 16:23
2  
@EricLippert, thank you for this excellent answer. As a self-taught developer who has yet to be bitten by his lack of formal knowledge of data structures, do you recommend a book that could show me what I've been missing? –  Closure Cowboy Aug 19 '11 at 7:42
3  
@Closure Cowboy: For the basics of data structures and algorithms, "Introduction to Algorithms" by Cormen, Leieserson and Rivest is the standard textbook. If you are interested in functional style data structures, Chris Okasaki's book is very good but quite advanced. –  Eric Lippert Aug 20 '11 at 22:53
show 1 more comment

One important point about data structures is that they are universal and timeless, at least for practical purposes. Anyone who's been a developer in the last 30 years should know basic data structures like single/double linked lists, binary trees or graphs. If you ask two developers about them, you can compare the developers' knowledge by their answers. This can hardly be said for frameworks or even languages: If you ask two developers about Rails, and one knows a lot more than the other, what does that tell you, really? As you say in the question, a smart developer can learn a new framework quickly enough, so testing their current knowledge doesn't make much sense.

Does, Not having knowledge in Data Structures really effect one's career in programming?

Yes. Definitely. Unless you want to spend all your life writing CRUD applications.

Or is the knowledge in this subject really a sufficient basis to differentiate a good and a bad programmer?

No, it's not sufficient. But there are few things you can ask in a job interview that are sufficient. And I'd say algorithms knowledge is one of the better indicators, at least for people fresh out of school, where you can't ask about work experiences.

share|improve this answer
2  
@konrad: That's what I meant by "for practical purposes". I can't think of a data structure or algorithm that became "obsolete", and I doubt you would come across one in a job interview. And since most algorithms/data structures were developed long before our current hardware and are still useful, I'd even guess there's some kind of coevolution going on, where new hardware developments are guided by the data structures we know. –  nikie Aug 18 '11 at 13:05
8  
@konrad: And if/when quantum computers become standard, I can think of a few more. But I assume the OP doesn't want to wait with his job interviews until then ;-) –  nikie Aug 18 '11 at 13:20
3  
...or when our new AI overlords make puny human programmers obsolete –  konrad Aug 18 '11 at 13:23
show 7 more comments

I am a quick learner and I can learn new frameworks, APIs or even programming languages within considerably short amount of time.

Not to sound too harsh, but any half-decent developer will be able to pick up a new language or framework in a relatively short period of time.

Data structures are universal, they are a fundamental building block of computer science -- a red-black tree is basically the same, whether it's implemented in Java, Python, PHP or whatever. So rather than testing specific languages, or specific frameworks, an employer (at least, an employer looking for stand-out developers) will test whether you know the fundamentals of computer science, rather than just whatever flavour-of-the-month they're currently using.

(at least, they should be testing the fundamentals in addition to whatever they're currently using... no point hiring a computer-science wizard if he's never written a line of code in his life)

share|improve this answer
1  
Computer science is one of the keywords here. Data structures are usually seen in-depth in a Master's and is apparently an important subject. –  James Poulson Aug 19 '11 at 19:15
1  
Data structures are universal until you get hooked on purely functional programming :P. –  Tikhon Jelvis Jul 18 '12 at 9:20
add comment

Do you believe that F1 racers just drive fast cars? No, they understand the car they drive and they work with the mechanics/engineers to tune it. Of course, a normal driver just drives.

You can be a normal/average programmer that just writes code. You don't understand what's behind. You get things done. That's all, see you next day.

But many companies look for F1 developers. People that will develop knowing what is behind their code. People that will also help the company to build something better.

It's quite good to know data structures not only because you will use them in a "pre cooked" form a lot. It's also good because you will create something that derives from their idea.

share|improve this answer
3  
1  
Yup. My dad taught me how to take anything apart. He neglected to teach me how to put things back together, been figuring that out all my life. –  Robbie Aug 19 '11 at 13:41
show 2 more comments

In my class on data structures, the very first thing the professor said was: This class is not about being able to search really fast. We then spent half a year finding the best possible data structures and algorithms to search really fast.

Still, he remained right. Being able to analyse data structures, apply the right data structure to a given problem or even come up with new data structures requires many qualities of an engineer:

  • Finding abstractions to model a concrete problem
  • Being able to decompose problems
  • Being able to reason logically/formally
  • Creativity
  • etc.

When Amazon and Microsoft hire people, they don't ask questions on data structures because they hope to invent the next quicksort. They want to make sure they hire someone with the above-mentioned qualities.

Of course it's possible to have a large set of these qualities and still suck at data structures. But then, if that's the case, it won't take you long to become an expert in data structures.


That being said, there is still the problem that ArrayList just doens't quite scale. When systems get large, better adapted solutions are required to perform the job. And without a good grasp of data structures, you won't be able to find and compose structures and algorithms which scale at large in your concrete scenario.

share|improve this answer
3  
And regarding ArrayList, without a good grasp of data structures you might not even realize that ArrayList doesn't quite scale and you need to find and compose structures and algorithms that scale. –  phoog Dec 23 '11 at 19:21
add comment

In generally algorithms and data structures is regarded as two of the most "hard core" topics in programming. This is because there's a huge body of work and research regarding them in computer science. They also attract the typical "left-lobe"-programmers that like things like math and science (which is a whole lot of programmers)

That being said, knowledge of these might affect your career in terms of interviewing, especially if you interview at engineering-oriented workplaces like google. Other companies might now however care about that aspect at all.

In my experience algorithm/data structure demands can sometimes come across as "programmer elitism" where alpha geeks are jockeying to show who's the smartest. Its always good to know what's out there, but there are great many different programming jobs where you never will need to know how to use a red/black tree or code a boyer-moore search.

I'd recommend learning more about the topics if you find them interesting and have some personal project where you can tinker with them, otherwise you can probably get by without them for now

PS. Profiency with rudimentary data structures (linked lists, dictionaries, hashtables etc) should be a mandatory knowledge for any programmer DS.

share|improve this answer
add comment

They are fundamental, but also, what would you quiz graduates on? They may or may not have experience outside of their course work. Their course may have covered Microsoft technologies more than say Java, or vice versa. Data structrues are common ground.

share|improve this answer
show 1 more comment

So really why all this emphasis on Data Structures?

Two reasons.

For one thing, it shows you can think about the problem in abstract terms, rather than in terms of a specific programming language. Do you know why a hash table may be a better or worse choice than a red-black tree in a given situation, regardless of the underlying implementation?

For another, there are a scary number of people out there interviewing for jobs who simply lie about their experience and have very little if any programming ability; data structures questions are a quick way of weeding these people out.

share|improve this answer
1  
Picking the right data structure up front based on applicability and expected performance characteristics independently of the underlying implementation is not an example of premature optimization. –  John Bode Aug 21 '11 at 12:48
show 2 more comments

To build on what @Pelshoff says, it is to show that you know what you're doing. If you use a LinkedList for everything, that may show you don't know what you're doing or you don't care to stop and think about the problem. On top of that, at least the data structures course I took covered, basic, complexity theory of those data structures which, when dealing with large data sets is very important. That would be why companies like Amazon or Microsoft would do such a thing.

I must say, before I took a data structure class I thought that they weren't important but at least being able to recongnize when a linked list (or ArrayList) isn't practical or what the draw backs of them are is important.

share|improve this answer
show 2 more comments

Data structures display how well someone understands abstract concepts like pointers. It shows if someone is smart or really really smart.

Read what Joel Spolsky had to say about java schools here: http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

share|improve this answer
show 1 more comment

Often times the best code avoids reinventing low level data structures. This is especially true in high level languages. I have noticed a trend towards low level data structure questions even in CRUD jobs. YMMV, but it seems the emphasis on hacker scientist expertise has overshadowed the other skills that make a great developer:

  • project/time management: being able to keep up with the real world that is driven by business, not a new linked list that operates 1% faster.
  • a minimum amount of social skills: a developer that is arrogant and cannot get along is nothing but an anchor.
  • the ability to learn new things quickly and continuously: data structures hardly change over the years...but everything else does. Data structures are great fundamentals and every developer should know them pretty well, but an accountant does not get tested on their long division skills when they go in for an interview. Great developers are the type of people who can figure out new things and like it.

Data structures are great. Data structures are important. Every programmer should have an understanding of them. However, we have become obsessed with pushing these fundamentals outside of their place. It is not ALL about data structures, and in 99% of cases there is no need to ask questions beyond the basics of data structures. If you are interviewing an accountant, sure ask them what 81 divided by 9 is, but if you keep asking "What's the cube root of 98425454242412 * 4512324?...without a calculator!" then you will be frightening a good percentage of the reasonable, smart, talented, and agreeable people you could have had. Ask if they can build a basic relational data model, ask if they can use the enhanced array structures provided by the relevant framework, and ask if they can explain when a binary search is faster than flat search, but there is not much point going too far beyond that. If they can do those things, then start looking for the nicest, most professional, most creative one of the bunch.

I love Joel's writing, but I think his "Java Schools" thing is dead wrong. There are plenty of things that can prove someone is smart beyond mastering C++. Think about it, you can talk to someone for 10 minutes, without asking them about pointer arithmatic, and get a pretty good idea of whether or not they are the type who can get things done and figure stuff out. We don't need to be like this:

Interviewer: "Tell me about your accomplishments."

Coder: "In my last position I was the sole developer for a custom ERP system for a billion dollar financial firm. We delivered months ahead of schedule, and the system has been in production for the past 3 years."

Interviewer: "Let me clarify. Tell me about your programming accomplishments"

Coder: "Umm..."

Interviewer: "For example, have you ever made your own linked list?"

Coder: "...[walking out]"

share|improve this answer
1  
I can imagine that the guy who worked on the ERP system isn't a good fit for the team. –  Christopher Mahan Aug 18 '11 at 23:07
show 2 more comments

that matches my experience but only partially. Data Structures steal all the lime light at my interviews only when I fail to prepare for quick passing of this "entry barrier" for some reason.

  • When this happens, it typically goes as follows: - Interviewer asks something basic, - I waste few minutes to extract it from my "long term memory" - Interviewer spots some slippery point - I waste another few minutes to recall how to address it - etc. Feels pretty exhausting - and of course leaves too little time to dig through what I really like.

I don't blame the interviewers though - I rather believe it's my fault - because when I am well prepared, going through this "layer" does lightning fast. In my experience it takes 5 minutes or less for good interviewer to complete this part when I am in good shape for answering.

My overall impression is if one wants to get good chance to cover his favorite topics at interview, it is better to prepare to quickly pass-through few typical time-eaters: data structures, O-notation, search/sort, patterns and basic concurrency.

  • It's like... you know, like one has to check the gas level, fasten seat belt and turn the key before driving a car. There's no use of whining if this feels boring because it doesn't matter; the best one can do is to learn how to do this fast.

Side note another trap is there waiting for those who managed to quickly pass the entry passage and got to beloved topic to discuss in depth. Without dedicated preparation for this, chances to fail at interview are surprisingly high.

  • - Lack of practice in <my favorite topic> through last few months doesn't matter because year ago I passed it at every interview with flying colors. - Nope it matters; and you'll likely fail if you don't prepare.

Thing is, if your resume has something like strong skills in <my favorite topic> and if the interviewer has read it and is interested in that area, (s)he will take quite some effort to prepare. And when the interview will start quickly drilling deeper into that area, you'll be surprised to find out how much one can forget in "just a few months" without practice. Been there done that :(


PS.

  • As for the usage of data structures (and other time-eaters listed above) at the job - have to admit, in my experience this was usually not the case...

...and I myself am a living proof of that. Say, when interviewing candidates for our team, I ask concurrency questions not because these skills are important in our project (these are not) but because these somehow make it easier for me to evaluate general knowledge of language we use (Java).

I even recall once or twice when we dived quite deep because both me and candidate just were both excited to chat about it, I specifically pointed at the end of interview that our job does not assume much use of concurrent code - to avoid setting false expectations and further disappointment in case if we decide to bring the guy on board.

share|improve this answer
add comment

Data structures are building blocks of many things you want to do. If you know the uses for each data structure, its weaknesses and strong points then you can easily solve problems. For example, we had a requirement to manage thousands of objects. Every once in a while we need to update an object's timestamp according to its ID. Every once in a while we needed to remove the objects that were not updated for more than X minutes. If you know your data structures you can easily define the problem, and it is also very easy to come up with a solution. When a programmer that don't know enough data structures tried to come up with a solution, his solution was awkward. He was like you - smart, code programmer, able to learn frameworks quickly. But without a knowledge in data structures he had to invent the wheel by himself. More then that - he had hard time understanding simpler solutions since they were based on data structures he did not understand such as red-black trees (your old TreeMap in Java). So, I'd say that the important thing is to know how and when to use each data structure without having to think about it. But I don't think there is any way of achieving that without actually understanding how they work.

share|improve this answer
add comment

Because they are problems that were solved decades ago, so it's easy for the interviewer to look up the correct answers in a textbook.

share|improve this answer
add comment

Begin a good programmer is not about being able to learn languages and frameworks. It is about being able to build solutions to complex problems. For these solutions to be efficient and reliable will almost always rely on good algorithms and appropriate use of data structures. Knowing the data structures exist is not enough. You need to understand the data structures will enough to use the right one for the problem. Lists and maps offer some valuable features, but they come with costs, and using the wrong one can significantly undermine the performance of your software.

A good interviewer knows this and is trying to determine if you can be valuable to his team or company. The language(s) you will be using 2 years from now may be very different, but the need for effective algorithms and data structures will not change.

share|improve this answer
add comment

A very important observation is that if your data structure is right for your problem at hand, the code gets very clean.

If your data structure is not optimal your code will be convoluted and hard to read and maintain.

Just think if you have a single linked list and you need to transverse it backwards.

share|improve this answer
add comment

Smart data structures and dumb code works a lot better than the other way around.

This is the Eric S. Raymond's quote, explains why they do care about data structures.

share|improve this answer
show 1 more comment

They teach you hard thinking. Even if you don't use them regularly, you should often get involved in things that require hard thinking. Of course you can do that in other ways (like reading hard engineering or physics research paper, game theory, newer algorithms etc.). Good for your brain muscles that get lazy over time by default.

share|improve this answer
add comment

Data structures, time complexity, memory manipulation, and pointers are all fundamentals that someone who calls themselves a Computer Scientist should innately know. Any code monkey can learn a language and learn how to use it, but where CS professionals and students should set themselves apart is knowing not just how to use a linked list or a hash map, but WHY.

The WHY is what really sets us all apart from the basic script kiddie, code monkey, and grunt of the computing world. WHY use a hash table instead of a linked list, WHY should my hash table be at a cluster density of roughly .6-.8, WHY should I use a circularly linked list here instead of a doubly linked list. WHY should my code be running at efficiency 'x' in the worst case and 'y' in the average case.

These basic data structures and knowledge of not just the HOW they are used (the how should be in every programmers repritoire anyway) but the language agnostic WHY they are used, which tends to be more of what they're looking for in these cases.

Many places will make you write the code in a language that you're firmiliar with, but that's more of a generality, seeing as C is really not the langua franca of the programming world anymore, and structuring pseudo code can be a mishmash and all over the place and, in most cases with pseudo code/p&p code not really being taught, down right impossible to deal with.

share|improve this answer
add comment

Data structures are the fundamental bedrock of all programs. You don't necessarily need to have a deep understanding of them, but you absolutely must know how they work.

Why? Because all of your code interacts with and manipulates data. If the data set cannot be stored in a structure, then it cannot be used. Data is like the building materials of a house. Until you put it together into a structure, you just have a useless pile of boards.

Once you have decided on how to think about and define your data set, then you can start using it to do things, the classic algorithm part of the duo. Every single program you write uses a data structure, though in many cases this structure is so simplistic as to almost not exist. A few variables for state data and we are done!

Once you move beyond trivial programs, almost everything requires a data structure. Which would you prefer, a professional architect who designs your skyscraper with best practices and math, or uncle joe bob who immediately starts building?

share|improve this answer
add comment

Interviewers have a tendency to obsess with interface and abstract class questions and other basic OO questions. However, the emphasis on data structures is most likely because without them, it would be virtually impossible to create a useful application; data would be indecipherable and effectively useless. Thus, when you ask if it affect’s ones career in programming, the answer is, “absolutely”. One must be able to visualize how input data will be collected, manipulated, stored…etc. Working with data structures is fundamental to programming as it is for humans to breath air.

share|improve this answer
add comment

One word: scalability. If your data structuring/grouping is all out of whack, it can:

  • take gobs more space (disk, RAM, net bandwidth) (such as DB normalization)

  • take lots more time to process

  • be difficult to debug if/when problems arise

  • be unmaintainable

Rolling your own inefficient or bizzarre data structures for your own system or LAN is one thing; doing it when scaled up to "enterprise size" is quite another.

share|improve this answer
add comment

Whether you write good code or not is a subjective statement. It's important to know that functional code does not always make good code.

That said, data structures are important because they are like the behind-the-scenes workers that you, as the programmer, are directing. It's true that you can call methods on a structure without really understanding what it's doing and you can utilize a structure without really getting how the data is stored, but knowing these details will better prepare you to understand when it is appropriate to use one structure over another.

Knowing, for example, that you can traverse in both directions through a doubly-linked list and only forwards through a singly linked list can help you determine which structure is important when storing data. You can make an even more education decision by knowing that a singly linked list can potentially have lower overhead in terms of memory consumption (since it doesn't contain pointers to previous elements) so, if you only need to iterate forward through a list, you can save some memory by using an appropriate structure.

These are just small examples and, ultimately, if you're feel you're doing well in your career without intimate knowledge of data structures then maybe you don't need to learn more. Understanding what's going on under the hood, though, can really help turn functional code into good code.

share|improve this answer
add comment

I agree that data structures are indeed important to some functions. I however also know that in my experience, some people who performed pretty average on data structures in interviews, actually ended up writing some pretty cool stuff later in the job. This was quite intriguing for me initially. But as I discovered, creative problem solving minds all don't think alike to deliver all answers in an interview. Some like to sleep over, some take some time to build pattern etc. Confusion is an essential part of resolution.

I don't necessary look at even problem solving skill. I look for elements of confusion, problem understanding, play out scenarios etc. Solutions follow, not necessarily in the interview. Solutions coming in interview is an indication of prior knowledge, not necessarily creativity in unknown situations.

Programming is not necessarily a war like situation that needs quick reflexes.

I also dislike asking data structures in telephonic interview. You got to see the person in action on a whiteboard to make any useful sense.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.