My Secret Life as a Spaghetti Coder
home | about | contact | privacy statement
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:
  1. The Art of Computer Programming series by Donald Knuth
  2. Wikipedia's list of data structures is another good place to start.
  3. 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!


Comments
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

Leave a comment

Leave this field empty
Your Name
Email (not displayed, more info?)
Website

Comment:

Subcribe to this comment thread
Remember my details
Google
Web CodeOdor.com

Me
Picture of me

Topics
.NET (19)
AI/Machine Learning (14)
Answers To 100 Interview Questions (10)
Bioinformatics (2)
Business (1)
C and C++ (6)
cfrails (22)
ColdFusion (78)
Customer Relations (15)
Databases (3)
DRY (18)
DSLs (11)
Future Tech (5)
Games (5)
Groovy/Grails (8)
Hardware (1)
IDEs (9)
Java (38)
JavaScript (4)
Linux (2)
Lisp (1)
Mac OS (4)
Management (15)
MediaServerX (1)
Miscellany (76)
OOAD (37)
Productivity (11)
Programming (168)
Programming Quotables (9)
Rails (31)
Ruby (67)
Save Your Job (58)
scriptaGulous (4)
Software Development Process (23)
TDD (41)
TDDing xorblog (6)
Tools (5)
Web Development (8)
Windows (1)
With (1)
YAGNI (10)

Resources
Agile Manifesto & Principles
Principles Of OOD
ColdFusion
CFUnit
Ruby
Ruby on Rails
JUnit



RSS 2.0: Full Post | Short Blurb
Subscribe by email:

Delivered by FeedBurner