Hacker News new | past | comments | ask | show | jobs | submit login
Data Structure and Algorithms Interview Questions for Programmers (hackernoon.com)
198 points by javinpaul on Nov 14, 2018 | hide | past | favorite | 102 comments



I officially refuse to do these in interviews (along with whiteboard coding) anymore and I'm very upfront about it with hiring managers and recruiters. My reasoning is twofold: (a) I'm generally not great at these kinds of questions so I think it's an unfair disadvantage and (b) I think that my experience, open source contributions, Apress book that my name is on, blog that I often post to, etc. speaks for itself. However, I will gladly do your take-home assignment. I'd be even more thrilled if we can discuss it during my interview.

It's kind of how in dating people have deal-breakers (e.g. no smokers, no kids, and so on) -- when looking for a job, this is one of mine.

Obviously, the caveat here is huge companies like GOOG, FB, AMZN -- these are big companies that need filters and I completely understand the reasoning behind their process. If I wanted to work there, I would certainly study data structures and algorithms before my interviews.


There was a time when I was hiring vendors for my team (at a big company) rather than FTEs and I had a bit of leeway to diverge from the company's interviewing guidance. What I would do was sit them in front of a computer with Visual Studio and internet access for an hour and ask them to do something like write a program that restarts a service given its name, and they could use whatever (e.g. google, Wikipedia, and/or stack overflow) short of copying and pasting the code to do it. I figured if they couldn't do that, then they couldn't do it in real life either, and if they could it was good enough.


I think this is fair. I prefer take-home assignments, but your idea is a refreshing take on the on-site interview.


I think I prefer the on-site version, because that way I know they aren't BSing me when they tell me "this should only take 2 hours".


Well, if I was a manager and there are about 200 developers like you with a GitHub and experience and open source contributions applying for about 3 positions, I am going to make a decision to filter candidates out.

Most managers would reach for the algorithms/hackerrank/leetcode because it's the least risk to them.


> Most managers would reach for the algorithms/hackerrank/leetcode because it's the least risk to them.

You mean it's least effort. Least risk would probably be hiring a private investigator to dig up everything about the candidate for the past 10 years.


It’s least risk in the same sense as “Nobody ever got fired for buying IBM [/Microsoft/Oracle].”

In other words, there is actually substantial long-term risk involved in simply electing for the default solution, but it feels safe on the short term and won’t make you look bad to your boss.


That carries the significant risk of getting chewed out for being completely ridiculous.


Is it? It solves the problem of somebody lying on their resume. It's probably not that much more expensive than chewing through a dozen candidates over the course of a year without finding a single suitable match.


I think that's because HR tends toward avoiding false positives rather than false negatives, as the latter tends to be more expensive. Therefore, they would rather miss an ideal candidate in order to avoid the risk of hiring a sub-standard one.

In a perfect world, HR would understand the position well enough to properly vet it but in practice they tend to revert to easier measures like the ones described.


No, they do it because most don’t know how to interview. So, they just do what everyone else is doing.


I thought software engineers with even a hint of talent were in short supply? Have I read the market totally incorrectly?


The problem is that those are not the only ones that apply.


The problem is that there is no reliable metric with which to measure talent. There is no interview process at the moment that currently does this accurately.


I'd say the problem is lacking accreditation. It's bonkers a person given a CS degree is not understood to know CS well enough to render whiteboarding unnecessary.

For a medical doctor it suffices to gets one doctorate. I don't think hospitals will drill him on the core fundamentals of his craft similar to whiteboarding in cs. A patient arrives with a slight fever and a headache. Quick! Which lab tests would you assign him!


It's ironic that for a doctor that actually would make sense since it's something practical that is needed on the job. E.g. "Patient has those symptoms, what could it be?"


How do other fields actually deal with that? Electrical Engineering should be close to our software field... Are they asked to draw common circuits or so?


> Well, if I was a manager and there are about 200 developers like you with a GitHub and experience and open source contributions applying for about 3 positions

When is the last time a hiring manager had 200 good resumes for 3 positions?????

For most companies it is the opposite experience - many open positions, few good resumes, which makes me wonder why they work so hard on keeping people out


Big "celebrity" companies like Google do get flooded by huge numbers of resumes, which is one reason they have the hiring process they have.


I have a mixed view on this. I don't have a traditional CS background, so when I started focusing on datastructures and algorithms a couple years ago, I found that it helped my programming. Recently, I was in a position where I had a chance to create an interview process for a smaller firm. I included some algorithm questions, but it was roughly 25% of what mattered. We looked more at communication skills and past work. Judging someone on a random algorithm question seems a bit too harsh for me. Even the best developers probably have some holes in their algorithm knowledge and would miss a few leetcode "easy" questions!


