Data structure and systems design questions

If one is asked to "Design a system for such开发者_运维技巧 and such" or "What data structure would you use for such and such?"...is it okay to answer with a relational database system design? Complete with the tables, entities, relationships between them, foreign keys and primary keys, etc? Would this be okay for one that has a lot of experience using database systems, but no project experience using data structures? I only know Linked Lists, binary trees, binary search trees, stacks and queues...nervous for my upcoming intern interview. Any advice?

Linked lists, trees, and stacks are tools for acting on data in a program. Database tables and table designs and relationships are tools for storing data. The "system" uses both of these but for different purposes, but they do work togethor.

"Design a system for such and such" This is a higher level question, and so I would first start by talking about database tables, and then depending on how much detail they are after, move into program specifics.

"What data structure would you use for such and such?" This sounds like a question about algorithm design, so here is where you are probably being asked about trees and stacks.

Hope that helps :p

In interviews, questions designed to test your familiarity with data structures (and often with algorithmic complexity) are NOT about relational databases. Questions about system design may well involve a database design part.

The data structures you mentioned are all important. The one that's most obviously missing and very important is hash tables (or unordered maps, and the basis for data structures in many scripting languages, such as dicts in python and objects/maps in javascript). You should also read up on btrees, which are usually used to implement relational databases (and have properties like binary search trees, but are better suited to disk storage).

In an intern interview, that's not ok.

I would expect you to be familiar with fundamental data structures, but I wouldn't expect you to be an expert in any of them. (Not what I'd call an expert, anyway.) I'd be more interested in how you respond to questions that are clearly beyond your current knowledge. If I asked you about the theoretical advantages of a van Emde Boas tree, "I don't know" would probably be the right answer. (Better than trying to bluff me.)

But, as a practical matter, you can apply relational design principles profitably to many problems that aren't obviously relational. Most Lotus Notes applications would benefit from a solid relational design. Even though you can't implement constraints declaratively in Notes, you still have to account for them somehow--exception reports, period document crawling, whatever.

And, IIRC, the first extended example in Large Scale C++ Design was as much a relational design issue as a C++ or OO design issue. (That thing was published in 1996. Am I that old? Yes, I guess I am.)