Hacker News Reader

Comment by exabrial | Hacker News Reader

I was asked in a Google interview to randomize a List. I wrote Collections.shuffle(list); The interviewer was not pleased.

View on HN

It's normal to not be pleased when a candidate fails to understand a question (or exhibits smart-ass behavior), though in this case the easy and correct thing for the interviewer to do is to say "OK, how is Collections.shuffle implemented?"

I think it's stupid to ask an interviewee to demonstrate something they should never do at their job.

I think it's stupid to assume that a decision regarding time complexity would never come up at their job. Where I work right now, and especially in Google (not where I work right now), it is important that one understands time and space complexity issues well. The data sizes are huge and optimization skills are highly valued.

Sure I can teach constant vs. linear time. But what incentive or reason do I have to spend time teaching these fundamental concepts when I can just hire an engineer who demonstrates the understanding of basic CS at the interview time itself?

Given two candidates with all things equal except that one demonstrates the understanding of CS fundamentals and other does not, why would I want to hire the second person and spend our time teaching him those concepts?

>why would I want to hire the second person and ...

Someone commented on here recently that they would take motivated candidates over knowledgeable candidates. That's one reason. I can easily think of at least two others.

There are balance points here that vary according to all sorts of things.

I said, "Given two candidates with all things equal except ..."

I mean if there are two candidates who are equally motivated and are more or less equal in all things except that one is strong at CS fundamentals and another isn't, is there a good reason to reject the candidate who is good at CS fundamentals.

In many hiring decisions, I am faced with a similar choice, and I go for the person who is good at CS fundamentals. If two candidates are good in all other ways, then the understanding of CS fundamentals becomes a tie breaker. I see no rationale for selecting the guy who does not demonstrate his strength in CS fundamentals.

I don't really agree ... doing thing A well usually means understanding B, C and D which underpin A. It's actually quite useful to ask people about B, C and D because if you only ask them to do A you don't know if they are doing A the right way because they really know what they are talking about or if they are just cargo culting something they pretend to understand but have no deep knowledge of.

With most people, it is impossible to gauge how good they are just by observing what they do in half a day on the job. Thus, any interview process must necessarily be somewhat artificial in trying to gain insight into a candidate's abilities in the span of a half a day.

A real life task might be implementing a much more complex library over several days or weeks. Asking the person to implement a simple function like shuffle is the closest you can get in the span of an hour.

> though in this case the easy and correct thing for the interviewer to do is to say "OK, how is Collections.shuffle implemented?"

And very likely that's what really happened. I have been in such interviews and it is sometimes hard to guess whether the interviewer wants the practical answer (calling a library function) from engineering standpoint or the conceptual answer (demonstrating that I can implement the inner workings of the function) from CS standpoint. Often I would just ask a follow up question to clarify exactly at which level of abstraction does the interviewer want my solution to be in?

In situations where I offer a solution that does not match the interviewer's expectation, they clarify the expectations.

And on the opposite side, my wife once had a job interview where they asked her to reverse a string. She wrote some code on the board to do it, and the interviewer just dismissed it with something along the lines of "No, that's not right. Try again."

She thought of a different method and wrote it out, and they dismissed it again. After that, she said that she didn't know what they wanted, and they condescendingly told her that she should just use the equivalent of a string.reverse() function (I don't remember which language it was).

Stories like yours and the grandparent comment give the impression that there is little communication actually happening in an interview. I guess if it was an at home assignment given in an email you might not know what the interviewer wanted, but in an actual in-person interview why wouldn't you just say "Well, you could do String.reverse(), is that what you're looking for[?], or would you like me to implement a solution without using String.reverse() or some other way?"

And on the other side, if the interviewers are looking to identify whether a candidate knows about String.reverse() and the candidate starts writing out some 20 line algorithm on the whiteboard, why would you just sit there and watch instead of being like "actually, we're looking for something else, let me ask it a different way; do you know how to reverse a list using the standard library? We're looking for a one-liner here, not an full algorithm implemented on the board."

If your story is true, then apparently there are at least some interviewers willing to just sit there while a candidate writes out 2 completely different algorithms on a whiteboard without interrupting and communicating what they actually want. Such an interviewer is either socially incompetent or trying to make a fool out of the candidate. Either way it doesn't reflect well on the company.

Yes, you would think. But for some reason, a lot of interviewers seem to treat interviews as an opportunity for them to prove that they're superior to the person that they're interviewing.

That or they have already made up their mind and are just looking for an excuse to reject the candidate.