And the hiring managers buy that reasoning?

It's a decent reasoning and would only be able to get away with it if you have some decent years of experience OR some very good open source contributions. Or Both.


Some do, some don't. Some women don't want to date me, either, but I don't stay up worrying about it :P


I refuse to give these kinds of interviews. They don't really tell me much other than they know algorithms and data structures. And with thousands of articles and even whole books dedicated to passing those sorts of interviews, that's not saying much at all. What I really want to know is:

- can the candidate get the work we need to do done?

- what do they prioritise when doing the work? What do they value?

- can they do it well? In reasonable time?

- how well do they fit in with my team? Are they somebody my people want to work with? (Probably one of the most important things)

- how much will they grow? Are they open to feedback? Are they focused on getting better?

A whiteboarding session doesn't really tell me much here. But if all the answers to the above are positive, I'm sure the candidate has the flexibility to find and learn what they need to solve a problem.


But this is all negative. What do you do in an interview to predict how effective they'll really be?

I don't think anyone is especially fond of judging candidates by using riddles, trivia questions, and unrealistic tasks, but the constraints of the interview process rule out a lengthy and thorough assessment.


There are hundreds of companies that don't use algorithmic interviews, they are neither necessary nor particularly useful.

http://they.whiteboarded.me/companies-that-dont-whiteboard.h...


What's the positive answer to "What do they value?" for you?


Join the resistance, refuse these pointless interviews!!

http://they.whiteboarded.me/companies-that-dont-whiteboard.h...


I don't mind those questions in an interview as long as the recruiter is not just reading them from a paper sheet, and actually know this stuff. This can be a way to find a candidate with a strong theorical CS background. Which can be relevant for some positions.

Now, I've seen my fair share of recruiters that did not really understand the topic at hand when asking theorical CS questions, let alone the desired answer. I do so always get really suspicious when they occur.


> It's kind of how in dating people have deal-breakers (e.g. no smokers, no kids, and so on) -- when looking for a job, this is one of mine.

Not everybody can afford to be as picky as you regarding job choice (this is not meant derogatorily).


Are you able to get good jobs that way? Not criticizing, just genuinely curious.


Yep! I think the biggest boon in job searches (for me) has been Stack Overflow.


Thanks for sharing your experience


I feel frustrated by the concept of software interview questions but only recently do I think I've figured out why. They feed my impostor syndrome.

They're often trivia that I'll never learn from my job, so if I didn't go to school for programming I won't know. Or they're specific to a domain I'll never touch so I won't know.

I don't think they're fundamentally bad (I used to), but I've never read one of these without coming out the other side feeling lower about myself.

Not sure I have a point. Just wanted to share.


You have a perfectly valid point. After a PhD and 10 years of industry experience I interviewed at Google, mostly out of curiosity and because a former colleague recommended me.

I had never done an "algorithms" type interview before, had done no specific preparation, and was a bit baffled by being asked to do a coding exercise in a text editor whilst talking on the phone.

Since I was an "internal recommend" they gave me a second chance. Presumably because they were surprised at how badly I did. But the second interview was worse than the first.

I came away feeling quite humiliated.


Just out of curiosity: Are these kind of questions relevant/representative for the type of work that one does at Google?


Well, my reasoning at the time (2007) was that since my areas of expertise were machine learning and parallel processing, then if they wanted to hire people who knew low-level sorting and searching algorithms by heart, it wasn't the place for me.

I was surprised how one dimensional their process was. And I believe it may have changed since then. My former colleague did apologise when I related my experience and admitted that Google knew they had a problem with the process.


I know what you mean. Even if you think you are fairly competent, have a CS degree that is a few years back, reading these articles you only realise how many seemingly simple questions you probably could not answer correctly in an interview scenario. I try to let it motivate me, to try to stay on stop and play with these questions a bit, like going to the gym to stay fit and healthy, but imposter syndrome is real.


Why do interviews for dev jobs increasingly becomes a game beaten by "grinding" leetcode or other websites listing questions?

It's like many companies have given up trying to rank applicants based on actual job experience and skills. "You've created and ran successful software for hundreds of thousands of paying customers? That's cool, but if you can't write a merge sort implementation on this whiteboard we'd rather hire the guy that learnt it by heart."


It's because lying on a Resume is extremely easy. I do interviews for a large software company about once a week. The relationship between what a candidate says they did and actually doing simple programming problems is non-existent.

