In C#, List >, foreach, AddRange, OrderBy, ToList
That's not the optimal solution by runtime complexity, which is often the point of these interview questions.
How to solve a hard programming interview question
11–20 of 84 posts
Re: How to solve a hard programming interview question
#12Am 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.
> 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?
I 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).
Re: How to solve a hard programming interview question
#13In 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 0; n--) {
result.push(i);
}
}
return result;
Re: How to solve a hard programming interview question
#14Am 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.
"find the minimum of the elements being pointed at" - doing that efficiently (e.g. with a heap) is the 'trick' to the problem.
Nah, the trick is knowing that merging and then sorting isn't the best way.
Re: How to solve a hard programming interview question
#15In 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 (mi…
But 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]]
Re: How to solve a hard programming interview question
#16Scrolling 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?
Re: How to solve a hard programming interview question
#17> 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).
Re: How to solve a hard programming interview question
#18Scrolling 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, predator…
What about using some ad blockers? I only see text :)
Re: How to solve a hard programming interview question
#19> 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 h…
Does 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?"
Re: How to solve a hard programming interview question
#20Am 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.
> 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?
[deleted]