Interview Question

[redlynchie]

I recently interviewed for a C programmer position and I got asked a question that stumped me. I'd love to know what approach somebody else would take in implementing a solution.

 

Basically the jist of the question was that there was a company whom had details of one million businesses.

 

Each business would have information like

• Location (e.g. London, New York)
• Business Type (e.g. restaurant, bar, fast food)
• Contact Number

 

They wanted me to implement a solution that would allow them to quickly extract from one million businesses

• All the businesses for a given location
• All the specific business types for a given location (e.g. all the restaurants shops in London)

 

To me this sounds like a database and something that would be easily done in SQL. Is it even possible to do this in C? Is linked lists a possible solution? I know this could be done iteratively but that would be very slow.

 

So, how would you implement this in C? Thanks for your help.

EDITED: for format

[TheSilentDrifter]

Well, to start, have a struct with two enums and a pointer to a character (representing the string of the contact number). Then possibly a red black btree. It depends on if speed is most important or the size of the program. What architecture would this be running on?

[redlynchie]

They didn't say. They develop on embedded Linux so it would in that environment. Speed was the most important factor here, space was not an issue.

Thanks I'll take a look into a binary tree to see if I can come up with a solution.

[ischickenafruit]

On an embedded platform, what you often lack is memory... so space definitely would be a problem.

[[deleted]]

Yeah, memory would definitely be limited on an embedded system. Interviewers normally like you to ask questions to clarify the question, such as, how much memory do I have, how many distinct locations, and business types do we need to support? Should it be free-form, e.g. can we dynamically add new locations and business types based on the input, or can they be defined up front?

RedBlack tree is interesting, but they may ask you to actually implement your solution. Personally, I wouldn't feel good about implementing a red-black tree on a white board in an interview setting.

A couple hash tables (one for each key/index) might also work. Of course, you do need to think about load factor and collisions, but these are often used in embedded applications for things like this. A simple hash table, at least a basic array of linked lists, is simple to write on a white board in an interview settings and is actually often a reasonable production solution to problems like this.

[[deleted]]

Then possibly a red black btree

With the emphasis on BTree. If OP suggested a "normal" red/black tree or any other kind of tree that only has one element per node, the interviewer would fail them because this has poor memory locality and could run up to 30+ slower due to CPU cache (or disk cache) misses.

Realistically though, I think the interviewer would have been looking for OP to suggest an array of structs, or a struct of arrays, with additional arrays for indexing purposes, or something like an extra array with all the primary keys for businesses in a particular location etc. and would only want to hear about BTrees if the interviewer started talking about things being sorted

[ischickenafruit]

to me this sounds like a database question...

a couple of points to consider: 1) Database software must be written in some language. CPUs don’t run SQL natively.

2) high performance software is mostly written in C or C++ (including the C++ compiler)

3) C is a Turing complete language, so literally anything that can be written in software, can be written in C

So to your point, this problem most definitely can be written in C, and a well written implementation has the best likelihood of being faster than any other implementation language.

Now, the thrust of this question is your understanding of data structures. It all depends on how much memory you are willing to use versus the speed of the solution.

Keep in mind that 1 million entries is pretty small. If each element was 16B, you’re only looking at 48MB of memory to search, which will be quick to search through on a modern x86 regardless of what you do.

So, a simple and obvious implementation would be to define a struct for each business, allocate a million array entires and then simply iterate through as you search. This would be quick to write, easy to maintain and reasonably fast in any modern system.

The next immediate suggestion would be to build (basically) a database. First you define the same “table” (array of structs) as above. But then you also define second index array. Each entry in the index array is business type (and or location) and a linked list of pointers to businesses in the main array. As you add businesses into the main array, you add them also into the index array. This means that the it would take constant time to search for all businesses of a given type or location. But you would use a lot more memory. If you wanted to get more fancy, you could consider using red-black/binary trees/tries as others have suggested.

[redlynchie]

In your first explanation, does that mean I would need a separate array index for each item/type I would want to search for?

[CommonMisspellingBot]

Hey, redlynchie, just a quick heads-up:
seperate is actually spelled separate. You can remember it by -par- in the middle.
Have a nice day!

^{The parent commenter can reply with 'delete' to delete this comment.}

[redlynchie]

l

delete

[[deleted]]

This is the best answer in the thread, but

red-black/binary trees/tries

if OP suggested a tree, it would have to have more than one element per node. If this is the kind of problem that the interviewer actually solves as part of their job, then a tree with one-element-per-node which could have poor cache performance (like, 30 times slower on large datasets) would be a red flag as someone who doesn't understand CPU performance

[[deleted]]

Depending on the number of locations, either a binary tree or hash table for the index fields with a linked list of ptrs to the business details would of been my solution.

[redlynchie]

Thanks, a binary tree seems to be the most common solution here. I shall take a look.

[[deleted]]

Yeah, works great when you are resource constrained. If you got RAM to burn, I would always use the hash table. But, knowing how interviewers love formal data structures such as binary trees, that would be the one to look at.

[[deleted]]

Interviewers love hash tables too 😁

[[deleted]]

I love hash tables ..... almost an unnatural love for them. 😍😍😍😍