> It's like many companies have given up trying to rank applicants based on actual job experience and skills.

Yes.

> "You've created and ran successful software for hundreds of thousands of paying customers?"

They probably are taking credit for someone else's or their teams work. It's depressing to say aloud, but it's the norm rather than the exception.


I recently went through an interview process at a few companies. One in NYC, London and Bermuda. The one in NYC required me to do a leetcode style algorithm question. I somehow worked myself into a nervous wreck and bombed out even though I had prepared a lot and could have answered the question in my own time.

I ended up landing the London gig and having a fantastic interview experience with the Bermudian company. They all had VASTLY different interview processes but it really made me realise how stupid that whole algorithm/whiteboard process is.

I think this perception that the big 3 use it as a filter is even a bit lame and lazy. I've heard they do it because it's more costly to hire a dummy than to miss a star, but I would love to see the data around that.

Unless of course they aren't interested in hiring "stars" and just want leetcode monkeys to file in and churn out code with perfect asymptotic behaviour.


It's because lying on a Resume is extremely easy. I do interviews for a large software company about once a week. The relationship between what a candidate says they did and actually doing simple programming problems is non-existent.

My C++ interview is pretty easy. No whiteboarding, just a conversation. I want to know for example if this candidate uses templates judiciously or if they are a maniac. Either is fine btw, I’d just like to know.

But more times than you’d perhaps think, the candidate has admitted that they don’t know C++ at all, and then the really awkward questions come, such as why did they write it down, then apply for this job, then show up for the interview...


If you ask in-depth questions about their past projects, the challenges they faced, the decisions they had to take, I think it's very possible to find out whether they were major parts of it, or if just small code-pushers who just implemented things like they were told.


This would likely result in interviewer bias based on how familiar they are with the project the candidate was working on. How do I fairly compare 10 candidates based on their answer to that question? The interview questions need to be objective and have a clear right answer. If you interview regularly (and work directly with the people you hire), I think the problem with your approach will become obvious.


> The interview questions need to be objective and have a clear right answer

Then it's a test, not an interview. I don't think interviews were ever supposed to be perfectly objective. If the interview is only based on CS textbook questions, they might as well replace the interviewer with an online test, which by the way increasingly happens for screening, but my point is that it filters out great engineers who worked and delivered solid products because the interviewers are just not interested in details of past work experience


> but my point is that it filters out great engineers who worked and delivered solid products because the interviewers are just not interested in details of past work experience

Again, yes. It is hard to fire a bad candidate in case the interview was misleading. Companies would prefer false negatives over false positives. What you see in interviews is a product of laws about hiring and firing.


> Companies would prefer false negatives over false positives.

If this is the case (i.e. companies can afford this behavior), all the claims about skill shortage are a lie and should be called out.


   in-depth questions 
That is true, but time-consuming, and not objective. How, for example, would you evaluate whether they tell you the truth about their past project? If you have to interview a large number of people and need to make decisions effectively, that's a disadvantage.


> How, for example, would you evaluate whether they tell you the truth about their past project?

How is that any better than hiring a terrible dev that just spent 3 months memorizing Leetcode solutions? Aren't they essentially being dishonest about their skills?

>time-consuming Phone screens are already several hours over several days and on-sites are typically 8 hour affairs. Is this not already time consuming?

Genuinely confused by the Stockholm Syndrome-like mindset that devs have for Whiteboard interviews.


   memorizing Leetcode solutions
Are the hard Leetcode questions rote memorable?

I have my doubts. Indeed from my own experience with Leetcode is I can only do well on the questions that I think quite hard about. Recently I tried to do a Leetcode question marked Medium, but my 3 line solution (while correct, and working on my own test cases) always resulted in "Time Limit Exceeded". I studied their test cases, and realised that my brute-force solution was of exponential time complexity. I then read of the discussion of the problem, was so delighted with, and surprised by one of the proposed solutions (linear time) that I felt compelled to write down the loop invariant in Hoare logic! Fun evening, and I'll never forget this neat algorithmic trick. I think that practising enough Leetcode so as to do well on the Medium/Hard questions requires developing an understanding of algorithms which is highly useful in practise, in particular, if you work with large data sets, clever algorithms are unavoidable for getting anything done. Have a look at the list of past ACM coding contest winners, e.g. the 1993 winners [1] include Craig Silverstein (first hire at Google) and Tony Hsieh (Zappos, LinkEchange).

Summary: I don't believe that doing 3 months coding challenges is meaningfully described as memorisation.

On top of that, doing coding challenges is perfectly compatible with asking other questions.

