Amazon Interview Question : SDE2
Summary
I encountered a specific data structure problem during my SDE2 interview at Amazon, where I was tasked with adjusting custom random pointers in a linked list.
Full Experience
During my SDE2 interview at Amazon, I faced an interesting challenge involving linked lists. The problem presented a custom node structure with both next and random pointers. The main task was to manipulate the random pointer of each node, making it point to the node containing the next larger numerical value within the entire list. This required careful traversal and logic to identify the appropriate target for each random pointer.
Interview Questions (1)
You are given a linked list where each node has two pointers: next and random. The next pointer points to the subsequent node in the list. The task is to modify the random pointer of each node to point to the node that contains the next larger numerical value in the list.
For example, given the list: 110 --> 16 --> 114 --> 13 --> 18 --> 11, the random pointer of node 110 should point to 114 (as 114 is the next larger value after 110 in the list).
110 --> 16 --> 114 --> 13 --> 18 --> 11
| \ / | / | / | / |
->--->---/ -->---->-->---/ |-->-/ |-->---/ |
\ |
-----<-----------<-----------<-------------