Want to give it a shot?? Sign up with us to make sure your upcoming interviews are the best they can be by practicing with our experienced engineers. interviewing.io/signup?.com&
how to be a programmer - step 1 - learn most efficient sorting algorithm step 2 - learn most efficient tree traversing algorithm step 3 - using knowledge from previous steps write some spring rest api with react front-end
Lol, that's how things are nowadays, building a real-world application is way too much away from learning sorting algorithms. These all companies ask shits on an interview
You can read into step 3 without any bigger knoledge. I think the actual point was, the woman did not know the partial quicksort algorithm, but was able to implement it with minor help. This shows that if she had a rather complex problem, she could solve it by her own/talking about work with the other employees and this would make her valuable.
If you don't know data structures and related algorithms and complexities, there is no way you'll be able to write efficient, scalable and good quality code.
Interviewer does a good job of not intimidating the interviewee. I usually get so nervous but if my interviewers were like this it would be so much more comfortable
Interviewer: Can you find me the n'th smallest element in this unsorted array Me: Sorts the array Interviewer: I said unsorted array Me: I don't want to work for this company
Usually these types of problems are solved by heaps. Just build a maxheap of size K and take out the top element which is minimum kth. Time complexity is N * log(k).
8:15 in, the interviewer was on to an edge issue, but plugged the wrong numbers in to create the issue. By preloading min and min2 with the first and second variables and just using < comparisons we can end up in a situation where the first number in the array could get loaded twice (Into min and min2). Using an input of (1, 2, 3, 4), we preload '1' into min. We preload '2' into min2. We then run through the array and we do our first comparison, For arr[0], Is 1 < 1 (arr[0] VS preloaded 1)? No, so we jump to the else if statement. Else If, is 1 < 2 (arr[0] VS preloaded 2)? Yes min2 = 1. We now have a 1 in both min and min2, and no other numbers are going to be lower than either, so they will not be replaced. We will then return a 'second lowest' of 1, which is incorrect. Great overall though.
another way would be to just add in another condition to ensure current value is greater than min but lesser than min2 . "else if(arr[i] < min2 && arr[i] > min)"
Shit like this is why I'm a manager, not a technical specialist. Even though I could solve these things, I wouldn't put up with shit like this. Also, I have a huge problem with authority and people testing and judging me or telling me what to do. I get an almost visceral fight or flight response. Glad I'm paid to lead.
@@seigemain Nope, I have never worked as a technical specialist and never worked myself up. The concept of working yourself up is fake news that is being told to worker drones. Do you think any rich person has ever worked a day of hard labour in their life? Trump is an imbecile and the president of the US. He isn't even a good business man. He's just rich. You think multi-millionaires got rich because they worked so hard? You can become a top level manager without any technical expertise. As a manager, you aren't concerned with technical labour, you are paid to make decisions and if your team messes up you blame the losers working for you. Making less than 200k for a job significantly harder than my own? No thanks. You start as a manager and stay in that class. Much easier. The only reason to "work yourself up" is if you need it to get a better understanding of whom to hire and how much to pay them to get the most out of them. I never needed any experience to do management and think it's easy. I never worked longer than 30h/week, just pretended, and make significantly more than most other people. I know that the higher ups have an even better labour/income ratio. Also, please don't think I'm sounding harsh because I'm looking down on engineers and real workers, I consider them far more important than myself, just realize that you are being exploited and that all that "work yourself up" bullshit is a capitalist scam. I'm good at what I'm doing, which is leading technical staff to deliver large scale IT projects in accordance to specifications handed down by some hapless manager above me. The only programming I ever did was at university and I was bad at it. I get paid a lot in a senior position at an industry leading company. I never worked as a developer, I never worked as a product manager, I never worked as anything technical. My job doesn't require it. I need to understand what people are capable of and by when they can approximately accomplish which task. I also need to understand what resources they need to get it done. I also need to know how to do PowerPoint presentations. If you want to be a relativelh rich manager, become a relatively rich manager. Being a worker drone is unlikely to turn you into one. Being a top manager and bringing home cash requires luck and connections. The only you will ever need actual skills is when you found your own company and are the tech lead. Which is also the only way you will ever get adequate compensation reflecting the value of your work.
I feel like the questions are not that hard but the streess builds up because you are worried about not getting the job if you fail to impress the interviewer. Maybe making the environment stressful is part of the test as well to see how you comprehend problems during stressful situations.
What is this? How is this scalable? Just use a priority_queue: int nThSmallest(int n, const vector& myVec) { priority_queue myQueue; for (int i{}; i < myVec.size(); i++) { myQueue.push(myVec[i]); } int res; while (n--) { res = myQueue.top(); myQueue.pop(); } return res; }
Maintain an m sized max heap, go through the array,for each num, put it into the heap, then pop one out. The top element of the heap is always the kth smallest of the traversed array.
@@cartersherman925 I don't understand why it's k log n. Thinking about the max size, it seems like it's O(n log k) because insertion into k-sized heap is log of the total size of the array, but you still have to do the linear search through n elements of the total array. Edit: "log of the total number of nodes", not total size of the array
The question was like Quick Sort (Even better, cause you just process one part of array). You were supposed to stop in between when you got the right element (When you choose the right element as pivot). 13:35
@@MrMakemusicmike It has an average of O(nlogn) but it has a worst case of O(n^2) if the input array is sorted in a way that the maximum is always chosen as the pivot.
I don't think this is a real interview. It says in the fine print under the video that "interviewing.io offers senior engineers free anonymous technical interview practice with engineers from Facebook, Google, and more" I only watched the first 15 minutes, but this also seems a little too easy (and informal with the interviewer eating）to be a real Google interview
import random def kthSmallest(l, k): start = 0 cur = l[random.randint(0, len(l)-1)] small = [] large = [] for i in range(len(l)): if l[i] < cur: start += 1 small.append(l[i]) else: large.append(l[i]) if start < k: return kthSmallest(large, k - start) elif start > k: return kthSmallest(small, k) else: return cur I was doing it without the random numbers and was running into issues where the list was in ascending order and it was no longer splitting the subarray. great interviewer. Interviewing it hard not only when it comes to reading other people's code but also when there is something wrong and you either notice it or don't notice and you need to gently nudge them in the right direction while being tactful in your approach.
for the nth smallest you can do a quicksort where you stop considering half of the remaining array at each point, basically sorting only the nth position. O(n) time
He's helping her out so much, even by saying "mhm", "yes", "sounds good". When I had similar interviews over the phone I got none of that unfortunately.
I've had 5-10 interviews a day for a few months for all kinds of companies. Architects and engieers have all kinds of interview styles. People eating on the phone is not crazy at all.
If that were true then you would have had 450 interviews over the last two months. That makes no sense. Are you exclusively applying for jobs for which you are not qualified?
@@potatolord7319 also "all kinds of companies" would also imply he isn't working for any given company. If he were working as a head hunter then calling his correspondance interviews would be a stretch.
Didn't watch their solution for finding the nth smallest integer in an array, but I managed to come up with one after the interviewer gave his hint. Basically you look at index n-1 and count the # of integers in the array less than the n-1th element. If the count equals n-1, then return the n-1th element. Otherwise, put the n-1th element into the index which is equal to the count (the index where it would be in a sorted array), and put the element that is already there into the n-1th index. The two elements are swapped. Then repeat the process until the base case is reached. I implemented this in racket and it worked. It's probably not close to the best, but it works.
I'm looking to hire the next big programmer, and man, does your algorithm ever get me excited about your genius. How does $550K/yr at Facebook sound? >joking
OBVIOUSLY this is the wrong way to go about this problem. It’s *very* clearly: int num1 = 1; int num2 = 2: int num3 = 3: int num4 = 4; int num5 = 5; int num6 = 6; int num = num1 + num2 + num3 + num4 + num5 + num6; System.out.println(num); As you can see, your code will now be completely readable and run *super* fast.
If you have done this exact challenge before and know how to solve it, then you could call it easy (becasue everything is easy by that logic) but if you haven't done this exact challenge it is hard to answer up front. But she seems to have been well prepared or else she would have become stuck.
I haven't done any programming problems like this. But after he asks, I paused the video and spent 10~15 minutes to write the code for it. The way I did it was different from her but I think I reduced the runtime down to n with my code. So I would call the problem easy... for me at least.
Been programming for 18 years, video games for 10. Have yet to need an O(n) sort, most cases are negligible. Sorting algorithms seem to mainly come up in interviews, and are used seemingly infrequently in my field. For that reason, I don't really like interviews like this because it really just means you have to go back, and study all your sorting algorithms again. To each their own I guess, I'm sure Google has many cases for optimized sorting, but if someone fully understands algorithm complexity I wouldn't stop them on this.
Jacob Raffe while I agree, I think he meant that an n log n solution is acceptable in many realistic cases. Sure, if you’re working with a ton of data, go for a non-comparison based O(n) solution. However, for every day tasks/code that won’t be running on tons of data, i think it can be seen as overkill. I’m fairly certain that most standard libraries use a sort of randomized quicksort in their sorting algorithms which yields the n log n solution. (Difference is much more negligible than the brute n^2 algo).
I suspect Google is trying to judge how quickly and fully the candidates can grasp new concepts rather than how much they can remember from their school or previous job. For that they need to talk about things it's unlikely the candidate has come across before.
@@TheHeadlets +scott5146 +Jon Miller +Jacob Raffe I'm not disagreeing with any of you. @Jon Miller hit it right on the nose on what I was saying. I think there's merit in saying they're testing their ability to adapt to new problems. However, I think having a recollection of sorting algorithms in the back of your head will make that problem incredibly easier. So based on that idea, I would like to see an interview that's more real world. I could be bias however, in the game industry we will tend to give you more problems that are more applicable to what we're working on.
@@bentky2528 You're exactly right, that's why a good interviewer will realize when a candidate simply knew the answer from memory, and move in a different direction to actually test the ability to adapt.
@@bouggyman180 It is. If the item at index 0 is already set at the min. It makes no sense to compare it to itself, thus it's better to start the for loop at index 1, where it makes sense to compare the min (item at index 0) with the second item.
Here is my approach using python def min(arr, n): for i in range(len(arr)): if i < n and arr[i] > arr[n-1]: arr[i], arr[n-1] = arr[n-1], arr[i] elif i >= n and arr[i] < arr[n-1]: arr[i], arr[n-1] = arr[n-1], arr[i] return arr[n-1]
Partitioning takes n operations. Then you recurse on one side of the pivot, and the expected size of the partition you recurse into is 1/2 * n so the recursive step takes 1/2 * n operations. The expected size of the next partition is 1/2 * 1/2 * n. And so on. And so the sum of all these is n + 1/2 n + 1/4 n + 1/8 n + ... which is a geometric sum that converges to 2n.
I used an ArrayList for this solution and I think it's more easier to make it with that. Here's my solution: public static int minAtN(ArrayList arr, int n) { for (int i = 0; i < n - 1; i++) arr.remove(getMin(arr)); return getMin(arr); } public static Integer getMin(ArrayList arr) { Integer min = arr.get(0); for (Integer i : arr) if (i < min) min = i; return min; } I used 2 methods because it's more easier to work like that. I think that she should've used the first method that she made a helper method for the nth smallest number method so it'll be more organized and easier to solve. She made it complicated when she could make it easier. Also I tried to do it with an array: public static int minAtN(int[] arr, int n) { int m = min(arr); if (n == 1) return m; int[] arr2 = new int[arr.length-1]; int j = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] > m) { arr2[j] = arr[i]; j++; } } return minAtN(arr2, n-1); } public static int min(int[] arr) { int m = arr[0]; for (int i = 0; i < arr.length; i++) if (arr[i] < m) m = arr[i]; return m; }
during the whole swap thing, around 30:00 , Her elements won't be swapped as she says. She is comparing the first element of the array with every other, since she doesn't update index, she only updates i. I don't get it. So only 2 will be at the right place and not 10.
This algorithm is known as Quickselect: en.wikipedia.org/wiki/Quickselect You can also do it in guaranteed n log k time using a min heap (PriorityQueue). Just add all of the numbers to the heap, and then pop off a number every time the size of the heap > k. Obviously this takes more space than Quickselect.
At 8:06, for people that want to use this as a template to find the smallest digit, if the first 2 digits happen to be sorted, then this code would not work. If the first 2 digits is in fact sorted, all you have to do is change int min2 = arr[1] to arr[0] and int min = arr[0] to arr[1].
I think we can do insertion sort for first m element. time complexity O(n*m) def get_m_smallest(arr, m): for i in range(0,m): find_small(arr,i) return arr def find_small(arr, index): pivot = arr[index] small_index = index for i in range(index+1, len(arr)): if arr[i] < pivot: pivot = arr[i] small_index = i arr[index], arr[small_index] = arr[small_index], arr[index]
You could do a Radix sort of the array--which is O(nk) where n is the number of elements in the array and k is the number of digits in the integers you are sorting. Where k is small this will have better performance than presorting and then selecting which is O(nlogn) for an unsorted array.
this was my instinct. I paused the code and wrote the solution real quick, and felt so cool. then I got butt hurt when he proposed the sub-array method, which I think is O(n*log(k)). anyway, your comment gave me solace, friend. I need to watch the video again to really comprehend the approach fully.
I was doing this in C++, and I think I may have found a small improvement to the classic sort-all and select strategy. Please critique if you have any thoughts also. general principle: 1.) corner cases when kvector.size() return -1 because illegal k value[ time complexity should be constant] 2.) from ind0 to and including k, sort the subarray with quicksort,[quicksort time complexity with the subarray size.] 3.) make that ind(k) as candidate min 4.) iterate from ind(k+1) until the end and check if the looped vector value is smaller than candidate min,[need to check rest of the array] 5.) if you find smaller than candidate min, make a binary search into the already sorted subarray on the lefthandside of the array, and then you need to insert that new candidate min into the index indicated by binary search. (this was a little tricky in C++ because the default binary search sucks and I just used lower_bound I think.). This can give bad memory performance at least in C++ because if you insert into the middle then vectors have to shift the elements forward I think... 6.)return the candidate min. 7.) probably it will not give a huge boost in performance, but something that I thought about...???
hmm... I may have made some off-by-one error in that description because I used iterators mainly for the sort subarray and lower_bound, but that was still my general principle. I also had it so that k=1 smallest is a separate special case where I just find the minimum, and general principle starts for the k=2
First question is so easy. I can think of couple different ways to sort the array. But I will chose insertion sort because the length of the array is very small. And you can also apply ADT something like a heap to sort the array and whenever you need the min value then you just extract the min node and trickle down again do the shifting and swapping jobs.
Wow. So you just do this and internet happens?!? I can imagine that there are thousands of Googlers just hammering at their keyboards finding those mth indexes day in and day out, sweat pouring off their brows as they fight to keep the proper ads served to the appropriate targets. I still watched the entire thing, though.
Just like the entire world is hammering away at 'solve x for ...' or figuring out the lengths of certain arms inside a figure.... right? You barely ever get directly tested for the skills you're going to be putting to use in everyday worklife tbh - I'm trying to illustrate that with a mediocre highschool example :P
There is a small mistake at 31:30 because you guys are not updating the index value, if you want 10 to keep shifting rightwards then you need to change the index. (Though alternative solution might exist). So in this case you won't get the predicted output.
Why don't use a priority queue bounded to size m? Every enqueue and dequeue would take O(log m), but since m is fixed that means that O(log m) is O(1) with respect to the length of the array of numbers. So we have an procedure that is O(n) in time and O(1) in space, where n is the length of `arr`.
built in priority_que (c++, or java), specifically min heap, pop k smallest times. prob < 7 lines of code. whenever you are finding the k smallest or k biggest or anything regarding biggest/smallest, min/max heaps are your bff fyi
For anyone who wants to cut to the chase the answer is: a binary heap, which is O(nlogk) time with a storage requirement of O(k) time. (In the interview he uses m, but k is proper.) Some might think Quickselect ( en.wikipedia.org/wiki/Quickselect ) would be ideal, with an average of O(n) time, but in real world benchmarks a binary heap is both faster and uses less memory. This is due to quickselect using more ram (which is often slower than raw number crunching) and having a worse case time of O(n^2). So if you thought heap, yes, your intention did not mislead you.
I haven't done java, so I did in in python, it seems correct: def nth_smallest(arr, n): if len(arr) == 1: return arr[0] target = arr[len(arr)//2] small = [] big = [] for i in arr: if i < target: small.append(i) elif i > target: big.append(i) if len(small) == n - 1: return target if len(small) >= n: return nth_smallest(small, n) return nth_smallest(big, n - len(small))
Didn't hear any space constraints at the beginning so: What about make a new array of size max(arr), iterate through arr and mark each i of new array corresponding to values in arr, then iterate through new array counting marked indices to find mth marked index. This does break down in time if there are arbitrarily large numbers in arr though
I wouldn't have had this thought without watching, but at 5:04 when the interview asks "is there a faster way we could do it" you could probably make the search multi-threaded by splitting an array and giving each thread a piece of the array to search.
Unfortunately, it is still possible to hit a data sequence which will result in (n + n - 1 + n - 2 ...) complexity, due to the problem of pivot selection. Only in case of the positive scenario array will be divided by half and algoruthm will result in (n + n / 2...) complexity.
I think a better interview technique would be to have some written code and ask the candidate to explain what that code does. Anxiety can get in the way of technical interview which means a lot of very good experienced engineers slip through the net. When I interview people I give them some code and we have a chat about it and that works out great.
Not many people think like you. There is so much ego in asking algorithms questions.Many engineers think they are above everything, and ask heavy mathematical and algorithms question. It's so stupid.
In reality, this is the type of code base you want to work with: concise, generic, using standards. Only try to be smart when you know youre bottlenecked by a specific function.
I would have chosen M as my pivot point. Worst case is everything is already sorted (ascending or descending) or if you keep randomly choosing the next smallest or largest value in the array. You can mitigate one of those bad cases. If the array is sorted, ascending then you only have to loop through N elements. That is the best case. If you choose index 0 you must loop through multiple times to get to M in a sorted, ascending array.
I'm not a native english speaker, and I found that the audio over the phone is not clear enough, worse than how we hear a voice over a standard youtube video. Is there any solution to tackle this issue for phone interview ?
I'm sorry for didn't explain it clearly, but my issue regarding the voice clarity is not just limited for this video, but also based on my real experience when I was being interviewed by Google over the phone.
@@Illu07 thanks for the advise. They indeed was offering me a choice to do the interview over phone call or Google-Hangouts. Hopefully the voice can be clearer over the Hangouts.
been in your shoes...my advice...start listening English only radio, tv, etc..no captions!...what you have is an untrained hearing due the diffs between your native language and English...as soon as your hearing get used to the words (and possible acoustic variations) you will have no issue at all doing a phone interview..
I have a good friend who works at google right out of college. This was not how he got the job. He told me that there was a hiring event and he just showed up, they interviewed him on the spot. They asked him what his major was, and what he wanted to do. The odd thing he majored in Bio and wanted to go to med school, but google offered him a job for the summer and ended up. He tells me its nothing like they make it out. I think he forgot about med school.
5:27 This is a really petty thing to bring up but the loop is starting at i=0 when the value stored is already i at index 0 of the array. That's a redundant check, use i=1.
Yeah I think that would be efficient. Build the heap from array, logn. Then, to find n-th order you would pop n times and heapify each time ... thus, an n*log(q) solution where q is the size of array and n is number of times to pop
@@BorisMediaProds Heap construction is O(n) on average, not O(logn). Total runtime would be O(n + mlogn). When m < arr.size()/2, a min heap can be used. Otherwise, a max heap is favored so the amount of times you pop the heap is minimized.
@@BorisMediaProds Worst case is also O(n). You're thinking about inserting each node iteratively. The optimal heap construction takes an array as input and swaps references. Look it up, it is O(n) even in worst case.
5:05is there any faster way you can do it? actually yes. She can make a var called size of the array and use it in the for loop. That way we do have to use .length() method each time in the for loop.
@@alekseiduleba9508 I don't get why you need to know any of this by heart if you can just google it. It's not like you need to find the best sorting algorithm ten times a day. And if you eventually really need to you will learn it at work.
She could of skipped one iteration in the first function since it doesn’t make any sense to check if arr[0] < arr[0]...I don’t know why that frustrated me so much
The whole time im thinking, why not just use a queue? Every time u find a smaller value than the current min, push it into the queue. If the queue size > m, poll. At the end the peek of the queue would be ur answer.
Had a few phone interviews with FAANG companies and above, the interviewers were never this helpful... If I didn't train myself to write bugless code, I would've failed them even if my algorithms were optimal
If this were a C++ test the solution would be trivial: int order_statistic(std::vectior arr, int k) { std::nth_element(std::being(arr),std::begin(arr)+k,std::end(arr)); return arr[k]; }
Spent 10min of the video screaming "use the sort function that comes with java and you can make the function a twoliner" and at 11:08 she explained it. 10/10 satisfaction
Question: coming from someone with zero knowledge of coding, where does this code come from? Why or how does it do what it does? Is there code underneath? If so, where does *that* code come from? At what point are 0s and 1s turned into code?
The code is written in a high level language, such as java. Then it is compiled, into machine code. Machine code is a set of instructions that ultimately are processed by the cpu.
To state it simply, the Java compiler will turn your code into that (well first into JVM byte code, but that's too much for now). 0's and 1's go into transistors and logic gates which are what processors and elements of computing are comprised of. If you put enough logic gates together and input into them (in the form of bits, 0's and 1's (essentially true and false), you can make stuff that does calculations. I'd recommend reading up on boolean algebra and then learning about logic gates, then how you can make things like multiplexers, encoders, decoders, etc. These things can then make elements of a processor like a register and eventually a register file, etc. There are many more components, but essentially the 0's and 1's get turned into code by people manipulating them by saying if you put a 0 here and 1 here, this thing will output whatever (another binary bit) and then a TON of those allow you to make a particular process, like store memory. And then a lot of those things together, combined with more logic can make stuff on the computer happen.
I haven't finished the video yet, but I think that 2nd minimum number algorithm at 8:10 would fail if the numbers were like this : [2,3,5,6] Because at first min=2 & min2=3. Then we check if arr[0] i.e. 2 is less than min i.e. false . Next we check if 2 is less than min2 i.e. true and so min2 also becomes 2. This will make min and min2 both the same and since the first element was the smallest element in the whole array, both the min vars will stay the same and thus return 2 as the 2nd minimum variable instead of the correct answer i.e. 3. The solution should be to initialize both the values of min and min2 as the largest value of an integer data type and then it'll work out correctly.
Her solution depends on initial values. When tmp[1] > tmp[0] her code doesn't work. I don't think you can do this with one iteration WHEN you depend on initial values, and i dont know if you can find the min2 with 1 iteration at all. Maybe with a third variable its possible to do this with 1 iteration. But with 2 absolutely no. Because if the min2 value is at the very beginning of the list and the min value is at the very end of the list, your min variable is gonna store the 2nd_min value and you are going to exclude that from the min2 variable, since you have split the list in smaller fragments (size of 1 num). So with a third variable is gonna be solvable with 1 iteration.
It seems like just sorting the array and getting the nth -1 element should do it. But is sorting not allowed? I think a bubble sort is best case and complex O(n2) or something like that.
For the min2 problem, an edge case you could have asked would be: what if array was {0,0,2,0,8,1}? Her function would return 0 as min2 whereas it should be 1
I was thinking that at first, but when he explained the question he did say the value at position n, not necessarily the true second smallest value? So depending on whether or not the interpretation is literal to that, she could still be correct.
On the finding m minimum, I am thinking you could use an iteration of quicksort and if it divides the array well then you basically only have to check the remainder half of the array. If the final position of you pivot is greater than m than you check the left part, otherwise the right part and reapeat until you get the exact index as m. Meaning you get n+n/2+n/4+n/8+.. = 2n meaning log(n) time. I was right :O
5:04 I believe there is a slightly faster way to do it: Since the min() function first sets min to arr[0] you can start the for-loop on the second element of the array, because there is no point in checking if the value that you just set is smaller than itself, right?
when you got tested in this way... damn man .... I don't like it..... I prefer a test where you can work relaxedly... I hate this kind of test .... the guy on the other side sounds like he thinks he is Yoda ..... eating while he's talking.... etc.... it's always like that though...
Want to give it a shot?? Sign up with us to make sure your upcoming interviews are the best they can be by practicing with our experienced engineers. interviewing.io/signup?.com&
how to be a programmer -
step 1 - learn most efficient sorting algorithm
step 2 - learn most efficient tree traversing algorithm
step 3 - using knowledge from previous steps write some spring rest api with react front-end
Lol, that's how things are nowadays, building a real-world application is way too much away from learning sorting algorithms.
These all companies ask shits on an interview
You can read into step 3 without any bigger knoledge. I think the actual point was, the woman did not know the partial quicksort algorithm, but was able to implement it with minor help. This shows that if she had a rather complex problem, she could solve it by her own/talking about work with the other employees and this would make her valuable.
@Ahmed Baahmed coderpad.io
If you don't know data structures and related algorithms and complexities, there is no way you'll be able to write efficient, scalable and good quality code.
@Ahmed Baahmed Java
Interviewer does a good job of not intimidating the interviewee. I usually get so nervous but if my interviewers were like this it would be so much more comfortable
I just watch 1 hour of two people implementing a sorting algorithm at 4:40AM? I have no life.
not fully sort, but sort of "half sort".
thanks to God i read your comment at 23:00 it`s 2:38 a.m I should leave.
This is great life.
same here
2:49am.
I wouldn’t be surprised to hear toilet flushing sound in the next round of this interview :)
You made me laugh so hard
LOL !
It is not a real interview
@@theghostmachine You only know it if you read description, but most of the people will only read the title.
lol
I'm so bad at technical interviews. That dude would put that code on the screen and then I would instantly die
stop playing league of legends
lmao why am i laughing
same here buddy😂
life :
@@jomp4 ты на чем кодишь генацвли?
Interviewer: Can you find me the n'th smallest element in this unsorted array
Me: Sorts the array
Interviewer: I said unsorted array
Me: I don't want to work for this company
Robert 🤣🤣🤣🤣
Sorting will cost SizelogSize(Size=Size of Array) complexity, it can be done with less than this complexity i.e SizelogN now start thinking how.
hahahahahahaha same here
Who else's heart started beating harder when he finish giving instruction and she started with "um"?
I felt that.
Did you just assume xeir genders?
Not really. If you dont get it, its cool just think it over
nessa You can get in serious trouble, misidentifying someone's gender puts them at risk of suicide.
@@hoakingfermenstine6851 wait are you serious?
Young City Bandit no it's a joke lol
Usually these types of problems are solved by heaps. Just build a maxheap of size K and take out the top element which is minimum kth. Time complexity is N * log(k).
8:15 in, the interviewer was on to an edge issue, but plugged the wrong numbers in to create the issue. By preloading min and min2 with the first and second variables and just using < comparisons we can end up in a situation where the first number in the array could get loaded twice (Into min and min2).
Using an input of (1, 2, 3, 4), we preload '1' into min. We preload '2' into min2. We then run through the array and we do our first comparison,
For arr[0],
Is 1 < 1 (arr[0] VS preloaded 1)? No, so we jump to the else if statement.
Else If, is 1 < 2 (arr[0] VS preloaded 2)? Yes
min2 = 1.
We now have a 1 in both min and min2, and no other numbers are going to be lower than either, so they will not be replaced. We will then return a 'second lowest' of 1, which is incorrect.
Great overall though.
Yes, it's because the min should be the only predefined value. Min2 should be defined automatically after the comparison in the second loop iteration.
You just traced through the first iteration.. Go through all 4 you'll have min2 to be 2.
@@DhananjayNaik how does it make a difference after 4 iteration?
Paul Chon yes it would
another way would be to just add in another condition to ensure current value is greater than min but lesser than min2 . "else if(arr[i] < min2 && arr[i] > min)"
this makes me so anxious.,..
Shit like this is why I'm a manager, not a technical specialist. Even though I could solve these things, I wouldn't put up with shit like this. Also, I have a huge problem with authority and people testing and judging me or telling me what to do. I get an almost visceral fight or flight response. Glad I'm paid to lead.
@@lynth Couldn't agree with you more. I have the same problem.
@@seigemain Nope, I have never worked as a technical specialist and never worked myself up. The concept of working yourself up is fake news that is being told to worker drones. Do you think any rich person has ever worked a day of hard labour in their life? Trump is an imbecile and the president of the US. He isn't even a good business man. He's just rich. You think multi-millionaires got rich because they worked so hard? You can become a top level manager without any technical expertise. As a manager, you aren't concerned with technical labour, you are paid to make decisions and if your team messes up you blame the losers working for you.
Making less than 200k for a job significantly harder than my own? No thanks. You start as a manager and stay in that class. Much easier. The only reason to "work yourself up" is if you need it to get a better understanding of whom to hire and how much to pay them to get the most out of them. I never needed any experience to do management and think it's easy. I never worked longer than 30h/week, just pretended, and make significantly more than most other people. I know that the higher ups have an even better labour/income ratio.
Also, please don't think I'm sounding harsh because I'm looking down on engineers and real workers, I consider them far more important than myself, just realize that you are being exploited and that all that "work yourself up" bullshit is a capitalist scam.
I'm good at what I'm doing, which is leading technical staff to deliver large scale IT projects in accordance to specifications handed down by some hapless manager above me. The only programming I ever did was at university and I was bad at it. I get paid a lot in a senior position at an industry leading company. I never worked as a developer, I never worked as a product manager, I never worked as anything technical. My job doesn't require it. I need to understand what people are capable of and by when they can approximately accomplish which task. I also need to understand what resources they need to get it done. I also need to know how to do PowerPoint presentations.
If you want to be a relativelh rich manager, become a relatively rich manager. Being a worker drone is unlikely to turn you into one. Being a top manager and bringing home cash requires luck and connections.
The only you will ever need actual skills is when you found your own company and are the tech lead. Which is also the only way you will ever get adequate compensation reflecting the value of your work.
I feel like the questions are not that hard but the streess builds up because you are worried about not getting the job if you fail to impress the interviewer. Maybe making the environment stressful is part of the test as well to see how you comprehend problems during stressful situations.
this interview is very kind and forgiving... my interviewer for a job was just giving me hard time and confused the hell out of me
Why is the Google Engineer eating food while interviewing?
because lunch breaks are an hourly workers mentality /s
... It's a practise interview
Disrespect, mostly.
because food is free at google
this guy reddits
What is this? How is this scalable?
Just use a priority_queue:
int nThSmallest(int n, const vector& myVec) {
priority_queue myQueue;
for (int i{}; i < myVec.size(); i++) {
myQueue.push(myVec[i]);
}
int res;
while (n--) {
res = myQueue.top();
myQueue.pop();
}
return res;
}
Maintain an m sized max heap, go through the array,for each num, put it into the heap, then pop one out. The top element of the heap is always the kth smallest of the traversed array.
The comment I was looking for
I thought of that, too, but in the worst case, isn't that still O(n log n)? That's really just heap sorting it.
@@BlueEyedSexyPants no its O(k log n)
@@cartersherman925 O(k
@@cartersherman925 I don't understand why it's k log n. Thinking about the max size, it seems like it's O(n log k) because insertion into k-sized heap is log of the total size of the array, but you still have to do the linear search through n elements of the total array. Edit: "log of the total number of nodes", not total size of the array
The question was like Quick Sort (Even better, cause you just process one part of array). You were supposed to stop in between when you got the right element (When you choose the right element as pivot). 13:35
agree, this problem tests our understading of quick sort. Many people ignores quick sort just because they can use the built-in library.
But quicksort has a worstcase of O(n^2). Would the complexity really be that much better if you stop in between?
@@guitarockdude I thought QuickSort is O(nlogn)?
@@MrMakemusicmike It has an average of O(nlogn) but it has a worst case of O(n^2) if the input array is sorted in a way that the maximum is always chosen as the pivot.
@@guitarockdude gotcha!😉
Only 1056 rounds to go.
I don't think this is a real interview. It says in the fine print under the video that "interviewing.io offers senior engineers free anonymous technical interview practice with engineers from Facebook, Google, and more"
I only watched the first 15 minutes, but this also seems a little too easy (and informal with the interviewer eating）to be a real Google interview
@@user-ds7up1fi2y It does get harder. I thought the same.
@@user-ds7up1fi2y Everything is easy from an outsiders perspective.
They would use 1024 rounds
import random
def kthSmallest(l, k):
start = 0
cur = l[random.randint(0, len(l)-1)]
small = []
large = []
for i in range(len(l)):
if l[i] < cur:
start += 1
small.append(l[i])
else:
large.append(l[i])
if start < k:
return kthSmallest(large, k - start)
elif start > k:
return kthSmallest(small, k)
else:
return cur
I was doing it without the random numbers and was running into issues where the list was in ascending order and it was no longer splitting the subarray.
great interviewer. Interviewing it hard not only when it comes to reading other people's code but also when there is something wrong and you either notice it or don't notice and you need to gently nudge them in the right direction while being tactful in your approach.
for the nth smallest you can do a quicksort where you stop considering half of the remaining array at each point, basically sorting only the nth position. O(n) time
worst is O(m*n)
min heap guaranteed to be O(n+m*log(n))
He's helping her out so much, even by saying "mhm", "yes", "sounds good". When I had similar interviews over the phone I got none of that unfortunately.
F. Lol, that was lame
I've had 5-10 interviews a day for a few months for all kinds of companies. Architects and engieers have all kinds of interview styles. People eating on the phone is not crazy at all.
If that were true then you would have had 450 interviews over the last two months. That makes no sense. Are you exclusively applying for jobs for which you are not qualified?
@@sethborne how do you know he inst recruiting
@@potatolord7319 the interviewer in this video was the one eating. His comment would be nonsensical if he were the interviewer.
@@potatolord7319 also "all kinds of companies" would also imply he isn't working for any given company. If he were working as a head hunter then calling his correspondance interviews would be a stretch.
Also it is very clearly lip smacking. It appears only when he is talking and during particular consonant sounds. Not eating.
Didn't watch their solution for finding the nth smallest integer in an array, but I managed to come up with one after the interviewer gave his hint. Basically you look at index n-1 and count the # of integers in the array less than the n-1th element. If the count equals n-1, then return the n-1th element. Otherwise, put the n-1th element into the index which is equal to the count (the index where it would be in a sorted array), and put the element that is already there into the n-1th index. The two elements are swapped. Then repeat the process until the base case is reached. I implemented this in racket and it worked. It's probably not close to the best, but it works.
interviewer: Write a algorithm that can solve this 1 + 2 + 3 + 4 + 5 + 6
me: OK
num = 1 + 2 + 3 + 4 + 5 + 6
print(num)
I'm looking to hire the next big programmer, and man, does your algorithm ever get me excited about your genius. How does $550K/yr at Facebook sound? >joking
Dank Jank MTG All-Star 1990 bad programming obviously it's print(1+2+3+4+5+6)
Can you make your code more efficient?
OBVIOUSLY this is the wrong way to go about this problem. It’s *very* clearly:
int num1 = 1;
int num2 = 2:
int num3 = 3:
int num4 = 4;
int num5 = 5;
int num6 = 6;
int num = num1 + num2 + num3 + num4 + num5 + num6;
System.out.println(num);
As you can see, your code will now be completely readable and run *super* fast.
@@TheTacticalMess it is
var num = 1 + 2 + 3 + 4 + 5 + 6
console.log(num)
I would literally tell the interviewer give me a sec let me google this real quick :)
hahaha , i just ctrl+t as i heard order statistic
my mouth is dry and my hands are sweaty just watching this
His palms are sweaty, knees weak, arms are heavy, There's vomit on his sweater already, mom's spaghetti
If you have done this exact challenge before and know how to solve it, then you could call it easy (becasue everything is easy by that logic) but if you haven't done this exact challenge it is hard to answer up front. But she seems to have been well prepared or else she would have become stuck.
I haven't done any programming problems like this. But after he asks, I paused the video and spent 10~15 minutes to write the code for it. The way I did it was different from her but I think I reduced the runtime down to n with my code. So I would call the problem easy... for me at least.
Nah ， I never saw this problem before , but the second he gave out the first hint , it was so clear and easy :)
i've literally took out snacks too and started watching this around midnight
Taco Bell ran 42 lines of java
Been programming for 18 years, video games for 10. Have yet to need an O(n) sort, most cases are negligible. Sorting algorithms seem to mainly come up in interviews, and are used seemingly infrequently in my field. For that reason, I don't really like interviews like this because it really just means you have to go back, and study all your sorting algorithms again. To each their own I guess, I'm sure Google has many cases for optimized sorting, but if someone fully understands algorithm complexity I wouldn't stop them on this.
Jacob Raffe while I agree, I think he meant that an n log n solution is acceptable in many realistic cases. Sure, if you’re working with a ton of data, go for a non-comparison based O(n) solution. However, for every day tasks/code that won’t be running on tons of data, i think it can be seen as overkill. I’m fairly certain that most standard libraries use a sort of randomized quicksort in their sorting algorithms which yields the n log n solution. (Difference is much more negligible than the brute n^2 algo).
I suspect Google is trying to judge how quickly and fully the candidates can grasp new concepts rather than how much they can remember from their school or previous job. For that they need to talk about things it's unlikely the candidate has come across before.
They're assessing how well you approach a problem and you can adapt to new knowledge quickly. Not literally how well you can make a sorting algorithm.
@@TheHeadlets +scott5146 +Jon Miller +Jacob Raffe I'm not disagreeing with any of you. @Jon Miller hit it right on the nose on what I was saying. I think there's merit in saying they're testing their ability to adapt to new problems. However, I think having a recollection of sorting algorithms in the back of your head will make that problem incredibly easier. So based on that idea, I would like to see an interview that's more real world. I could be bias however, in the game industry we will tend to give you more problems that are more applicable to what we're working on.
@@bentky2528 You're exactly right, that's why a good interviewer will realize when a candidate simply knew the answer from memory, and move in a different direction to actually test the ability to adapt.
I watched a few interviews, I can easy tell I enjoyed both of you going through journey of thinking. I love you
The first algorith could have been written a bit more efficient if the for loop would have started at i=1. Because i=0 is already set as min.
Thought the same! Was about to comment it, but you did it first.
Because u count 0 1 2 3 not 1 2 3 in arrays
vincent perez we know that. Read the comment again. Starting at 0 is useless...
Diego Rodríguez is it Diego
@@bouggyman180 It is. If the item at index 0 is already set at the min. It makes no sense to compare it to itself, thus it's better to start the for loop at index 1, where it makes sense to compare the min (item at index 0) with the second item.
Here is my approach using python
def min(arr, n):
for i in range(len(arr)):
if i < n and arr[i] > arr[n-1]:
arr[i], arr[n-1] = arr[n-1], arr[i]
elif i >= n and arr[i] < arr[n-1]:
arr[i], arr[n-1] = arr[n-1], arr[i]
return arr[n-1]
Wow she was really good at coding on the spot. I couldn't quite understand how the quick sort pivoting works out to be ~O(2n) though.
Partitioning takes n operations. Then you recurse on one side of the pivot, and the expected size of the partition you recurse into is 1/2 * n so the recursive step takes 1/2 * n operations. The expected size of the next partition is 1/2 * 1/2 * n. And so on. And so the sum of all these is n + 1/2 n + 1/4 n + 1/8 n + ... which is a geometric sum that converges to 2n.
I used an ArrayList for this solution and I think it's more easier to make it with that.
Here's my solution:
public static int minAtN(ArrayList arr, int n) {
for (int i = 0; i < n - 1; i++)
arr.remove(getMin(arr));
return getMin(arr);
}
public static Integer getMin(ArrayList arr) {
Integer min = arr.get(0);
for (Integer i : arr)
if (i < min)
min = i;
return min;
}
I used 2 methods because it's more easier to work like that. I think that she should've used the first method that she made a helper method for the nth smallest number method so it'll be more organized and easier to solve. She made it complicated when she could make it easier.
Also I tried to do it with an array:
public static int minAtN(int[] arr, int n) {
int m = min(arr);
if (n == 1)
return m;
int[] arr2 = new int[arr.length-1];
int j = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > m) {
arr2[j] = arr[i];
j++;
}
}
return minAtN(arr2, n-1);
}
public static int min(int[] arr) {
int m = arr[0];
for (int i = 0; i < arr.length; i++)
if (arr[i] < m)
m = arr[i];
return m;
}
Didnt watch the entire interview, but your first attempt would still have a complexity of O(n^2) (or did i miss something?)
@@DujiBuji Yes it is
during the whole swap thing, around 30:00 , Her elements won't be swapped as she says. She is comparing the first element of the array with every other, since she doesn't update index, she only updates i. I don't get it. So only 2 will be at the right place and not 10.
thanks, I thought I was not seeing something
Yep, I checked her code twice to see if I am missing something
Thought I was missing something, but glad you saw the same thing
yes, it lacks "index++;" line right after swapping insife if statement
This algorithm is known as Quickselect: en.wikipedia.org/wiki/Quickselect
You can also do it in guaranteed n log k time using a min heap (PriorityQueue). Just add all of the numbers to the heap, and then pop off a number every time the size of the heap > k. Obviously this takes more space than Quickselect.
I wish my technical interviews gonna be this easy
Same
At 8:06, for people that want to use this as a template to find the smallest digit, if the first 2 digits happen to be sorted, then this code would not work. If the first 2 digits is in fact sorted, all you have to do is change int min2 = arr[1] to arr[0] and int min = arr[0] to arr[1].
Lol facts
Curious to know if the interviewee got into the 2nd round? Just in sense of the time complexity...
I think we can do insertion sort for first m element. time complexity O(n*m)
def get_m_smallest(arr, m):
for i in range(0,m):
find_small(arr,i)
return arr
def find_small(arr, index):
pivot = arr[index]
small_index = index
for i in range(index+1, len(arr)):
if arr[i] < pivot:
pivot = arr[i]
small_index = i
arr[index], arr[small_index] = arr[small_index], arr[index]
Wow, i never understood coding, but the way this girl thinks out loud makes everything make so much sense.
To find m-th order statistics i would divide the the array into n subset arrays (if m
You could do a Radix sort of the array--which is O(nk) where n is the number of elements in the array and k is the number of digits in the integers you are sorting. Where k is small this will have better performance than presorting and then selecting which is O(nlogn) for an unsorted array.
Was shouting that out loud!
this was my instinct. I paused the code and wrote the solution real quick, and felt so cool. then I got butt hurt when he proposed the sub-array method, which I think is O(n*log(k)). anyway, your comment gave me solace, friend. I need to watch the video again to really comprehend the approach fully.
I was doing this in C++, and I think I may have found a small improvement to the classic sort-all and select strategy.
Please critique if you have any thoughts also.
general principle:
1.) corner cases when kvector.size() return -1 because illegal k value[ time complexity should be constant]
2.) from ind0 to and including k, sort the subarray with quicksort,[quicksort time complexity with the subarray size.]
3.) make that ind(k) as candidate min
4.) iterate from ind(k+1) until the end and check if the looped vector value is smaller than candidate min,[need to check rest of the array]
5.) if you find smaller than candidate min, make a binary search into the already sorted subarray on the lefthandside of the array, and then you need to insert that new candidate min into the index indicated by binary search. (this was a little tricky in C++
because the default binary search sucks and I just used lower_bound I think.). This can give bad memory performance at least in C++ because if you insert into the middle then vectors have to shift the elements forward I think...
6.)return the candidate min.
7.) probably it will not give a huge boost in performance, but something that I thought about...???
hmm... I may have made some off-by-one error in that description because I used iterators mainly for the sort subarray and lower_bound, but that was still my general principle. I also had it so that k=1 smallest is a separate special case where I just find the minimum, and general principle starts for the k=2
wow apparently I was wrong also that this is not best case... allegedly it should be possible to get k-smallest in O(N) for average case
This is a "quick select" algorithm
First question is so easy. I can think of couple different ways to sort the array. But I will chose insertion sort because the length of the array is very small. And you can also apply ADT something like a heap to sort the array and whenever you need the min value then you just extract the min node and trickle down again do the shifting and swapping jobs.
Wow. So you just do this and internet happens?!? I can imagine that there are thousands of Googlers just hammering at their keyboards finding those mth indexes day in and day out, sweat pouring off their brows as they fight to keep the proper ads served to the appropriate targets. I still watched the entire thing, though.
Just like the entire world is hammering away at 'solve x for ...' or figuring out the lengths of certain arms inside a figure.... right?
You barely ever get directly tested for the skills you're going to be putting to use in everyday worklife tbh - I'm trying to illustrate that with a mediocre highschool example :P
i mean there are different jobs and assignments..
90% of the internet is _.map(data, (item, idx, arr)=> {RENDER OUT SOME KIND OF INTERFACE HERE})
This but with multiple servers and datasets larger than a single computer.
LouSaydus angular？
There is a small mistake at 31:30 because you guys are not updating the index value, if you want 10 to keep shifting rightwards then you need to change the index. (Though alternative solution might exist). So in this case you won't get the predicted output.
This is not like a google interview in my opinion. The interviewer is way more helpful than a normal google interviewer.
I agree, if only interviewers were this patient and helpful in real interviews.
That's because he is interviewing a girl
@@xtredeabm2080 hahahahahahahahaahahahah 100% TRUE
23:33 it's looking like quicksort, so I think final solution is modification of quicksort, to only apply the algorithm on the half that's "needed"
That's the truth. It's a modification of a quicksort.
Why don't use a priority queue bounded to size m? Every enqueue and dequeue would take O(log m), but since m is fixed that means that O(log m) is O(1) with respect to the length of the array of numbers. So we have an procedure that is O(n) in time and O(1) in space, where n is the length of `arr`.
built in priority_que (c++, or java), specifically min heap, pop k smallest times. prob < 7 lines of code. whenever you are finding the k smallest or k biggest or anything regarding biggest/smallest, min/max heaps are your bff fyi
building the heap takes O(nlogn) time in worst case, and the interviewer is asking for O(n)
For anyone who wants to cut to the chase the answer is: a binary heap, which is O(nlogk) time with a storage requirement of O(k) time. (In the interview he uses m, but k is proper.)
Some might think Quickselect ( en.wikipedia.org/wiki/Quickselect ) would be ideal, with an average of O(n) time, but in real world benchmarks a binary heap is both faster and uses less memory. This is due to quickselect using more ram (which is often slower than raw number crunching) and having a worse case time of O(n^2).
So if you thought heap, yes, your intention did not mislead you.
Second min program is wrong what if inputs are {0,3,1,2,4}
Initializing the variables to infinity could have been a solution.
adding to the else if --> && arr[i] > min
@google buddy, you were correct. just missed at 9:07. if array was "2,3,5,6", answer would be wrong. min2 will give 2, instead of 3.
why does my brain says " stack overflow"
I haven't done java, so I did in in python, it seems correct:
def nth_smallest(arr, n):
if len(arr) == 1:
return arr[0]
target = arr[len(arr)//2]
small = []
big = []
for i in arr:
if i < target:
small.append(i)
elif i > target:
big.append(i)
if len(small) == n - 1:
return target
if len(small) >= n:
return nth_smallest(small, n)
return nth_smallest(big, n - len(small))
Could we not use say a min heap and then extract from it in order to get O(n) time?
but you have to create a heap which will take O(n) and then extract min which will take log(n)
overall it will take O(n)+k*log(n) where k is the order
@@usmankhantech Sorry for the dumb question but isn't O(n) + kO(logn) just equal to O(n) in the long run as O(n) is the bigger term?
no because k could be as large as n and than it becomes n log n
Didn't hear any space constraints at the beginning so: What about make a new array of size max(arr), iterate through arr and mark each i of new array corresponding to values in arr, then iterate through new array counting marked indices to find mth marked index. This does break down in time if there are arbitrarily large numbers in arr though
so the solutions should be quickselect or maxheap?
I wouldn't have had this thought without watching, but at 5:04 when the interview asks "is there a faster way we could do it" you could probably make the search multi-threaded by splitting an array and giving each thread a piece of the array to search.
Unfortunately, it is still possible to hit a data sequence which will result in (n + n - 1 + n - 2 ...) complexity, due to the problem of pivot selection. Only in case of the positive scenario array will be divided by half and algoruthm will result in (n + n / 2...) complexity.
n + n/2.. is 2n, which amortizes to simply an O(n) time complexity because it is a constant factor.
52:00 is definitely the highlight of this video
till tryna figure out the best explanation to this n log n lol but can see..index is stuck at 0 in her Nth smallest
looping
I think a better interview technique would be to have some written code and ask the candidate to explain what that code does. Anxiety can get in the way of technical interview which means a lot of very good experienced engineers slip through the net. When I interview people I give them some code and we have a chat about it and that works out great.
Not many people think like you. There is so much ego in asking algorithms questions.Many engineers think they are above everything, and ask heavy mathematical and algorithms question. It's so stupid.
public static int findMin(int arr[], int nElement) {
Arrays.sort(arr);
return arr[nElement-1];
}
solution is nlogn, can be done in n time with multiple pointers and a counter.
C-style array declaration? Side effects on parameters? That's nasty!
Real Tech Bro It cannot be done in O(n).
@@Rahul-Nalawade Try using median of medians technique to obtain O(n)
In reality, this is the type of code base you want to work with: concise, generic, using standards. Only try to be smart when you know youre bottlenecked by a specific function.
I would have chosen M as my pivot point. Worst case is everything is already sorted (ascending or descending) or if you keep randomly choosing the next smallest or largest value in the array. You can mitigate one of those bad cases. If the array is sorted, ascending then you only have to loop through N elements. That is the best case. If you choose index 0 you must loop through multiple times to get to M in a sorted, ascending array.
I'm not a native english speaker, and I found that the audio over the phone is not clear enough, worse than how we hear a voice over a standard youtube video. Is there any solution to tackle this issue for phone interview ?
There is a transcript over at their page: interviewing.io/recordings/Java-Google-1
I'm sorry for didn't explain it clearly, but my issue regarding the voice clarity is not just limited for this video, but also based on my real experience when I was being interviewed by Google over the phone.
@@horriblefate just ask them to talk a little slower and clearer or improve on audio quality by changing to Skype instead.
@@Illu07 thanks for the advise. They indeed was offering me a choice to do the interview over phone call or Google-Hangouts. Hopefully the voice can be clearer over the Hangouts.
been in your shoes...my advice...start listening English only radio, tv, etc..no captions!...what you have is an untrained hearing due the diffs between your native language and English...as soon as your hearing get used to the words (and possible acoustic variations) you will have no issue at all doing a phone interview..
I have a good friend who works at google right out of college. This was not how he got the job. He told me that there was a hiring event and he just showed up, they interviewed him on the spot. They asked him what his major was, and what he wanted to do. The odd thing he majored in Bio and wanted to go to med school, but google offered him a job for the summer and ended up. He tells me its nothing like they make it out. I think he forgot about med school.
I'm lazy. What i would do to get the min is arr.sort() then return arr[0];
The point he made was can you do it faster, I.e. more efficiently in machine resources.
You ever tried sorting a 700k row Excel file with 100 columns?
5:27 This is a really petty thing to bring up but the loop is starting at i=0 when the value stored is already i at index 0 of the array. That's a redundant check, use i=1.
can't we use a heap ?
Yeah I think that would be efficient. Build the heap from array, logn. Then, to find n-th order you would pop n times and heapify each time ... thus, an n*log(q) solution where q is the size of array and n is number of times to pop
@@BorisMediaProds yeah . i dunno why a google interview candidate would skip this solution
@@BorisMediaProds Heap construction is O(n) on average, not O(logn). Total runtime would be O(n + mlogn). When m < arr.size()/2, a min heap can be used. Otherwise, a max heap is favored so the amount of times you pop the heap is minimized.
@@ferasboulala6220 average case isn't important, worst case is that you need to insert n nodes and each node takes logn time.
@@BorisMediaProds Worst case is also O(n). You're thinking about inserting each node iteratively. The optimal heap construction takes an array as input and swaps references. Look it up, it is O(n) even in worst case.
5:05is there any faster way you can do it? actually yes. She can make a var called size of the array and use it in the for loop. That way we do have to use .length() method each time in the for loop.
quicksort partition...
could also use a heap n log k
@@EatHotLead4Ever She could use a heap, but on average her solution with quicksort is N
@@alekseiduleba9508 I don't get why you need to know any of this by heart if you can just google it. It's not like you need to find the best sorting algorithm ten times a day. And if you eventually really need to you will learn it at work.
10:10 In case there are 2 same small numbers min1 and min2 would be the same, so else if can be like;
min2 = (arr[i] != min) ? arr[i]:min2;
When he asked this question at first "Heap" came in my mind
Usman Khan same
Me too got the same Idea
SAME!!!!!
her feedback was "i can tell youre new to this, sorry but try again" no good that, she pretty much was flawless.
She could of skipped one iteration in the first function since it doesn’t make any sense to check if arr[0] < arr[0]...I don’t know why that frustrated me so much
You want to check that if you are trying to find the 2nd smallest
helps with readability anyway so doesnt matter
I managed to justify it in my head to handle the case that the array was len 1
@@jaspermacnaughton5259 if array was length 1 you would just return min. it works perfectly.
It's she "could have" instead of she "could of"
The whole time im thinking, why not just use a queue? Every time u find a smaller value than the current min, push it into the queue. If the queue size > m, poll. At the end the peek of the queue would be ur answer.
Had a few phone interviews with FAANG companies and above, the interviewers were never this helpful... If I didn't train myself to write bugless code, I would've failed them even if my algorithms were optimal
minghao liu 好好
Ive had a couple of interviews with google and none of them were even close as how patient/helpful as this guy. I think this is staged.
The Last Orca it literally says it's a "mock interview"
If this were a C++ test the solution would be trivial:
int order_statistic(std::vectior arr, int k)
{
std::nth_element(std::being(arr),std::begin(arr)+k,std::end(arr));
return arr[k];
}
Come on... don't use 'arr' as a variable name for a vector... use 'vec' like a sane person!
Supersonic Taco ran 64 lines of Java:
and you have the stupidest profile pic...so?
@@brucealvin4227 "Return to Me," declares the LORD, "so that I may return to you."
-Zechariah 1:3
@@justins7796 what in the schlong is this..?
Justin S Tucker is the man also lol at original comment
Spent 10min of the video screaming "use the sort function that comes with java and you can make the function a twoliner" and at 11:08 she explained it. 10/10 satisfaction
In hindsight and after reading the comments and testing it in an online java compiler, sort really is an inefficient solution. Should've used heap.
Question: coming from someone with zero knowledge of coding, where does this code come from? Why or how does it do what it does? Is there code underneath?
If so, where does *that* code come from? At what point are 0s and 1s turned into code?
the matrix
The code is written in a high level language, such as java. Then it is compiled, into machine code. Machine code is a set of instructions that ultimately are processed by the cpu.
To state it simply, the Java compiler will turn your code into that (well first into JVM byte code, but that's too much for now). 0's and 1's go into transistors and logic gates which are what processors and elements of computing are comprised of. If you put enough logic gates together and input into them (in the form of bits, 0's and 1's (essentially true and false), you can make stuff that does calculations. I'd recommend reading up on boolean algebra and then learning about logic gates, then how you can make things like multiplexers, encoders, decoders, etc. These things can then make elements of a processor like a register and eventually a register file, etc. There are many more components, but essentially the 0's and 1's get turned into code by people manipulating them by saying if you put a 0 here and 1 here, this thing will output whatever (another binary bit) and then a TON of those allow you to make a particular process, like store memory. And then a lot of those things together, combined with more logic can make stuff on the computer happen.
@@andrewmarek Thank you for your detailed explanation. :)
@@TheDcfan01 thanks
I haven't finished the video yet, but I think that 2nd minimum number algorithm at 8:10 would fail if the numbers were like this :
[2,3,5,6]
Because at first min=2 & min2=3.
Then we check if arr[0] i.e. 2 is less than min i.e. false . Next we check if 2 is less than min2 i.e. true and so min2 also becomes 2.
This will make min and min2 both the same and since the first element was the smallest element in the whole array, both the min vars will stay the same and thus return 2 as the 2nd minimum variable instead of the correct answer i.e. 3. The solution should be to initialize both the values of min and min2 as the largest value of an integer data type and then it'll work out correctly.
Sorry but the bar has gotten so much higher than this. I dont think she would pass a Google/FB phone screen.
y? this is only a phone screen right?
Yeah this seems basic as fuck. Maybe this is a preliminary screening interview?
this was just a free practice interview, link in description. Not a real google interview session.
Her solution depends on initial values. When tmp[1] > tmp[0] her code doesn't work. I don't think you can do this with one iteration WHEN you depend on initial values, and i dont know if you can find the min2 with 1 iteration at all. Maybe with a third variable its possible to do this with 1 iteration. But with 2 absolutely no. Because if the min2 value is at the very beginning of the list and the min value is at the very end of the list, your min variable is gonna store the 2nd_min value and you are going to exclude that from the min2 variable, since you have split the list in smaller fragments (size of 1 num). So with a third variable is gonna be solvable with 1 iteration.
is this even real? lol, seems like the interviewer is munching on some really good pizza
It seems like just sorting the array and getting the nth -1 element should do it. But is sorting not allowed? I think a bubble sort is best case and complex O(n2) or something like that.
why didn't she use Min Heap?
Agreed!
Min heap does not work in O(N), as every lookup has a complexity of O(log N) resulting in O(N * log N)
Did anyone notice at 30:00 somewhere they just swap and increment the value of index from zero to ++ and there is no code of index++;
?
Did he really start eating while doing an interview? 😳🙄🤔
Shah Jacob Calm down there. It's still rude.
senior engineer my ass XD
Why, you think people normally don't eat while on business-related teleconference sessions? You'd be surprised...
just your imagination, bro
It makes you feel comfortable with an intrerviewer, like if he was your fellow, who tries to challange your coding skills XD
Finding second smallest doesn't work with input array as arr[] = {0,5,7,2,3,9,1}; it gives both min and min2 as 0.
For the min2 problem, an edge case you could have asked would be: what if array was {0,0,2,0,8,1}?
Her function would return 0 as min2 whereas it should be 1
yep her answer is wrong. coulda put (arr[i] !== min && arr[i] < min2)
I was thinking that at first, but when he explained the question he did say the value at position n, not necessarily the true second smallest value? So depending on whether or not the interpretation is literal to that, she could still be correct.
He specified that it was a `set` which implies that all the values are unique.
She should've clarified her assumptions tbh
That isn't a case he is asking, suppose all numbers are different
On the finding m minimum, I am thinking you could use an iteration of quicksort and if it divides the array well then you basically only have to check the remainder half of the array. If the final position of you pivot is greater than m than you check the left part, otherwise the right part and reapeat until you get the exact index as m. Meaning you get n+n/2+n/4+n/8+.. = 2n meaning log(n) time.
I was right :O
Guess this is an interview for somebody working in facility management at Google?
why?
5:04
I believe there is a slightly faster way to do it: Since the min() function first sets min to arr[0] you can start the for-loop on the second element of the array, because there is no point in checking if the value that you just set is smaller than itself, right?
Faster in terms of big O notation. So it's still O(n).
when you got tested in this way... damn man .... I don't like it..... I prefer a test where you can work relaxedly... I hate this kind of test .... the guy on the other side sounds like he thinks he is Yoda ..... eating while he's talking.... etc.... it's always like that though...
I feel like atleast the questions are answerable, although its stressful, it gives me hope.
It's all about making the interviewer feel smarter.
It's a mock interview. Eating isn't really that bad when he's helping her practice for an interview lol
Nice ellipses bro
In my opinion the interviewer sounds like a nice guy and is really trying to help the interviewee
I hope he told her about a PriorityQueue in his comments. She could have done the last part in less than 5 minutes.
It looked fairly simple to me, and I haven't even finished elementary school yet. Do I get the job?
Do you know what binary heap is?(Be honest)
😭
@Jacob Raffe Lol
Why did you reply?