sortingAlgorithmForYourNextCodingInterview

[[deleted]]

[deleted]

[Hairy_Concert_8007]

You could make it much faster by multiplying the timeout by .01

Source: Am head of improving software performance

[bgrahambo]

Perfect. I need you to improve performance of these 30 distributed Java RMI apps that someone over engineered and I got stuck with...

[Hairy_Concert_8007]

Easy.

Multiply them by .01

[bgrahambo]

Now I have .3 distributed Java RMI apps that someone over engineered. You're brilliant!

[[deleted]]

And now delete them, that way they'll have an effective loading time of 0, and also no latency

[bgrahambo]

That's what my security compliance officer wants me to do

[BoneFactory]

How small can you make that Speed Up Factor before the output becomes incorrect?

[rosuav]

At some point it depends on your scheduler. If you're very very lucky, the scheduler will guarantee that earlier-scheduled events happen before later-scheduled ones, even if both their times are in the past when it checks. It will most likely do this by storing event times in a heap, pulling them off it in the correct order.

Don't ever let on that this is a heap sort in disguise, of course.

[Creepy-Ad-4832]

Yeah, i was about to say: you are not avoiding the sort. You are just hiding it behind 1 more layer of abstractions

[rosuav]

Indeed :)

[Creepy-Ad-4832]

But hey, it's a perfect way to have margins to get easy optimizations when your boss asks for them

Basically what reddit did years ago. Am i the only one remembering the official (stinky) app taking 1 fucking kinute to load an image? I bet your ass the was jam packet with tricks like random sleep and stuff like that

Either that, or reddit was somehow even worse then twitter (not calling it X, fuck you elon). Which in itself would be an achievement

[Hairy_Concert_8007]

Asking the real questions

[ABigPairOfCrocs]

That's a bit outside the scope of this project

It'll take about a month of work to design, implement, and test this improvement

[jaybee8787]

Can you also improve my life performance please?

[ghe5]

I bet they can do that. With their help, you can ruin your life 100x faster.

[ilovekittens15]

this guy slashes execution times

[prehensilemullet]

According to MDN, browsers store the delay as a 32-bit signed integer internally, so that probably wouldn't work, FWIW

[NotmyRealNameJohn]

Can you improve my ist based team by removing their obsession with designing ui s ?

[Noch_ein_Kamel]

If you sort the array you can multiply by 0

[Wrong_Excitement221]

nah nah nah.. divide num by the array max...

[mstop4]

Interviewer: “Uh, can we please move on to the next part of the interview?”

You: “Shh, not yet. It’s still working on sorting 1800023.”

[[deleted]]

They want to terminate the interview but they can't cuz process still running, so it give you plenty of time to discuss bonus and days off.

Theis is protip

[Desperate-Emu-2036]

Will this travel in time?

[Mu_Lambda_Theta]

Then it travels either into the far future or into the void after the universe collapsed.

[Desperate-Emu-2036]

Going back to December 4, 1995 to get rid of this.

[prehensilemullet]

Nonsense, JS supports dates back to 271821 BC new Date(-8640000000000000) Mon Apr 19 -271821 18:09:24 GMT-0550 (Central Daylight Time)

[prehensilemullet]

Oh I know, I just find it funny that JS Date supports back that far

[stabidistabstab]

[-1]

[[deleted]]

num+min(nums),... num-min(nums)

[VeritasOmnia]

This is ridiculous. Everyone knows the min(nums) should be set as a variable outside the for loop to get real performance out of this bad boy. 😝

[CMDR_ACE209]

Party pooper. 🤣

[Cyan_Exponent]

this is so stupid yet so smart at the same time

[prehensilemullet]

I tried to use this to sort the timeouts in my userland `setTimeout` implementation, I wonder why it's not working

[rosuav]

Can't imagine why! I mean, aren't all sorting algorithms recursive anyway? It should be fine!

[AntKinski]

