7 ms·
How to solve a hard programming interview question
- theossuary 9y agoAm I missing something, or couldn't you just merge the lists like you would in merge sort? Begin with a pointer at the start of each list, find the minimum of the elements being pointed at and increment that pointer, until all pointers are at the end of their respective lists. You could possibly even do it in place. That was my first thought anyway.
- jaredsohn 9y ago> find the minimum of the elements being pointed at Can you describe how you would do this and talk about how it would impact the time complexity of the algorithm?
- unsatchmo 9y agoYou have to do K comparisons unless you keep track of the ordering of the other K-1 indices every time you pick a new element. Keeping a heap makes this log(K), yielding a KNlog(K) instead of K^2N. The naive solution is probably better when the number of lists to merge is small.
- btschaegg 9y agoI would guess the time complexity is the crux with this issue: Without knowing the nature of what the algorithm is used for in practice, you're left guessing. If you assume continuous memory "lists", cheap comparisons and a relatively small set of lists, you're not necessarily wrong to pick a brute-force approach, since maintaining the heap will result in much bigger constant factors in the complexity formula (even due to prefetching and so on). It's basically the same problem that peeks its head in every std::vector vs linked list discussion (and it's really amazing how many items you need before std::vector ceases to be a good pick for almost any problem).
- deleted 9y ago[deleted]
- hendzen 9y ago"find the minimum of the elements being pointed at" - doing that efficiently (e.g. with a heap) is the 'trick' to the problem.
- Vendan 9y agoNah, the trick is knowing that merging and then sorting isn't the best way.
- deleted 9y ago[deleted]
- Karliss 9y agoIt can be done on O(nk log k) if you always merge two shortest list. If all the lists have length k initially it can be easily done with couple of loops as all the lists will have the same length - n in the beginning, 2n after fist iteration, 4n after second.
- Karliss 9y agoHere is a quick implementation https://gist.github.com/karliss/ebc27b0b2baa3e6fc0f50fadda733554 https://gist.github.com/karliss/ebc27b0b2baa3e6fc0f50fadda73...
- urgoroger 9y agoThis is correct, and I think it's mentioned in the article. I think this is probably what most people would think of too rather than the heap based solution. Using the heap solution also requires you to know how to use a heap in whatever language your interviewing in, or you could implement one (which would probably a lot more effort), so I prefer this one. EDIT: Ah, I didn't read your comment carefully enough. I thought you were referring to a divide and conquer approach when you meant 'like merge sort', where you the list of lists in half for each recursion, the recombine the sorted halves using a standard merge sort list merge. What you describe is basically the same as the solution given by the author. However, you don't give a way to find the minimum pointer, in the case of the author, a heap is used. Using a more naive data structure/algorithm (e.g. just finding the min over all pointers every time) will probably give worse asymptotic complexity than using a heap to maintain the least element
- Samarth1234 9y agoI see domain was registered a few days back and they already have some testimonials. Fishy ?
- deleted 9y ago[deleted]
- audio1001 9y agoIn C#, List<List<T>>, foreach, AddRange, OrderBy, ToList
- redmorphium 9y agoThat's not the optimal solution by runtime complexity, which is often the point of these interview questions.
- audio1001 9y agoMicrooptimizations... waste of time
- paulsutter 9y agoThis is the basic core of a sort-merge. It depends if the sorted lists are on disk (usually are with each about as big as memory), and how many you merge at once (which is about dividing all available memory into disk buffers, or the disk bandwidth, whichever is the bottleneck), and merging the memory resident lists using a treelike structure to be compute efficient. Also depending on the OS it can take parameter twiddling to achieve full sequential bandwidth. If the lists are on other nodes, like in a petabyte sort, that’s where it gets complicated because you need to recover from node failures during the sort.
- warent 9y agoIn my experience, when interviewers do grade based on algorithmic performance, they want to see low time complexity, and care much less about space complexity. In this example, you could actually accomplish the solution in linear time using a hashmap and keeping track of the min/max vals; O(max-min) Something like... let map = {}; let minVal = null; let maxVal = null; for (let a of arrays) { for (let v of a) { if (minVal === null) minVal = v; else minVal = Math.min(minVal, v); if (maxVal === null) maxVal = v; else maxVal = Math.max(maxVal, v); if (!map[v]) map[v] = 0; map[v]++; } } let result = []; for (let i = minVal; i <= maxVal; i++) { for (let n = map[i] || 0; n > 0; n--) { result.push(i); } } return result; Haven't ran the above, just an example
- Vendan 9y agoBut you have to quantify the max-min, cause it's quite easy for the data to make that way more expensive then "merge then sort". I.e., run your algo on [[0, 1000000000], [1, 2]]
- warent 9y agoGood point :) Perhaps add a check to see if min-max is greater than K*N, and if so then use alternative method (e.g. merge sort)
- myegorov 9y agoWhat about continuous data (real numbers, strings)? Your approach has rather limited application. On a different note, merge/sort approach (O(n log n)) is in general less efficient than the heap approach (O(n log a)), and may be impractical or wasteful of space (O(n) vs O(a)) if dealing with realtime data for example.
- Rainymood 9y agoScrolling down we are greeted with >Only accepting 98 more subscribers. >Subscribe for $9.99 / month Which then slowly ticks down. I was very sceptical about this and refreshed and I found that it just resetted to 100 again and started ticking down again. In other words, it's just a timer. I thought the article was of good value and that you provide a good service, but then this is contrasted by this scummy, predatory, and dishonest advertising trick. Thoughts?
- shokasg 9y agoWhat about using some ad blockers? I only see text :)
- Brotkrumen 9y agoI'm not sure what your point is. Parent says that the article signals it isnt credible by employing a dishonest sales tactic. Your answer is to ignore the potentially valuable signal?
- CobrastanJorji 9y ago> I often find it’s not enough to just be able to solve the question; you really need to vocalize your thought process. I interview candidates regularly, and I can't overstate how important this is. If I ask you a hard interview question, and you sit silently for 10 minutes and then write out a perfect solution on the board without any discussion of how you got there, all I've learned is that you knew the answer. I have very little evidence for why I should hire you. Talking through your problem solving out loud does not come naturally to a lot of people, but it's an important skill to master for interviewing (as well as for working through real problems in small groups).
- mattm 9y agoDoes it really matter though? What if I solve problems by eating a piece of toast? There's really no way you can understand how someone else thinks in an hour. All you're really going to look for is "Does this person think the same way that I do?"
- CobrastanJorji 9y agoIt matters a lot! If I could reduce your toast-based problem solving technique to something we could implement on silicon and gluten, imagine the applications! Also yes, hearing you reason also matters a lot. I need to see how you refine my lousy problem statement into a solvable problem. Do you make a lot of assumptions about the problem without noticing? Can you consider alternatives or do you get completely stuck on the first solution you encounter? Can you explain a technical idea to someone reasonably clearly and concisely? I don't need you to be like me, but if we can't brainstorm together about technical problems, we're going to have trouble working together as a team.
- virgilp 9y agoI concur - it does matter. I'm not looking for "thinks the same way that I do" - I'm looking for "thinks". And specifically, how. I want to see you evaluate & discard ideas. I want to know that you quickly identified the "brute force"solution and discarded it, rather than sitting there for 10 minutes, not knowing how to even start. You must realize, if the problem is hard, I don't even expect you to solve it. You're suspicious if you do. I don't have half an hour to sit on a single problem - that's not the purpose of the interview.
- reyg 9y agoA systematic approach like this or others (Gayle Laakmann Macdowell’s BUD) seem to reduce the risk of underperforming, but I haven’t had success with it. Instead, problem identification has been most helpful to me. The approaches for solving Dynamic Programming problems are different than those that require a fundamental data structure (like a heap). Recognizing the heart of the problem is harder, probably what the interviewer is really testing for, and in my opinion differentiates oneself better than following a step by step guide.
- suyash 9y agoCare to elaborate how do you go about problem identification?
- reyg 9y agoHm, here is an example: // 1. Explore the possibility of a recurrence relation. If the problem can be solved as a function of sub problems, then candidate techniques are DP, backtracking, greedy, and divide/conquer // 1a. Explore DP. If it’s DP, then optimal solutions of its subproblems are all that’s necessary. Confirm that subproblems are repeated so that I can reason for memoization and later leave room for a bottom up implementation. // 1b. Explore backtracking. If it’s a backtracking problem, then I should be able to test for the viability of a partial solution quickly. ...and so on
- abhirag 9y agoI think your example can be simplified :) Recursion + memoization provides most of the benefits of dynamic programming, including usually the same running time and well backtracking is recursion so the strategy can very well be -- Explore the possibility of a recurrence relation, if the possibility exists, try recursion :D
- thaumasiotes 9y agoSolve problems. Hopefully, after solving a problem several times, you'll be able to recognize it.
- 9y ago
- psergeant 9y agoI wrote a similar article a little while ago, which you may enjoy if you liked this: https://codeformore.com/technical-interviews-show-working/ https://codeformore.com/technical-interviews-show-working/
- deleted 9y ago[deleted]
- Nuzzerino 9y agoThis is not new advice. People have been giving this same advice for years. And frankly, people are sick of hearing it, and it borders on patronizing. However, that's not to say that it's a bad idea to aim for. The problem with this kind of advice though, is it only tells you what proficiency to aim for, and not how to get there. People only have so much brainpower to use during an interview. If you have to use every ounce of it in order to solve a "hard" problem in the first place, then diverting some of it to explaining things will distract the candidate. The real secret here is to make sure that you have that extra brainpower, so that you do not have to expend your brain's full capacity while solving that hard problem. So the first step is to practice interview problems until they're second nature. The second step is to practice doing those same problems, while explaining a thought process. Once that is second nature, you can further practice by throwing in unique types of explanations, or using the opportunity to make the conversation more interesting, to make the interviewer more impressed. I hope that some readers out there understand as well as I do, that the entire job interview process is a farce, and selects for sales skills more than it does for engineering skills. The pervasive idea that you have to explain your work only serves those who learn the type of methodology I described above. There are many brilliant candidates out there who believe that it would be a huge waste of their time to refine these skills, instead of engineering skills or other things that they may want to learn. After all, it would only serve to increase your odds of getting your foot in the door at those companies that use such irrational means to select their employees, and why would a brilliant engineer want to join such a team? This is the ultimate tragedy for (some, but not all) who are passionate about engineering and rationality, but not necessarily passionate about money. I think we can do better, folks.
- ToJans 9y agoWith all do respect, I think the author is missing an important point: he is talking about communication, but he seems to be the only one talking... IMHO you should first figure out why it's needed, and optimise for it's use case. F.e. if it's only used once a year and a simple merge+sort takes half an hour, it wouldn't be worth implementing it yourself. IME good (10x?) developers are way more efficient because they reason from first principles: don't start from the solution space, but from the problem space, and optimise based on constraints and requirements.
- aaronbrethorst 9y agoGood engineering skills and good interviewing skills are not necessarily identical.
- b0rsuk 9y agoI tend to solve programming problems when I visualize them. So for me the steps are: 1. Draw the input list on a sheet of paper 2. Try some solution methods on paper, writing them down so I can later re-examine them with new findings.
- TheSmoke 9y agodisregarding the performance, if someone asked me to write it pythonic i'd just do: sorted([i for i in chain(*lists)])
- half-kh-hacker 9y agoYeah, this is what I thought too. I guess in an interview you'd have to ask whether to favour performance or readability, though.
- estomagordo 9y agoHey Lawrence, might wanna point out that the result should be sorted too. Currently, that is not listed as a requirement.
- fencepost 9y agoYeah, I was reading through and when he talked about the output being sorted it jumped out at me as a "Wait, what? No, probably not" thing. Perhaps his definition of "merge" is different from mine. Even for his example I don't believe it's correct - he comes out with 10, 12, 15, 15, 17, 20 but I believe if it's basically zipping the lists I'd expect it to be 10, 12, 17, 15, 15, 20.
- blt 9y agoI tend to find problems like this one, where the brute force solution is straightforward and then you can improve it by using a special data structure, easy. The ones I struggle with are the puzzle-like ones, where solving the problem depends on having some single flash of insight.
- angarg12 9y agoConversely, if you just happen to know the answer because you saw it before, it feels a little bit like cheating. Quite honestly, I wonder how useful those kind of questions are to test someone's capacity to do the job.
- aaronbrethorst 9y agoTotally useless.
- blt 9y agoYeah, I do not think they are very useful. I know a lot of people, myself included, who perform worse than their true ability during interviews. It can be an anxiety thing, but also some people just prefer to take their time and deliver solutions in writing vs. work things out in real time on a whiteboard. I think a good alternative is to give the candidate a nontrivial project that should take around 8 hours, and pay them a day's wage to do it.
- speedplane 9y agoThat's better, but probably still not exactly indicative of real-world work... so much of on-the-job work is teamwork. Perhaps you could interview a group of candidates together and as a group assign a project that you know no one person could finish on their own, but would be manageable broken up. The people that form groups and work well together could presumably bubble up.
- blt 9y agoBut then if one candidate is an asshole, they ruin it for everyone...
- Bahamut 9y agoIMO, the first thing one needs to do in order to be high functioning with challenge is take the mindset that it is ok to underperform in an interview session and not get a particular job. Taking the stress out and focusing on clarity of deep thought helps almost everyone in almost all situations (I hesitate to say everyone since some people do thrive under pressure). It is one thing to read disciplined approaches to solving a problem - it is another thing to control oneself while under strong emotional states.
- amelius 9y agoI'd like to see algorithm questions replaced by architecture questions, as IMHO they are more important and can also invoke algorithm knowledge.
- Double_a_92 9y agoWhy are those interview questions mostly random algorithms? Wouldn't it be more sensible to ask for design patterns? At least you can use them in real life. Or refactoring patterns. Like give them a page of shitty code and ask them to make it nice. Forcing people to memorize obscure algorithms and solve them on a whiteboard seems like the worst possible solution. Unless you are really looking for some expert on algorithms.
- oldandtired 9y agoThe first question one should be asking is: What relevance does the question actually have to do with the job in question? The second question to ask is: Will this be of benefit for the end-user population? I find that I have no wish to join an IT related part of the organisation when it becomes obvious during the interview that they have no interest in serving the end-user community. They rather want to dictate what the end-user will be using, irrespective of all end-user needs. So for many years, I have worked on behalf of the end-user to get them to a point that they can do their actual jobs. With the advent of large corporate IT systems, one has seen an increasing amount of null work being required of the company staff (its purpose is to feed the egos of management, instead of actually getting things done). What was that movie?? If what you are doing doesn't enable the end-user to be more productive then what on earth are you doing? Interviewers who are not focussed on building teams to solve end-user problems are failing in their jobs. End rant.