[1] https://icpc.baylor.edu/community/history-icpc-1993


I think you misunderstood. It's certainly possible to learn a lot by doing Leetcode. I'm saying that since solutions are available to their problems that you could simply memorize as many of them as you can and would probably pass most whiteboard interviews with memorized optimal solutions


Ask them non-trivial questions about the problems they solved and how they solved them.


They are likely to know more about the project they were part of then you do. Even if they are really bad.


That's okay. The important thing is their knowledge of common problem patterns and solution patterns.

Ask them how they identified a complex problem, what process they used to get to its root, what they thought was causing it but actually wasn't, which solutions they discarded and why, etc.

You don't need to have a better understanding of their project than they have. You just need to determine whether they have the ability to solve complex technicals problems in competent ways, and at what level.

For example a more junior person might talk more about solving the problem for today and less about solving the problem for tomorrow. Let them talk it out and see where their attention goes.

A more senior person might talk about similar problems they've seen on other projects and how they leaned on past experience to discard non-optimal solutions faster.

You don't need an algorithms test to determine if someone is likely to be able to "get stuff done" in their role. Talking through past problems and solutions might be a better predictor.


You don't need to know anything about a project to spot that the candidate is being very vague when quizzed about the details of something that they claimed but didn't actually work on.

And it is surprisingly common.


Walmart labs never asked me DSA questions, they grilled me on the projects that I worked on. That was definitely the best interview I had ever attended. Other companies should follow the same model.


I never though I'd ever say it, but Walmart looks like it has a couple of interesting software practices


I feel like the interviewing grind has become akin to gymming - you go to your mental gym, build up your 'muscles' by doing pointless repetitive tasks AKA algorithms you'd never use in real life (probably like how bodybuilders would never need to deadlift 125kgs in their daily life). It doesn't directly help you do your job but you know bodybuilders have higher than average fitness levels. So in the same manner, devs grinding leetcode probably have higher 'fitness' levels than devs who don't.


I'm uncomfortable with the fact that you can study for a non-entry level interview . In fact, you're very likely to do better on an interview if you haven't been working recently, but have been grinding leetcode questions. It's unlikely this situation reflects the employer's actual preferences.


I can spend my time learning a new skill or technology, or I can do quizzes on algorithms I will never use. Since I'd like to work for myself in 5-6 years, I resent the time I waste on quizzes.

Another analogy is jiu-jitsu: grapplers can train strength and endurance by going to the gym, but many do not. Just working on useful technique also doubles as a workout that improves endurance - for a large number of athletes, this is preferred to a gym that targets muscles in unrealistic ways and has no skill-gaining benefits.


Professional competitors in the majority of physically demanding sports supplement their training with gym work. Tennis, cycling, golf, etc all do. Targetting muscles in gyms have all sorts of benefits. If you are an amateur who competes for fun then you probably don't but if your paycheck is determined by performance than it's likely you're in the gym.


I’ve never heard of a pro athlete being evaluated by their ability to bench press. Very good analogy that demonstrates how silly those interviews are.


The NFL combine has bench press as one of their evaluations.


I grinded a significant portion of my time on leetcode. I would rather have worked on programming projects during this time.


Data structures and Algorithms are fun, but more and more I see that general software engineering is something we need. Several useful questions venture too deeply into domain specific things, making them difficult to give to candidates. For example:

* Make a simple memory allocator.

* Make a simple HTTP Proxy

* Make a simple URL parser

* Make a simple CSV parser

* Make a threadsafe Queue

* Design a class to handle exponential backoff

None of these are particularly useful, but I think they can let a candidate show off how they can handle a simple problem, and how they modify their code as the problem grows in complexity. Sadly, most of these questions candidates have no familiarity with. I would much rather see it than more O() analysis.


My recent favorite question is how to design a proper login page, store the password and authenticate them.

You'd be surprised how many things can go wrong.


There are various answers which seem a bit sloppy to me. For example, "How do you find the middle element of a singly linked list in one pass?" The answer, without comment, makes a presumption about how to define the "middle" of a list with even length. And it defines a linked list implementation with a magic, invisible head that requires extra code beyond the loop to compensate for. In the "How do you check if two rectangles overlap with each other?" answer, the code will determine that the rectangles which merely coincide at edges or corners are overlapping, without noting that distinction. The vending machine example tries to drive home the point of requirements definition, but the point applies equally to these much simpler examples. I only gleaned maybe 10 examples...maybe I just got "lucky".