Yup. If I get even the slightest inkling of this attitude from the interviewers, I will refuse to join the company. I'll give a pass for one smug interviewer, but if I encounter multiple such interviewers, I assume it's not a company I'd like to work at.

When I was interviewing for my current job I was asked to theoretically sort a list with with N elements where N >> M where M is the total number of bytes in RAM (but with infinite disk). I thought ok, easy, I basically explained every step of MergeSort except instead of doing operations in the memory, we need to some operations in the memory (i.e. merging) and then need to dump middle products to disk. You need to be a little more clever since you can't just merge in memory and save in disk (e.g. you can't perform the very last step of merging two N/2 N/2 arrays in memory since N/2>>RAM). Anyway, I was confident with my answer, and my interviewer sounded happy too. Then he asked me "but why don't you use swap?" Hmm I was very surprised. Since this wasn't a coding question (I was already asked dozens of questions involved programming) I thought this was a purely theoretical question. So, I never thought about the systems aspect. On a second glance, it indeed seemed like I just reinvented swapping.

I think CS interview questions can be hard because sometimes you don't know what sort of "model of computation" are you operating on. Am I on a totally abstract setting where all I have is an abstract machine. Or do I literally have an Intel CPU running Linux? Or am I even higher level than that and can think in terms of the abstraction of python. I think sometimes this is not clarified.

One other time in a different interview, I was asked "how does OS free memory in constant time". Having implemented malloc etc a few times I thought this was a stupid question because it depends on the C library implementation of malloc/free as one could also implement free in O(logn) using tree-like structures. Anyway, said something like "it just clears the pointer in the linked list in sbrk()'d space so that node is inaccessible" which apparently was the "correct" answer.

>"Or am I even higher level than that and can think in terms of the abstraction of python. I think sometimes this is not clarified." //

Which may be the point, they want you to ask "what am I optimising for", to be aware that there's no simple best answer without needing prompting. Also that the optimisation might be at the business level, like time critical implementation, or use of excess resources gleaned from some other part of the corporation.

So instead of telling you they want a one-liner, you saying "what are our constraints; how long have I got to implement it, ...".

Well, that is very informative, but probably not in the way the interviewer intended. Certainly doesn't sound like a great place to work?

It's clear to me that in a tech interview, unless otherwise told, it is your algorithm skill that is being tested. If I were you, I would begin talking about Fisher Yates, outline its implementation, explain why it correctly shuffles the list, show why it's an O(n) solution, etc. I might even talk about alternatives.

It's always better to demonstrate in an interview that you have a lot of knowledge about whatever that is being asked. It's not just being able to code, but also the ability to explain why and how it works.

Sometimes tech interviews will ask questions that are more along the lines of API memorization. They can be valid questions too, I've worked with "senior" developers that would implement their own sort algorithms (in .net) rather than use the built in ones. "Does this enormous framework I'm using have a way to do x" is a question some developers never ask.

It all comes down to the question asked, if they were literally asked to randomize a list then OP gave the correct answer, if they were asked to implement a list randomizer they were wrong. If the interviewee didn't make this explicit they were wrong.

This is completely subjective and depends on who is interviewing you. I could give a crap about someone's deep algorithim knowledge. I want to see them write productionizeable code.

Granted, there should be 1-3 people around who can be tapped for algo knowledge when bottlenecks need to be addressed. However the rest of the dev team just needs to worry about productionizeable code...

Often the people who know the algorithms struggle to write maintainable code that isn’t esoteric garbage to everyone but them and will fight to the death to say their way is correct. So your mileages may vary...

> I could give a crap about someone's deep algorithim knowledge.

That's just proving the point of the person that you replied to, though. If you could give a crap then you obviously care about it.

That's a reasonable answer.

Of course, the follow-up question is going to be: Randomize a list that doesn't fit into memory.

I would have failed you as well. The point is to test whether you have a clear picture of what goes on one layer of abstraction below or if you are confined to the surface.

I don't get the fuss about interviews. They seem to largely consist of basic programming exercises.

You don't need to know the solution before hand and it is easily intuited on-the-fly. I would never hold it against someone to miss some corner-cases or maybe go for a naive implementation first.

I remember a few years ago, someone was complaining that they had been rejected for not being able to reverse a binary tree even though they had a copious amount of OSS.

