This is the sixth in a
series of answers to
100 Interview Questions for Software Developers.
The list is not intended to be a "one-size-fits-all" list.
Instead, "the key is to ask challenging questions that enable you to distinguish the smart software
developers from the moronic mandrills." Even still, "for most of the questions in this list there are no
right and wrong answers!"
Keeping that in mind, I thought it would be fun for me to provide my off-the-top-of-my-head answers,
as if I had not prepared for the interview at all. Here's that attempt.
Though I hope otherwise, I may fall flat on my face. Be nice, and enjoy (and help out where you can!).
This week's answers about data structures are complementary (indeed very intertwined with) last week's
questions about algorithms.
Also like last week, I'll
wait until the end to give reference information because all of this post relies on experience, but there
are two sources where I'd start learning the information for every question.
- How would you implement the structure of the London underground in a computer's memory?
Without having travelled to London or on its subway system, I'd guess a graph would be the right
data structure. The set of vertices would represent the stations, and the edges connecting them would
be the tracks.
Not safe for work (language):
I don't know the proper in-memory representation of tramps.
- How would you store the value of a color in a database, as efficiently as possible?
Efficiently for retrieval speed, storage speed, size? I'm guessing size. After asking why such efficiency is
needed, and assuming we're talking about a range of up to 166 colors (FFFFFF), I'd just store it as the smallest
integer type where it would fit.
- What is the difference between a queue and a stack?
A queue is typically FIFO (priority queues don't quite follow that)
while a stack is LIFO. Elements get inserted at one end of a
queue and retrieved from the other, while the insertion and removal operations for a stack are done
at the same end.
- What is the difference between storing data on the heap vs. on the stack?
The stack is smaller, but quicker for creating variables, while the heap is limited in size only by how much
memory can be allocated. Stack would include most compile time variables, while heap would include anything
created with malloc or new. (This is for C/C++, and not strictly the case.)
- How would you store a vector in N dimensions in a datatable?
I need a little direction for this question, as I know not what it means. I encourage my readers, who have
on most occasions proven themselves more adept than me, to come through again.
- What type of language do you prefer for writing complex data structures?
I can't imagine using anything higher level than C or C++. Anything more advanced has most anything already
built and not very easily molded. Or perhaps I just wouldn't think of it as complex.
- What is the number 21 in binary format? And in hex?
10101 in binary and 15 in hex, and no I didn't cheat and use a calculator. It works just like decimal.
Take the following digits of an arbitrary number in base B:
UVWXYZ
The number in decimal is U*B5 + V*B4 + W*B3 + X*B2 + Y*B1 + Z*B0
As more digits are added, you just increase the power by which it is raised. Also note that any number raised
to the zeroth power is 1, so the Z element is just itself, and the ones digit.
- What is the last thing you learned about data structures from a book, magazine or web site?
As with my answer to this question with regard to algorithms, I'm certain I've used to web for reference here,
but I'd guess my introduction and original knowledge acquisition came from a book.
However, I would add journal article to the list of answers, because in both cases that would have been my
answer, even though I read them via the web.
- How would you store the results of a soccer/football competition (with teams and scores) in an XML document?
<fixtures>
<fixture>
<team name="Chelsea FC">
<score>0</score>
</team>
<team name="Fulham FC">
<score>1</score>
<!-- any other stats? -->
</team>
</fixture>
</fixtures>
That might be reasonable.
- Can you name some different text file formats for storing unicode characters?
I have to be honest here and say I don't know what you're talking about. I can't think of a file format
that wouldn't take it.
Again the reading material is similar to last week:
- The Art of Computer Programming series by Donald Knuth
- Wikipedia's list of data structures is another good place to start.
- Perhaps a book or resource on data modeling, since there were XML and DB questions.
What advice would you give?
Hey! Why don't you make your life easier and subscribe to the full post
or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate
wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!
Leave a comment
Thanks man for these Q&A. I know it's an old posting but maybe what i write will still help somebody. Here's my take on the N dimensions vector: as it can be represented mathematically as V[S1][S2]...[SN] (where Si is the size of a dimension) then the total number of elems is S1*S2*..*SN. You make a database table with N + 1 columns and S1*S2*..*SN rows.In the first N cols you write the indexes of each element in the corresponding dimension. In the (N + 1)th column, the actual value.
Posted by GC
on Dec 05, 2012 at 07:45 AM UTC - 5 hrs
Thanks GC, I'm sure it will be helpful for future visitors!
Posted by
Sammy Larbi
on Dec 09, 2012 at 12:19 PM UTC - 5 hrs
i am searching over internet for interview Q. and i found your site.
Very good list
Posted by
funnymemes
on Apr 27, 2016 at 12:39 AM UTC - 5 hrs
