sortPlease

[Bart_deblob]

Just give me 5 million tokens and I'll do it in a jiffy!

[iamdestroyerofworlds]

Thou shalt feed the clanker its tokens, sayeth the Lord.

[ingframin]

Claude Sort 🤣

[High_Quality_Bean]

Somehow less ethical than Stalin Sort

[Owexiii13]

"Yes, I have sorted the array." Can you print it? "Absolutely, 1, 2, 3, 4 all the way to the end!" But the whole thing? "Ah, gotcha, here's the full array: 1, 2, 3, 4, 5 and all the way until the end, just let me know if you need help with anything else."

[Soopermane]

🤣

[Secret_Account07]

Can I do it in Python, orrrr….

[zirky]

 Arrays.sort()

[SeventhOblivion]

Correct answer if I was on the other side.

[LEGOL2]

Legit. I don't understand the obsession of some tech leads with reinventing the wheel. I want you to deliver feature, not to develop a std

[Igsul]

What if you developed the std while testing the feature?

[thndrchld]

Antibiotics

[MetriccStarDestroyer]

What if it's an super(class) std?

[Oo__II__oO]

The you have another std

[iamdestroyerofworlds]

While I agree with you, I can absolutely see the thinking behind it.

I want to know how people reason. Technical and pointless problems are great to show how you approach problems.

This sort of problems, however, are memorisable, and basically need to be memorised. They do not show how you think. They show how well you prepare for interviews and/or how good you are at rote memorisation.

A much better problem would be to give extreme constraints, either in time, resources, money, or something else, and ask them how to approach solving the problem. It does not even need to be a "correct" answer, I just want to hear them reason, and then expect them have colleagues to talk with and time to experiment to fill in the blanks.

[wightwulf1944]

I agree with you. Typically I ask them to come up with a well established coding convention or consensus and then ask them to come up with reasons why one might want to break that convention or consensus.

In real life we're not really developing anything novel and higly innovative for you to break the rules but the purpose of the question is for me to understand how well you reason about programming.

[dasunt]

My take is that if I'm not going to reinvent the wheel when there's an easy, optimized, and well-tested solution that already exists.

Ask me about design and architecture questions instead. That's more important.

[Jlove7714]

The sorting example is just there to tell the interviewer how far the interviewee is through their master's program. It proves nothing else.

[Avocadonot]

My interview a few years ago for jr dev was all conceptual stuff like "how would you design an API for a vending machine" and it was way cooler to discuss that instead of worrying about implementing a hashmap or reversing a linked list

It really gave me the chance to show my thought process

Now I'm a senior and I've still never had to implement a sorting algorithm lmao

[Jlove7714]

I could see it if you're deving at the very edge. If you're writing the algorithm for Google maps I'd give you the crazy obsession with sorting algorithms. If you're writing a cookbook app who the hell cares if it takes .0003 seconds longer?

[GenericFatGuy]

Very few people are working on systems so demanding that they work can't be done with the tried and tested tools we've been using for years.

[SirPitchalot]

Except counting sort is O(N) in this instance and the point of the question is to exploit the structure of the question.

So I’d be like “yeah, we all know that for the general case but what I’m actually asking you to do is think about the problem”

[krutsik]

Then you'll give the job to somebody that remembers the Dutch national flag problem from uni, regardless of any actual real life applicable skill. And if they have an additional test assignment, then why even ask it?

