Mutable Points in a Hash Set and a List
Updated
Problem statement
A point has two integer fields, x and y, and both can be changed after the point is created. Two points are equal when their x values are equal and their y values are equal. The hash of a point is 31 * (31 + x) + y, computed from its current fields. This is the value Java's Objects.hash(x, y) returns.
You keep one hash set and one list of points, both empty at the start, and run the operations in operations in order. Points are numbered 0, 1, 2, ... in the order they are created. Both collections hold the points themselves, not copies, so a change to a point shows up wherever it is stored.
The hash set. When a point is added, the set stores an entry with the point and the point's hash at that moment. A stored hash never changes, even if the point changes later. To look up a point q, the set computes the hash of q's current fields and checks only the entries whose stored hash is equal to it. Such an entry matches q if its point is currently equal to q.
["ADD", "SET", id]adds an entry for pointidonly if no entry matches it. It returns"true"if it added one and"false"otherwise.["CONTAINS", "SET", id]returns"true"if some entry matches pointid, and"false"otherwise.["REMOVE", "SET", id]removes the earliest added entry that matches pointidand returns"true". If no entry matches, it returns"false".["PRINT", "SET"]lists the points of all entries, in the order the entries were added.
The list. It works only with equality and ignores hashes.
["ADD", "LIST", id]appends pointidand returns"true". The same point can be in the list many times.["CONTAINS", "LIST", id]returns"true"if some element is currently equal to pointid, and"false"otherwise.["REMOVE", "LIST", id]removes the first element that is currently equal to pointidand returns"true". If there is none, it returns"false".["PRINT", "LIST"]lists the elements in order.
Points. ["NEW", x, y] creates the next point with those fields. ["SET_X", id, v] sets the x of point id to v, and ["SET_Y", id, v] sets its y. These three operations return nothing.
A print writes each point as (x, y), separates them with a comma and a space, and puts square brackets around the list, for example "[(2, 1), (0, 32)]". An empty collection prints "[]". All numbers in operations are strings.
Return the strings returned by the ADD, CONTAINS, REMOVE and PRINT operations, in order. This is how Java's HashSet and ArrayList behave when a point changes after it was added; the set prints in insertion order, as a LinkedHashSet would. You may write the simulator in any supported language.
Function
simulatePointCollections(operations: String[][]) → String[]Examples
Example 1
operations = [["NEW","1","1"],["ADD","SET","0"],["ADD","LIST","0"],["CONTAINS","SET","0"],["CONTAINS","LIST","0"],["SET_X","0","2"],["NEW","2","1"],["CONTAINS","SET","1"],["CONTAINS","SET","0"],["CONTAINS","LIST","0"],["REMOVE","SET","0"],["PRINT","SET"]]return = ["true","true","true","true","false","false","true","false","[(2, 1)]"]- Point 0 is
(1, 1). It goes into the set with the stored hash31 * (31 + 1) + 1 = 993, and into the list. BothADDcalls and bothCONTAINScalls return"true". - After
SET_X, point 0 is(2, 1), whose hash is31 * (31 + 2) + 1 = 1024. Point 1 is a new(2, 1), also with hash1024. - The only set entry still has the stored hash
993, so neither point 1 nor point 0 is found in the set: two"false"results. - The list compares fields only, and its element is now
(2, 1), soCONTAINSon the list returns"true". REMOVEon the set finds nothing and returns"false", so the set still prints the changed point:"[(2, 1)]".
Example 2
operations = [["NEW","1","1"],["ADD","SET","0"],["SET_X","0","0"],["SET_Y","0","32"],["CONTAINS","SET","0"],["NEW","0","32"],["CONTAINS","SET","1"],["ADD","SET","1"],["PRINT","SET"]]return = ["true","true","true","false","[(0, 32)]"]- Point 0 starts as
(1, 1)and is stored with hash993. - It is changed to
(0, 32). Its hash is31 * (31 + 0) + 32 = 993, the same as the stored one, and the fields match, soCONTAINSreturns"true". - Point 1 is a new
(0, 32): same hash and equal fields, so it is found too, andADDreturns"false"without adding a second entry. - The set prints
"[(0, 32)]".
Example 3
operations = [["NEW","1","1"],["NEW","2","1"],["ADD","SET","0"],["ADD","SET","1"],["SET_X","0","2"],["PRINT","SET"],["REMOVE","SET","1"],["PRINT","SET"],["ADD","LIST","0"],["ADD","LIST","1"],["REMOVE","LIST","1"],["SET_Y","1","5"],["PRINT","LIST"]]return = ["true","true","[(2, 1), (2, 1)]","true","[(2, 1)]","true","true","true","[(2, 5)]"]- Both points go into the set:
(1, 1)with hash993and(2, 1)with hash1024. AfterSET_X, both are(2, 1), so the set prints"[(2, 1), (2, 1)]". REMOVE SET 1looks for hash1024. Only point 1's entry has that stored hash, so that entry is removed, and the set prints point 0:"[(2, 1)]".- The list holds point 0, then point 1.
REMOVE LIST 1deletes the first element whose fields equal(2, 1), which is point 0. - Point 1 then becomes
(2, 5), so the list prints"[(2, 5)]".
Constraints
1 <= operations.length <= 500- Every operation has one of the forms above, and every
idis the number of a point that was already created. - Every
x,yandvis an integer from-1000to1000, written in decimal with no leading zeros and no plus sign.
More Millennium interview questions
- Calculate the Half SpreadOA · Seen Sep 2026
- Debug the Impact ModelOA · Seen Sep 2026
- Debug the Risk-Limit QuoterOA · Seen Sep 2026
- Hedge Inventory with Return CovarianceOA · Seen Sep 2026
- Quote One RequestOA · Seen Sep 2026
- Risk Limits and Inventory SkewOA · Seen Sep 2026
- Track the Book and Mark Final PnLOA · Seen Sep 2026
- Clean the TapeOA · Seen Sep 2026
- Client Markout AnalysisOA · Seen Sep 2026
- Debug Fair-Value LookupOA · Seen Sep 2026
Similar questions at other companies
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- LRU CacheServiceNow · PHONE SCREEN · ONSITE INTERVIEWServiceNow interview questions
- Rectangle Point Coverage CountsOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- File Storage ServiceCresta · PHONE SCREENCresta interview questions
- Camel CardsRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Return Every Matching DecryptionDuolingo · PHONE SCREENDuolingo interview questions
- Corporation Reporting LinesMicrosoft · PHONE SCREENMicrosoft interview questions
- Key-Value Store on a Block DeviceLambda · PHONE SCREEN
- LRU Key-Value Cache OperationsCohesity · PHONE SCREEN