Java Interview with a Google engineer

Watch someone solve the third order statistic of a set problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Third order statistic of a set

Interview question

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

Interview Feedback

Feedback about Colossal Lizard (the interviewee)

Advance this person to the next round?

How were their technical skills?

2/4

How was their problem solving ability?

2/4

What about their communication ability?

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

How helpful was your interviewer in guiding you to the solution(s)?

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!

Interview 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.

Colossal Lizardoom break]

Colossal Lizard

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<Integer>. 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<Integer> 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<Integer> 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.

Colossal Lizard

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.