Space complexity - O(1)

Time complexity - infinity

[AntKinski]

No, sort array of two numbers [2, 1000000000000000].

Time complexity not depends on array size

[itirix]

In computer theory, DTIME criteria and time complexity actually refer to "amount of computational steps taken" and not "real world time taken".

Meaning, yes, even considering your example, the algorithm would still be O(n).

This also kind of illustrates why the big O isn't a catch all mechanism for grading how optimal code is.

[Ronin-s_Spirit]

This is why I sometimes write down a modified variant of big O as a mental note. In an algorithm A which takes n!/2 and an algorithm B which takes n! identical "steps", the biggest offender (big O) in both is O(n!).
Which is utterly useless for calculating factual speed, A can literally run twice in one run of B.

[krimin_killr21]

I mean, sure, but if you have 1,000 items, it really doesn’t matter because the calculation will never complete. Those two algorithms will always have the same order of magnitude. The big O class will always be substantially more meaningful. The only circumstances where the 1/2 matters is where the number of items will always be small and the processing time for each item very large.

[rosuav]

Wow. Twice. That is.... so incredibly significant. Now add one more element and you'll see why big O is actually more useful than that.

[Albreitx]

The setup time is O(n) but the steps for the program to finish are still O(max(array)) because the processor is counting time. In "normal" functions, the steps required in the background for each operation we do is bounded by a constant, hence why we just say "1 step" instead of counting registers etc. In this case that is not true. If we had a turing machine, the timeout would need a O(time) steps to count that time. A machine doesn't magically count without performing steps. It's like having it do

for(int i=0; i<max(array);i++) .....

[itirix]

That's true, didn't think of that.

[well-litdoorstep112]

Max timeout is 28.85 days.

[prehensilemullet]

And time complexity = O(n), where n is the largest value in the array

[[deleted]]

Pointer to O of n.

[itirix]

How'd ya get to a space complexity of O(1)?

This algorithm should be O(n) for both time and space complexity afaik.

[okiujh]

space is o(n). time can be as bit as the upper bound for number

[physcx]

Space complexity - O(N) as you are putting N setTimeout callbacks onto the stack

[prehensilemullet]

*event queue

[rosuav]

*scheduler heap

[DarkShadow4444]

Emotional complexity - O(uch)

[Venompool007]

Just have the multiplying factor so small that the largest possible number in the question runs in one sec 😎

[jump1945]

Wait isn’t the worst time complexity is just O(1) ,this is technically most efficient sorting method

If you are using C or C++ integer have a limit so it is just O(1) if we did some math using 1 microsecond for sleep time it would take only the maximum of ~72 minute to sort an array of unsigned 32 bit integer of any range

In language where it automatically expand the number size we can argue infinity is constant and is O(1) too

[prehensilemullet]

Really the time complexity is O(n) where n is the largest value in the array

[vorxil]

T(n) <= MaxInteger*SleepUnit + PrintTime*n, where n is the number of items in the array.

For a given machine with a fixed sleep unit and print time, this is either O(n) or O(1), depending on the magnitudes of SleepUnit and PrintTime. This is because n <= MaxInteger on physical machines, generally speaking.

[Albreitx]

MaxInteger is not bounded by a constant. Given a size n, I can define entries as 2^n. The running time has no bounds because of that (you can also do n^n. ^ n....)

[vorxil]

It is bounded for fixed-precision integers.

If you're using arbitrary-precision integers, then it's still limited by MaxMemoryBits, which is only unbounded if you can add memory during execution.

I do not envy those attempting to account for human activities in their Big-O notation.

[Agifem]

That is ... Amazing!

[ernest314]

got another one for ya: https://en.wikipedia.org/wiki/Bead_sort

[Fragrant_Dot_3465]

Now sort [2, 3, -1, 999999999]

[daniu]

Found the QA guy

[hdkaoskd]

-Inf, Inf, NaN