The thought process is simple and it's an exercise that students do within the first few weeks of their freshman year.

    (struct node (value left right))

    (define (reverse-tree root)
      (cond
        [(equal? root 'EMPTY) root]
        [else
             (node (node-value root)
               (reverse-tree (node-right root))
               (reverse-tree (node-left root)))]))

A tree is intuitively defined as a recursive data-structure.

There is one base case: when we reach a leaf.

We want to reverse the left and right subtree at every stage of recursion.

Combine all of this and it's done. I would even be content with a pseudo-code implementation.

I'm much more concerned if the candidate is a person that shows up on time, with a good attitude, takes heat and shares credit, builds people up and isn't afraid to speak their mind. If they have a rudimentary understanding of the time constraints of linear vs constant time that's a bonus, otherwise I could teach them that.

I come across candidate A who shows up on time, with a good attitude, takes heat and shares credit, builds people up, isn't afraid to speak their mind and offers a smart-ass answer to a problem designed to evaluate whether the candidate understands the underlying concepts.

Then I come across candidate B who shosw up on time, with a good attitude, takes heat and shares credit, builds people up, isn't afraid to speak their mind and offers a genuine and insightful answer to a problem designed to evaluate whether the candidate understands the underlying concepts.

I am definitely going to hire candidate B.

And where did they give a "smart-ass answer"? A question was asked, an answer was provided. Does the answer solve the problem? Yes. If you want to know more then ask. If you want to hear something else that's a failure of the interviewer, not the interviewee.

I would have given a +1 for creativity. If the interviewer didn't say that standard libraries were off bounds that's fair game IMO.

I've asked similar questions and if I forget all the constraints just a simple, hah that's clever + reframe the problem is a reasonable approach and doesn't come off as being a jerk(keep in mind the candidate is interviewing you/company as well).

"Implement a method that shuffles a list" vs. "Shuffle a list"

I would want the candidate to ask me whether they can use their language's standard library. I would say no/yes depending on how the question is framed.

The absolute worst is when question is framed like 1) - the candidate just makes an unwanted assumption, and then acts outraged or smug when I tell them I expect them to demonstrate that they aren't oblivious to the underlying implementation.

Then we venture off whether they can make improvements/trade-offs if the list becomes 10K, 1MM, 1B, etc. records of N bytes etc.

But all this amounts to trivia questions about things you would never actually do or have to know when working as a software engineer.

The point of a library function is that I don't have to worry about how it works, so I can focus on writing things that are not already in libraries!

> The point of a library function is that I don't have to worry about how it works, so I can focus on writing things that are not already in libraries!

The point of a library function is so it doesn't have to be re-implemented everywhere, not so you can be oblivious to how it works. If your oblivious to what is going on behind every function call you will write terrible code.

I was asked in a Spotify interview to reverse a string as a warm up. When I wrote std::string(s.rbegin(), s.rend()) the interviewers seemed pleasantly surprised.

To be fair, using a library to do what you want is not what they're asking for. This is completely different from the functional vs OO discussion above.

On the contrary, if someone that worked for me needed to randomize a List and implemented their own function, I would be gravely concerned about the rest of work and what they're spending their time on.

And when Google implemented Java for Android, how, pray tell, should they have implemented Collections.shuffle?

Implementing a stdlib isn't a thing you do every day. Presumably GP was referring to more common situations, where using the stdlib is (usually) preferable to rolling your own solution.

They were interviewing for Google. It's not uncommon to have to implement a standard library function (or not be able to use one) in many contexts at Google. Besides, the question is just the most basic setup to assess how a candidate would fare in comparable situations.

Is it though? Because the answer to "suddenly I need to implement a standard library" is "I google the accepted solutions" and if I don't have Google then I goto the library and check out a bunch of old CS books.

And then the interviewer's follow-up question should be "fine, since you don't want to indulge me and implement a solution to this toy problem, I'll ask you to implement a much more complicated function which doesn't exist in any library!"

They were interviewing for Google.

99% of developers at Google are doing commodity work. It is are practically IBM or HP now.

They grabbed it out of harmony.

But you would not be concerned about a candidate that does not understand that this question is clearly (very clearly) meant to assess how they understand and approach algorithms and randomness?

It's obvious that you should use a library function if there is a library function.

A question like "how do you reverse a string" surely is like asking a chef to cook an egg? Any idiot can do it, it's got to be an opening on to "who are my customers?", "what are the cost and time constraints?", "what team members do I have?" "what's our angle" ...? If the answer is just "boil it for 5 minutes" then you know you're looking at someone with simplistic thinking; which is fine if you just need someone to mindlessly do as they're told. They might be an absolute expert at it.

Yeah, it's just an opener. Setting the stage, making sure everyone is on the same page, and then you can build onto that à la "and now suppose xyz...".

Reply on news.ycombinator.com