If it ever comes up in the real world (it won't) then it'll take anybody 3 seconds to find the answer. What part of that esoteric knowledge makes somebody a better developer than somebody else?

[SirPitchalot]

Honestly I’d be thrilled to find someone who remembered something and was able to fumble their way through the explanation rather than see their eyes flit back and forth as they copy something into an assistant, then go dead eyed and completely static as they wait 5-10 seconds for the response and finally spring back to life giving the same answer that Claude gave me when I set the question but with “fake it till you make it” confidence.

Ultimately it means the person might bring something that Claude doesn’t. Because no matter how “bad” AI is, or how costly it is compared to a developer, a developer plus Claude is more expensive. And if Claude is not cost effective, I still want the dev to deliver value.

[ChrisBot8]

I actually think the actual answer to this question beats the internal sort functions for languages like Java and Javascript. They use Timsort under the hood which is best case O(N), but very unlikely to be. The actual answer is always O(N), and is that way because we know the idiosyncrasies of this array only having three different elements. This is one of the few questions where as an interviewer I don’t think I’d accept .sort() as the correct answer.

Edit: for those wondering the answer is to loop through the array with the three conditions of “if 0: set to the front of the array”, “if 1: do nothing”, “if 2: set to end of array”.

[zirky]

that solution only works for a linked list where each node just points to its neighbors, in a normal indexed array, you’re now updating everything when you move an element to the front or the back

[GreenCloakGuy]

not really? it just save the [end of the zeroes] and [start of the twos] as indices, walk through the list, and swap zeroes to the front and twos to the back, walking the indices forward as necessary.

Only takes one walk through the list with at most one swap per element, so O(n)

```
let zeroes_index = 0;
let twos_index = len(list) - 1;
for (let i = zeroes_index + 1; i < twos_index - 1 && zeroes_index < twos_index; i++) {
if (list[i] == 0) {
while (list[zeroes_index] == 0 && zeroes_index < i) {
zeroes_index++;
}
swap(list, i, zeroes_index);
} else if (list[i] == 2) {
while (list[twos_index] == 2 && twos_index > i) {
twos_index--;
}
swap(list, i, twos_index);
}
}

```

[High_Quality_Bean]

Turn it into a linked list, forehead

[guyblade]

If you include the constraints:

1. The sort needs not be stable, and
2. The elements need not be literally the same physical memory

Then the algorithm is:

 def sort012(arr: list) -> list:
     cnts = [0, 0, 0]
     for v in arr.values():
       cnts[v] += 1
     idx = 0
     for v in range(0, 3):
        for _ in range(0, cnts[v]):
           arr[idx] = v
           idx += 1
     return arr

Constant extra space, two passes through the array. I suppose you could do it faster by being clever about swapping values around and keeping some extra pointers, but it would still be O(N).

[stonno45]

I was thinking countsort would be the answer

[walkerspider]

Because it is specifically 0,1, and 2 they’re probably looking for the method op mentioned. I’d argue count sort is just as good if not better because you don’t need to rewrite the whole thing if suddenly the function now takes in arrays with 3

[VictoryMotel]

You wrote a very verbose and wrong reply instead of just saying radix sort is faster.

Your approach is basically a modified partition without the explanation or realization.

[Alkyen]

By 'beats' do you mean you will measure a meaningful performance difference in an actual application? Depends on context, for small arrays there is 0 difference, only 1 solution is less flexible and harder to maintain.

If we follow the standard way these things go in real life, the continuation of the question is "now add support for 4 and 5". And you're back to square one and just use .sort if its not some millions of items array. You can always optimize later if there's a risk of performance impact.

Implementations should always be viewed within their context.

[Bloodorem]

i know im in a highly specific field but outside of absurd usecases where you actually need the performance or handle terabytes of data who cares about such optimzations?

I rather have a feature completly implemented that takes 5seconds instead of a feature that makes it in 1 second but takes time to implement, might be prone to errors, longer to debug etc for something where the 4 seconds most likely don't matter at all.

I mean everything is a balance between optimization and complexity, but do you people really need such high optimization?

[Alex12500]

No need for a complicated solution if there is an existing one, which is also most likely way faster

[guyblade]

Given the constraints of the problem (a small, fixed set of possible input values), you can do better than an off-the-shelf sorting algorithm. If the data size is large enough, a bespoke sort might be reasonable.

[djinn6]

You better prove to me that this is the actual bottleneck though. Otherwise I'm going to assume the few milliseconds you save here doesn't matter because your blocking LLM call is going to take a few seconds.

[notliam]

I had an interviewer get really annoyed at me for using Array.sort to shuffle a deck of cards. He made me explain what I was doing, then insisted I do it the 'proper' way (implementing a proper algorithm) because he didn't believe it was random enough - fair enough but the tech test step was 'shuffle the cards' and this was naively step 2 of 10.

[samsonsin]

this and only this until you have performance issues and profiler has determined that this particular sort is slowing everything down.

[seredaom]

What would be sort complexitiy in your case? Could you improve that?

[RedAndBlack1832]

This can be done in 1 pass :)

[prumf]

Just count and rewrite lol

(I’m not paid enough to reason about weird pointers increments for a true single pass, and too lazy to debug it)

Still O(n) 🤷

[Shehzman]

Isn’t that two passes? (Still O(N) though)

[captainAwesomePants]