Also, the overlapping rectangles example has an error in the explanation. It says "If any of above four conditions is not true then two rectangles are overlapping with each other, as in following diagram first condition is violated, hence rectangle A intersects rectangle B." This somewhat nonsensical statement refers to a diagram that's not there, but furthermore, incorrectly indicates that the rectangles overlap if "any of [the] conditions is not true", when in fact all of them must be false. The code is correct on this point, but the explanation is wrong.


> For example, "How do you find the middle element of a singly linked list in one pass?" The answer, without comment, makes a presumption about how to define the "middle" of a list with even length. And it defines a linked list implementation with a magic, invisible head that requires extra code beyond the loop to compensate for.

I'm not sure what you mean by complaining about a magic, invisible head to the linked list. If you can't access the head of a linked list, you can't access any other part of it either.

However, as another comment points out elsewhere in the thread, there is a bigger problem -- the solution offered uses more than one pass.


I mean that the LinkedList class is defined so that "new LinkedList()" returns not a list of length zero, but a list of length 1 with the first element containing the string "head". The actual list it creates is {"head", "1", "2", "3", "4"}, despite the fact that the output claims the list has 4 elements.


I've been trying to weed out a lot of these problems from my team's interviewing set- they filter for CS students, not practical development knowledge. I can honestly say I've never used a linked list in 15 years of being paid to develop software. I've been pushing interviewers to come up with a problem based on code they've actually written in the past and use that for their interview question.

I'm starting to think I might have better luck having a pre-built some code with some poor practices and asking a candidate to refactor and improve it- evaluating their ability to at least know what clean code is supposed to look like.

That being said, I'm not willing to give up my whiteboard code interviews yet- they are too useful a filter. I still get candidates that sound fine talking about their previous experience and then say things like "oh man, its been a while since I've used arrays" when asked to code.


I was really impressed with one of the interview rounds I was given at Microsoft - I was shown a mock code review and asked to comment on bugs (ranging from easy to spot like null reference exceptions, to harder like race conditions and edge cases) and code quality.

It felt like good fair test of someone's day to day ability, isn't really something you can grind for, and presumably also gives quite a good quantitative measure of a candidate if you assign a weight to each bug/quality suggestion.


I will add on- no, I didn't find out how its possible to professionally program for 5 years and not use arrays. But the poor guys response showed he hadn't.


Probably depends on what you mean by "arrays". If you use high-level languages like Java, you probably don't use arrays often, if at all, in almost all cases you use collections that provide you with convenient abstractions for everything, even if they are still arrays underneath.


>I didn't find out how its possible to professionally program for 5 years and not use arrays

Python maybe?


I’ve started telling non-techie people that you don’t interview for software engineering jobs: you audition for them.

They get it.


Definition of Audition: "practical demonstration of the candidate's suitability and skill"

Nope, Audition doesn't sound right.


Nah. Auditions demonstrate skills necessary to do the actual job. Tech interviews demonstrate ability to regurgitate Leetcode questions.


I’m too old. I’m telling recruiters that I will not spend even 5 minutes preparing for the interview. I believe that interviews should be based on what you did, not on your ability to memorize a book of CS problems and solutions.if you a company with good BS department (like google, db,...) you can be arrogant and still have candidates, but if you not them, I highly recommend to rethink how you interview people.


I think you are mislead here. I was trained by Facebook for their interview loop and yes, these are the kind of questions interviewers might ask (with the caveat that the middle of the linked list problem would be formulated as "given a list of items, find the middle"). But they are not the only ones.

A FB interview loop consists of a series of discrete interviews, starting with a phone screening (or two, for PE), followed by on site interviews consisting of coding tests, architecture tests, behavioural tests etc.

The coding tests usually consists of questions like "given foo, write a function that does bar". The questions are designed to extract a number of signals from you, including "do you know the language you picked", "did you pick a good language for the question asked", "how fast can you provide a solution". After you provided the initial solution, you might be asked variations of the question, like "given infinite memory and limited cpu, how will your approach change" or even point you to possible improvements. This is not a pass/fail test, just a way to extract some info about your capabilities. At the end of the loop, all feedback is collected and a panel will decide if you will get an offer or not. You might be bad at algorithms, but providing you know your way around the language(s) you picked, show at least a basic level of problem solving and did good in other fields, you will get an offer.

Imho, if you don't get an offer from Facebook, it means you are really bad or not enough experience. Luckily the recruiter will let you know the areas where you need improvements.


I worked at Google and I failed onsite interview at FB once. I guess I’m too bad as I have plenty of experience and didn’t get an offer. Could be I came across as an arrogant asshole, as I was itritated by questions I was asked and folks I met (was told that one group will do an interview, but was talking to engineers with 5 years in the industry and the only company they worked was FB) When I interview, I never ask questions from the book, no coding on the whiteboard. Those questions answer only 1 questions - how much free time you have to prepare for them.


