Graph Data Structure Interview Questions | Hacker News Reader

Graph Data Structure Interview Questions

techiedelight.com

169 pointscoder00732 comments

While this is really interesting and I'll probably read through all of them just to brush up on my graph knowledge... but "Interview Questions"?

Does anyone really ask you to write this kind of code in interviews? They feel more like Computer Science homework questions.

Yeah honestly anything after number 6 (bfs and dfs to be more specific) you would not be asked or really even have time for in an interview.

Unless of course you are interviewing for a graph heavy job.

Very interesting stuff though. Love graph algorithms have coded many myself in JavaScript to prep for interviews.

edit source:

my algorithms code base test suite

https://travis-ci.org/williscool/code_gym/jobs/129218676

To be fair, almost all the problems after 6 are just variations on BFS and DFS, just different ways to ask the question.

For example, (11. Check if an undirected graph contains cycle or not) can easily be solved by just performing a DFS with some exit conditions.

> Love graph algorithms have coded many myself in JavaScript to prep for interviews.

...but have you coded any in JavaScript after the interview as part of the job? I suspect for most people the answer is no. It has always seemed strange to me to ask a topic that you're never going to encounter during your day to day work (yes, I know for some roles this isn't true).

I think there's a general consensus that mastering the specific material you would encounter in an undergraduate CS program proves you have the more general cognitive skills necessary to succeed in any entry-level programming job.

We just don't trust the university to say that you've done the projects and sat the exams and demonstrated competence (what it's doing when it issues a degree), so each company unwraps that abstraction and runs its own projects and exams on the same material. But it is fundamentally based on college curricula.

Trusting universities is likely out of the question. Eventually, I expect the industry will create something like the Bar Exam so each candidate can pass a trusted test once upon graduation (or even without going to college), rather than creating the burden for each company to do all that grading.

Lawyers and doctors don't do LSAT and GMAT questions on the job. It's not a problem specific to tech. An interview is a performance test. It's popular to say an interview should be like a day at work, but when we performance test our code, we don't throw an average load at it and say it's ready.

>Does anyone really ask you to write this kind of code in interviews

Whoh!! All big IT companies ask these type of questions.. but mostly to graduate students and less experienced candidates.. but some companies might ask it to a 10 year old programmer as well..

> All big IT companies ask these type of questions.

Careful with absolutes. Although I used the word "any" in my post so I guess I shouldn't talk.

Having worked at some large tech companies I can say definitely it is not "all"

Some of these examples are 90+ lines of code which is why I ask. It would not be unrealistic with that much code that candidate will be sitting in the interview room for a half hour+ coding just one question.

Several of these are borderline trick questions or only test your ability to memorize. For example, I learned Dijkstra’s algorithm in school 10+ years ago but if you were to ask me to implement it without reading the algorithm I wouldn't be able to.

Asking graph data structure questions, sure. But here are more effective ways to know if a candidate will be a good fit than asking them to implement one of these.

Use these as your interview test questions and all you are testing is the ability for the candidate to regurgitate algorithms. None of these test creative problem solving.

The thing about Dijkstra's algorithm is that it't just the obvious one that you would think of if you had never been introduced to the problem before. I'm pretty sure I "invented" it myself at least twice, and then forgot it.

Kudos to Dijkstra for nailing it down, but I think we do students a disservice by invoking his name all the time, thus making it seem scary.

>Kudos to Dijkstra for nailing it down, but I think we do students a disservice by invoking his name all the time, thus making it seem scary.

Ofc, going the other way, once they realize Djikstra's algo is simple makes every other named algo less scary

And finally they (hopefully) realize such naming is a stupid thing to be scared by and disregard it entirely

> but some companies might ask it to a 10 year old programmer as well..

I'm glad I wasn't interviewing at 10. I could program, but couldn't have handled any of these algorithms.

not saying these companies[0] wont ask these types of questions, but at least they wont ask you to answer them on a whiteboard

[0] https://github.com/poteto/hiring-without-whiteboards

related HN discussion thread[1]

[1] https://news.ycombinator.com/item?id=13874026

Like another commenter I think pretty much anything after DFS/BFS is asking a bit much during a normal interview. Floyd-Warshall? I guess it might be doable if you have a mathematical description handy, I've only implemented it once for a school assignment and don't remember how long it took but it's not something I'd ask or expect to be asked... I sometimes get asked to do interviews, I'm always torn by a desire to shake things up with the broken interview process but also somewhat conform to management expectations and feedback I can give like "was able to solve Arbitrary Parts of Arbitrary Programming Challenge X." In phone screens I spend ~10 mins on data structures, I'll ask some graph representation questions if they seem like they don't have an issue with others.

In longer settings (at least an hour) and especially if I know other interviewers are asking other things I'll ask them to solve a problem and actually write code on a computer. A problem I sort of like is https://leetcode.com/problems/jump-game/#/description While I think there's a pretty simple solution that just loops over every element, what I did when I tried solving it myself was recognize it's a search problem and apply the generic search algorithm to it. (Create a frontier list with an initial starting point. Create a seen/visited set. While the list isn't empty, pop an item off. If it's what you're looking for, you're done. Mark it seen, expand its children and for each one add it to the frontier list if it hasn't already been seen.) Knowing the generic (iterative) algorithm is to me more important than the particulars of DFS/BFS (you can control which one by choice of data structure), I just want to visit all reachable nodes in my search space and it works. Of the several people I've given this to only one has solved it, and by solve I mean had any right approach even if non-compiling/terrible code. (They ended up using a BFS approach.) They also are a promotion level above mine and have had more years of experience. So maybe I need to retire it, but I still like the idea of seeing if someone can recognize a search problem and solve it because there are usually many ways of solving search problems.

