Google | Phone | Repeating Integers
Anonymous User
2550

Google Phone Screen Feb 2020
Interviewing with 2.5 yrs exp probably for L4

Implement a function such that given a list of integers and list of frequencies, returns true if the number of duplicate integers maps to some frequency. Eg.

[1, 2, 3, 4] and [2] --> false -- because there is not 2 of anything
[1, 1, 2, 3] and [2] --> true -- because there are 2 1s
[1, 1, 2, 3] and [2, 2] --> false -- because there are 2 1s, but not 2 of anything else
[1, 2, 3, 4] and [1] --> true -- because there is 1 1, or 1 2, etc.
[1, 1, 1, 1, 1] and [2, 2] --> true -- because we can satisfy frequency count w number of duplicate 1s

boolean hasRepeats(List<Integer> numbers, List<Integer> repeats)

Took forever to solve it, and didn't even really by the end.. think this was a warm up. Definitely my bad for not leetcoding hard enough. Kicking myself..
My soln -

  • Iterate over numbers and get num duplicates by hashtable
  • sort both lists (num duplicates and repeats)
  • for every repeat
    • get greatest num duplicate (first item in the list)
    • if repeat greater than num duplicates, return false we're done, nothing can satisfy
    • else subtract repeat from num duplicates, reinsert that value into list, advance num duplicate pointer

things I missed (among others): don't reinsert if value is 0, remove num duplicate list item so list doesn't become very long

Comments (18)