FastPrepMutable Points in a Hash Set and a List
Problems/Mutable Points in a Hash Set and a List

Mutable Points in a Hash Set and a List

Millennium logoMillennium● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a video interview at Millennium for an experienced full-stack engineer role. One of several Java code-reading questions used a point class whose hash and equality both use its two fields. The program put one point into a hash set and a list, changed one field, created a new point equal to the changed one, and asked what each lookup, a removal and the final print show.

The report keeps the whole program, but the comments in it guess outputs that Java does not actually print. We turned the program into a general simulator: you get a list of operations instead of one fixed program, the set prints in the order entries were added, removing from the set takes the earliest matching entry, and every field stays from -1000 to 1000. Example 1 is the reported program, and its results come from running it on Java 17.

Our version is about 70% the same as the reported question.

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 point id only if no entry matches it. It returns "true" if it added one and "false" otherwise.
  • ["CONTAINS", "SET", id] returns "true" if some entry matches point id, and "false" otherwise.
  • ["REMOVE", "SET", id] removes the earliest added entry that matches point id and 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 point id and returns "true". The same point can be in the list many times.
  • ["CONTAINS", "LIST", id] returns "true" if some element is currently equal to point id, and "false" otherwise.
  • ["REMOVE", "LIST", id] removes the first element that is currently equal to point id and 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 hash 31 * (31 + 1) + 1 = 993, and into the list. Both ADD calls and both CONTAINS calls return "true".
  • After SET_X, point 0 is (2, 1), whose hash is 31 * (31 + 2) + 1 = 1024. Point 1 is a new (2, 1), also with hash 1024.
  • 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), so CONTAINS on the list returns "true".
  • REMOVE on 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 hash 993.
  • It is changed to (0, 32). Its hash is 31 * (31 + 0) + 32 = 993, the same as the stored one, and the fields match, so CONTAINS returns "true".
  • Point 1 is a new (0, 32): same hash and equal fields, so it is found too, and ADD returns "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 hash 993 and (2, 1) with hash 1024. After SET_X, both are (2, 1), so the set prints "[(2, 1), (2, 1)]".
  • REMOVE SET 1 looks for hash 1024. 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 1 deletes 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 id is the number of a point that was already created.
  • Every x, y and v is an integer from -1000 to 1000, 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

Interview reports that mention this question

  • Millennium Full Stack Engineer Java Interview: 1 Experience
All Millennium interview questionsSee Millennium hiring insights
Saved
class Solution {
    public String[] simulatePointCollections(String[][] operations) {
        // Write your code here.
    }
}
Checking account…