# Watch a technical mock interview with a Google engineer

Intergalactic Avenger, a Google engineer, interviewed Colossal Lizard in Java
Share
Summary

Problem type

Third order statistic of a set

Given a Set of numbers, find and return the 3rd smallest number

• Order statistic of unsorted array

Feedback

Feedback about Colossal Lizard (the interviewee)

Advance this person to the next round?
No
How were their technical skills?
2/4
How was their problem solving ability?
2/4
3/4
I could tell the you're a bit new at this, but no worries it will get easier as you practice more. You'll definitely want to practice the basics of whatever language you'll be programming in -- maps, lists, sets, and how to do basic operations like adding, iterating etc. At interview time you'll want to have those down so you can focus on the problem solving. As far as problem solving, I liked how you identified the simple solution first (sort) and were able to to code that up to a working example that compiled/ran. That's an excellent first step and that approach of getting a complete example working first is a great strategy. You started to falter a little bit with the optimization of the algorithm though. Again, practicing solving problems you can find on the internet will help get you thinking of optimized solutions more naturally. Good luck!

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
4/4
Please make sure the phone connection is good. Please don't turn your speakers up too loud as I could hear myself talking on your side. Other than that, you were an awesome interviewer!
Transcript
Colossal Lizard: Hello can you hear me? Intergalactic Avenger: Yeah, can you hear me? Colossal Lizard: Yeah yeah. Intergalactic Avenger: Alright, how's your evening going so far? Colossal Lizard: Pretty well, just woke up from a nap. Intergalactic Avenger: Alright, that's good. Now you won't need to take any breaks in the middle Colossal Lizard: Yeah, hopefully not. Intergalactic Avenger: So have you used this platform before? Colossal Lizard: No it's my first time. Intergalactic Avenger: Alright, it's pretty basic stuff. We're just going to pick a language for you to do a programming challenge in and you'll code it up and you'll run it and that's about it. The only thing we need to do to get started is picking a language that you want to work with. Colossal Lizard: Yeah sure, I'd like to say I want to do it in Python, but I'm not too familiar with it. I definitely want to switch eventually, but I'll just use Java for now. Intergalactic Avenger: Okay, let's just do Java then. So I'm just going dive on in to a programming challenge and at the end if you have any questions for me we can do that then. So my first question for you is if you're familiar with the concept of Order Statistics like finding the third largest number in a set of numbers or like that. Colossal Lizard: Yeah I've definitely heard of something like that. So I actually kind of need to go to the bathroom right now, I'm really sorry. Intergalactic Avenger: Yeah no worries no worries. Just come back whenever you're done. Colossal Lizard: Yeah I'll be like five minutes. Yeah I'll come back. [User has bathroom break] [8:00] Colossal Lizard: Hello? Intergalactic Avenger: Yep Colossal Lizard: Yeah, sorry about that. Back now, sorry had a bit of stomach pain. We were talking about Orders? Intergalactic Avenger: Yeah, you doing alright? Colossal Lizard: Yeah yeah I'm okay now. Intergalactic Avenger: Alright, so let's just start by implementing basic forms of this then we'll sort of expand it and make it more and more general. So the first one, just to get us started, with the platform and everything. Let's just start by finding the...Write a function to determine the third smallest number in a set of numbers. So basically in the class up above, you'll definite a function. Just make it `static int` and you'll call it `thirdSmallest()`, and it'll take a `Set`. Does that make sense? Colossal Lizard: Sure yeah. Okay, let's get to it. So, `public static int thirdSmallest()`Intergalactic Avenger: Yeah so it can be run in the platform in Java, you'll want to make it as part of this platform… Colossal Lizard: Oh, you're right, of course. `thirdSmallest()` and you're given a `Set candidates`. So the third smallest number? What if the `candidates` decided that `candidates < 3`. Say the `candidates` was only containing `2` numbers? Intergalactic Avenger: Just return `null` it's fine. Oh, nevermind, return `0`. Colossal Lizard: I'm going to first find the size of the `candidates` and I'm going to say, if that's less than `3`, I return `0`. What's jumping on me right now is to sort the `candidates` and if I sorted it I could return the 3rd smallest element just by starting the last element of `candidates` and just moving two over. Intergalactic Avenger: Mhm Colossal Lizard: Okay so I'm going to try to sort it. So I know in Java you can do `Arrays.sort()` and `Set` is...Not sure if I can call it on a `Set` directly. But we'll try that and I'm going to say that the third smallest is walking two over from the end so `int res = candidates.get(size - 3)`. And return `res`, and so let me see if this works for a small `Set`. Intergalactic Avenger: Yeah so go ahead and put the example in the `static void main()` stack. Colossal Lizard: Sure, so I can do `Set nums = new HashSet<>()`. So do I actually have to actually `add()` the numbers in? I guess I do. `add(1)`, `add(2)`, `add(3)`. Hopefully it's `{1, 2, 3}` in the collection. And then I need to call it: `return thirdSmallest(nums)`. Intergalactic Avenger: Why don't you try printing it out. It'll be easier to see Colossal Lizard: Gotcha: `println()`. Okay so let me try to run it. Okay so I guess you can't call `Arrays.sort()`, so `Arrays.sort()` is expecting an `Array`. I'm wondering if there's a way to convert `candidates` to an `Array`: `toArray()`. Intergalactic Avenger: Yeah feel free to use `toArray()` method. You're right, that will turn the `Set` into an `Array`. Colossal Lizard: Yeah and if that's the case I'd probably have to use `candidates` using `Array` notation right here. If that really changes it to an `Array`…. Intergalactic Avenger: So `candidates.toArray()` doesn't actually change the type into an `Array`. It returns an `Array` that contains all of the `candidates` that you have. Colossal Lizard: Okay, so it doesn't change it to an `Array`, so my `candidates` is still a `Set`? Intergalactic Avenger: So when you call `candidates.toArray()`, `candidates` the `Set` doesn't change, it just creates a new `Array`, and returns it. Colossal Lizard: Oh gotcha, so maybe I can save that somewhere right? So `int[] sorted = Arrays.sort()` and then instead of using `candidates` I can use `sorted`. `sorted.length` and I move `2` over which would just be `- 3`. Let me try that. `Void` cannot be….So maybe `Arrays.sort()` does not return an `Array`? Intergalactic Avenger: Alright so, what does `Arrays.sort()`...so does `Arrays.sort()` create a new `Array` and return a pointer to it? Or does it sort the `Arrays` in place and return a `void`. And you can definitely look in the Java documentation if you want to take a look. Colossal Lizard: Yeah okay, I'm going to do that right now. I'm looking at the Oracle docs right now. So it says it returns `void`. `static void` is the return type. Intergalactic Avenger: So the problem isn't with the input, so `Arrays.sort()` here is taking in the result of calling `toArray()` on `candidates`. So `Arrays.sort()` has the input as an `Array`, the issue here is that `Arrays.sort()` doesn't return any value it's a void and it actually just is a side effect taking whatever array you've given it and sorting it in place. Colossal Lizard: Gotcha, okay so in that case I can't assign it to anything because it doesn't return anything. So I'd need to….so if I just call...so if it turns my `Set` into an `Array` and my `candidates` is an `Array` at this time, I was wondering if I could just do `candidates`…. Intergalactic Avenger: So `candidates` doesn't change at all, so `candidates.toArray()` doesn't change `candidates`, it returns an `Array` with a copy of all the data that has all the integers in it. So after you call `toArray()` there's now two separate things: there's `candidates` and there's the `Array` that was returned by that function call. You have the right intuition with storing the sorted `Array`, but you need to do it at a little different way, because in essence you;re losing that `Array` by writing it this way. So you call `candidates.toArray()`, it creates an `Array`. It sorts it and then you have no way of accessing it at all. So you're like one line off from having this work. Colossal Lizard: So I'm still looking at the doc for `sort()` and it's still `static void`. So you said I was in the right ballpark in…. Intergalactic Avenger: So you're close but that's not quite it. You're almost there. Colossal Lizard: So looking at the docs it says `Java.util.Arrays.sort()` takes and integer `Array` and sorts that `Array` into descending order does not return any value. So I don't think I can do left hand assignments here. Intergalactic Avenger: Correct. Colossal Lizard: Since I'm sorting the array here… Intergalactic Avenger: Do you want to try storing the `Array` first, before sorting it so then you can have access to it later? Colossal Lizard: Oh okay. Okay. If I do `int[] temp` and I save it here, and then I would want to `Arrays.sort()` `temp`. Intergalactic Avenger: There you go, Colossal Lizard: And I would get `int[] res` equals...replacing `candidates` with `temp`. So this copies the `Array` beforehand then sorts it. Yeah okay I see, and then operates on the `temp`….`Object[]` cannot be converted to `int[]`. Intergalactic Avenger: Yeah this is a funny thing about overload of `Arrays.sort()` Colossal Lizard: Yeah, I wonder if I can cast it to `int[]` Intergalactic Avenger: I think casting it to an `int[]`.... Colossal Lizard: Nope that didn't work Intergalactic Avenger: There's actually two different `toArray()`s that you can call. One is the one that you have, I'm looking at this one. Colossal Lizard: Yeah yeah I think I'm calling the wrong version of `toArray()`. So maybe if I called `toArray()` like this….and this requires an `Object`….So I wonder if I can do…. Intergalactic Avenger: This is one of the more obscure parts of Java, being a little bit weird. So just to give you a little bit of hint here. So t in this case you want to be an `int`, because you're trying to make a `int[]`. So what you want to do is to pass it in as an `int[]`. So you have the right thing where you have `candidates` here but you need to pass it in as an `int[]`. So you could just do something like this: `new int[] {}`. You have to pass it in some kind of `int[]` to let it know that the type that you're going to return is an `int[]`. And it's super clunky, if you did this in another language it usually works out a little easier, but Java in this particular sense is just a bit clunky about the whole thing. Colossal Lizard: Sorry did you say something Intergalactic Avenger: No, go ahead. Colossal Lizard: Yeah I just remember something like this where I tried using `Arrays.sort()`...so I think it would be like `candidates.size()` or something. Let me try to run that. Whoops, `no suitable method found for toArray()`: `candidates.toArray()`. Well I am passing in an `int[]` now and I'm declaring the size of the `int[]` to be `candidates.size()`. Intergalactic Avenger: Wow. Colossal Lizard: No suitable method found for `toArray(int[])`. `Method collection is not applicable`. Intergalactic Avenger: Amazing. Well, what you might want to do...that's the other thing that's super clunky about, well why don't you first try the form that I put in, which is just an empty `Array`. So it's not really used to create the `Array`, it's just use to give it a hint about the type. See if that works. Colossal Lizard: Yeah, let me go back to what you have. See how that goes. Intergalactic Avenger: Oh it does not like that. My god, Java. Colossal Lizard: Yeah this is why for programming interviews just switching to Python, seems like its a lot easier to use. Intergalactic Avenger: So it's fine. We'll get through this. So what I'm thinking you could do is you could make it an `Integer`, like a capital “I” `Integer`, if that makes it any sense? Colossal Lizard: Capital “I” so the type? So like here: `new Integer[]`? Intergalactic Avenger: Yeah so it's a little clunky and then you have to make this one on the left also an `Integer[]` with a capital “I”. Colossal Lizard: Oh nice, okay. So then we got `1` for our output, which is what we expected. Let me conduct a bit more testing here, say `{1, 2, 3, 4, 5}`. I'll `add()` a few more numbers to my `Set` and I expect it to return `3`. Yeah I think it works. Intergalactic Avenger: It works pretty good! Okay this solution here with `Arrays` and such is definitely a bit clunky in Java. The one thing to think about is...sometimes it's a bit easier because...So I guess not a big deal but here you've used `Arrays`, the old style fixed `Arrays`. For some of these programming challenges it's sometimes easier to use `Lists` because there's more things you can do with them and they are a little bit easier to use like you don't have to do so many of these little tricks that we had to use like `toArray()` thing here. Colossal Lizard: Got you, so use `Lists`. I'll keep that in mind. Intergalactic Avenger: So here's a question: what is the runtime of this algorithm? Colossal Lizard: I'd say the runtime is `O(nlogn)` because the fastest comparison base sorts is `O(nlogn)` and I call `sort()` here, and that's the bulk of my complexity is when I call `Arrays.sort()` it'll use some kind of `quicksort` or `mergesort` and that'll take `O(nlogn)` time. Intergalactic Avenger: Okay, very good. And so `O(nlogn)`, do you think there's a way to get any faster than that? Colossal Lizard: So in order to faster than `O(nlogn)`, I'm assuming we'd want to have linear runtime. In order to have linear runtime, you'd need to scan your input `Array` once to find the third smallest. I'm thinking of somehow keeping some temporary variables and comparing them as we go. So I have `1, 2, 3, 4`. I'm thinking if I set a `temp` to be `1` originally...So I'm actually not sure if there's a way to do it in `O(n)` time, I know that if you find the maximum in this `Array` you can do it in `O(n)` time, but I'm not sure if you can find the third smallest is `O(n)` time, at least, nothing is jumping out at me. Intergalactic Avenger: So how would you find the smallest number out of a list? Colossal Lizard: If you find the smallest number, you would set it to the first element and then you would go through the rest of the list and compare it to the first element and if any were smaller, you would reset your smallest element, and towards the end you would find it and that would be `O(n)` time. Intergalactic Avenger: Okay, sounds good. So continuing with that algorithm, how would you find the second smallest? In that same kind of pattern where you look at the first element, you have this base case where you take the first element, you scan the list and each time you compare what you have saved with your temporary minimum, and you compare that with the value you're looking at and if it is the smallest you swap it. Now that's the algorithm for the absolute smallest, now how do you extend that to get the bottom two. Colossal Lizard: Okay so get the smallest two elements? Okay so maybe I could. Should I write pseudocode for this or just talk it through? Intergalactic Avenger: Just talk it through I mean like. I guess I'm saying that there's is a way to do it that's very similar to the way you just described. So you just described and algorithm where you start with a base value where you start with the first element and that becomes your temporary smallest variable. And you're always holding on to this and you hold on to that value and then you start scanning to the right, and each time you hit a new number you compare what you're scanning to what you're currently holding: the single number that you're holding. See whether that next number that you scanned is any smaller, and if it is, you rest that special value that you're holding onto as your current smallest value. So that's the algorithm that you just described, so can you think of a way to extend that same algorithm so that you can get the bottom two elements and not just the bottom one element? Colossal Lizard: Sure so assuming I had a set like `{4, 2, 5, 6}`, after one pass of the `Array` you could see that my smallest is `2`, and if I made a second pass through the `Array` and say that keep another temporary variable say a second smallest, and I compare that.. Why can't I just say if the second smallest is greater than the smallest...it would work for this case because I would just get `4` but if it were like...if the order was switched then it wouldn't work. So assume I have `int smallest` here and I already have that as `2` and I found that out already so I want to….So what if I set smallest to the first one at the beginning and use the same algorithm to find the `smallest` but for the second smallest I'm going to say that if next...I'm still struggling to see where I can get the next `smallest`. Intergalactic Avenger: Okay so let's go with this two pass idea. So you know that you've gone through it once you've found that the `smallest` was `2`, now let's just run through that same algorithm again, but remembering that the smallest number is `2`. So you start with `4`, that's your base case, then you go to `2`, and you see that `2` is smaller than `4`, maybe I should set that to be my current `smallest`. But can you use some piece of information to stop yourself from doing that? Like if you were to set the `smallest` to `2` again, then you would just find the smallest number again, that wouldn't be the correct answer for the second smallest. But you already know what the `smallest` is, so… Colossal Lizard: So maybe if I set my second smallest to `2` originally, and I'm saying if `Array[1]` is smaller than the current element and greater than the `smallest` then I want to set my `smallest`? Yeah so, in that case: `2` is not the `smallest` and I move on to `5` and then I say hey, is `5` less than `4`? It's not so...yeah I think I get the gist of the algorithm now.. Intergalactic Avenger: Yeah, okay so, let's code that up and see what we can do. [41:20] Colossal Lizard: Definitely. So I'm going to say, `static int` and return an `int[]` of size two. Intergalactic Avenger: How about you just return the third smallest, you can just rewrite over the code. I mean can you see how you would extend this from the second smallest to the third smallest? You can just erase or comment it out, but you can just keep this the same. Colossal Lizard: Sure, sure. `int smallest`. Intergalactic Avenger: Maybe want to keep that `temp`. Colossal Lizard: Yeah, so I'm going to say if `temp[i] < smallest`, set to `smallest`. So at this point I have my `smallest`, so let's try `2ndSmallest`. Originally that's the start of the array too as the base case. Sees like I'm doing some repeat work. If `temp[i] < smallest` and `temp[i] > smallest` then I'm going to reset my `2ndSmallest`. And I'm going to have the same idea for the third smallest, and I'm going copy stuff over and if I want to make sure that it's less than the `2ndSmallest` and if the `Array` that I'm looking at...Wait no I might have messed up somewhere here. Intergalactic Avenger: Yeah you're checking to see if it's at the same time, less than and greater than. Colossal Lizard: Yeah, so that's never going to be true. So what was I doing with this. So I have my `smallest` at `2`, so if `temp[i]`...so it should be `< 2ndSmallest` here and `temp[i] > smallest`. So here it should be `temp[i] < 3rdSmallest` and set my `3rdSmallest` here and return `3rdSmallest`. I think this is okay. Intergalactic Avenger: Let's not worry about the duplication yet. Let's try running this and see what happens. Colossal Lizard: So I get an error on line 49… Intergalactic Avenger: So I think the issue is that in Java, you can't start a variable with a number. Colossal Lizard: Oh, of course, right. Totally forgot about that rule. So I'm going to change this all to start with a character. And now let me try to run it again, it returned `1` which is not what I wanted because `1` is actually the smallest. So let me try to debug. So I know my `smallest` should be right, so here, `smallest` should be equal to `1`. Intergalactic Avenger: You can go ahead and print that out if you want, just to debug it. Colossal Lizard: Okay so `secondSmallest` is set to the one in the beginning and go through the rest of my `Array` and check if it's less than `secondSmallest` and greater than `smallest`. So here it should be `2`, and the next time I'm going through and I'm saying now it's `3`. `3` is not less than `secondSmallest`. Intergalactic Avenger: Now let's double check and see if `secondSmallest` is being correctly… Colossal Lizard: Yeah, yeah let me do some debugging. So well `secondSmallest` is definitely being set to `1` originally. Oh this should be greater than right? But then it would just be set to `5`. So my `secondSmallest` is definitely `1` originally. Intergalactic Avenger: So you can go ahead and add some more debug statements in the loop right there and help figure out what's going on in there. Colossal Lizard: So let me try to, maybe I'll move this guy here and every iteration of the loop I'll print out `secondSmallest` and also the current element that I'm looking at. Let me run it now. So it seems that it's never set, and that is because...well I think this is the case because the elements are sorted and you find `smallest` element at the beginning. Intergalactic Avenger: So you've just hit on a very interesting case right? As you started, you happened to unluckily pick the `smallest` element, and that's not a valid candidate. So here's the idea with the first round of the loop was you said: in my loop, I'm starting and I'm going to set it to the `smallest` is of what I've seen so far, and if I don't see anything `temp[0]` is definitely the `smallest`. So for the loop is correct, but the second loop you initialize the value to something that's already lower than what's a valid value so it's kind of a funny edge case. So you wouldn't have run into this in any other ordering of the numbers, but you ordered it in just the right way to have this edge case come out. So that's fine, you only have to make a pretty small adjustment. So what you've done is you accidently set the value of `secondSmallest` to an invalid value. It can never be that, so can you add something to your if statement to check something to make sure `secondSmallest` gets updated to something valid now? Colossal Lizard: Yeah, so the problem is `secondSmallest` is also just the `smallest`Intergalactic Avenger: The if statement is basically saying if that thing holds, then you need to update `secondSmallest` and make it something else. So in your first iteration…. Colossal Lizard: Or you know, `secondSmallest` that's also equal to `smallest`, then you want to… Intergalactic Avenger: Right. Colossal Lizard: Gotcha, thanks for that. Then I would kind of need to do the same thing for the `thirdSmallest`. So here I would say or `thirdSmallest <= secondSmalleset`. So here my `thirdSmallest` is `1` originally but I'm going through the rest of my `Array` and saying and hey if you're less than or equal to `secondSmallest` then I want you to update. So let's try this out. Intergalactic Avenger: Okay, very good. So what's the runtime of this new algorithm? Colossal Lizard: So this new algorithm is. Let's say the runtime of this would be `O(n)` because you're going through the array three times but you're never constant so it's still `O(n)` and it's better than `O(nlogn)` as soon as you get larger and larger `Arrays`. Intergalactic Avenger: Awesome, very good. I think we're just out of time. So that's all I have for today, and did you have any questions for me? Otherwise I will leave some feedback on the platform with tips and stuff like that. Colossal Lizard: Yeah, I thought this was really cool. I've actually never tried this kind of in person practice interview before and definitely help me a lot. So do you get paid to do this, or are you like a volunteer or something? Intergalactic Avenger: Oh no, this is a paying gig. But mostly I do it because I want to help people getting interviews. I've done many many interviews in my day and they're kind of scary when you're not used to them so want to do what I can to help people get through them. And I think that when you first get started you sort of trip up over little things but if you practice you smooth out a lot of the rough edges so it's something I like to do, help people out. Colossal Lizard: Cool, this definitely helped me out a lot. Just another question that I had was: I knew we spent a lot of time kind of doing the `Arrays.sort()` thing in Java and that was not the main focus of the algorithm and in an interview I wouldn't really want to be wasting that time when the time could be better spent finding the optimal solution or picking and algorithm. Have you found that Java is maybe not the best programming language to use and do you prefer Python or something? I know a lot of my friends are doing that. Intergalactic Avenger: So I definitely would say: stick with whatever you're most comfortable with, but whatever you're most comfortable with make sure that these things like sorting and Array or changing different types: turning a Set into a List and back again and these kinds of things. Make sure you have them down packed, so you can do them quickly and easily and you don't even have to think about them, you just start typing. That being said, it is a lot simpler in Python: like literally you would have just say sorted and it would have given you exactly what you were expecting to see the Java thing with half the effort. If you're just getting started in both, I would say it's definitely worth it to play around in python a bit. But when push comes to shove if you're actually doing an interview, definitely stick with the one you're most comfortable with, because that's going to be the one, like you said, you want to focusing on the algorithm and not focusing on these little detail and using the language you're most comfortable with will help you with that. Colossal Lizard: Gotcha gotcha yeah thanks for the advice. Yeah this is great, thanks so much it was great, Intergalactic Avenger: Yeah no problem, you have a great rest of your night okay? Colossal Lizard: Alright you too sir, alright thank you. Intergalactic Avenger: K, bye Colossal Lizard: Bye.