Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Background

I was just asked in a tech interview to write an algorithm to traverse an "object" (notice the quotes) where A is equal to B and B is equal to C and A is equal to C.

That's it. That is all the information I was given.

I asked the interviewer what the goal was but apparently there wasn't one, just "traverse" the "object".

I don't know about anyone else, but this seems like a silly question to me. I asked again, "am I searching for a value?". Nope. Just "traverse" it.

Why would I ever want to endlessly loop through this "object"?? To melt my processor maybe??

The answer according to the interviewer was that I should have written a recursive function.

OK, so why not simply ask me to write a recursive function? And who would write a recursive function that never ends?

My question:

Is this a valid question to the rest of you and, if so, can you provide a hint as to what I might be missing? Perhaps I am thinking too hard about solving real world problems. I have been successfully coding for a long time but this tech interview process makes me feel like I don't know anything.

share|improve this question
172  
The only correct answer here is "I don't understand the question." –  user16764 Apr 12 '12 at 21:17
15  
Well, if they really didn't say what A,B, and C are (like - they are objects) and they put object in quotes, they seem to have there own unique terminology. If they asked how to traverse an object graph where object A references object B which references object C which references object A it would have been intelligible, but why it has to be recursive I don't know. It needn't be infinite if you maintain a list of already visited objects, by the way. But yes, I would be concerned about working for a company using that test - they seem confused. –  psr Apr 12 '12 at 21:18
72  
The question as described is nonsensical, and so is the answer. Either you're misremembering what they asked, or the person doing the asking is an idiot and you're probably better off not working with him. –  Mason Wheeler Apr 12 '12 at 21:18
24  
Why do dev interviews have to be painful? Can't we all just sit down and look at each other's code and discuss? Devs will know where other devs are at by doing this and it won't take 6 hours. Code tests are the worst. I don't mind admitting that I suck at delivering optimum solutions while 3 devs I've never met watch me as I type. –  Erik Reppen Apr 12 '12 at 23:10
18  
I had to check your profile to see if you lived in the same area as me because I worked for a short time at a job where a fellow interviewing me asked, "Are you detail-oriented?" To which I replied, "Can you be more specific?" And his reply, "I can't explain it, but I know a detail-oriented person when I see their work." Love ambiguity. –  Jesse C. Slicer Apr 13 '12 at 5:42

14 Answers 14

up vote 272 down vote accepted

It's a baffling, invalid interview question. The interviewer couldn't clearly articulate what it was that he/she was looking for and expected you to read his/her mind instead of responding meaningfully to your appropriate attempts to clarify the statement of the problem. Consider yourself lucky you didn't get the job.

The meaning of the verb "traverse" operating on a generic "object" is ambiguous, in my opinion. Start substituting a variety of different nouns for the word object and it quickly becomes obvious that traversal of an object is only meaningful for a small subset of the universe of things that are objects.

It makes sense to "traverse" the nodes of a "binary tree". It doesn't make sense to "traverse" a "clown". Yet, an object can just as easily represent a "clown" as it can represent a "binary tree".

share|improve this answer
206  
+1 for clown traversal. –  Mason Wheeler Apr 12 '12 at 21:47
9  
I've recently gotten into the practice of replacing nouns in silly questions with the word "clown" +1 sir! –  rupjones Apr 12 '12 at 21:57
96  
"Clown traversal" - what a great Meme for "stupid technical question". Pass it on! –  radarbob Apr 12 '12 at 22:50
8  
Hmm, I can traverse var clown = { hat:"with flower", hair:"bright red", nose:"red ball", mouth:"Red mouth framed in white",...} ;) –  mplungjan Apr 13 '12 at 7:29
30  
My entire area of theoretical CS research involves iterative clown traversal, you insensitive clod! –  Jack Maney Apr 13 '12 at 15:54

Coming very late to this party, but I think the interviewer incorrectly asked this question:

Write an algorithm to traverse an array and determine that A is equal to B and B is equal to C and A is equal to C, in that order.

Then the correct answer would be a recursive algorithm.

share|improve this answer

I was just asked in a tech interview to write an algorithm to traverse an "object" (notice the quotes) where A is equal to B and B is equal to C and A is equal to C.

The object in question is made up of the parts A,B and C, and it forms a triangle. The person is simply asking if the object (a collection) contains all equal parts.

