Java Interview with a Google engineer

Interview Summary

Problem type
Order statistic of an unsorted array
Interview question
Given an unsorted array, find the nth smallest element in the array

Interview Feedback

Feedback about Supersonic Taco (the interviewee)
Advance this person to the next round?
Yes
How were their technical skills?
4/4
How was their problem solving ability?
3/4
What about their communication ability?
4/4

Great job! I needed to give you a few hints on the algorithm and time complexity, but really it was quite minor. I appreciated how you verbalized your thought process in working through the problem, which gave me confidence you understood the problem and the challenge. Your ability to code up algorithm into a working solution was very solid. Keep up the good work.

Feedback about Intergalactic Avenger (the interviewer)
Would you want to work with this person?
Yes
How excited would you be to work with them?
4/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4

Interview Transcript

Intergalactic Avenger: Hello?
Supersonic Taco: Hi!
Intergalactic Avenger: How's it going?
Supersonic Taco: Good, how are you?
Intergalactic Avenger: Doing good, doing good. Yeah sorry, couldn't hear you for a second so I just wrote this on the screen there. Have you ever used the platform before?
Supersonic Taco: Yes, a couple times.
Intergalactic Avenger: Okay so then I guess you're familiar with how it all works, so I'm just going to jump straight into a coding question.
Supersonic Taco: Alright.
Intergalactic Avenger: So the first question is: are you familiar with the concept of order statistics. Have you heard that term before?
Supersonic Taco: No
Intergalactic Avenger: It's actually a very simple thing with an overly complicated name. So, given an unordered set of numbers like what I've written here: 1, 6, 3, 9, 8, 5, the order statistics are like the nth element in the list if it were sorted. So, the first smallest number in this list would be 1, and the second smallest number is 2, and basically the nth order statistic is then the nth smallest. That make sense?
Supersonic Taco: Yeah
Intergalactic Avenger: Alright so we're just going to have some algorithmic questions about finding some of these nth order statistics. Just to get started as sort of a warm-up problem: how about you write a function that, given a list of numbers that are out of order, you just find the smallest. So basically the first order statistic.

Supersonic Taco: Okay sounds good.

Supersonic Taco:

Supersonic Taco: So I'll just declare it here: public static int is the return and I'll just call it min, and this takes an int I'll call it n.

Intergalactic Avenger: So this should be like an array.
Supersonic Taco: Yeah, sorry. So then I'll loop through the array, and the for each of those iterations I'll compare it against a min that I've already set up. So I'll set the min to be arr[0], and so what should I return if the array is null, or if there's no value?
Intergalactic Avenger: Don't worry about that case. We'll just assume it'll always have some values in it.
Supersonic Taco: Okay, sounds good. So then moving through the array, if the element at the index of i is less than min then we make that the new min. And at the very end of the for loop you return. So just to test it to make sure, I'll write a litte test here: int[] input = {2, 3, 0, 6} should give us 0.
Intergalactic Avenger: Yup, sounds good.
Supersonic Taco: And let's try that then. Alright there we go: it returned 0.

Intergalactic Avenger: Perfect, and what's the runtime of this algorithm?
Supersonic Taco: O(n)
Intergalactic Avenger: And is there any faster way for you to do it?
Supersonic Taco: For an unsorted array that I know of, no.

Intergalactic Avenger: Correct. Okay, so now you get the idea, let's make this a little harder, a little trickier. How about you give me the second smallest number?
Supersonic Taco: Okay, so for the second smallest number, then I think what we would need to do is maintain two variables and check across both of them to see...like a larger min and a smaller min so we can check if there's a number that's smaller than both of them then we would put it into the smaller min, and if it's only smaller than the larger one then we can put it into the larger min. So once again are we assuming that the array's length is two or greater?
Intergalactic Avenger: Yep
Supersonic Taco: Okay, then I'll just call this min2 and we'll put this at the second element of the arr[], and if the arr[] is greater than the min then it's the very smallest one so the min becomes arr[1]. min2 should be set to min and min is set to the new minimum. And then otherwise, if arr[i] is less than min2 whereas it's still greater than min then this means min2 becomes the arr[i] and instead min becomes min2.
Intergalactic Avenger: min2 becomes arr[i], but what happened to min then?
Supersonic Taco: Oh sorry yeah, this is maintained the same I think, because if it's less than min2 then min is still the smallest so it should stay the same, but min2 gets updated.

Intergalactic Avenger: Okay, let's run this.
Supersonic Taco: I have to return min2 this time. Okay this should give me 2. There, it gave me 2.

Intergalactic Avenger: Perfect. Okay, I'm trying to think if there is a corner case here. What if these were the numbers here: {3, 2, 5, 6}. It should actually be 3, because 3 is the second smallest.
Supersonic Taco: Yeah, it returns 3.

Intergalactic Avenger: What if...Oh because you start back at 0 again, then you flip it all around, I got it. Alright, yeah perfect. And what's the runtime of this one?
Supersonic Taco: This one is still O(n).

Conclusion

After working through various strategies for finding the nth smallest element, we found that by implementing a recursive approach, we were able to reduce the runtime of our algorithm to O(n) on average, which is a significant improvement.