News for hackers. Stuff that matters.

A comment on Sleeping Through the Technical Interview (2022). Parent comment

Re:Sleeping Through the Technical Interview (2022) by squeaky-clean on Friday July 07, 2023 @07:12PM (#36639478)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

is just as fast as

[9]

If you really want to make it strictly constant time, just append INT32_MAX to the end of the array before sorting, and then pop it after.

[ Parent | on HN ]
Re:Sleeping Through the Technical Interview (2022) by libealistand on Saturday July 08, 2023 @03:02AM (#36642047)
Oh yeah, because assumin maximum values in your domain doesn't move all algorithms into constant time and renders complexity theory void.
[ Parent | on HN ]
Re:Sleeping Through the Technical Interview (2022) by squeaky-clean on Saturday July 08, 2023 @08:47PM (#36650276)
It doesn't though. How would merge sort become constant time if you assume a maximum value? It's also a joke...
[ Parent | on HN ]
Re:Sleeping Through the Technical Interview (2022) by libealistand on Monday July 10, 2023 @02:05AM (#36662676)
The main "value" in the domain of sorting problems is the number of elements in your collection.

A subproblem also considers the elements to be integers, then they become another "value" domain. (But in general, sorting problems only need their elements to be comparable, not necessarily integers.)

[ Parent | on HN ]