The interviewer wants to know if presented with parts A, B and C can you tell if they are all equal without getting stuck in an infinite loop. This question is stupidly simply to understand and still they managed to f*** it up in asking it.

They are all equal when A == B && B == C && A == C, but that can be simplified to just A == B && A == C.

The simplicity of the question resulted in confusion, and it really is worded badly.

The correct wording should have been.

Write an algorithm to check the parts of a collection to see if they are all equal to each other. Care must be given not to get stuck in an infinite loop. For example; if parts A is equal to B and B is equal to C and A is equal to C could cause problems.


The answer according to the interviewer was that I should have written a recursive function.

Yes, you can answer the question are all my parts equal using recursive functions. No, this is not an efficient solution.

EDIT: After some thought. No it's not possible to check a collection contains all equal parts using a recursive function.

The most efficient solution is as follows.

function are_all_equal(parts)
{
   for(int i=1; i < parts.length; i++)
       if parts[i] is not same as parts[0]:
           return false;
   return true;
}

print are_all_equal(parts) ? "yes" : "no";

This problem does occur in programming, and asking someone to write an algorithm to test a collection is perfectly normal. Depending upon the programming language this problem can often be solved with just one line of code.

Wording as they did, and expecting the wrong answer is not normal. Since this question was ask a year ago. I truly hope you ended up working somewhere else. I'd be interested in hearing from the original post how things turn out for him/her.

share|improve this answer
1  
Things turned out great--ran as fast as I could from that company and have been happy ever since. –  Matthew Patrick Cashatt Jun 17 '13 at 22:41

Was this a Java interview question, if so, may be he wanted to test your skills with overriding "hashcode" and "equals".

You would have to override these two methods and use the overridden equals method to stop the recursion when you compare A with A.

Without overriding, your comparison for "object" A to B, A to C and A to A will all result true but after overriding, only when object A compared to object A will return true where as other comparisons will return false.

share|improve this answer

Write an algorithm to traverse an "object" (notice the quotes) where A is equal to B and B is equal to C and A is equal to C.

It seems like most people assume that A, B, and C are pointers, but they could just as easily be clowns, too. (Or members of the clown class.) Or they could be clown names. (Or class names. Or subclasses of the clown class.)

I would have turned the tables and asked if this is how they typically prepare development specifications, and then tell them how I could help them with the requirements specification stage of development. Poor communication of expectations leads to poor work product. Either they would get it or they wouldn't, If they didn't get it, I would walk away.

share|improve this answer

While the question was poorly worded and the interviewer was clearly unhelpful in providing any direction, I have a slightly different take on what was being asked.

I think interviewer was looking for a solution that traversed the object structure using some type of reflection. The information that the three objects were equal should have prompted a conversation of object identity comparison (A == B means the objects are really the same object in memory), or object equality comparison (A == B means the values of the objects are the same).

The fact that the interviewer said that the answer was a "recursive" function, probably indicated that a discussion of deep versus shallow copying and comparison was expected.

share|improve this answer

While I cannot speak for this specific interviewer, I've seen similar questions in a front-end developer position interview, so the language I'll use in this example will be JavaScript.

Given:

var A = {
    key1: 'value1',
    key2: 2,
    key3: {
        innerkey1: 'value3'
    }
}

A typical wrong response may "traverse" the first level only and print/compare:

'value1'
2
[Object object]

So while coding a recursive example that would traverse all levels, I would mention things like:

  • Circular reference handling
  • How to handle arrays (should they be recursively traversed too?)
  • Should functions be evaluated and their return value processed?
  • For JavaScript: should the prototype match and should inherited properties also be compared?

So the "solution" that I'm guessing the interviewer was going for was to get a conversation started on a seemingly-simple question that has many advanced topics - recursiveness, pointers/references, expectations, etc.

share|improve this answer
4  
That makes sense that way you put it, WSKid. Unfortunately, none of that context was offered. –  Matthew Patrick Cashatt Apr 12 '12 at 21:28
2  
True, this is really grasping at straws. They should have presented a use case, or an example 3 objects, or something to give a lead in to the actual problem. –  WSkid Apr 12 '12 at 22:37
1  
I was thinking the same, only for python object attributes. Knowing which question they expected an answer in would have been hugely helpful, but that could be expected by the context of the position, ie python dev, c# dev, javascript dev, php dev, etc –  Kenneth Posey Apr 13 '12 at 1:34
1  
+1 for finding a context where the question makes some sense! –  Donal Fellows Jun 17 '13 at 18:06