The "one pass" solution to find the middle of a linked list visits each element twice (or more precisely, it visits half of the elements twice). It is hardly one pass.


This often trips up people who don't know how big O works (loops are not directly correlated to N), or why it works that way (in general a constant before N is negligible, the curve is more interesting).

This single pass approach introduces a conditional branch inside a loop, which I've found to be generally slower on x86 - because I've made that mistake and years later found a huge performance benefit by using the "dumb" (multiple loop) approach.


> This often trips up people who don't know how big O works

They didn't ask for an algorithm with linear complexity. They explicitly asked for a solution "in one pass". That's highly misleading.

Edit (after the reply by zamalek): And you are perfectly right about the performance: it's probably slower than just doing two passes (one to find the length, the second to find the middle).


As the root comment points out, both solutions (the second being two loops) are 1.5 passes.


Proposal:

Convert the linked list to an indexed structure with dynamic capacity like a vector or a hash table. This is easy to do in one pass. ("Visit the node; add it to the hash table. Visit the next node...")

Once you're done, access the middle element.

You've reduced the number of passes from 1.5 to 1, and all it took was duplicating the entire input.


Which could be ok depending on memory constraints


Well, it's ok based on this statement of the problem. It's never going to make sense as an approach in reality, because the work you need to do constructing the second data structure is considerably more than the work you'd need to do to make the extra half pass through the linked list. You're losing on space and time by doing it this way.


To teach programming, many universities structure their courses "bottom-up":

1. Intro: learning how to implement an algorithm

2. Algorithms+datastructures: learning about existing algorithms/datastructures and how to design your own, reasoning about complexity

3. Program design: how to write larger programs (OO, compiler construction, distributed algorithms, etc.)

4. Managing the development process: project management,...

Those interview questions are highly annoying because they only cover levels 1+2. Other important technical skills (able to quickly understand code written by others, how to organize programs, etc.) are not tested. The questions are also rather insulting if the candidate has already several years of experience because they suppose that the candidate is still stuck at those lower levels.

But even if the goal is to test those lower levels, the questions are highly ineffective. Many of them do not test skills, they test your memory. You either have already heard about the cycle-detection question or you haven't. I am surrounded here by very smart people and I doubt that anyone of them would be able to find the answer to that question by themselves in a few minutes.

* The following rant is slightly off-topic:

However, I have to say that I am encountering more and more people like the person who posted here yesterday: People who have been programmers for several years and who admit that they have problems with loops and simple datastructures. In my opinion, if you have problems with those levels 1+2, you should not even think about the other levels. Many problems that we have for example in performance and cybersecurity are caused by the fact that most programmers simply don't know what they are doing. If you have problems with loops, you will not understand what a buffer overflow is. If you don't know what pointers are and how main memory works, you will not understand why your program is slow. And I am saying this as somebody who hates low-level languages like C (although I am quite good at them).

I know that this is currently a highly unpopular opinion among certain teachers who are pushing for a "softer" introduction to programming (with a lot of GUI designing and project management right from the beginning) and I have some sympathy for their position (students should not get the impression that CS is only about programming). But at some point you have to learn how a computer works, otherwise you will copy-paste from stackoverflow for the rest of your life.


Here are some of the popular array-based coding interview questions for your practice:

How do you find the missing number in a given integer array of 1 to 100? (solution) [1]

How do you land a job at "startups like Uber and Netflix; big organizations like Amazon, Microsoft, and Google; and service-based companies like Infosys or Luxsoft"?

Easy - by rote memorization. And a healthy sense that it's to best not question the basic idiocy behind cargo-cult interview tactics like these.

Because apparently genuinely useful critical thinking skills -- beyond such trivial matters such as how to get a better space-time tradeoff on that petabyte-scale fibanocci generator[2] our customer desperately needs you to design a viable POC for right now, on the whiteboard, before lunch -- basically aren't needed at these companies.

Notes:

[1] You think I'm just being snarky? It's famously common out in hedgefund-land for people to get hired more or less on the basis of being able to whip out a deadpan response to "gee-whiz" questions like these. And to get "flushed" for their inability to do the same. Startups aren't quite so naively reliant on shibboleth questions of this sort -- but but only slightly so.

