hash would be appropriate for the general problem since the lookup times are faster than an array

Yeah I think that's basically what I did.

Did you ask if they were checking for the case if there is multiple numbers with equal repeating times.

Also javascript will round the answer if you have large numbers in your array and you won't get the exact number.

Yeah if it's tied as long as you returned one of the top #s that's ok.

If you want to maintain some additional state information, you can add an optimization of breaking out of the array iteration early when you know one value has such a large lead no other value can catch up.


Probably not worth implementing on your first run through the problem ( better to make sure you get a working solution and not confuse the person interviewing you), but mentioning these sort of things after you have finished can't hurt. Some some more advanced thinking.

What you might do is use indexOf to build an array of unique integers then from that figure out which number occurs most frequently.

Edit : for some reason I read it as max length. I guess you call this the functional way. Isn't that how all the cool kids are doing it nowadays?

@Craggoo: That functional version seems to have pretty bad runtime complexity though? I can't imagine array.indexOf having less than O(n) by itself, so this looks very much O(n^2). (But I'm terrible with functional runtimes,...)

Yeah, definitely use a hash. Indexing in an array is really bad if your input looks like [1,2,MAX_INT,3]. Esp if those are int64s

And you don't need to iterate over the map, see suzzer's code. Simply keep track of the highest count/value so far.

I like your original version better, but you could get rid of maxCount and replace with the slightly slower:

I guess i just find endless single if blocks / if - else blocks pretty ugly. The reality is that, if we're going purely for performance, a for loop will always be the fastest.

That algorithm seems to be pretty much optimal if space isn't a issue.

If space was expensive, you could bump it up to O(n log n) by sorting first then going over the sorted array to identify the largest count.

Had a few questions in the past where they'd come up with limitations like that, so just sayin'.

I'd do it like this in C#:

Might be a more efficient way of solving it tbh. Ordering might be a little slow.

Edit, here we are think this is good:

Edit: just saw that's what was done above me as well, doh!

Remember it was just the phone screen. Nobody wants to ask tough questions when a large percentage of people aren't going to be able to answer them and you'd have to sit through an awkward/painful process.

It probably depends on the interviewer, but I like it when someone describes the brute force answer at the start - especially if its reasonable.

My strategy is usually something like:

1. Make sure I understand the question (clarifying questions, diagrams, examples, whatever makes sense)

2. Figure out a simple-to-implement solution (usually brute force or other fairly obvious solution).

3. Point out if its really sub-optimal and spend a minimal amount of time trying to figure out a better solution. You can sometimes just discuss with the interviewer and see if the brute-force solution is reasonable. For example implementing O(N) is possibly ok, implementing O(N^3) is almost never a good idea.

4. Write code.

and all this is done in the span of... 30 minutes? 3 hours?

how long are these tech questions supposed to last?

30-60 minutes at most.

has anyone read Cracking the Coding Interview? Is it pretty spot on for the types of things you should know for tech interviews? (such as below)

Was fiddling around with the Ruby track on codecademy the other day and ran into almost that exact question, except it was counting the frequency of strings. So that had a little more to it with formatting and splitting the words into an array. It's cool to know some of these lessons could be useful, if I remember them later on when I think I'm competent enough to be hireable.

It went a little something like this:

This sounds about right in terms of background knowledge but at the end of the day, you need to be able to solve problems on your own.

Edit: also, I don't think "Singleton/Factory" design pattern questions are that common during interviews - I'd replace that with Object-Oriented Design and Inheritance

Using hashes to find a common element in an array adds additional space complexity.

While an 8 element array isn't a terrible offender of space, consider:
arr = [0, 1, 2, 3, 4, ..., 999999998, 999999999, 999999999, 1000000000]
or something to that effect.

If you aren't allowed to solve it using a hash:
Sort the array.
Track a maximum count, maximum element, current count, and current element.
Start iterating through the array.
All you care about is whether the current element differs from the previous, adjusting current counts, comparing to max count, adjusting maximum element and max count if necessary.

Comparing your max count to the number of elements remaining could prevent iterating through the entire array. If max count is greater than elements remaining, terminate your loop/return max value.

This approach adds additional computational complexity but saves on the space complexity.

I think both approaches have trade-offs and is something worth bringing up in an interview.

Would anyone mind explaining hash tables to me like I'm 5?

A hash table is basically an associative array that is optimized for faster look-up times. Say you had an array that mapped people to their phone numbers:

PhoneNumbers["John Smith"] = 555-453-4567
PhoneNumbers["Abigail Adams"] = 555-973-4170
PhoneNumbers["Michael Turner"] = 555-779-0340
...

Imagine there are thousands of entries. If you want the entry for "Michael Turner", you're going to have to search through the keys to find it's index. There could be thousands and thousands of keys, so this might take a while.

What a hash table does, instead, is to use some function to compute the index for each key. This way, when it's time to look up "Michael Turner", you just run the hash function to find his index and then access it directly, without searching through the array. Behind the scenes, your array would look something like this:

PhoneNumbers[d131dd02c5e6eec4] = 555-453-4567
PhoneNumbers[55ad340609f4b302] = 555-973-4170
PhoneNumbers[d8823e3156348f5b] = 555-779-0340

And your hash function would work like this:

SomeHashFunction("Michael Turner") -> returns d8823e3156348f5b

This method also allows for insertions/deletions into the array without worrying about sorting/reordering. For more: http://en.wikipedia.org/wiki/Hash_table

Really awesome explanation thank you very much.

Huh, look what I just got in my inbox: a variation on Suzzer's question:

https://www.interviewcake.com/questi...e=weekly_email

They first ask for a single duplicate, then ask for finding all duplicates, which I suppose can be then extended to most duplicates. The article is a bit tricky, but an interesting solution.. and what do you know, it uses plain old non-functional programming.

Seems like the non-hash approach I suggested as an alternative would work - with slight modifications of course.
By sorting and then iterating, you don't have to care about the duplicates, only when the elements change.

What do you use to sort? Lodash? I talked about sorting during the code screen but didn't want to mess with it.

Goddamit there is an array.sort() method. I actually mentioned that in the meeting and the dude said there was no native method. I should downgrade him.

I even included array.sort in my solution