Some interviewers specifically try to ask questions to see if the candidate is smart and honest enough to give one of these two answers:

I don't know.

or maybe:

I can't answer that as stated.

They don't want a candidate who will accept pure BS as a spec, and waste their employer's time and pay trying to implement it.

share|improve this answer
6  
Our entire lives we are conditioned, in such a scenario as this interview, to be able to provide an answer to a question. If saying "I don't know" (which I did, by the way) was acceptable, then I should have been told that before hand as well. An attempt in good faith to answer an interview question is not necessarily tantamount to how one would treat an inadequate spec or set of requirements. And I think this is the whole point, these interviews have veered off course and are missing the point in many cases. –  Matthew Patrick Cashatt Apr 13 '12 at 7:41
    
Such a good answer. However, don't forget that it takes a lot of experience to be able to say this. Personally, I can say that experience with interviews is a vital part of the job. @MatthewPatrickCashatt if the interviewer will not accept "I don't know", then not much more to dicuss IMO. –  arin Apr 13 '12 at 16:12
2  
Trick questions are either trolling or abject incompetence. Either way if an interviewer asks trick questions you don't want to work there. –  Ben Brocka Apr 13 '12 at 21:26

I would have said that one algorithm for traversing an object is the classic depth-first search DFS. To traverse any object whatsoever, we visit that object first and then enumerate its constituent sub-objects (or else neighbors in a graph), and recursively traverse those objects. Since there may be cycles, to avoid getting into infinite loops, we keep track of objects we have traversed already, for example by adding them to a dynamic set which is passed around in the recursion, or by marking bits inside the objects themselves. This bookkeeping takes care of not only cycles but situations when there are multiple paths to reach the same node, such as the A = B, B = C and A = C graph. That, dear interviewer is DFS in a nutshell; I can write down pseudocode if you like.

That bit about A is equal to B is a cryptic way to describe a graph, because in graphs adjacency can be directed (go one way) and doesn't have to represent anything particular, such as equality. But it is giving an equivalence relation and that is a kind of forest in which all of the elements in the same equivalence class form a connected component. If you want to find the set of items in an equivalence class, you can do that by performing a graph traversal starting at any one of the items.

Note that an equivalence graph is inherently cyclic because the edges are two-directional. That is to say, because A is equal to B, B is also equal to A (reflexivity). So when traversing from A to B, you must take care not to proceed from B to A. It's easy to forget that a graph with undirected edges is actually cyclic because each undirected edge can be visualized as two directed edges in opposite directions. The use of an equivalence relation is probably deliberate, to trip you up.

share|improve this answer
1  
This is a pretty good interview question because it weeds out the interviewees without sufficient imagination, who need every word defined, and everything explained before they can proceed. That kind of literal-minded developer is cranked out from the institutions at a dime a dozen. Interviews are like jazz improv. Just catch three notes, like ACE, and start jamming in A minor, then adjust if it's actually A dorian, or whatever. Don't ask, what is the key signature, where is the sheet music, etc. –  Kaz Apr 13 '12 at 3:24
1  
But this only emphasizes the absurdity of the question for a job that will only need to handle common objects of mostly known dimension. Why not just ask how I would traverse an XML file and retrieve a given object? Why not have me demonstrate a binary search of an array? These would be useful demonstrations of skills that the job would require (it's only a contract job for crying out loud!!). I can appreciate that you are smart, but this line of thinking is exactly what is wrong with the process--you have people with a myopic view of the job requirements keeping the gates. –  Matthew Patrick Cashatt Apr 13 '12 at 4:36
1  
A question like "How would you traverse an XML file" has the merit of being kind. I would traverse it by opening the door behind me and recursing out into the street, as far away from the XML-pushing shop as possible. :) –  Kaz Apr 13 '12 at 4:55

It seems to me that this is a (poorly articulated) question regarding a circular linked list. I would have likely asked if that is what was meant (because the answer would be certainly different than another above which is to say they are all references to the same object).

