How to solve a hard programming interview question
dailycodingproblem.com
How to solve a hard programming interview question
1–10 of 84 posts
Re: How to solve a hard programming interview question
#2Am 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.
Re: How to solve a hard programming interview question
#3Am 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?
Re: How to solve a hard programming interview question
#4Am 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.
Re: How to solve a hard programming interview question
#5Am 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.
[deleted]
Re: How to solve a hard programming interview question
#6I see domain was registered a few days back and they already have some testimonials. Fishy ?
Re: How to solve a hard programming interview question
#7[deleted]
Re: How to solve a hard programming interview question
#8In C#, List>, foreach, AddRange, OrderBy, ToList
Re: How to solve a hard programming interview question
#9Am 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?
You 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.
Re: How to solve a hard programming interview question
#10This 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.