[2] I'm being slightly hyperbolic with this example -- but only slightly. I've long since lost count of the number of times been asked "design" questions really only slightly more ridiculous than this example. And as a matter of fact I've been asked an "advanced fibanocci" question -- and apparently received a job offer to a large extent on the basis of my ability to "nail" it -- quite recently


Would you be looking for the solution where you subtract every number in the array from 5050? If anyone says that they 99% studied it.

A more "natural" sulution would be to sort the list first, and then look for consecutive array items where the difference is not 1.


I just woke up (still in bed). I've not seen this question before. For about 2 seconds I thought of iterating through and creating a map and... Wait a second, if one number is missing, I can just find the sum and subtract! Admittedly, I would have had much more trouble in a high pressure situation.

I think questions like this are fun and novel and also have absolutely no place in an interview for software developers.

Edit: the slightest of arguments for a question like this is can they find novel runtime optimizations. A work sample test is better. Grab some crap code from the codebase like a double forloop that should have been a map look up and have them make it more performant.


Would you be looking for the solution where you subtract every number in the array from 5050?

Unless they can swear up and down that what they actually do at this company, for at least a significant part of the day, is throw each other against the wall (er umm, whiteboard) and insist that they solve problems like these (and do so elegantly) within 10 minutes or less...

... or get fired ...

... then what I'll be looking for is simply -- the door.


Would you be looking for the solution where you subtract every number in the array from 5050? If anyone says that they 99% studied it.

I was asked this exact question at my on-campus interview with one of the Big Five software companies for a Program Manager internshi between my 3rd and 4th years of college.

I had done no “leetcode grinding”-style prep.

Subtract from 5050? No, I didn’t think of that. But I did think of summing the numbers 1..100 with a for loop, sum the numbers in the input array, and subtract.

Not the perfect solution. But it’s O(n).

And I did get the internship.

My point being not that I’m some kind of algorithmic prodigy: I’m very much not. But if a college kid can solve it without any prep, nor rote memorization as GP suggests...


If you're asked to sort a list and if you suggest something better than bubble sort, it means you 100% studied it. There is no way someone could come up with the quicksort(or alike) algorithm on an interview.


Insertion sort is actually the one that comes naturally for me. :)


I wish I had seen this yesterday. I had an opportunity (interview) and a had a lot of "Oh I know this" but when asked to explain further I was like "Oh...?"


I find these questions are a bit too simple and direct. Some of the interview questions I've seen are much more nuanced and often more indirect.


Apparently one of the questions was:

Q. Given X-Y coordinates of two rectangles, determine if they intersect or not.

I'll try for an answer -- I looked up nothing, and it took longer to type in the answer than it took to think of it!

A. Given positive integers m and n and m points A(i) = (a_i1, a_i2), i = 1, 2, ..., m and B(j) = (b_j1, b_j2), j = 1, 2, ..., n, determine if the convex hull of the points A(i) intersects the convex hull of the points B(j). So, look for a line that has all the points A(i) on one side and all the points B(j) on the other side.

Suppose we have numbers u, v, w, and consider the set of all (x,y) such that

ux + vy = w

Then those points (x,y) form a line, and every line can be written in this form.

Then we seek u, v, w so that all the A(i) are on one side of the line and all the B(j) are on the other side. So, without loss of generality, we seek u, v, w so that for all i

ua_i1 + va_i2 >= w

and for all j

ub_i1 + vb_i2 <= w

Or, we seek u, v, w to solve the linear program

maximize z = u + v + w

subject to

ua_i1 + va_i2 >= w

ub_i1 + vb_i2 <= w

for all i, j.

The simplex algorithm will determine if this linear program is feasible, that is, if u, v, w exist to satisfy the m + n linear constraints, or not feasible. If the program is feasible, then the two convex hulls are separated by the line the set of all (x,y) such that

ux + vy = w

Else the linear program is not feasible, no line exists separating the convex hulls, and the two convex hulls overlap.

Yes, we could tweak this simple formulation to something a little more involved and, then, determine if the two convex hulls just touch but otherwise don't overlap.

This solution solves the problem about rectangles in the OP as a special case.

Let's see: Given a closed convex set C with points A(i), is the convex hull of the points A(i) also in C?

Well, the intersection of any collection of closed sets is closed (the union of any collection of open sets are open). The intersection of any collection convex sets is convex. Then, the intersection of any collection of closed, convex sets is closed and convex.

The convex hull of a set of points is the smallest closed convex set that contains all the points, that is, the intersection of all closed convex sets that contain all the points and, thus, is closed and convex. Here convex hull is well defined since the intersection is unique. A line in X-Y and one side of that line is closed and convex. So the convex hull of a set of points on the line and some one side of it is closed, convex, and a subset of the line and that side of it. Our algorithm needs this result.

