152

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.

Community
  • 1
Matt Cashatt
  • 3,315
  • 5
  • 24
  • 35
  • 1
    Language agnostic. I was just in front of a white board and asked to write out the algorithm. Of course the interviewer said that the answer was a recursive function (function <> algorithm) but hey. . . – Matt Cashatt Apr 12 '12 at 21:14
  • 199
    The only correct answer here is "I don't understand the question." – user16764 Apr 12 '12 at 21:17
  • 16
    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
  • 77
    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
  • 2
    @psr and Mason Wheeler--Yes, in fairness, she did say that it was a graph AFTER I gave up. Should I have known that ahead of time? I am happy to take my licks and learn from the experience. – Matt Cashatt Apr 12 '12 at 21:21
  • 4
    Sounds like a poor question asked by amateur interviewers, esp given the lack of a language implementation. What does 'equals' mean? Do they reference the same pointer? Or are they copies containing the same data? And there's no particular reason here that recursion is necessarily 'correct'. A simple loop also would work. – GrandmasterB Apr 12 '12 at 21:23
  • 6
    @Matthew: No, you shouldn't have known that ahead of time. If it was an *object graph*, that makes more sense, but she should have said that up-front. Calling it "an object" is just not right. GIGO. – Mason Wheeler Apr 12 '12 at 21:31
  • You probably should have replied with an even more cryptic answer to this. – Venki Apr 12 '12 at 21:33
  • 5
    bool TryTraverse(object target) { return true; } Bam! Done and done. I'll just relax and wait for the offer letter. – Erik Dietrich Apr 12 '12 at 22:42
  • 26
    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
  • 2
    @ErikReppen--Exactly!! None of the more important questions are even discussed: what is an object and what is a class and why do they matter? Why is encapsulation important? How would you profile a sluggish app, or troubleshoot a given bug, etc. Thanks for the comment Erik! – Matt Cashatt Apr 12 '12 at 23:12
  • 3
    BTW, I suspect you got hit with a JavaScript question that was mistaken for a general language question by somebody who probably shouldn't be allowed to interview devs since he clearly doesn't understand it himself. – Erik Reppen Apr 13 '12 at 04:56
  • 19
    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 05:42
  • 1
    An object cannot be traversed. You can traverse a data structure like a tree, list or graph. But to traverse a single object is just nonsense because there is nothing to traverse. And what has this to do with transitivity? – ThomasX Apr 13 '12 at 09:11
  • 1
    As a side note, *"should have written a recursive function."* in interviews I've been (on both sides), any solution with recursive function would be questioned and considered a red flag. Unless candidate would be either explain how to unroll that into iteration, or explain how tail recursion optimizing in language he has choose works. – vartec Apr 13 '12 at 09:15
  • 3
    @user16764: Nope. The only correct answer is: "The question as is does not make sense". – phresnel Apr 13 '12 at 09:36
  • **Mod note**: Comments are [only meant for asking clarifications on the post](http://programmers.stackexchange.com/privileges/comment), nothing else, and certainly not for extended discussions. If anyone wishes to further discuss this question, please take it to chat. – yannis Apr 13 '12 at 09:49
  • Is this correct? You have A=B, B=C & **A=C** in your question, that would make A=C & B=C. That is not circular, as C never points to anything. – jmq Apr 13 '12 at 14:27
  • 1
    It's important to know when to use a recursive function than to just know how to write one. A lot of programmers write recursive functions that never end because of this. – JeffO Apr 13 '12 at 15:48
  • [The only winning move is not to play](http://www.imdb.com/title/tt0086567/quotes). I would walk out of the interview and leave the manager with this thought: I would rather work for someone who has coherent thoughts. –  May 01 '15 at 02:17

13 Answers13

307

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".

gnat
  • 21,442
  • 29
  • 112
  • 288
Matt
  • 2,232
  • 1
  • 13
  • 13
  • Brilliant! Sorry @RobertHarvey, but I need to reassign the points here (plus you have a ton already). Way to articulate what I was thinking but couldn't articulate myself. Thanks Matt! – Matt Cashatt Apr 12 '12 at 21:50
  • 10
    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
  • 110
    "Clown traversal" - what a great Meme for "stupid technical question". Pass it on! – radarbob Apr 12 '12 at 22:50
  • 1
    I think it's just a manager who doesn't really code pulling a JavaScript question out of a hat and treating it like any dev would have the faintest idea of what they're on about. – Erik Reppen Apr 13 '12 at 04:49
  • As a non-native English speaker, I wonder why 'clown' can represent a 'binary tree'. – Sanghyun Lee Apr 13 '12 at 06:17
  • 3
    @Sangdol you misread. An "object" can represent both, but 'clown' can **not** represent a 'binary tree' - and that's the whole point (re-read the answer if you're interested in more details). – gnat Apr 13 '12 at 07:19
  • 4
    @rupjones: it's not "clown", it's "marklar" – kevin cline Apr 13 '12 at 07:29
  • 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 07:29
  • @kevin-cline ahh googled it, nice, but clown sounds more ridiculous :) – rupjones Apr 13 '12 at 08:29
  • 5
    So when a bunch of people think that a stupid technical idea is actually something good, and a bunch of others understand that it's stupid, would that make it a clowntroversial idea? ;) – Mason Wheeler Apr 13 '12 at 15:26
  • 38
    My entire area of theoretical CS research involves iterative clown traversal, you insensitive clod! –  Apr 13 '12 at 15:54
  • 5
    I was just going to mention that I thought I recently read a research paper on effective clown traversal using intelligent swarms. – Michael Brown Apr 13 '12 at 16:24
  • 1
    "Would you please explain to me the algorithm you would use to traverse a clown?" – Joe Phillips Apr 14 '12 at 21:35
  • 6
    @JackManey: Everyone knows that clowns must be traversed *recursively*. – Adam Robinson Apr 15 '12 at 03:09
  • 4
    When traversing clowns you really must take "Pi" into account, especially as it tends towards "face" :) – Binary Worrier Apr 20 '12 at 17:37
  • 2
    LOL Anyone heard of the Traveling Clown problem? I heard it is NP-Hard. – Hyangelo Aug 15 '12 at 14:22
  • Recent research suggests it's actually N-Pie-Hard. – scrwtp Jun 17 '13 at 21:06
40

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."
Jerry Coffin
  • 44,385
  • 5
  • 89
  • 162
  • 7
    "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 06:52
  • 9
    Do you usually use female pronouns when the gender of the person is not mentioned? – Chan-Ho Suh Apr 13 '12 at 10:01
  • +1 Seeing how you'd react. – Ernest Friedman-Hill Apr 13 '12 at 11:10
  • 8
    @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
  • 12
    @Chan-HoSuh: The OP mentions the gender in one of his comments. – Jerry Coffin Apr 13 '12 at 13:31
  • While companies don't typically share their views on candidates, candidates typically share their views on companies, which can lead to the practice of #3 backfiring when good people who network turn down interviews. Of course, if #1 is true, the Dunning-Kruger effect might lead to #3. – Blrfl Apr 13 '12 at 16:36
  • 4
    @JerryCoffin My apologies then. – Chan-Ho Suh Apr 13 '12 at 16:43
  • @JerryCoffin: *"there's virtually no chance"* - Sure, and also physical! (I mean, even if there is a chance, may be not convenient to anyone, but still a symptom of unfairness) – Emilio Garavaglia Apr 13 '12 at 19:26
  • 1
    A variation on #3--they're trying to hire H1-Bs and thus need to show any Americans that apply are unqualified. – Loren Pechtel May 24 '13 at 20:01
32

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.

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
  • @Robert-- Gah!!! I said that even. This is so frustrating. Would it be poor form to e-mail the company and politely say that I take issue with this question? – Matt Cashatt Apr 12 '12 at 21:15
  • @Robert--Thanks, by the way, for your response. You just made my day by making me feel a lot less dumb! – Matt Cashatt Apr 12 '12 at 21:18
  • 28
    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
  • Aye carumba! LOL! – Matt Cashatt Apr 12 '12 at 21:23
  • 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
  • 3
    @James He didn't tell me pseudocode was a valid choice until *after* the interview. :) – Robert Harvey Apr 12 '12 at 21:48
  • 8
    What's the difference between pseudocode and Python? :) – David Robinson Apr 13 '12 at 05:30
  • 5
    @DavidRobinson: one is not executable, the other is a circus; guess which is which. – Lie Ryan Apr 13 '12 at 11:47
  • 3
    @LieRyan: One's a *flying* circus! – Dennis Williamson Apr 13 '12 at 19:54
  • 1
    @MatthewPatrickCashatt, it's not worth it. Dumb questions and dumb reasons for rejection are, unfortunately, commonplace when interviewing. The best policy is to have enough interviews lined up that you don't get too attached to the outcome of any particular one. – Kyralessa Apr 16 '12 at 19:39
  • @DavidRobinson, Python has silly indentation :-) – ChuckCottrill May 02 '14 at 15:14
14

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.

Peter Mortensen
  • 1,050
  • 2
  • 12
  • 14
WSkid
  • 240
  • 1
  • 5
  • 5
    That makes sense that way you put it, WSKid. Unfortunately, none of that context was offered. – Matt Cashatt Apr 12 '12 at 21:28
  • 3
    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 – Ken Apr 13 '12 at 01:34
  • 2
    +1 for finding a context where the question makes some sense! – Donal Fellows Jun 17 '13 at 18:06
9

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.

hotpaw2
  • 7,938
  • 4
  • 21
  • 47
  • 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. – Matt Cashatt Apr 13 '12 at 07: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
7

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).

Maich
  • 99
  • 2
5

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.

JB King
  • 16,795
  • 1
  • 40
  • 76
  • 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. – Matt Cashatt Apr 12 '12 at 21:47
3

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.

BenjaminB
  • 1,706
  • 1
  • 12
  • 15
3

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.

Jim
  • 161
  • 4
2

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.

Lucas
  • 121
  • 3
2

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.

pgthew
  • 31
  • 1
1

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.

Reactgular
  • 13,040
  • 4
  • 48
  • 81
0

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.

rpatali
  • 21