How should I practice Thread-Safe Concurrent Linked List?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Apple onsite interview problems in FastPrep.

Is Thread-Safe Concurrent Linked List associated with Apple?

FastPrep tags this as a Apple onsite interview coding practice problem when the problem catalog has that company and stage context.

Thread-Safe Concurrent Linked List

Apple● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Source note: The interviewer asked for a "Thread-safe Concurrent LinkedList" that supports concurrency-safe insert(), delete(), and read() operations. The report says the round tested multithreaded concurrency control, fine-grained locks (node-level or hand-over-hand locking), sentinel nodes, and lock contention and thread safety under high concurrency.

The report does not say what the three calls take or return, how to handle a bad position, whether values can repeat, or how big the input is. Here, calls use zero-based positions, an insert goes before the node at its position, a position equal to the size adds to the end, a bad position returns -1 and changes nothing, an insert returns 1, a delete returns the removed value, a read returns the value and leaves the list as it is, values can repeat, 0 is a normal value, there are at most 500 calls, positions go up to 500, and values run from 0 to 10^9. You get the calls as lists in one legal order instead of a class used by real threads. The judge runs on one thread, so it checks each result and does not check your locks. The locking is explained in the editorial.

The judged task matches the report at about 60%.

Implement a singly linked list of integers that many threads can use at the same time. It starts empty and supports insert, delete, and read. Positions start at 0, and repeated values are separate nodes.

For this exercise, the calls arrive as two lists. operations[i] names a call and args[i] holds its arguments. The lists show one legal order of the concurrent calls, so each call must see the complete list left by the call before it, with no partial change showing.

"INSERT" with [index, value]: add value so that it sits at position index, and return 1. Values at that position and later move back by one. An index equal to the current size adds to the end. If index is greater than the size, return -1 and change nothing.
"DELETE" with [index]: remove the node at position index and return its value. If no node is there, return -1 and change nothing.
"READ" with [index]: return the value at position index and leave the list as it is. If no node is there, return -1.

Return an array with one result for each operation, in order.

The interview focused on making these calls safe under real concurrency. Try hand-over-hand locking: take the next node's lock before you release the current one, and keep a sentinel node before the first position. The judge runs your code on one thread, so it checks the results of each call and cannot check your locks or how well they scale.

Function

runConcurrentLinkedList(operations: String[], args: int[][]) → int[]

Examples

Example 1

operations = ["INSERT","INSERT","INSERT","READ","DELETE","READ"]args = [[0,10],[1,30],[1,20],[1],[0],[0]]return = [1,1,1,20,10,20]

Three inserts build the list. The third insert puts 20 at position 1, so the list is [10, 20, 30]. READ at position 1 returns 20. DELETE at position 0 returns 10 and leaves [20, 30], so the last READ at position 0 returns 20.

Example 2

operations = ["READ","DELETE","INSERT","INSERT","READ"]args = [[0],[0],[1,5],[0,5],[0]]return = [-1,-1,-1,1,5]

The list is empty, so READ and DELETE at position 0 both return -1. INSERT at index 1 also returns -1, because the size is 0. INSERT at index 0 works, and READ at position 0 then returns 5.

Example 3

operations = ["INSERT","INSERT","INSERT","DELETE","READ","READ","READ"]args = [[0,7],[0,7],[2,0],[1],[0],[1],[2]]return = [1,1,1,7,7,0,-1]

The inserts build [7, 7, 0]. The two 7 values are separate nodes. DELETE at position 1 returns 7 and leaves [7, 0]. READ at position 0 returns 7, and READ at position 1 returns the stored 0. Position 2 is now empty, so its READ returns -1.

Constraints

1 <= operations.length <= 500
args.length == operations.length
operations[i] is "INSERT", "DELETE", or "READ".
args[i] is [index, value] for "INSERT" and [index] for "DELETE" and "READ".
0 <= index <= 500
0 <= value <= 10^9