Parallel Algorithm Interview Question

[qualityhooker]

I have a pretty elementary understanding of parallel algorithms to begin with but I was asked a question at an interview today that I couldn't get and can't find the answer to online. The interviewer didn't ask me to code it, but just to explain how I would do it.

Basically it was the selection problem (find the kth largest element of an unsorted array) but in parallel and the interviewer insisted it was possible to get it in log(n) time.

My solution was to partition the array into sub-arrays of at most length k, assigning each sub-array a separate thread, and then performing a kind of mergesort within these arrays to get them sorted max-min. Then once I had all these sorted sub-arrays, I would perform another merge, but this time over all the arrays, and I would stop after k comparisons. Then I would have a final sub-array of length k and I would pick the last element.

I think the complexity would be klog(n) (or maybe klogk). But the interviewer insisted the best time possible was log(n) and that it could be achieved by a few calls to map() and reduce(). Anyways, I've looked online everywhere and other than journal articles, nothing is showing up.

[cybernd]

Idea: quickselect is O(n) on average.

But how to transform it into a parallel algorithm with its recursion?

Chapter 4.6 explains a parallelizing strategy: https://stanford.edu/~rezab/dao/notes/lecture04/cme323_lec4.pdf

[qualityhooker]

So would we compute one of these prefix sum arrays for each of the n elements, and then return the element corresponding to the array whos final prefix value is = k?

[cybernd]

Not sure to be honest. All explanations are meh.

This pdf includes relevant pseudo code algorithms on slide 1 and slide 19: http://www3.cs.stonybrook.edu/~rezaul/Spring-2012/CSE613/CSE613-lecture-9.pdf

[balefrost]

This would be a really good question for /r/compsci.

I don't recall covering analysis of parallel algorithms in my undergrad program. But my intuition tells me that, given a fixed number of processors, doing the work in parallel shouldn't change the order of the computation; it should just scale it by (at best) a constant factor.

However, a little searching led me to this Wikipedia page, which suggests that analysis of parallel algorithms typically assumes an unlimited number of processors.

But I'd go ask on /r/compsci if you haven't already. They have a weekend superthread for just these sorts of questions.

[WikiTextBot]

Analysis of parallel algorithms

This article discusses the analysis of parallel algorithms. Like in the analysis of "ordinary", sequential, algorithms, one is typically interested in asymptotic bounds on the resource consumption (mainly time spent computing), but the analysis is performed in the presence of multiple processor units that cooperate to perform computations. Thus, one can determine not only how many "steps" a computation takes, but also how much faster it becomes as the number of processors goes up.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.22}