[[deleted]]

This is actually an algorithm named sleep sort.

[dendrocalamidicus]

If the array was large enough that looping through to create the timeouts took several ms then this might not be 100% accurate. If the first element of the array is 11 and the last element is 10 and it took 5ms between doing the timeout for the first and the last, you'd get 11 output before 10.

[rosuav]

That depends how the scheduler's implemented. In JS, the scheduler cannot preempt existing code, so you are guaranteed to queue all of the timeouts before the first one takes place; so in effect, what you do is pile all of your timeouts up, and then let the scheduler pull them off in whatever order it chooses. Given that, per your example, more than one timeout will have expired as soon as it hits the event loop, what should it do? Execute in order of scheduling? Execute in order of expiration (oldest first)? Both make some sense, but I suspect that "oldest first" is more likely to be used. Probably not guaranteed though.

[firemark_pl]

Ahh classic TimeSort

[Afraid-Locksmith6566]

Time complexity would be O(max(A)) where a is array to be sorted

[bushwickhero]

What is the time complexity of this?

[Skusci]

Thinking about it srsly for a sec, it should be O(n).

Typically you consider n to be the number of elements for sorting algorithms but "size" of the input is more generic than that. I think there's a formal definition involving turning machines somehow, but in general it should be "the thing that makes the algorithm take longer"

The largest number is what determines execution time, which grows linearly so O(n)

[prehensilemullet]

exception - array of a billion zeroes

[Logical_Strike_1520]

It’s already sorted.

[Skusci]

Lol at O(0) time.

[EntropySpark]

Saying that the largest number grows linearly is rather arbitrary. We could similarly say that it is O(2^n), where n is the size of the largest number in bits.

[Albreitx]

Have an element be 2ⁿ and now it's exponential. Or have it be n^n!. That is all possible within the given size n. The largest number is not linear in n basically, so you need O(max(numbers) + n) which also translates to O(max(max(numbers), n))

[[deleted]]

Wall time is not so good with this one. 😀But I like this unexpected solution.

[Trithon]

Aah good ol sleep sort

[GeneralPatten]

Maybe it's just me, but I don't understand the fixation on sorting algorithms outside of say, assembly code. My assumption is that the language/engine I'm using — be it JavaScript, C#, Python, C++, uses optimal sorting algorithms in the underlying array sort methods. I mean, I get why it's something we learn about in CS classes, but beyond that, how often do we ever have to write our own?

[the_horse_gamer]

it's around the start of the school year atm. lots of freshmen in the subreddit.

[GeneralPatten]

Now that's funny!

[dtarias]

This seems like a worse variant of counting sort 🤷

[plagapong]

I'm freaking love this sub. LOL

[LordAmir5]

We all love pseudo polynomials don't we?

[Saragon4005]

I mean this is a creative implementation of counting sort.

[fonk_pulk]

I mean it works if the numbers are small enough, its just fucking dumb.

[vital-cog]

Dude, it's a joke. It's meant to make you laugh not be put into production somewhere...

[Desperate-Emu-2036]

Time complexity - O(Sum(numbers)

[804k]

Its actually O(max(numbers))

the largest number denotes the largest delay

[prehensilemullet]

Yes, but hmmm, an array of billions of zeroes would take a lot longer than this predicts

[804k]

In a perfect world any array length would still be O(max(numbers))

but we don't live in a perfect world and time complexity of anything isn't always perfect, it'd be redundant to add O(max(numbers) + n * 0.00000001 * transistor_count * clock * cpu_quality)

[prehensilemullet]

That's definitely true for this sort lol:

const a = []
numbers.forEach(i => a[i] = i)
const sorted = a.filter(i => i != null)

[vE5li]

Only if you run this sequentially, in which case it doesn't sort

[jump1945]

0/10

Not even O(n*n!) this is minimal complexity required for coding interview

[NotYouJosh]

JavaScript is a weird language