Where can I learn more about datastructure tricky questions?

Question

I am relatively new to programming (around 1 year programming C#-winforms). Also, I come from a non CS background (no formal degree)

Recently, while being interviewed for a job, I was asked about implementing a queue using a stack. I fumbled and wan't able to answer the question. After, the interview I could do it(had to spend some time). I have learnt (and think that I know it well) basic algorithms in datastructures using the book Data Structures: A Pseudocode Approach with C - Richard F. Gilberg (Author) . I want to know about sites/ books which have such questions along with answers. I think this will allow me to develop my CS specific problem solving skills. Any help is appreciated.

BOUNTY: I am looking at some blog/website with datastructure and algorithms Q&A.

Answer 1

I think Introduction to Algorithms is the best book on algorithms you can get. Don't be mislead by the title though - its a fairly difficult read.

Answer 2

This is the best resource for data structures like the ones you describe in the question:

Algorithms and Data Structures
Get information on programming algorithms and data structures in C#.

http://msdn.microsoft.com/en-us/vcsharp/aa336800.aspx

There is also this:

Data Structures and Algorithms with Object-Oriented Design Patterns in C# http://www.brpreiss.com/books/opus6/

Answer 3

I don't think that question is at all goofy, it sounds like a pretty reasonable interview question to me. The idea that people think questions that require only basic knowledge of fundamental data structures are unreasonable is pretty troubling though. I guess that's the lagacy of things like the Java Collections framework. As for books, any data structures & algorithm book should cover this stuff.

Taking a look at my bookshelf the ones I have are:
* Classic Data Structures in C++, Timothy Budd
* Data Structures, Algorithms, and Applications in C++, Sahni Sartaj
* Introduction to Algorithms, Cormen, Leiserson, & Rivest

THe first two may well be out of print at this point and I suspect you're not really into C++ (not nearly as popular now as it was 10 years ago when I was in school). I'm not even sure that they first two are that great, but they're what's on my shelf. Intro to Algorithms, as noted above, is mostly restricted to algorithms (with the notable exception of trees) and the pseudo code it uses for examples I found somewhat difficult. It aslo spends a lot of time with proofs using discrete math. I've never used discrete math or done proofs professionally, though I'm sure those skills have proved useful to those in more difficult parts of the field.

I got the sense you were geniuinely interested in learning the concepts behind this stuff. If it's more because you just want to pass interview questions a better bet is something like
* Programming Interviews Exposed
but to me that's kind of like reading hte Cliff Notes for a book you were assigned in school rather than the actual book. It is good if you were already familiar with the concepts (which you said you were not) and just need a little refresher.

EDIT: Not knowing of anything better, looked around for old syllabi from my school and found this from a recent instance of one of the courses I took. It has some material, including homework assignments, and lecture notes, that may be of interest, but no answers to the assignments unfortunately: http://irl.eecs.umich.edu/jamin/courses/eecs281/syllabus.html

Answer 4

Well, you're on a Q&A site - Questions tagged data-structures, sorted by votes:
http://stackoverflow.com/questions/tagged?tagnames=data-structures&sort=votes&pagesize=15

Answer 5

Topcoder.com has some great tutorials that will help you start thinking like a smartypants interviewer. Take a look

Answer 6

Go through these Questions. This is a comprehensive list of common questions (with solutions ) based on c/Trees/Link List/ Sorting etc.

http://profile.iiita.ac.in/pkmallick%5F03/adfaqpublish.html

Plus one more thing. Don't try to mug up the solution. Try to follow the logic. This will help you solve questions which you haven't encountered before.

Answer 7

Hacker's Delight is an absolute must-have for everyone who likes coding a bit (pun intended).

Answer 8

Begin with Purely Functional Data Structures. Don't be fooled by the fact that it's "purely functional" - this limitation will help you reason about the structure itself without being bogged down in the barely-tenable tricks of mutable memory (which quickly fall apart in the face of parallel processing unless guarded by a complex series of locks). As an example, the data structure from your interview is purely functional. The author, Chris Okasaki, has a blog which will give you a flavor of his way of thinking. The book is tiny, but every single sentence will help you think about data structures. Carry it with you everywhere and read it whenever you need enlightenment.

(Edit: The book was based on Okasaki's thesis, which I have linked to. Take a look at it if you want, but the book improves upon it with invaluable exercises and additional material.)

It will take a long time to master that book, but if you do, you could do worse than to move on to Advanced Data Structures. I must admit that I have not read this one, but it is a state of the art book on data structures. I trust the reviewer who compares it to Motwani and Raghavan, as such a recommendation requires a high degree of sophistication.

Answer 9

Sorry, not a Q/A site, but definitly worth reading (especially if you're into c#) is boyet.com For question, as already mentioned, may as well come back here.

It's a little hard to navigate, but posts specifically on Algorithm's / Data structures can be found here.

Answer 10

Hacking a Google Interview from MIT: http://courses.csail.mit.edu/iap/interview/materials.php

Answer 11

Wikipedia has a surprisingly detailed guide to many data structures (and their associated uses) including quite a bit of formal theory in terms of Big-O behaviour and links to implementations in various languages.

As a jump in point for high level overview go to Data Structures

For a simple a categorized list

If you have specific goals as to efficiency with large numbers of entries then this is a good "what should I try first" page.

Many of the 'top level' pages like Tree are excellent guides to the standard nomenclature used in CS to describe the aspects of both abstract and concrete structures. Thus improving your ability to converse with others in the field. Contrast this with learning from a specific libraries implementation where you see things like the .Net Dictionary verses java's Map verses perl's Associative arrays(1).

Sometimes there is no consistent name for things and then wikipedia's tendency to avoid indicating emphasis on one particular view helps since there is a tendency to be explict about the various differeing names invovled (see Associate Array for an example.

Whilst you must read it with a eye to the quality of each page I have found it useful both as a direct resource (comparison of sorting algorithms and as an excellent way to look for alternatives to another data structure.

---

1. The most common abstract names for this sort of key value conceptual data structure is Map or Associative Array, map can confuse people due to it's prevalence in functional programming languages as a commonly used function.

Answer 12

My answer: Introduction to Algorithms : T.Cormen & Leiserson & Rivest

Answer 13

Sandbox,

Your interviewer was not asking a trick question. More than that, I am simply floored by the number of comments to your question which insist that the question is "bad" or that the implementation is "daft", "stupid", or "inefficient". A queue from two stacks is the canonical way of implementing immutable queues.

You're interviewer is testing whether you have a solid understanding (or at least cursory familiarity) with immutable data structures. Another user has already recommended the book, but its worth posted again: Purely Functional Data Structures by Chris Okasaki.

All of the source code in the book uses a non-standard variant of SML. For what its worth, I wrote a very watered down introduction to immutable data structures using F# which provides a queue implementation from two stacks, and most of the other code is based on Okasaki's book. If you don't grok pattern matching and can't read ML-like languages, then I recommend the following series of articles on immutable data structures using C#:

1. Kinds of Immutability
2. A Simple Immutable Stack
3. A Covariant Immutable Stack
4. An Immutable Queue (Read this!!)
5. A Simple Binary Tree
6. More on Binary Trees
7. Even More on Binary Trees
8. AVL Tree Implementation
9. A Double-ended Queue
10. A Working Double-ended Queue

I personally think the C# code is ridiculously unreadable by comparison to the ML versions -- but, once you understand the underlying principles, you'll be a better programmer for it and won't be stumped so easily by these "tricky" interview questions.

Answer 14

Some of the tricky datastructure problems have solutions like, "swap the names of datastructure 1 & 2" you have to think out of the box a bit.