Most Frequent Integer (Java)

Watch someone solve the most frequent integer and pairs of integers sum 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

Most frequent integer and pairs of integers sum

Interview question

1) Find the most frequent integer in an array 2) Print out pairs of numbers in an array that sum to N 3) Find the only integer that only appears once in an array in constant space and O(n) time

Interview Feedback

Feedback about Propitious Bear (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Great job on the interview. If anything, I wish I had asked you a slightly more challenging question. My main suggestion is to avoid cleverness in interview questions as much as possible -- in part 1, you used n++ when ++n would have been correct, but n + 1 is the simplest (and you did make that change after finding the bug.) It would have saved time to just write the code the simplest way to begin with. This isn't a big deal, but when solving a more complex problem, trying to be clever can trip you up in other ways. In part 2, I didn't press you on this, but sorting doesn't really buy you much because (even if you printed out the pairs, which was what the problem specified, rather than returning a list), MergeSort uses O(n) space. You can get O(n) space and O(n) time by using a similar approach to what you did in the first problem (using a map). That said, the 2-pointer solution is elegant. I also like that you thought of arithmetic overflow when asked about the edge cases. Good luck on your future interviews!

Feedback about Paisley Wallaby (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

4/4

Not much really, you were really helpful! thank you for the third hard question, it really got my brain going and I truly enjoy those type of questions. This isn't really a great feedback , but I thought you you were a great interviewer.

Interview Transcript

Paisley Wallaby: Hi can you hear me okay?

Propitious Bear: Yeah I can hear you fine, how are you?

Paisley Wallaby: Good, how are you?

Propitious Bear: I 'm doing well, I 'm doing well.

Paisley Wallaby: Great, what language would you like to use?

Propitious Bear: Java, is that okay with you?

Paisley Wallaby: Yep.

Propitious Bear: All right.

Paisley Wallaby: Okay, so this question has a couple parts, so this is the first one. If it seems easy, just think of it as a warm-up. So given an array of integers, find the most frequent integer. So in other words write a method that takes an array of integers and returns an integer. How you handle the empty array is up to you. You can throw an exception, that 's not too important to me. So for example so if you were given 1 2 3 3, you would want to return 3. If there is no most frequent integer, if they all occur the same number of times, you can return any one.

Propitious Bear: Okay.

Paisley Wallaby: And the array doesn 't have to be sorted, so if you have like... Um yeah so let 's start with that. Um let 's see, so try to think out loud as much as possible and we 'll go from there.

Propitious Bear: Alright, sounds good. Let 's see, so the array is not sorted. I mean obviously we could do a one-pass thing. We could do in O(N) just set up a counter and just every time we see a number we could store the frequency into the set, the map sorry, so we could have <integer, integer> let 's say, the key being frequency. Actually... and then we 'd have to iterate through the map. That wouldn 't work very well, it 'd be very ugly. Let me see. So if we 're given that array, we could... when we do our pass through it once... Okay since it 's not ordered, that wouldn 't work. I 'm sorry because I was thinking about having a second array that would just hold the frequency of each number, but since we could have a number that 's outside the range of the array that would not work. Now... so... we could if we pass through it once, so we can find information of the frequency of each numbers, getting the frequency we can either store in a map and iterate through a map. I mean could do that, although that 's not very efficient in terms of memory.

Paisley Wallaby: Well let 's just try that first, and then we can figure out how to write a more efficient solution because it 's good to start from something that works and optimize it.

Propitious Bear: Sounds good, alright. So let 's say we 're given a map... I will call it our frequency hashmap, and just remember this is a key, it 's frequency. Actually that doesn 't really matter, I can figure that out after. Now we can just literally iterate through the array. Actually no, my key would be the number. Now we could have the integer i = 0. Yeah I forgot, I 'm sorry I 'm used to LeetCode. Sorry. Now going through this, loop we 're going to get all the frequencies, so in this case we 'd have put 1 : 1, 2 : 1, 3 : 1, then we 'd say we contain it, so we see it a second time. Alright so now we have all the frequencies in there and what I can do is that I can literally just iterate through it, I could say int number and...

Paisley Wallaby: Um, yeah you can have any integers in the array.

Propitious Bear: Now we say, so we would need to do... Sorry, I change the value because the value is a frequency and our number would be to get the key and then we 're going to keep track of our frequencies, so frequency is equal to entry.getValue(). There you go. So now we would do... so this map here... ah we should be, let 's just go through it. So we go through the array length and all, then we get the key if it exists. Retrieve the frequency number and with the key here and then we add, we increase by 1, now otherwise we insert the key for the first time with 1, and then we iterate through the map and we first instantiate frequency to negative values since we don 't have a frequency at all, just to be safe and then we say if that current value is greater than our current highest frequency, we just store that number and that frequency and we 'll keep iterating and we return the number. So now in this case you have 3 & 2, so say... we 'll say 1... while 1 is greater... and then we 'll store 1 : 1, then two won 't get store because it 's not going to be higher than and then three will, since we 're going to return three. Okay. I think that should work.

Paisley Wallaby: Okay.

Propitious Bear: We can try it and just to be sure. I can try to run this if it works.

Paisley Wallaby: Sure.

Propitious Bear: Apparently I forgot a bracket. Let me see where did I forget that bracket. Oh sorry sometimes I don 't always remember the exact syntax for...

Paisley Wallaby: Yeah no problem and you 're welcome to look up things like this.

Propitious Bear: Alright. Oh look at that, I have an error. It doesn 't return the right number. Let me see. What did I do wrong. I put the number in there and iterate through it. Three should have two. Okay I 'm not used to debugging in interviews like this.

Paisley Wallaby: Yeah, I divided up a part of it so.

Propitious Bear: Let 's try, we 're going to get... since we know we have three, we 're going to get three, to see if we get every time, oh look at that, I have a mistake. Yeah, I 'm not adding them. Oh whoa... oh yeah I 'm not at I 'm not re-adding it here. Yeah, this is not adding itself.

Paisley Wallaby: You see why that change fixed it?

Propitious Bear: Yeah because I 'm adding the one afterwards, I should have done here.

Paisley Wallaby: Yeah.

Propitious Bear: I added one before and I 'm adding the one after I add in the map.

Paisley Wallaby: Yeah you can use um... you could put the plus plus before, but I mean I think it 's clearer the way you just wrote it, so um good. So let 's see. Excuse me. So what 's the time and space complexity of your code?

Propitious Bear: Space complexity will be O(n), since the array... I mean I 'm storing an extra map here, and that 's always going to be size depending on the array. And the complexity should also be O(n) since you know we 're iterating once for the array and then once for the map. It 's definitely not the most efficient, I 'm just blanking out right now on how to get the highest frequent number.

Paisley Wallaby: Yeah well I have another part of the question, so let 's go on to that before we think about optimizing it. Um let me, let me think for a sec. Okay let 's try this, it 's kind of similar but not entirely. So I 'll just add this as part one. So part two, given an array of integers and an integer n, print out all the pairs of integers whose sum is n.

Propitious Bear: Okay.

Paisley Wallaby: So your your method can return void, it doesn 't have to return a list of pairs or anything, just print them out. So for example if you 're given... the output should be 1 9 if you 're given something like 1 9 1 9 and 10 it should print 1 9 new line 1 9, the formatting, I 'm not picky about as long as it 's clear and if you 're given something like 1 9 1 and 10, you would only want to print out 1 9 once, you wouldn 't want to like you know use the 9 more than once, if that makes sense? So basically like every... when you have duplicate numbers, you 're allowed to use it and then it 's sort of off limits to be used again. So I hope you can see the difference between the 2nd and 3rd examples.

Propitious Bear: Sounds good and are we only doing addition, or do we also count subtraction, because here we could have 12 and minus 2?

Paisley Wallaby: Um yeah, that 's a good question. So let 's just assume for simplicity that all of the arrays are... sorry all of the integers are non-negative and you can also assume that n is positive.

Propitious Bear: Okay, so can I take let 's say 12 - 2 and assume that this pair... Okay one way we could do this actually, we could sort it. I mean we 've used arrays.sort() function in Java and we could just use binary search and find two numbers whose sum adds to n. So we could have two pointers, one that starts at the end and one that starts at the beginning, and then we can increase left and right seeing what we want. I mean for instance, I 'm going to write under, so we could sort this. Then we started at 12 + 1 we see it 's 13, so we know that we want something bigger, we can move left, or actually just computed to. Since actually no, we should say if the number is bigger than our sum, then our target number, we move left, so in this case it 's 9, so it 's 1 + 9, then that would give us 10. Let 's say we want something like... so you wanted something like 10 here, do we have 10. So 10 + 1 would give you 11 and oh yeah so since this sum is above, we would move left and then it 's 9 + 10, but let 's say we actually wanted um... Let 's say we wanted this. So 12 is bigger than 11, 11 is not bigger than 11, but 11 plus 1 gives us 12, so we move to the left, since it 's above our target. And then we would have 9 and 1 + 9 would be our target, so and we could try that.

Paisley Wallaby: Okay let 's do public static return an array...

Propitious Bear: Okay ah so we 'll say first of all we 'll say arrays.sort(array). I believe Java I uses merge sort on and primitives. Okay so we sorted and we say... okay yeah we 'll just do a another map type integer... I like somehow zoned out, I forgot about that part. When we have our duplicate here, if we store in the map we 're going to have a collision on the 1 : 1, we could have 1 9 9 and if you have a repeated number we can just repeat the key or we can just say... okay that 's good. Okay so new hash map, and then we can say if it 's equal to target we 'll say... Kind of scared we 're going to be stuck in a while, in an infinite loop. So let 's see if that works. So I have 19 1 2 9 12. We 're going to sort it. Then we 're going to start at zero, which is one, and it 's going to be three. So we 're going to say if this is going to be twelve on the beginning, so if the third index is greater than the target, we 're going to reduce this by one, this should go to two, then we 're going to continue. Then we 're going to say 9 + 1 is equal to 10. Then we 're going to say if 10 is equal to target, do this. I 'll add it to the list. Otherwise then we 're going to keep going through our loop, and then it 's going to be I think it will be two and two, so 2 + 2. Oh actually, our two numbers allowed to add to themselves to the target, let 's say we have a five here.

Paisley Wallaby: Sure yeah, you can have that. So for example, if we had... you would want print out 5 5 in that case.

Propitious Bear: So we can 't add a number by itself, it has to have a duplicate of it.

Paisley Wallaby: Right so if you had like 1 2 5 10, this would print out nothing.

Propitious Bear: Sounds good okay. So okay, so now say we have this here, then we 'll add 1 2 then we have to say we had 1 2 1 5 9 12, we 'll add 1 & 9 here then we 'll increase by 1 minus 1. And okay, so now we should do... Okay, might get stuck in a loop, I 'm not too sure I 'll try to run this and see. Also I have if, where did I put that. Oh my bad. Okay that 's great, I think I returned array, what did they return to. Let me see. Okay I 'm printing. Sorry, I 'm quite confused about what 's going on. It 's not even printing the right array. I have one five nine and passing the array here. It 's printing it all out. Okay so you 're all in there. Now I 'm doing I... Yeah I 'm really stumped at this one, I don 't know what 's wrong with my code.

Paisley Wallaby: Let 's see.

Propitious Bear: I 'm not able to output the right numbers when I 'm getting my base case.

Paisley Wallaby: Can you just print out what the list is using toString, at the beginning and the end if you want.

Propitious Bear: Actually that could be a smart idea.

Paisley Wallaby: You can just use like at the end, you can use ls.toString().

Propitious Bear: Oh yeah.

Paisley Wallaby: Or it 's a value, you have to print it out. You have to print out...

Propitious Bear: Yeah, I 'm kind of stumped at this one...

Paisley Wallaby: So you 're returning the result.

Propitious Bear: Oh my god, I...

Paisley Wallaby: Oh I see, okay I didn 't see that either.

Propitious Bear: I think I 'm still asleep.

Paisley Wallaby: Understandable.

Propitious Bear: There you go.

Paisley Wallaby: Okay great. And do you want to try the test cases with duplicate numbers?

Propitious Bear: Let 's try it. So my list has it, but apparently I 'm printing it twice.

Paisley Wallaby: Yeah you are printing it twice, so that 's good. And try the one with the 1 9 1 case.

Propitious Bear: 1 9 1 case. Yeah. I went out of bounds, look at that. That makes sense, since I moved left and right here, one and one. I had to... wait that should have kept you out of bound for like three... let 's see... yeah, I have 1 1 9. Now we say, if we go through here...

Paisley Wallaby: Cool, can you think of any other edge cases that we might want to test?

Propitious Bear: We can try a... for fun we can see if I handle negative number.

Paisley Wallaby: Sure.

Propitious Bear: Let 's see, five shouldn 't work. And look, empty. Other edge cases... could we possibly get arithmetic overflow, that could be actually something if our target is integer, this will not work actually. We 're going to get an arithmetic overflow, and I should actually cast it to long if we wanted to catch that. Let 's say we... I don 't know what the value is by heart, let me go check.

Paisley Wallaby: Yeah no problem.

Propitious Bear: Yeah it should work I think usually the... oh it 's my bad, copied it from Google. Yeah this should work... Oh no, this shouldn 't work... Yeah okay apparently it worked. I do know though that it would be safer to cast it into longs here and printing it out after because it happened to me in the past, I do know arithmetic overflow could be an issue, depending on the case, but I can 't think of one right now.

Paisley Wallaby: Sure no problem. Um good observation. Um now what are the time and space complexity of this code.

Propitious Bear: Well doing this in mergesort, so O(n log n) would be the worst case scenario I think, so this would be O(n log n), ordering it and going through it, so the time complexity would be O(n log n) and in terms of space since we 're having an extra list and would the O(n) space too.

Paisley Wallaby: Okay um and let me think, yeah that 's fine. Um let 's try one more question and then that 's probably all we 're going to have time for, so part 3. Given an array of integers, you may assume that every element appears twice except one, so a length must be at least 3, return that one element. For example, if you had 1 9 9 1 5 12 12 you 'd want to return five, if you had 12 12 1, you 'd want to return one. And the twist here is, try to do this in constant space. So it would be easy to do this using a map similar to the first one, but there 's a way to do it in constant space, so see if you can think about how to do that. And this is a bit of a trick, so if you don 't get this it 's not a big deal, but we 'll see if we can get there.

Propitious Bear: All right, well you 're cutting my legs here, not using a map. Yeah okay let 's see. Um okay I mean we could order it. If you order it then you have all the duplicates next to each other and could do it in one pass, right? So if we have one element that doesn 't repeat itself then that one element is not going to have a neighbor that 's itself, so that could be one thing. That 's the one I can think of, I mean let 's say we order it, we have... but again I probably could do this in n, so let me see it after I do this, that we have it in order. Yeah this, will you just say, you know, if you check its neighbors, if there 's i + 1 and just increase and increase and increase until it 's both neighbors aren 't itself. Uh but, let 's see what we could... that doesn 't require us to sort this array. Um...

Paisley Wallaby: Yeah I should say, also, constant space and O(n) time. I should have said that, but yeah you don 't want to sort it.

Propitious Bear: Alright cool. Okay Let 's see... so if we have constant time, that means we have one pass through this array. Okay, having two pointers wouldn 't help either, and it 's not sorted and then even that if we move to the next here, one still has some duplicates. Um wait... If you have one, could say we keep track of the total that we have up to now if that helped us. Say we have ten then we have 19 we know that... I 'm think I might have something... it might be far-fetched though. So let 's say we keep track of the total right? We have one. Now we add nine. We have ten. So okay wait... Following the water right now. We have ten and when we add nine... Okay so we can either have an odd or even number. If two different number add each other, so if you add two different numbers, let 's say you have 1 + 9 = 10, then you know that these two numbers are not the same and it gives you an even number and if you add this number... if you had an even to an odd number, it should tell you that that new number has not been met. So in that sense, 10 + 9, but 9 has been added. Doesn 't work.

Paisley Wallaby: I think it 's a good thought, but since you know you could have a list where all the numbers are even, I 'm not sure that would help. A hint is, there 's a way you can do this using bit manipulation.

Propitious Bear: Oh God. You could have... this would be easier in Python. You could do an xor I think. I think it 's xor, I 'm not too...

Paisley Wallaby: Yeah, it is xor.

Propitious Bear: I think if I 'm going... and then you add it to the total, then it should give you... oh god this one I won 't be able to code. I can tell you bit manipulation is very tedious. You could have the 1 xor 9, and then if you do... I think it 's this in Java... No, the xor is that... God... If you have the xor with the one and nine, this should give you one zero... I don 't think I 'd be able to solve it with bit manipulation to be honest.

Paisley Wallaby: Well um you 're close though. The observation that 's key is like does it matter in what order you XOR the elements together, does that affect the result?

Propitious Bear: You mean in order and if I start from the beginning, in the middle, or the end? Or you mean if I...

Paisley Wallaby: That 's right. That 's what I mean.

Propitious Bear: Oh... well no I mean if you XOR everything together, you should end up with 0 like this since they 'll cancel out at the end, you should have 0. I think. Because 1 xor 1 cancels each other, this cancels each other, this cancels each other. The issues I 'm having is that you can lose track of the bits, no if you have here, you have... actually no, you don 't... oh yeah because if 9 has a 1, let 's say you do 9, which would be 8 plus 1. This would give you 9 xor 1 would canceled out. And then you 'd say that the one is a lone number. U wouldn 't it?

Paisley Wallaby: Remember you know every number but one occurs twice, so on the first um... let me think. Yeah so basically the one and nine cancel the other one and nine cancel. Sorry I 'm messing myself up. So the one and nine don 't cancel, but then when you eight, nine you 'll have the one left. The nine cancels out the one cancels at the one, and then you have one left. So yeah, so that 's the trick. It 's kind of a... I mean it 's not a great question, because it 's not that useful in reality, but I think it 's fun. Yeah so that 's it, that 's what I have. I think you did great. Do you have any questions for me?

Propitious Bear: Uh when you code this, um how for those bit manipulation, do you have any trick to when like you start shifting towards that train of thought? That 's the one thing that I can never wrap my head around, like I never think straight away, you know this is a bit manipulation problem.

Paisley Wallaby: Yeah I don 't know hmm... I think like when you 're asked to do stuff with integer, with you know an array or a list of integers and you 're asked to use constant space, I think looking for a trick with bit manipulation is a good hint. I 'm wondering, I 'm trying to think of a deeper reason why that is but... You know one thing that I 'm just thinking of now is that you know one way to implement a a map is using bit factors underneath, so does that tell you that anything where you can use maps you can use bits? Like maybe not anything, but maybe that 's a reason why it 's to come to mind. I 'm not sure.

Propitious Bear: It 's okay, I mean uh I do the constant space with the integer array does is true that it gives you a bit more it pushes you in the right direction.

Paisley Wallaby: Yeah.

Propitious Bear: Alright well that was all really, thank you very much for your patience.

Paisley Wallaby: Nice talking to you and have a good rest of your day.

Propitious Bear: Thank you, bye-bye.

Paisley Wallaby: Bye.