+972 52-548-6969
The coding interview that I failed
I’m talking a lot about candidates and the hiring process we go through right now. I thought it would only be fair to share a story about an interview task that I failed.
That was close to 20 years ago, and I was looking for my first job. Absolutely no professional experience and painfully aware of that. I did have a few years of working on Open Source projects, so I was confident that I had a good way to show my abilities.
The question was simple, write the code to turn the contents of this table into a hierarchical XML file:
In other words, they wanted:
To answer the question, I was given pen and paper, by the way. That made my implementation choices quite hard, since I had to write it all in long hand. I tried to reproduce this from memory, and it looks like this:
This is notepad code, and I wrote it using modern API. At the time, I was using ADO.Net and the XmlDocument. The idea is the same, however, and it will spare you going through a mass of really uninteresting details.
I got so many challenges to this answer,though. I relied on null being sorted first on SQL Server and then on the fact that a parent must exist before its children. Aside from these assumptions, which I feel are fairly safe to make, I couldn’t figure out what the big deal was.
Eventually it turned out that the interviewers were trying to guide me toward a recursive solution. It never even occurred to me, since I was doing that with a single query and a recursive solution would need many such queries.
Comments
classic school case? you failed because the answer wasn't on their "solution" list?
And I thought the reason you failed is because there could be very long recursions and you should introduce refs as sub elements instead.
It seems interesting that you got challenges to that answer. What you wrote would be my instinctive response as well, because it is usually faster to get all of the data up front rather than the myriad of db calls a recursive solution would need. I would be curious (in a general rhetorical way) to know how many people fall into each camp (recursive vs dictionary).
I am sorry, but I fail to see how code this produces hierarchical (nested) XML. Doesn't it simply return the XML of all nodes with ParentPostId == NULL without any further child nodes? In fact, wouldn't it throw an Exception in the FOR loop for the first entry with ParentPostId != NULL, since no dictionary entry with that key exists?
I prefer your implementation. As a rule I don't use recursion on a potentially unlimited dataset with a finite stack limit.
Steve,
I don't think so. They understood my answer, they were trying to use this question to figure out if I understand recursion and where to apply it.
They didn't consider my implementation when writing this question, so they were kind of stuck, because they didn't want to come out and say "recursion".
D.R,
The question was to generate the hierarchical structure. When using recursion, yes, you have to be careful of overflowing the stack, depending on the data set in question.
My solution wouldn't have this issue.
Stuart,
That is a good question, and would be an interesting scenario to test out if I was running experiments on students, I guess.
My feeling is that most students would think about recursion first, you need to feel the pain on many queries to understand the issue with that and go to dictionary.
For fun, we can make this question assert a memory limit, so you can't hold the entire thing in memory. That would make it a lot more interesting, I think.
Manu,
You are absolutely correct, I missed a line where I assigned the new entry to the dictionary under its id.
I fixed the code and it should be clearer now.
You knew something they didnt - recursion and SQL dont mix very well.
Is the example wrong, or is your implementation wrong?
How can there be 2 post-id's=1?
But I would say that it depends on the typical data-size... If it has 10.000 levels then recursion would kill you. If it has 1.000.000 comments then the question is if you have the memory for the dictionary...
Christiaan,
You are correct, I messed up the example, fixed now
@ Stuart, for my part, my naïve implementation would probably be recursive; then, aware of the stack overflow issues, I'd probably refactor to a loop.
Comment preview