Parallel String Counts with a Custom Hash Table
NVIDIA● MediumFULLTIMEPHONE SCREENProblem statement
Count the frequency of every distinct string in words using a custom hash table, and implement a parallel-safe solution.
Return one string key:count for each distinct key, ordered by the index of its first occurrence in the input. Counts include every occurrence across all worker chunks. The number of returned rows is the distinct-key count. Return an empty array for empty input.
Use at most workers actual threads or goroutines to process nonempty input; split the input into contiguous chunks. All workers must finish before results are returned. This practice version permits ordinary arrays, string operations, core thread/goroutine and synchronization primitives. It forbids built-in maps, sets, dictionaries, counters, and external hash-table or frequency-counting packages.
The table must resolve collisions, preserve exact counts under concurrency, and produce deterministic output regardless of scheduling. Discuss the synchronization and adjacent-memory tradeoffs when scaling the same approach to a million keys.
Function
countStrings(words: String[], workers: int) → String[]Examples
Example 1
words = ["pear","apple","pear","kiwi","apple"]workers = 3return = ["pear:2","apple:2","kiwi:1"]Counts aggregate across worker chunks. Output follows first input occurrences, not completion order.
Example 2
words = ["a","a","a","b","a","b"]workers = 8return = ["a:4","b:2"]At most one worker per input element is started; repeated keys from different workers merge into one row.
Example 3
words = []workers = 4return = []There are no keys to count and no output rows.
Constraints
0 <= words.length <= 5000.1 <= workers <= 8.- Each key has 1 to32 lowercase ASCII letters or decimal digits, so
:is never part of a key. - Keys are case-sensitive. The input array is read-only during counting.