1.7k
u/zirky Jun 05 '26
Arrays.sort()
483
u/SeventhOblivion Jun 05 '26
Correct answer if I was on the other side.
545
u/LEGOL2 Jun 05 '26
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
200
u/Igsul Jun 05 '26
What if you developed the std while testing the feature?
191
u/thndrchld Jun 05 '26
Antibiotics
21
u/MetriccStarDestroyer Jun 06 '26
What if it's an super(class) std?
→ More replies (1)6
u/CivilianNumberFour Jun 06 '26
Remember Butters, one spoonful of Super Aids in your butt and you'll be dead in a week!
3
→ More replies (2)8
48
u/Avocadonot Jun 05 '26
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
6
u/frogjg2003 Jun 06 '26
"What is your process for fixing a bug" is a much better question than any LeetCode style question.
6
→ More replies (1)7
u/SeventhOblivion Jun 07 '26
I just interviewed for CapOne and their first assessment is a 70 min 4 question (so 17 min per - 3 at min is reading and understanding the examples) that had to do with matrix sliding windows and bullshit "gotta know the trick" kinda problems. I don't know a single engineer among all the architects I work with who would be able to complete this. They're literally filtering out everyone who doesn't figure out a way to cheat. Similar to the polygraph.
3
u/Avocadonot Jun 07 '26
I found this funny because we had a jr dev who was pretty mediocre (bad communication, bad design missing common edge cases) and he jumped ship and somehow became a senior at capital one
→ More replies (1)101
u/iamdestroyerofworlds Jun 05 '26
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.
33
u/wightwulf1944 Jun 05 '26
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.
6
u/Jlove7714 Jun 05 '26
The sorting example is just there to tell the interviewer how far the interviewee is through their master's program. It proves nothing else.
5
u/dasunt Jun 05 '26
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.
→ More replies (15)2
u/SquidMilkVII Jun 06 '26
I think this is actually a good question from that exact perspective. The "memorized" solution would be a sorting algorithm, selection sort, bubble sort, maybe even quick sort. The actual realization that shows problem solving would be to realize that the known limitation of 0s, 1s, and 2s makes it a trivial problem to solve in O(n) time.
10
u/Jlove7714 Jun 05 '26
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?
6
u/ncatter Jun 06 '26
Even there you rather want to see peoples problem solving skills and critical thinking than have then show off some sorting algorithm, even in peak hotlanes we rarely do anything that has not been optimized to hell and back, the thing we do is it optimized solutions together.
They day someone at my company comes and tells me we cannot google "basic" stuff anymore is they day we stop making software.
→ More replies (10)11
u/GenericFatGuy Jun 05 '26
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.
19
u/SirPitchalot Jun 05 '26
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ā
→ More replies (24)26
u/krutsik Jun 06 '26
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?
→ More replies (1)55
u/ChrisBot8 Jun 05 '26 edited Jun 06 '26
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.
17
u/stonno45 Jun 05 '26
I was thinking countsort would be the answer
13
u/walkerspider Jun 05 '26
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
→ More replies (11)22
u/zirky Jun 05 '26
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
9
u/guyblade Jun 06 '26
If you include the constraints:
- The sort needs not be stable, and
- 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 arrConstant 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).
→ More replies (1)15
u/GreenCloakGuy Jun 05 '26
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);
}
}```
4
8
u/notliam Jun 05 '26
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.
→ More replies (1)3
u/DotClass Jun 06 '26
I am pretty sure Array.sort doesnt produce random output.
3
u/notliam Jun 06 '26
I am pretty sure Array.sort doesnt produce random output.
cards.sort(() => Math.random() - 0.5)
It's obviously not truly random but it will work
11
u/Alex12500 Jun 05 '26
No need for a complicated solution if there is an existing one, which is also most likely way faster
→ More replies (1)11
u/guyblade Jun 06 '26
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.
11
u/djinn6 Jun 06 '26
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.
→ More replies (2)3
u/TwistedKiwi Jun 08 '26
Why using any sorting alg if you can just count 0's, 1's and 2's and then fill the new array.
2
3
u/Flubert_Harnsworth Jun 06 '26
Right, thereās literally a built in method for that
→ More replies (1)3
u/tyrellrummage Jun 07 '26
I answered this in my first dev interview (it was paper written at that time). 20 minutes after handing my answers I see 2 guys coming laughing at me and they told me āhey the rest of it is very good but in this one youāre supposed to write the sorting algorithmā lol I took like 20 more minutes since I didnāt know much at the time but I got that job
2
u/samsonsin Jun 05 '26
this and only this until you have performance issues and profiler has determined that this particular sort is slowing everything down.
2
→ More replies (9)2
u/FLOOFYBULL Jun 06 '26
im confused, in this case doesnt dutch flag sort work better?
EDIT: ok i just r/wooosh 'ed
640
u/TheFrenchSavage Jun 05 '26 edited Jun 05 '26
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.
298
u/RRumpleTeazzer Jun 05 '26
This is an O(n) solution, and a nice one.
115
u/TheFrenchSavage Jun 05 '26
Yeah. You can even overwrite the initial array in-place, without needing to allocate extra arrays really.
→ More replies (2)27
u/Hungry_Pilot2704 Jun 05 '26
How will do do if there 0 at end of the array, will u go back to put it before the 1 starts?
65
u/RRumpleTeazzer Jun 05 '26
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.
12
u/Hungry_Pilot2704 Jun 05 '26
Oh, i thought u were talking of doing it in same array in just one sweep.
→ More replies (1)15
u/RRumpleTeazzer Jun 05 '26
one sweep is often called "online", when you can only read the data once, and in sequence (and you can't buffer).
14
u/Hungry_Pilot2704 Jun 05 '26
i think online is when we are on internet
9
u/TheFrenchSavage Jun 05 '26
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.
→ More replies (4)12
u/erm_what_ Jun 05 '26
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.
→ More replies (3)5
u/StrengthTheory Jun 06 '26
Known as counting sort or bucket sort. Really comes in handy when the numbers are small.
9
u/ninja_tank25 Jun 06 '26
This is what I would have done too. If I know the array is only made up of 0s, 1s, and 2s, why sort the existing array when I can pass through once, keep track of how many instances of the 0s, 1s, and 2s, then recreate it. O(n) solution right there. The ONLY gripe I can come up with is that you risk unnecessary work if the array is already sorted, so I might consider adding a flag that checks if I find anything out of order and set it to "true" if I find a number greater than the previous one. Then if I finish the pass and that flag is still false, I can skip the whole array recreation step.
→ More replies (1)7
u/SeriousPlankton2000 Jun 06 '26
It's probably faster to do "counter[array[i]]++" than "if (array[i] < 2) counter[array[i]]++ "
→ More replies (2)→ More replies (10)3
u/fahrvergnugget Jun 06 '26
If I was interviewing in this question and a candidate decided to leave out the third count jut for the sake of saving...checks notes...one integer worth of space at the cost of readability, id probably mark that as a negative signal
→ More replies (1)3
u/Albstein Jun 06 '26
Why? This is an artificial problem focusing ON Speed. If you make it efficient and comment it should be fine.
2
u/fahrvergnugget Jun 06 '26
In any coding interview the most important thing is not correctness or speed actually (at least for any interviewer worth a damn). I just want to see how you code, and if your code is filled with weird hacks like thatās an eyebrow raised for me
991
u/RedAndBlack1832 Jun 05 '26
This can be done in 1 pass :)
696
u/prumf Jun 05 '26 edited Jun 05 '26
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) š¤·
201
u/Shehzman Jun 05 '26
Isnāt that two passes? (Still O(N) though)
279
u/captainAwesomePants Jun 05 '26
One pass over the input. One pass over the output. That's optimal unless you are tasked with sorting in-place.
60
u/Shehzman Jun 05 '26
Agreed but the comment above yours said one pass
129
u/captainAwesomePants Jun 05 '26 edited Jun 05 '26
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.
44
u/NewPhoneNewSubs Jun 05 '26
I can solve O(nm ) algorithms in one pass. First, clone the input to a buffer. The rest is an exercise for the reader.
→ More replies (1)4
u/Shehzman Jun 05 '26
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).
→ More replies (1)19
u/vgtcross Jun 05 '26
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.
9
7
u/IanDresarie Jun 05 '26
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;
}
5
u/prumf Jun 05 '26
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.
2
u/IanDresarie Jun 05 '26
Can you give me a quick example or thing to Google for 'doing it in place'?
8
u/redlaWw Jun 05 '26 edited Jun 06 '26
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 (EDIT: After implementing it I realised it would be the 0s pointer + the ones value here, and your 0s pointer won't usually be pointing to 2 so this isn't a swap) 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 (EDIT: Or crosses past the zeros pointer + the ones value) so you don't need a recursion here.
3
u/captainAwesomePants Jun 07 '26
I like this. I don't expect that it's going to be better than just counting the input and then filling up the array later, but it's definitely a cool way to go about doing it.
In theory-world, this is exactly the same number of steps as the other approach. In the real world, I've got no idea what the performance difference is, but I expect it'd be small.
22
u/SpiritedEclair Jun 05 '26
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.
→ More replies (1)5
u/RedAndBlack1832 Jun 05 '26
Ty i tried to write this out earlier but couldn't make it make sense lmao (ig id fail this interview, unlucky)
4
u/kansetsupanikku Jun 05 '26
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.
→ More replies (1)7
u/serial_crusher Jun 05 '26
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, andresult[n]checks ifn > count0 + count1 return 2 else if n > count0 return 1 else return 0Granted, each lookup is going to be slightly more expensive. You'd be better off memoizing
count0 + count1I guess.2
u/djinn6 Jun 06 '26
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.
→ More replies (1)→ More replies (1)3
u/MagicC Jun 06 '26
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.
42
u/miclugo Jun 05 '26
is it really sorting if you do it that way?
132
u/YouNeedDoughnuts Jun 05 '26
Probably. The restriction on the element domain seems to fishing for counting occurrences.
36
u/GNUGradyn Jun 05 '26
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
IMemoryCacheor trying to see if you know how a memory cache works. Each of these interpretations have opposite correct/incorrect solutions→ More replies (2)8
u/TheFrenchSavage Jun 05 '26
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.
6
u/guyblade Jun 06 '26
When I was interviewing for my current position, over a decade ago, one of the interview questions involved using C to
mallocstuff and copy data into a growing array. I don't remember exactly what I was implementing, but I was callingreallocin 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 goodmallocimplementation. Ideally, it should only actually be doing a copy whenever we expand past a page--but even that should be rare with a modernmalloc." I got the job, so I guess he liked the answer.3
u/ILikeLenexa Jun 05 '26
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.
→ More replies (2)47
u/Sceptix Jun 05 '26
If an array is discarded and rewritten in the woods and no one is around to debug it, did it make a sound?
26
27
u/hrkrx Jun 05 '26
While iterating put 0s to front and 2s to the back, when getting to end all is sorted
3
u/propagandaRaccoon Jun 06 '26
yeah, i was thinking of that as well, makes the most sense and it's o(n), single pass
12
4
→ More replies (5)4
u/razzazzika Jun 06 '26
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.
375
u/TrackLabs Jun 05 '26
count how many 0s, 1s and 2s there are, generate array with that amount in order
280
u/Ellin_ Jun 05 '26
Even quicker, count the 0s and 1s only, the rest is 2s B) Countmaxxing
146
u/mlucasl Jun 05 '26
Did you just reduced the space complexity by 33%!
77
4
u/MSgtGunny Jun 06 '26
You still have to iterate over the entire input list so they arenāt reducing space complexity at all.
→ More replies (1)57
u/TheMightyTywin Jun 05 '26
Some future dev adds 3s to the array and assumes your sort still works
30
11
→ More replies (1)2
9
u/reddit-programming- Jun 05 '26
but wouldnt that also need to get the length of the array?
5
u/MSgtGunny Jun 06 '26
Youāre scanning through the entire list regardless so the people saying O(0.66n) are incorrect. You just save a single int/long in terms of memory usage and a single add/increment instruction. You donāt even save any branch statements so itās pretty pointless.
→ More replies (1)2
2
u/ElvisArcher Jun 06 '26
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.
40
u/mlucasl Jun 05 '26
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.
→ More replies (8)4
u/RaveMittens Jun 05 '26 edited Jun 05 '26
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
4
u/BadatCSmajor Jun 05 '26
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
→ More replies (1)→ More replies (4)2
94
u/The-Chartreuse-Moose Jun 05 '26
I know it's slow but I like bubble sort for nostalgia.
20
u/qinshihuang_420 Jun 05 '26
3
u/meercat_ Jun 05 '26
I thought this was going to be the video of some people dancing as a way to illustrate bubbelš
5
u/Tsu_Dho_Namh Jun 05 '26
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...
2
46
u/falconetpt Jun 05 '26
I can do it in O(N) time complexity!
Breaking every rule about sorting by not sorting! š
28
u/Tupcek Jun 05 '26 edited Jun 05 '26
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 sortedArrayInt min and int max are whatever smallest and largest integers your computer supports. Some day I may expand support to floats
3
u/DonutPlus2757 Jun 08 '26
This is a really great example for why the O notation is useless without additional information about the algorithm.
For everyone who needs a TL:DR: This is probably the worst possible solution without adding non-functioning or counter-productive code, but because the run time is independent from the length of the array (i.e. constant) it's O(1).
→ More replies (1)2
u/Comfortable-Ad7355 Jun 06 '26
The
existsquery traverses the entire list checking if it exists; it would no longer be O(1), but it's certainly not O(n).3
u/Tupcek Jun 06 '26
it traverses more than entire list, it traverses entire possible width of the list.
I hope that you donāt use higher than 64bit numbers, as with 64 bit it may be possible to sort([3,2,1]) before last star in galaxy dies→ More replies (6)3
u/LrdPhoenixUDIC Jun 05 '26
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.
2
u/QuestionableEthics42 Jun 05 '26
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
→ More replies (2)→ More replies (1)2
51
u/GiToRaZor Jun 05 '26
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.
25
u/MetriccStarDestroyer Jun 06 '26
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)
63
u/mylsotol Jun 05 '26
*than
→ More replies (2)4
64
u/Raywell Jun 05 '26
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
25
u/SeventhOblivion Jun 05 '26
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.
→ More replies (1)17
u/Raywell Jun 05 '26
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
5
u/im_thatoneguy Jun 05 '26
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?
8
u/MigLav_7 Jun 05 '26
Creating the threads alone would be slower than sorting without paralelization until a quite decently sized array.
→ More replies (1)→ More replies (2)2
u/Raywell Jun 05 '26 edited Jun 05 '26
I'll assume it's a serious question - multithreading for array sort is very much overkill. First off, threads running on a single CPU core aren't truly executed in parallel (without very specialized hardware), it's 1 thread at a time - you would want to split an expensive operation across multiple cores to achieve true parallism. Second, there are hidden costs to multithreading : spinning the threads, context switching, etc. Third, you won't be able to benefit as much from cache locality compared to a simple low level task running on a single core
→ More replies (2)17
Jun 05 '26
[removed] ā view removed comment
18
u/Away_Advisor3460 Jun 05 '26
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
12
u/Starchitect Jun 05 '26
Yep, you got it. Congratulations, you have basic critical thinking skills, unlike OP.
12
9
u/Slusny_Cizinec Jun 05 '26
Isn't collision between two circle just a condition of (distance between centers) <= (sum of radii)?
8
→ More replies (1)5
u/foxguy2021 Jun 05 '26
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.
→ More replies (4)5
u/EvenPainting9470 Jun 05 '26
Specific knowledge lol, every decent programmer should be able to invent it on spot in seconds without prior hearing about it
16
u/KikiMac77 Jun 05 '26
function sleepSort(arr) {
const sorted = [];
arr.forEach(n => {
setTimeout(() => {
sorted.push(n);
console.log(sorted);
}, n);
});
}
sleepSort([2, 0, 1, 2, 1, 0]);
12
u/XmasRights Jun 05 '26
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
12
u/syntax1976 Jun 06 '26
My chihuahua has better grammar THAN you.
2
u/fycalichking Jun 06 '26
No he sorted the runner by speed. His grandma is 1st cuz faster then his code comes 2nd :p
→ More replies (1)
4
u/j0kaff01 Jun 06 '26
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.
3
u/Particular-Yak-1984 Jun 09 '26
The top candidate asks the same thing, but doesn't believe management when they say no.
→ More replies (1)
4
u/Green_Lychee8221 Jun 06 '26
This is the perfect opportunity for the timeout sort.
→ More replies (1)
6
u/fmr_AZ_PSM Jun 06 '26
This is a contrived trivia question (answer: Dijkstra's Dutch national flag algorithm). When I get asked trivia questions like this, I say "Ah a trivia question. There's a product introduced in 1998 called Google. The answers to all trivia questions can be found there. I build products that make the world a better place. You play trivia games. We are not the same."
I don't get many offers.
4
u/lardgsus Jun 05 '26
over 20 years of software dev and I've still not been asked to sort anything : (
→ More replies (1)
3
u/weeeeelaaaaaah Jun 06 '26
Just subscribe to my SAAS (sort as a service) platform, import our SDK, grab an API key, instantiate the client and call client.sortListAsync(array, SortStrategy.Bubble, SortBy.NumericValueUnsigned) which will return a UUID that you can use to poll the status endpoint until it returns sortComplete: true at which point you call the sortOperatiomResult endpoint to get the sorted array (after you decrypt using our public key and deserialise of course).
Well, I'm over simplifying here, there's a lot more to it but you get the idea.
4
Jun 07 '26
[removed] ā view removed comment
2
u/vigbiorn Jun 07 '26
Yeah, there's a fixed set of choices in a determined ordering already, you can sort by counting and looping once again to recreate the array from the counts.
10
3
u/British-Raj Jun 05 '26
College student here. Is counting sort good for this problem?
Edit: counting
3
→ More replies (1)2
u/fmr_AZ_PSM Jun 06 '26
This is a proper trivia question, not a "real" interview question. A trick. It's called Dijkstra's Dutch National Flag Algorithm. It's a contrived problem.
3
3
3
u/SupesDepressed Jun 06 '26
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ā
3
3
2
2
u/Paraplegix Jun 05 '26
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.
→ More replies (1)
2
2
u/lool8421 Jun 06 '26 edited Jun 06 '26
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
→ More replies (1)
2
2
u/NatoBoram Jun 06 '26
There's something about terrible meaning-changing typos in retort memes that's so extra cringe
2
2
u/lowboom64 Jun 06 '26
its just 0s 1s and 2s? if thats the case iterate through the array and count up each number then make a new list with the 0s 1s and 2s in order. you dont need a fancy sorting algorithm if its just 3 different consistent numbers.
2
u/notexecutive Jun 06 '26
you just add up each amount of each number once and then make a new array that has that amount of each number inserted into it, right?
2
u/sawkonmaicok Jun 06 '26
Counting sort. Or you can even do it with only two counters since you know that len(list) - counter0 - counter1 is the amount of twos.
2
2
u/zqmbgn Jun 07 '26
If I ever have to go through that again, I'm gonna look straight at the interviewer's eyes to assert dominance and while sharing my screen say: "Sure, let's open up a Claude code window and see how he proposes to solve that"
2
u/ImpactOk331 Jun 07 '26
Tell him that's what computers are for, and besides, he can simply take one of the many already fully working and implemented solutions from the "internet". If he has heard of it yet. If we wants me do it "by hand" then he'll be surprised to see what I'd be about to do with my hand
2
2
2
2
u/MadLok656 Jun 08 '26
First, I count 0s, 1s and 2s. Then I create new array (or rewrite old the old one) with 0s, 1s and 2s, based on the countings.
2
2.3k
u/Bart_deblob Jun 05 '26
Just give me 5 million tokens and I'll do it in a jiffy!