The last interview I went on was almost an entire work day full of computer science and programming questions, with a break for lunch.

That sounds pretty horrible, could you share what company this was?

I don't want to share the name, but it wasn't a typical tech giant, and the position was advertised as closer to entry-level as far as programming experience went.

Toward the end of the day, the last interviewer grilled me hard and I cracked under the pressure. It actually had been going well until the last two interviews (out of 5 or 6), in which one person asked me an unreasonably challenging problem (definitely not feasible for a whiteboard) and the other was not pleasant to interact with (almost confrontational the whole time; I felt on the defensive).

Prior to those, it was a healthy balance of reasonable challenge and solid conversation with engineers. It seemed like a cool place to work but their interviewing arrangement was brutal. I hope not to repeat that when I go looking again.

A full day of those kind of questions is pretty much the standard for the usual suspects (FB, Apple, Google, etc). Sometimes you might get a more generic design question thrown in.

I interviewed at Apple a few years ago and was not asked the whiteboard programming questions (that I got asked at Google/Netflix/every game company) for a programming position.

You would be surprised.

A candidate's performance on these questions is probably not indicative of his or her performance at your iPhone fart app company.

just in July of 2016, an unnamed hedge-fund was hiring architect/programmers. After a brief review of my resume (I have been in sr management and sr architecture roles for 17 of 25 years, but also code at home) -- was asked to take an online coding test.

The coding test was 2 hours through a interview/code website (forgot the name). They monitored your keystrokes and report to the interviewer when open tabs on web-browser outside of their window. (I can dig and recall what that website was if others are interested).

The coding problem was basically masqueraded Union Find graph problem. I knew that after about 2 minutes of 'browsing' (as I can translate a functional ask into an existing pattern that's already solved).

http://www.geeksforgeeks.org/union-find/

Still went ahead trying to implement this by hand.. and failed. So did not get a job.

Almost certainly TwoSigma.

On related topic (not necessarily graph):

DFS Interview Questions - http://www.techiedelight.com/dfs-interview-questions/

BFS Interview Questions - http://www.techiedelight.com/bfs-interview-questions/

Um, the graph doesn't match the given list of vertices and edges. At all. In the very first paragraph.

Added later: they fixed it. Quietly.

Unless I missed something, it matches if you don't treat it as a directed graph. Edge (1,6) accounts for both (1,6) and (6,1) in that case.

You didn't miss anything. This is why these are good interview questions, because it weeds out the people who are asleep.

Has the image changed or something? In its current state, I have a hard time seeing how anybody could misunderstand it...

Congrats! You passed the test ;)

Yeah, they fixed it... +1

The problem with these "interview questions" is that knowing a algorithms inside out is not how you solve problems it is how yiu solve A SPECIFIC problem. The problemsolving skill comes from the reductions one can make and thus apply different algorithms in order to solve a new problem.

Much more applicable than knowing how to implement these techniques, would be knowledge of "how to solve given realworld problems with these concepts". It is likely a developer would have access to optimized libraries implementing these, and would need to know when they apply.

The only questions an interviewer can ask is how to build a graph and do graph operation(to test data structure skill). Graph Theory is too specific and many programmers never use any graph algorithms in their life.

You can always ask these questions to reject a candidate because you don't like his body odor.

Reply on news.ycombinator.com