The number with the biggest number of repetitions within an array

1
votes

I was asked an interview question which asked me to return the number with the biggest repetition within an array, for example, {1,1,2,3,4} returns 1.

I first proposed a method in hashtable, which requires space complexity O(n). Then I said sort the array first and then go through it then we can find the number.

Which requires O(NlogN)

The interviewer was still not satisfied.

Any optimization?

Thanks.

1
algorithmsorting
Bucket sort still requires O(n) space, and the interwiever was not satisfied with it, it appears. – 3yakuya
do the number in array has a scope? – Tim
They weren't satisfied with the hashtable solution, that runs in O(n), you can't beat that – aaronman
Maybe it was about the space complexity, also O(n) for hashtable. – 3yakuya
@Byakuya I'm pretty sure you can't do better than O(n) space if you want O(n) time, and sorting can use no extra space – aaronman

1 Answers

4
votes

Interviewers aren't always looking for solutions per se. Sometimes they're looking to find out your capacity to do other things. You should have asked if there there were any constraints on the data such as:

  • is it already sorted?
  • are the values limited to a certain range?

This establishes your ability to think about problems rather than just blindly vomit forth stuff that you've read in textbooks. For example, if it's already sorted, you can do it in O(n) time, O(1) space simply by looking for the run with the largest size.

If it's unsorted but limited to the values 1..100, you can still do it in O(n) time, O(1) space by creating a count of each possible value, initially all set to zero, then incrementing for each item.

Then ask the interviewer other things like:

  • What sort of behaviour do they want if there are two numbers with the same count?
  • If they're not satisfied with your provided solutions, try to get a clue as to where they're thinking. Do they think it can be done in O(log N) or O(1)? Interviews are never a one-way street.

There are boundless other "solutions" like stashing the whole thing into a class so that you can perform other optimisations (such as caching the information, or using a different data structures which makes the operation faster). Discussing these with your interviewer will give them a chance to see you in action.

As an aside, I tell my children to always show working out in their school assignments. If they just plop down the answer and it's wrong, they'll get nothing. However, if they show their working out and get the wrong answer, the teacher can at least see that they had the right idea (they probably just made one little mistake along the way).

It's exactly the same thing here. If you simply say "hashtable" and the interviewer has a different idea, that'll be a pretty short interview question.

However, saying "based on unsorted arrays, no possibility of keeping the data in a different data structure, and no limitations on the data values, it would appear hashtables are the most efficient way, BUT, if there was some other information I'm not yet privy to, there might be a better method" will show that you've given it some thought, and possibly open a dialogue with the interviewer that will help you out.

Bottom line, when an interviewer asks you a question, don't always assume it's as straightforward as you initially think. Apart from tech knowledge, they may be looking to see how you approach problem solving, how you handle Kobayashi-Maru-type problems, how you'll work in a team, how you'll treat difficult customers, whether you're a closet psychopath and endless other possibilities.