Data Structure Interview Question

Question

I was asked the following Question: How would you store the data given below(which data structure would u pick):

A-1-2-3-4-5-6

|

B-7-8-9-10-11

|

C-12-14-15-16-17

My ans: Since this looks like a bunch of lists with its head nodes linked together. Use two node types one id the regular node type with the following definition:

Struct node1
{
int val;
struct node*next;
};
// to store the numerical part of the data

struct node2
{
 int val;
struct node *down;
struct node* next;
};
//this is the heads of each list.. for the alphabet part of the question.

The Interviewer's reaction: Is this the best data structure u can think of . How abt in terms of traversal and memory needed for each node?

My answer to that: We can traverse better if we create some sort of hash table.

My question to you comrades: Can we do a better job ?? Is there a better way to store this type of data?

we assume that the data is all numbers (even the ones at each head node) and non serial with repetitions possible . What would be the right answer ? Looking for answers in C/C++

Answer 1

For better traversal and memory usage, you could consider using a list of variable-length-arrays (Java ArrayLists)

Answer 2

I think that this question was aimed at getting thoughts from you about the data structure.

If it is really only a char and 6 integers for each node, you wouldn't need to store two lists. Also, how it is going to be used would be important to take into consideration. Maybe even a char and a numeric range would suffice, this depends on what the data really is.

Answer 3

The first question I would ask is about the data. It appears to be a simple case of where to break a series of continuous numbers. Given that I would just store the break points. These types of questions are designed to test your ability to ask questions and drill down into the underlying issue.

Answer 4

If they literally mean "store range #s from N to N+x", then you can compress this down to a map from a letter to start-of-range and end-of-range tuple ;)

Answer 5

I would ask how the data is going to be used. The interviewer will either reveal what he initially withheld to see if you'd ask, or make something up. Then I'd ask what kind of updates and how it will be updated. It would be less likely for him to have thought this far ahead, so bonus interview points. Otherwise make up an in-memory storage structure just complicated enough to account for all the facts, or maybe put it in a relational database.

Answer 6

In C# you could use a dictionary of string/int array:

Dictionary<string,int[]>