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!
Episode 9 - Sorting. Counting Sort.
00:00:02 - 00:05:11
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.