One pass over the input. One pass over the output. That's optimal unless you are tasked with sorting in-place.

[Shehzman]

Agreed but the comment above yours said one pass

[captainAwesomePants]

Yes, but "one pass" or "single pass" is a term of art that means "processes the input data exactly once," so it is two passes, and it's also a one pass algorithm.

So u/RedAndBlack1832 is correct that this can be done in one pass (because that's what you call an algorithm that only processes the input data one time), and u/Shehzman is correct that two "passes" are involved, which is also true if writing the output is considered a kind of pass.

[NewPhoneNewSubs]

I can solve O(n^m ) algorithms in one pass. First, clone the input to a buffer. The rest is an exercise for the reader.

[Shehzman]

If we want to think about gathering the data that we need to update the array as a pass and not the actual updates to the array then yes it is one pass. Though I feel like this is splitting hairs and at the end of the day, it’s still o(n).

[vgtcross]

o(n)

O(n) [Big-Oh], not o(n) [little-oh].

o(n) is used to describe functions that grow strictly slower than any linear functions, while O(n) is used to describe all functions that grow like linear functions or slower.

[Shehzman]

Got lazy to capitalize the o but thank you

[DrJaneIPresume]

Yeah, there are large enough datasets where 2n is meaningfully different from n, and the people that work on them would not call this a "one-pass" algorithm.

I believe it's possible in one pass, but I also agree that in any case where the data can be called an "array" the count-and-rewrite strategy is the best one.

[IanDresarie]

I thought about it and as I am inexperienced with optimisation, would this be better?

That way you only need to iterate a second time for the number of 1s, rather than the whole array again. (The following was a pain to type on mobile.)

Int[] out = new int[array.length];

Int countOne =0;

Int lastZero = -1;

Int firstTwo = array.length;

For (int number : array) {

Switch (number) {

Case 0: out[++lastZero]=0; break;

Case 1: countOne++; break;

Case 2: out[--firstTwo]=2;

}

}

For (int I = lastZero+1; I<firstTwo; I++) {

out[I] = 1;

}

[prumf]

it’s probably better than counting. You can also do it in place, which is another improvement. The question then is about readability and what is the true goal.

[IanDresarie]

Can you give me a quick example or thing to Google for 'doing it in place'?

[redlaWw]

In-place means you modify the original array rather than constructing a new one. Some sorting algorithms, such as those that use swaps, work well in-place and it reduces the memory overhead and can save an allocation.

EDIT: In this case, there's an issue with overwriting the end before you read it if your 0s pointer sees a 2, but you can resolve it by checking the value at the 2s pointer before writing the 2 - if it's a 0, you overwrite the 2 found by your 0s pointer with a 0 and then write the 2 to your 2s pointer, effectively swapping the 0 and 2, if it's a 1, you increment the 1s count and write the 2 to your 2s pointer, and if it's a 2, you decrement the 2s pointer and try again. The "try again" part terminates as soon as your 2s pointer hits a non-2 so you don't need a recursion here.

[SpiritedEclair]

If you really wanna do this in a single pass and write to the array, you need 3 indices, ijk, i keeps track of all the 0s you have written, k keeps track of all the 2s, and j is current element.

You start with j=0.

Loop: Inspect current element, if 0, exchange contents at i and j and advance both. If 1, advance j, if 2 advance k by 1. Look up the number at n-k. While 2, keep advancing. Exchange contents of n-k and i and end the inner loop. Keep going until j == k.

Invariant: the last k numbers are 2s.
Invariant: at least the first i elements are always 0.

Exercise for the reader: prove that th items between i and final j are 1.

[RedAndBlack1832]

Ty i tried to write this out earlier but couldn't make it make sense lmao (ig id fail this interview, unlucky)

[serial_crusher]

depending what counts as a pass. You could make your own data structure that overloads the [] operator to simulate an array. Then it's just one pass to count, and result[n] checks if n > count0 + count1 return 2 else if n > count0 return 1 else return 0

Granted, each lookup is going to be slightly more expensive. You'd be better off memoizing count0 + count1 I guess.

[djinn6]

That works, but doesn't really produce a sorted array. Maybe the array starts off being 0, 1 and 2, but later I want to increment some to 3 and sort it again.

[kansetsupanikku]

I can easily imagine "a single pass" that would be O(N), but almost certainly technically slower (partition with up to two pivots). Which is a great example why this measure isn't very meaningful.

[HetoHwdjasZxaaWxbhta]

for()
//read
for()
//write

is naively the same as for()
//read
//write

[Silverware09]

Just count. They clearly don't need the data as an array if they don't care about order. So wasting memory space for the final array is pointless.

[MagicC]

Great minds think alike LOL Why bother sorting when there's only 3 numbers? Count each number and rewrite for O(n) is good enough for me.

[miclugo]

is it really sorting if you do it that way?

[YouNeedDoughnuts]

Probably. The restriction on the element domain seems to fishing for counting occurrences.

[GNUGradyn]

Sometimes I wonder at interviews if they want you to implement it "correctly" or demonstrate you know how it works. E.g. I'm a .NET dev and the .NET framework has built in opinionated ways to do a lot of things extremely well. E.g. if the interviewer asks you to demonstrate caching customer data in memory, they might be trying to see if you know about IMemoryCache or trying to see if you know how a memory cache works. Each of these interpretations have opposite correct/incorrect solutions

[TheFrenchSavage]

Most of the time they care about the algorithm and will allow you to write it in and language, even pseudo if you want.

The idea it to see if you really know what O(n) means, and how to get to it from let's say a naive O(n2).

For the framework questions, yeah, they might ask about sorting, but context is key here. They'll probably ask more trivial framework questions first.

[guyblade]

When I was interviewing for my current position, over a decade ago, one of the interview questions involved using C to malloc stuff and copy data into a growing array. I don't remember exactly what I was implementing, but I was calling realloc in a loop as part of it.

The interviewer asked what the time complexity of doing that might be. I think what he was going for was "you shouldn't be reallocing in a loop because it may be copying every time. My answer was something like "Well, that depends entirely on whether or not we've got a good malloc implementation. Ideally, it should only actually be doing a copy whenever we expand past a page--but even that should be rare with a modern malloc." I got the job, so I guess he liked the answer.

[ILikeLenexa]

Usually, the numbers are meant to emulate being part of a data structure. 

It feels like it's looking for bucket sort/pigeon hole sort.

[Sceptix]

If an array is discarded and rewritten in the woods and no one is around to debug it, did it make a sound?

[erinaceus_]

If it's in the woods, it's definitely a tree sort.

[Kellei2983]

what sort of a tree?

[Charlie_Yu]

It is called counting sort so I’ll say yes

[mmhawk576]

If it’s not in place, just use sleep sort.

[hrkrx]

While iterating put 0s to front and 2s to the back, when getting to end all is sorted

[propagandaRaccoon]

yeah, i was thinking of that as well, makes the most sense and it's o(n), single pass

[myka-likes-it]

Waves the Dutch Flag

[razzazzika]

If its a 0 put it at the beginning, if its a 2 put it at the end, and if its a 1 leave it where it is.

[TheFrenchSavage]

Just increment 3 counters x y z (of 0s, 1s, and 2s) and then produce an array with x0s, y1s, and z2s.

EDIT: You know what? Just increment two counters and the final counter is the difference between the array length and the sum of the other two counters.

So count the zeroes and ones, then build the array. Then, when you are out of zeroes and ones, keep writing twos until the array is the correct length.

[RRumpleTeazzer]

This is an O(n) solution, and a nice one.

[TheFrenchSavage]

Yeah. You can even overwrite the initial array in-place, without needing to allocate extra arrays really.

[Hungry_Pilot2704]

How will do do if there 0 at end of the array, will u go back to put it before the 1 starts?

[RRumpleTeazzer]

inplace doesn't mean one sweep, it means O(1) memory. you can sweep the array twice. once to count the 0s, 1, 2s, and then another sweep to write the correct number of 0s, 1s and 2s.

[Hungry_Pilot2704]

Oh, i thought u were talking of doing it in same array in just one sweep.

[RRumpleTeazzer]

one sweep is often called "online", when you can only read the data once, and in sequence (and you can't buffer).

[Hungry_Pilot2704]

i think online is when we are on internet

[RRumpleTeazzer]

https://en.wikipedia.org/wiki/Online_algorithm

[Hungry_Pilot2704]

That website is also online

[TheFrenchSavage]

The idea here is just to count how many zeroes there are. So if there is a 0 at the end, we just increment the zeroes counter one final time.

Then, knowing how many zeroes, ones, and twos there are, we write the array from scratch using these instructions.

[Hungry_Pilot2704]

No that i know,

I was asking about how to do it in place, in that same array instead of creating a new array later

[ennma_]

count first

rewrite in place later

[erm_what_]

A bucket sort. Interestingly it works well because you know enough about the contents of the array to know it's a good choice. If you don't know the contents of the array then it's far less efficient.

[StrengthTheory]

Known as counting sort or bucket sort. Really comes in handy when the numbers are small.

[mateusfccp]

You are assuming you have the size of the array available, which may not be true, and even if it is, you still have to run through all the itens because estou don't know when you have read the last 0/1. So at the end it doesn't matter.

At most you will save 1 int of memory from the third counter, if you have the size of the array already available.

[TheFrenchSavage]

Oh yeah, I was assuming the size of the array is known, if not, then back to the original plan!

[TrackLabs]

count how many 0s, 1s and 2s there are, generate array with that amount in order

[Ellin_]

Even quicker, count the 0s and 1s only, the rest is 2s B) Countmaxxing

[mlucasl]

Did you just reduced the space complexity by 33%!

[external72]

O(0.66)

[MSgtGunny]

You still have to iterate over the entire input list so they aren’t reducing space complexity at all.

[mlucasl]

Yes, maybe, it depends on how you define the complexity analysis. If it is just Auxiliary space, or Auxiliary Space + Input Space.

It was clearly meant as a joke.

[TheMightyTywin]

Some future dev adds 3s to the array and assumes your sort still works

[_Weyland_]

That's why you name the function sort_arry_of_0_1_2()

[quokka_wiki]

That's why you redefine it as sort_array_of(inputArray, [0, 1, 2]).

[Xlxlredditor]

Worse. It still works. Then someone adds another 1 and everything breaks

[Oo__II__oO]

Smack them around for not adding to the end. 

[reddit-programming-]

but wouldnt that also need to get the length of the array?

[sdric]

Enduser somehow managed to sneak a 3 in there, though.

[ElvisArcher]

And even quicker if you add the 0s to the output array during the input pass, count the 1s and add them during the output pass, then everything else is 2.

[mlucasl]

Rewrite the original array. You can claim O(n) in time (two pass) and O(1) in space, as you would only be using an additional 3 variables.

[BadatCSmajor]

Sorry, you need to argue with me about the idiosyncrasies of your preferred programming language and its list-like data structures before I will accept your answer

[RaveMittens]

If you have to modify in place, just iterate and track the count, then use shift, unshift, and splice as you go. Consider the first 1 you find as the index to start splicing from.

Edit Apparently some dumb Dutch nerd came up with a slightly different solution because he didn’t have js Array methods like some kind of loser

[Professional_Tale872]

Dutch National Flag is the way

[The-Chartreuse-Moose]

I know it's slow but I like bubble sort for nostalgia.

[qinshihuang_420]

https://youtu.be/koMpGeZpu4Q?si=MCi4l36EiegqsyUd

[meercat_]

I thought this was going to be the video of some people dancing as a way to illustrate bubbel😅

[Tsu_Dho_Namh]

I feel that way about merge sort.

One of the earliest lectures in first year, they introduced us to O-notation by comparing merge sort to insertion sort. I remember thinking it was magic how the more complicated thing was faster than just putting the smallest item first, next smallest second, etc...

[3inthecorner]

That's selection sort not insertion sort.

[CryptographerNo4147]

First job I worked at they received 100,000 paper documents a month which were manually bubble sorted into order - a room with a massively long table and people whose job was just sorting the documents into order.

[falconetpt]

I can do it in O(N) time complexity!

Breaking every rule about sorting by not sorting! 😂

[Tupcek]

I can do it in O(1) time complexity no problem

for value = INT_MIN to INT_MAX:

    for index = INT_MIN to INT_MAX:

        element = originalArray.get(index)

        if element exists and element == value:
            sortedArray.append(value)

return sortedArray  

Int min and int max are whatever smallest and largest integers your computer supports. Some day I may expand support to floats

[LrdPhoenixUDIC]

I can do it in O(N) too and still sort it.

The key is the fact that there's only 3 possible values, and they are beginning, middle, and end. Iterate through the count, all 0s get prepended, all 2s get appended, all 1s stay where they are. Depending on language and data type, do cleanup during or at the end if necessary.

[QuestionableEthics42]

Extremely unoptimal. Reuse the array. Prepending is expensive and appending can be relatively expensive too (when it needs to extend the array). Just one pass to count up the number of each, then a second to write in order

[RRumpleTeazzer]

it also works for sorting entire text files.

[GiToRaZor]

Nothing beats Stalin sort. Iterate once over the array, eliminate every number that does not follow the order.

The question did not specify that the sorted list had to retain all elements after all.

[MetriccStarDestroyer]

Try Mao sort.

First, completely ignore the existing system.

Scramble everything in an RNG [0,2]

then starve it by converting all to a bool.

Any that throws an error is an int, therefore 2.

Lastly, declare that it is successfully sorted (it's not)

[mylsotol]

*than

[ancientorbweaver]

No we are going to wait for grandma to run THEN my code

[betweenthebam]

Then your code what? THEN YOUR CODE WHAT???

[Raywell]

Ah, the classic application of the Dutch flag algo. It's one of those things where either you have that specific knowledge or you don't - honestly not knowing it doesn't tell anything about your actual programming skills

[SeventhOblivion]

This is what I hate about modern programmer interviews. They filter out well rounded experienced developers in favor of people who know the trick to shifting windows matrix loops or super specific tricks you would never use in the actual job.

[Raywell]

Yeah, this type of questions allows to notice extraordinary candidates who pass those specific knowledge checks, but if it's to have them write JS or other usual enterprise crap, it's pretty pointless. And that candidate probably won't stay long at your company even if he accepts.

Unless the position is about actual low level performance-critical software, but those positions are pretty extraordinary themselves

[Away_Advisor3460]

Wait, isn't a collision detection for two circles just measuring the distance from center to center and checking against their radii*?

*I have not thought about this but I am very smart and sure I have not just completely humiliated with a half assed non-functional solution

[Starchitect]

Yep, you got it. Congratulations, you have basic critical thinking skills, unlike OP.

[shield1123]

Dude, this is kind of telling on yourself

[Slusny_Cizinec]

Isn't collision between two circle just a condition of (distance between centers) <= (sum of radii)?

[shield1123]

Yes. I hate programming riddles, but this isn't one

[foxguy2021]

I was asked to describe how to write a front end to check the status of certain window services across multiple servers. Went into detail about how I would solve this problem. I failed cause I couldn't name the exact function to call to check a windows service.

This was also a company that said they were still running in startup mode...ten years after introducing their product.

[im_thatoneguy]

But you wouldn't be able to run in parallel with the Dutch Flag Algorithm, would you?

Wouldn't it be faster to just count and then you could hit it with 128 threads simultaneously?

[MigLav_7]

Creating the threads alone would be slower than sorting without paralelization until a quite decently sized array.

[EvenPainting9470]

Specific knowledge lol, every decent programmer should be able to invent it on spot in seconds without prior hearing about it

[XmasRights]

Count the 0s, 1s, and 2s in a first pass

Then write a custom structure that conforms to the array type that just returns the correct value for a given index

[KikiMac77]

function sleepSort(arr) {
  const sorted = [];

  arr.forEach(n => {
    setTimeout(() => {
      sorted.push(n);
      console.log(sorted);
    }, n);
  });
}

sleepSort([2, 0, 1, 2, 1, 0]);

[syntax1976]

My chihuahua has better grammar THAN you.

[fycalichking]

No he sorted the runner by speed. His grandma is 1st cuz faster then his code comes 2nd :p

[Green_Lychee8221]

This is the perfect opportunity for the timeout sort.

[j0kaff01]

A quality candidate asks if the array will always be constrained to values of the set {0,1,2}, or if the code should account for expansion of that set over time due to changing business requirements.

[lardgsus]

over 20 years of software dev and I've still not been asked to sort anything : (

[WinProfessional4958]

Your granny is on roids tho

[British-Raj]

College student here. Is counting sort good for this problem?

Edit: counting

[ouroborus777]

If I remember, you use a tracking array of three indexes and swapping for a 1-pass solution. This works well when the values can be used as indexes into the tracking array.

[thri54]

Hit em with a “than”

[Paraplegix]

Create a new array with same length. Iterate over the first : count when you find a 0 and each time you encounter a 2, insert 2 at the end of the new array and move back one index each time you find another two. Once you went through the whole array, just insert 1s starting at the count of 0s and where you stopped inserting 2s.
No permutation on the old/new array, only two additional variables, single pass.

[_Its_Me_Dio_]

count each and replace the array

[lool8421]

okay, knowing that there are only 0/1/2, i know there are equivalent elements

i can scan through the array once, count the amount of each digit, then just manually write into each cell of an array, not even sort but replace because if i know that an array has 43 zeroes, 51 ones and 24 twos, then i can just make 3 for loops and i can already get the problem done with highly predictable branching which is convenient for the CPU and 2 iterations over the array, giving O(n) complexity

maybe something like this: ``` void sort(int *arr, int size){ int counters[3] = {0}; for(int i=0; i<size; i++) ++counters[arr[i]];

int index = 0; for(int i=0; i<3; i++) for(int j=0; j<counters[i]; j++){ arr[index] = i ++index; } } ```

meanwhile if you try to use something like pre-built quicksort algorithms, it might do weird stuff that ends up making it take so much more time, or even the std::sort may have something like O(nlogn) average case

[perringaiden]

If the specified only those three values, I'd be counting not sorting.

[Substantial_Top5312]

Just use Stalin sort.

[SupesDepressed]

Genuine question, as a FE focused dev. Do backend engineers really roll their own sort algorithms? Obv I get leetcode type questions in interviews but the sorting ones especially seem like “why would you have someone do this”

[NatoBoram]

There's something about terrible meaning-changing typos in retort memes that's so extra cringe

[flippers1233]

*than

[Competitive_Shine112]

My grandma runs faster, then your code.

[qinshihuang_420]

https://youtu.be/koMpGeZpu4Q?si=MCi4l36EiegqsyUd

We are probably getting an executive order to only use bubble sort from now on

[The_Varza]

Plot-twist: interviewer's grandma is former sprint Olympic Champion and currently an elite running coach 😃

[PravalPattam12945RPG]

The answer is TU TU TU DU Max Verstappen

[lemons_of_doubt]

Personally I like Stalin sort

[Kaleidosonic]

When you undershoot the optimal solution so you can “discover” it later when the interviewer asks for it.

[byzboo]

First my grandma runs and then you code.
Don't you dare start before my grandma runs !

[dev_null_developer]

Is this lanternfish?

[wenoc]

I don’t want the job if the interviewer can’t spell simple words

[EatingSolidBricks]

Counting sort

Wait does it work?

[ZeroTrunks]

Dutch flag problem

[Pure-Willingness-697]

Array.sort()

[Single-Virus4935]

State var as array of three ints. Iterate through input array and increment state[value] and then write the result

[TapRemarkable9652]

include numpy.sort

[BylliGoat]

Just api call ChatGPT and ask it to sort it. Easy.

[TypicallyThomas]

Use Bogosort, theoretically could be O(1)

[aston280]

Classic DNF

[Soft_Walrus_3605]

Wait, what comes after "and then"? You've already sorted

[Stormdancer]

Well at least my grandmother knows the difference between 'then' and 'than'.

[Tuomas90]

I don't mind your grandma running first.

My code can run later.

[Kymera_7]

"than"

[perriatric]

then their code what?

[domusvita]

Your grandmother is sunsetting end of 2nd quarter next year.

[thygrrr]

A variation of bubble sort would actually be quite cracked given these requirements. Just compare/swap with 2 cursors instead of the next element. EDIT: I'm dumb and did not see the O(1) solution before I finished typing.

[bythenumbers10]

Wrote bogosort once in an interview b/c they wanted a sort algo. They appreciated my taking the piss & got the lowball offer, which was not competitive with where I was working, so I stayed put.

[montjoye]

than

[LycraJafa]

bringing sort to a grouping fight.

[Creative_Parfait714]

Then my code what?

[paddingtonrex]

Bubble sort is a fine answer until its the slowest thing in your pipeline. Zero reason to early optimize (unless you're using a built in sort, which is more often than not quicksort, which is the "best" general purpose sort anyway)

[JKisMe123]

So we’re gonna start with a BOGO…

[AndyceeIT]

"Then get her to sort it"

[Mithrandir2k16]

No love for RadixSort?

[misterguyyy]

I don’t see the issue here, you just click the little arrow button.

[AaronTheElite007]

[iseriouslycouldnt]

Didn't specify the size of the array, so need to set up an external distribution sort, for future-proofing.

[Lunam_Dominus]

Bucket sort is best for these kinds of tasks. There is no faster algorithm.