If this was a linked list question, then you (in this case) have a singly linked list, where the end node points to the other end (although if it was worded as you say - then it may be doubly linked if A points to B and C - but clarification on the interviewer's part would help this).

A -> B -> C -> A

Also (and this happens all the time), the interviewer may have read this question, thought it was a 'good' question, but didn't actually know the answer themselves (or even what it meant).

share|improve this answer
1  
Thanks Maich--I think that your final point is the most likely. –  Matthew Patrick Cashatt Apr 13 '12 at 2:35

I can see three possibilities here.

  1. She was completely incompetent. Not much more to say on that one.
  2. She was deliberately making it ambiguous, to see how well you'd do at asking questions to figure out what you were supposed to do, and what she was really after.
  3. For whatever reason, she'd decided she didn't want you hired, so she asked a question that was unanswerable as given. When she was asked about your skills, she'd skip over that part and say something like: "I asked him about how to traverse a three-node graph, and he was completely stumped -- didn't have even a clue of how to start. Obviously he's grossly incompetent! We shouldn't even consider hiring him."
share|improve this answer
5  
"I asked him about how to traverse a three-node graph, ..." If the OP post i correct, there no mention of a graph or node. just "objects". This is a form of "false testimony". If she writes something like this can be prosecuted! –  Emilio Garavaglia Apr 13 '12 at 6:52
7  
Do you usually use female pronouns when the gender of the person is not mentioned? –  Chan-Ho Suh Apr 13 '12 at 10:01
7  
@EmilioGaravaglia: First of all, it might never be written. Second, even assuming it gets written down, you'll undoubtedly never get access to it, just a "we regret to inform you..." letter. Third, unless you have a recording of the interview, how would yo prove the interviewer wasn't telling the truth? Bottom line: in theory you should be right -- but in reality, there's virtually no chance. –  Jerry Coffin Apr 13 '12 at 13:31
7  
@Chan-HoSuh: The OP mentions the gender in one of his comments. –  Jerry Coffin Apr 13 '12 at 13:31
1  
@JerryCoffin My apologies then. –  Chan-Ho Suh Apr 13 '12 at 16:43

Part of the challenge here is to get more detail by asking specific questions to get out that there is a tree structure and what are the components involved in doing a traversal. There may have been the assumption that there aren't many other data structures that one traverses besides trees but that is a bit of a leap to my mind.

share|improve this answer
1  
Thanks JB King. It is good a good reminder to ask questions. In this particular case, I did. In fact, I even asked if it was a tree and the answer was no! But your point is well taken that it is my responsibility to distill as much information as possible by asking questions. –  Matthew Patrick Cashatt Apr 12 '12 at 21:47

They may want to try to figure out how you deal with strange problems. But in this case, it has nothing to do with a "tech interview". It looks more like a psychological interview.

share|improve this answer
5  
I'd love to see an example of one of their tech specs for a software project. –  Rubber Mallet Apr 13 '12 at 1:35
    
If the interview is for a systema analyst or a similar position, this is entirely apt: your job is to help customers clarify their questions, rather than to answer them. –  reinierpost Apr 13 '12 at 13:26
1  
@reinierpost--It wasn't. –  Matthew Patrick Cashatt Apr 13 '12 at 15:06

This is just a wild guess, but assuming the interviewer is talking about pointer references (and it's a trick question), the answer is: there's nothing to traverse, because all of the references point to the same object.

A recursive function? That's for traversing a tree. I see nothing in the original question that would imply that he's talking about a tree.

share|improve this answer
27  
Move on. There are better companies to work for. –  shufler Apr 12 '12 at 21:18
7  
Nah. It's a lost cause. If the interviewer thought he was wrong, he wouldn't have asked the question in the first place. I was once asked to write a sample in any language I wanted to; the person interviewing me assumed that pseudocode was a valid choice. –  Robert Harvey Apr 12 '12 at 21:19
8  
@Robert Harvey: What's wrong with pseudocode? –  James Apr 12 '12 at 21:37
6  
@Robert Harvey: To be fair all most people want is to figure out how you solve the problem not to find out if you've learned off the syntax of any particular language. It's quite common for algorithms to be specified in pseudocode. –  James Apr 12 '12 at 21:47
7  
What's the difference between pseudocode and Python? :) –  David Robinson Apr 13 '12 at 5:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.