Have you ever been frustrated during interviews thinking that your interviewer expects you to have memorized a bunch of sorting algorithms you'd never need in real life?
In this episode of the podcast learn how to approach such situations. In performance critical systems you may have to implement an efficient sorting yourself. Learn how to beat the built-in algorithm in a few lines of code!
Transcript
Episode 9 - Sorting. Counting Sort.
00:00:02 - 00:05:11
welcome to the programming podcast. Here you can learn about computers in the brief and accessible way. I'm your host mean could get low folks today. We're going to talk about sorting. We primarily focus on two different sub topics. We're GONNA talk about. What should we do if we have to sort a collection during a calling interview and whether we should implement the sorting algorithm ourselves if the task that you're sewing kits work requires a collection to be sorted in some order? So I'm giving these questions very frequently and I wanted to address both of them. I talked with whether we should implement the sorting algorithm ourselves or use. The one that is already provided by the Standard Library of the language that using or even built into the language so the short answer of this will not death starring cowards and up comes with the language it is definitely very well tested it has been tested by a lot of people like probably millions of people in hundreds of millions of programs and on top of that is very efficient. It's very unlikely for you to be able to achieve higher level of patients so a couple of years ago actually many years ago now maybe over ten years ago. I wrote a book post comparing different sorting Algorithms javascript. Our provide a link to this blog post but in general. My idea was to compare how well they're performing only alerts collection with random numbers. I also compare them to the built in sorting algorithm in V8. So what's turnout was that? V Eight was less performance compared to my customer implementation of heap sort and quick sort and that was absolutely surprising for me back then. I believe I was still in college. And I got a comment on my blog from one of the engineers working on V eight or on Chromium Batman like. You can't imagine how excited I was. I got some attention from the person from one of the people who are working on the tool sets that I'm using daily so his explanation. Was that my sorting. Algorithms are faster because they're unstable compared to V8's algorithm which back then was table. And since bride I guess recently is by standards. That's the javascript. Sorting Algorithm in arid prostrated sort is supposed to be stable was briefly talk about stability of sorting. Algorithm. In fact it is a very common situation that you would want rely on a stable algorithm. You mentioned that you have a collection of numbers and you have duplicates of these numbers. A stable sorting algorithm would not change the places would not swap any of the duplicates and this is very important especially when you have to sort e collection based on two different criteria now for numbers. It doesn't seem like a big deal because basically the numbers there they represent exactly the same entity in memory but if you have an object into I won't source of this object by an idea and try to ascertain by the first name or the people if this represents a person then you want to rely on a stable surgeon. Coward him even though. My article shown that a quick sort customer implementation of quick sorting. Javascript was more performance. Compared to the built-in are adults. Prostitutes sort algorithm. I DIDN'T TAKE INTO CONSIDERATION. And this is something that you should definitely consider when you're solving a problem so yes you may know a lot of certain algorithms but very rare. You have to implement one yourself. This shouldn't stop you from learning about sorting though because learning sorting algorithm would provide your huge level of insights into how it can solve other problems subset of the implementation of our it. There are many examples for this but probably the most popular ones are just merging two sorted a race. This is part of March. Cert- won't understand heaps. Well he's sort is good motivation for this. If you understand house he's or works. You'd have understanding as well of the heap data structure. We discussed already quick. Select few episodes back so quick. Select is an algorithm which uses the partitioning implementation from quick sort. Is he how by learning these three different algorithms. We're getting higher level of insight. We we know how to solve specific set of problems of course working but also we can people just implementation and go to something completely different often when we talk about algorithms people think of sorting out say this probably happens because the most popular computer sounds algorithm cerebral sorting.
00:05:12 - 00:10:08
They're also very popular interview with Barack Obama. Wear I believe that was Google where someone asks him. What is the most efficient way to sort one million sixty four bit injures and Barack Obama said out probably see that bubble sort is not the right way to go? Sorting is definitely popular. But this definitely doesn't include all the algorithm sold there. There are algorithms about crafts about threes searching Algorithms and so on and so forth. I guess because of this perception. Most people associates the coding interviews on white boards with just expecting the interview to have a bunch of algorithms and just write them down on the board. That's not the case during a according to interview. The interviewer is usually trying to check a couple of things. First of all whether you have a good technical knowledge whether we can evaluate the pros and cons of different approaches interviewer. Also want to check the weather. You can work in a team. That is very important if you have a problem. You shouldn't get a solution right away. You should discuss different alternatives with interviewer because some new things may show up for example. You can ask whether to collections in memory or not. You can ask if the interviewer Jeff sess like sort. This number of this list of numbers obviously does not going to be the question. But if that's the question you should ask well this list of numbers. It includes only integer or those include decimal numbers also chose whether you have good leadership skills because leadership can be demonstrated not only during situational questions when you are solving a problem. It is very clear whether you have some leadership skills just by considering different corner. Cases are taking initiative in order to implement a solution that you're aware of or just asking cobalt corner cases. That's the interviewer might have not given information about Eve however interview ask you. I wanted to implement quick -sorts right now in the next five minutes. You should pro- believe that's not the Best Company for you. I already mentioned that probably would not want to implement eastern cowards. Yourself if you have a problem to sort a couple of hint teachers or a couple of objects by a particular field right wherever there are some particular cases of when using e custom sorting algorithm must be a better solution here. You should understand that on average a sorting algorithm which uses comparison of the individual atoms. It cannot be more performance than all and log in. If you're not familiar with the big orientation I have left a couple of links in the description of episodes if you are barely familiar with it or you want to know a little bit more about it or just get an intuition you can think of big of n s performing an iteration over collection from one like an elements and performing some fast action. If we talk about and square this pretty much having two nested loops where for each iteration of the first loop were performing and ration- domestic looping said and for Logan well we were just performing Logan operation. It is very important that the sorting algorithm cannot be faster than and Logan. If we're performing comparisons so can we get faster without comparisons. There is a good question and in some cases. Yes we can't. If our data types that we want to sort the aligned to specific to specific requirements we can achieve much higher level efficient and this could be useful not only in our day-to-day practice but also during echoing interview. So here is a use case for implementing sorting Algorithm. Yourself if the reviewer is looking for a leaner solution instead of an logan so they're looking for a fast solution of a problem that involves searching elements. You can ask them to give you more details about the type of the elements in this correction. If there are only integer than here this you can use the algorithm counting sort. We're going to discuss counting sort of it. I have also left link description India episodes if they tell you that the decimals that issued sort but they're uniformly distributed. Well you can use buckets hurt. There are a couple of different hours which allows you to go faster which allows you to be faster ten and log in and you should be familiar with them as well. If you're looking for a very performance solution over a specific data type then well go for it of course claim or if you're operating covers more collections probably doesn't really matter which sorting.
00:10:08 - 00:13:19
Calverton you're taking advantage if so keep your your school realistic and clean and stick to the default implementation in the language that you're using if however you're working on a very performance critical system. You should consider one of these leaner sorting algorithms such as counting sort and bucket. Start talking about counting sorts. How does this work as you can imagine this related to counting numbers so if we have the collection? Let's see zero one one two. We just already sorted right now. We first started the algorithm by counting how many occurrences of individual elements we have so we have one zero. We have two times one and we have one time. To this way we can put an array and in disarray. We can in court for each index. How many numbers smaller than the element? On this index we have so for example. The first index is going to zero. Do we have any elements smaller than zero here. No we don't have any elements zero so in the first element of this array. We just put zero after we go to the index. One we count. How many atoms we have that. There are smaller than what what we do in. This particular case is count zero so yeah curious. We have one adamant more than one when to. We're going to count both zero and the two elements which are equal to one. Which means that here. We have three elements that are smaller than two and later than based on having this kind of index by having this array which includes how many elements we have more than the elementary side England. Particular in this we can return Anura which based on this knowledge creates assorted collection. I have a link to this algorithm as you can see in the linguistics. Nothing to complicate it. In this result we already discussed counting. Sort which is a very efficient algorithm for sort sorting positive integer. 's or it could be either even negative but we may have to perform specific transformation over them. We also discussed whether we should implement a sorting algorithm ourself when we have to sorta collection or take advantage of the one that is already provided by the platform and yes. Yasser is probably. We shouldn't implements ourself also discuss how can approach according to review and why the whiteboard interviews are actually providing some very important indicator for interviews. Make sure that you provide your interviewer wits a perspective for your technical knowledge for your teamwork as well for your leadership skills by just asking questions around the problem that you need to solve until next time bye bye. Learn about the episode's you can pull milk twitter at Ham. That is the resources and recordings is available at podcast dot M. dot com. Thanks for listening.