Implement Key Equality and Hashing
Updated
Problem statement
Implement value equality and a hash code for immutable keys used in a hash map. In this practice model, each key is an integer array.
Two keys are equal exactly when their lengths and every corresponding value are equal. Array identity does not matter.
For each key, start with h = 1 and update h = 31 * h + value for its values in order. After every update, keep the low 32 bits. Interpret the final value as a signed 32-bit integer.
Return [equal, firstHash, secondHash], where equal is 1 for equal keys and 0 otherwise. Equal keys must have equal hashes. Equal hashes alone do not prove equality.
Function
keyEqualityAndHashes(first: int[], second: int[]) → int[]Examples
Example 1
first = [1,2]second = [1,2]return = [1,994,994]The arrays have the same values. Each hash is (31 * 1 + 1) * 31 + 2 = 994.
Example 2
first = [0,31]second = [1,0]return = [0,992,992]The arrays differ, so equal is 0. Both hashes are 992, demonstrating a collision.
Example 3
first = []second = []return = [1,1,1]Both keys are empty and equal. No update occurs, so both hashes stay 1.
Constraints
- Each key contains from 0 through 10000 integers.
- Every key value is between -1000000000 and 1000000000, inclusive.
More London Stock Exchange interview questions
- Group Anagram StringsONSITE INTERVIEW · Seen Apr 2020
- Implement a Queue Using an ArrayPHONE SCREEN · Seen Feb 2020
- Lowest Common Ancestor in a Binary TreePHONE SCREEN · Seen Feb 2020
- Palindrome PartitioningPHONE SCREEN · Seen Feb 2020
- Two SumPHONE SCREEN · Seen Feb 2020
- Two Sum in a Sorted ArrayPHONE SCREEN · Seen Feb 2020
Similar questions at other companies
- List the Key and Value of Every Map EntryNewgen Software · ONSITE INTERVIEW
- Pizza Price CalculatorMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Cross-Day User Trust ScoresAffirm · PHONE SCREEN · ONSITE INTERVIEWAffirm interview questions
- Map and Accumulate Learning QueriesPalantir · ONSITE INTERVIEWPalantir interview questions
- Filter Pins by Excluded IDsPinterest · ONSITE INTERVIEWPinterest interview questions
- Best Average Student ScoreGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
- Longest Dictionary Word from Nine LettersGoogle · ONSITE INTERVIEWGoogle interview questions
- Two SumOptimus Information · ONSITE INTERVIEWOptimus Information interview questions
- Keep the First Key for Each Distinct ValueOneTrust · ONSITE INTERVIEW
- Two Positions That Add Up to a TargetDocuSign · PHONE SCREEN · ONSITE INTERVIEWDocuSign interview questions