Is that a sufficiently good answer?


If I was an interviewer I wouldn't like this response for most jobs, although it would be fine for a small subset of jobs. The overlap of two rectangles is an easy question with an easy answer and a long, more complicated answer would indicate that the interviewee missed social queues about what is expected in the answer and may be a difficult person to work with.


You have an easier answer that is correct?

Looking at the "solution" in the OP, there was a HUGE assumption NOT stated, implied, etc. in the statement of the question: The assumption was that the sides of the rectangles were parallel to the orthogonal X-Y axes. So, the question was badly stated.

For how the question was STATED, my solution may be about the easiest.

> The overlap of two rectangles is an easy question with an easy answer

You have an "easy" answer to how the question was stated? Until I hear or think of a much easier answer, I have to conclude that your statement of an "easy question" is false.

The OP certainly did NOT have a solution to the question as stated.

> If I was an interviewer I wouldn't like this response for most jobs, although it would be fine for a small subset of jobs.

The interview questions were to be for "most jobs". Then "most jobs" should prefer a correct answer, that is, correct for the question as stated.

Or, the question could be important for many jobs working with graphics, rectangles, triangles, etc., and there commonly we won't have specific orientations, say, rectangle sides parallel to the X-Y axes.

> social queues about what is expected

The interview questions are supposed to be challenging and to let the candidate show their capabilities. In that context, "what is expected" should not limit the power of an answer.

If the company wants only people who know not much more and not much less than the people already there, then the company, should not be looking for new people, is on the way downhill, also because of that should not be hiring, and no good candidate should want to work there.

The OP questions were to be about "data structures and algorithms". Well, I used the simplex algorithm, seriously ranked as one of the best pieces of engineering in the 20th century. A special case of that algorithm is min cost capacitated flows on networks, and there is a really cute algorithm there and a cute use of a spanning tree on a network. So, my answer was good for "algorithms and data structures".


Easy answer (even if the sides aren't orthogonal):

Step 1 - Find all pairs of line segments where there is overlap on the x and y planes. This step is O(n^2) but since we're dealing with rectangles it's only 16 checks.

Step 2 - For the line segments that do have overlap check to see if the intersection occurs within the line segments or outside of it. If there is a line intersection within a pair of segments then there is an overlap of rectangles.

For the question as STATED (4 sides) this will run quickly and a first year CS student could implement it, or read it and understand what is happening. I could use a whiteboard and explain this algorithm to high school students.

When you hire for a company you do want programmers that will have a correct code solution. You also want programmers that will write code that is easy for others to maintain, you want programmers who are pleasant to work with, aren't difficult people, etc. In an interview, the technical questions are only part of the interview process. There is also the underlying question of "is this a person I want to work with?".


Nice answer.

But since I studied a lot of optimization, I saw my linear programming answer first. On an interview, typically want to give the first correct answer do find.

My answer is more general, and that is goodness. Indeed, you mentioned that your answer solves a more general question than intended in the OP. So, you seem to like the generality of your answer but not the generality of mine.

The generality of my answer applies to convex polytopes, convex hulls, in any finite dimension, and dimension 3 should be of interest in some cases, e.g., see if two objects intersect. That might be of interest in some of robotics.

If the polytopes are determined by points, then my answer solves the problem and we are looking for a separating hyper plane. If each polytope is determined by the intersection of half spaces determined by hyperplanes, then we are looking for a point in common, and again we can use linear programming. So, given points we are looking for a separating hyper plane, and given hyper planes we are looking for a point. Smells like a nice case of duality.

Farkas lemma, a special case of my solution, is central to the Kuhn-Tucker conditions in nonlinear optimization. Since the ML people are interested in optimization, they might welcome Farkas lemma and my more general solution.

And, again, my answer really is part of "algorithms and data structures" which was the focus of the questions.

So, now we are into what is commonly called computational geometry, commonly regarded as part of computer science, and heavily about algorithms. E.g., doing nearest neighbor searches via k-D trees (in Sedgwick) and cutting planes is part of computer science, computational geometry, trees, data structures, and algorithms.

For the linear programming, just call a subroutine, e.g., IBM's old OSL (optimization subroutine library).

My more general answer indicates that I would be a good person to work with.

The question is a separation problem. Well, so as to have readers be more comfortable, I did omit mention of the Hahn-Banach theorem. For curious readers, there are lots of applications of that classic result in D. Luenberger, Optimization by Vector Space Methods.

"Hard to work with ...". How 'bout hard to please?





Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: