Re:Programmers can’t write algorithms without help
by a_t48 on Monday November 04, 2019 @11:51AM
(#21443487)
Mergesort is also worth looking into.
Re:Programmers can’t write algorithms without help
by dragontamer on Monday November 04, 2019 @12:06PM
(#21443707)
Strangely enough, I always found quicksort easier to write than Mergesort. But that's probably just how my mind works.
Hmmm... with Mergesort, you gotta be copying the data to new buffers, malloc-ing arrays and new arrays, managing the data etc. etc.
Quicksort can be trivially done in-place. And yes, I know Merge-sort has an in-place variation, but in-place Mergesort is non-intuitive IMO.
-------
I guess merge-sort is easy if you are willing to call malloc / free (or new / delete) over-and-over again. But those functions scare me. I prefer to get things done without dynamic memory, especially if its a whiteboard interview.
Quicksort does require more brainpower than selection / insertion / bubble sorts. But if I were to use a recursive methodology, trying to do quicksort would be my strategy.
Re:Programmers can’t write algorithms without help
by a_t48 on Monday November 04, 2019 @12:17PM
(#21443821)
Mergesort sticks in my memory better, for whatever reason. And yes, definitely agree that in real life, avoid those allocations. For a whiteboard interview, declare an std::vector and call it a day, no need to manually call new and delete.
But if I were asked to "sort" a set of numbers, I'm sure I'd come up with some unholy combination of bubble, selection, and insertion sort that got the job done.
I always have to consult the books to remember the difference between bubble, insertion, and selection sorts. But even without documentation, surely people can write a list of numbers (ex: 9, 4, 5, 3, 2, 6, 0, 1, 8, 7), and then tinker with an algorithm until that list was in order? (0 1 2 3 4 5 6 7 8 9)
------------
Here's the thing about programming: you don't have to travel very far before you get into the "nobody knows the answer". The internet provides enough information for the first ~2 months on the job. Specialized books on your topic (ex: GPUs, HPC, OpenMP, etc. etc.) may cover another 1 or 2 months of training on the job.
After that? Nobody in the world is doing what you do. Nobody has to work with your particular configuration of tools, your particular problems (performance? Bugs? Architecture?). Your particular office politics. Literally no one else in the world. And yet, you'll be responsible for coming up with a solution that works, even without any guides.
That's why people like testing people "without the internet". Because in most cases, there's no guide to tell you how to progress a real project in the real world.