4 ms·
1. It's the dumbest algorithm for sorting possible (bubble sort). Compare two objects, swap them if one is bigger than the other, go down the list, repeat. If a
by gjsman-1000 2y ago
1. It's the dumbest algorithm for sorting possible (bubble sort). Compare two objects, swap them if one is bigger than the other, go down the list, repeat. If a developer doesn't know that algorithm, what algorithm could they possibly know? It's the lowest bar.
2. 2 Languages of your choice is enough to show you aren't a frameworker and can think in more than one box. Doesn't matter if you do it in JavaScript and C#, Go and Rust, Python and Haskell. It's a chance to show off, while being quite obtainable for a competent developer.
3. The parallelism trick question merely shows that you actually understand what you are talking about. A leetcoder might make the trap of assuming it's log(n), or the square root of n elements, or some other overly-thought-through math that is bogus. If you think it through though, bubble sort is simple enough, that it's very easy to realize (in my opinion) why more threads than CPU cores doesn't really help.
- probably_wrong 2y ago> or some other overly-thought-through math that is bogus. So the mathematically-correct answer would be a minus while "in my opinion" would be a plus? I think your interview question brings you to your intended answer: the reason why every company makes their own process is because what's good for you would probably get you an instant fail in NASA and would get you labeled as "experience not relevant" in some research settings.
- gjsman-1000 2y ago> So the mathematically-correct answer would be a minus while "in my opinion" would be a plus? My opinion was only that it would be relatively easy to figure out. As far as I know, it is a certainty that sectioning a bubble sort, more or less than CPU cores, is less efficient. 16 threads on an 8 core CPU just means balancing 2 threads on every CPU core, each doing their own sorting and needing eventual merging back together. There's no way that can be more efficient.
- anonymoushn 2y agoIf you have hyperthreading then a low IPC workload like this is optimally done on twice the number of cores.
- PaulHoule 2y agoIf I want to separate the real algorithm masters from the rest I’d avoid questions about sorts with total ordering but instead cover algorithms with partial ordering such as topological sort, BSP trees and such which are super-beautiful and I think quite useful but obscure. Bubble sort is quite interesting from an algorithm analysis perspective (prove it completes, prove it gets the right answer, prove how it scales with N) but I’d almost rather a programmer I work with not know about it from a coding perspective because it increases the chance they code up a bubble sort than use the sort function that comes with the standard library.
- Bootvis 2y agoWhat does parallelism have to do with Big O and I do wonder how would parallel bubble sort be written to your standards in for example Python.