Count Distinct Strings With a Hand-Built Hash Table, Then Parallelize It for GPUs

This question comes from an interview for a team that is porting an open-source search engine to run on GPUs, but the problem itself is general. Given an array of strings, return the number of distinct strings it contains. You may not use library hash sets, hash maps or other ready-made lookup containers: build the data structure yourself. Then make the solution safe to run in parallel, with many threads processing the array at the same time, and discuss how to divide a large input among threads. ### Clarifying Questions - Are strings compared byte for byte, or should case and Unicode normalization be ignored? - Is only the number of distinct strings needed, or also how many times each one occurs? - Does "no library" rule out only ready-made hash containers, or also standard string and dynamic-array types? - Is the whole array in memory before counting starts, so that its length is known in advance? ### Part 1 — Single-threaded version Write a function that returns the number of distinct strings, using a hash table you implement yourself: choose the hash function, the way collisions are handled, and how the table is sized. ```hint Size it once How large can the number of distinct strings possibly be, compared with the length of the array? Use that to decide whether your table ever needs to grow. ``` #### What This Part Should Cover - A concrete hash function and collision strategy, comparing full strings only when hashes match - Table sizing and load factor, and whether the table ever has to grow - Expected and worst-case time and memory - Edge cases: an empty array, empty strings, all strings equal ### Part 2 — Parallel-safe version Now many threads insert strings into one shared table at the same time, and together they must produce the exact count. Make the table safe under concurrency, explain the synchronization you chose and how it behaves as the number of threads grows, and discuss how your choice carries over to a GPU, where thousands of threads run at once. ```hint Find the one transition that must be atomic Look for the smallest piece of shared state whose change must not interleave with another thread's, and ask whether anything else in an insert needs protection at all. ``` ```hint Race on a new key Two threads may insert the same never-seen string at the same moment. Make sure exactly one of them counts it, whichever one gets there first. ``` #### Clarifying Questions for this Part - Is the count needed only after all threads finish, or must it be readable while insertions continue? - May the table be allocated once, before the parallel work starts? #### What This Part Should Cover - A race-free insert that neither loses a new string nor counts one twice - How the total is accumulated without every thread contending on one counter - Scalability compared with a single lock or a reader-writer lock - Why the chosen layout suits a GPU, including where memory gets allocated ### Part 3 — Dividing a million keys among threads The array holds about one million strings. How do you assign them to threads, and how should the strings be laid out in memory so that the threads read them efficiently on a GPU? Does the same assignment work best on a multi-core CPU? ```hint Look at one instant On a GPU, write down which addresses the threads of one warp read in the same load instruction under each way of splitting the work. ``` #### What This Part Should Cover - The assignment of keys to threads and its effect on coalesced memory access on a GPU - How the best assignment differs on a CPU: cache lines, prefetching and false sharing - A memory layout for variable-length strings - Load balance when string lengths vary widely ### What a Strong Answer Covers - A correct hash table built from scratch, with exact comparison when hashes match - Clear reasoning about the empty-to-occupied transition under concurrency - A hardware-aware choice between chaining and open addressing, and between locks and atomics - Memory access patterns on both GPU and CPU, and why they differ - Concrete sizes for a million keys: table capacity and memory footprint ### Follow-up Questions - Your first parallel version wraps the table in a reader-writer lock: a lookup that finds the string takes the shared lock and atomically increments that string's counter, and a miss takes the exclusive lock and allocates a new node. Is it correct, and where does it stop scaling? - One string makes up most of the input. How does that affect contention in your design, and how would you reduce it? - When would you sort the strings, or their hashes, instead of hashing into a table? - How would the design change if strings arrived as a stream and the total count were unknown in advance?