Data Structures Linked Lists 3

Question 1

What is an LRU Cache and which data structures implement it in O(1) for both get and put?

Accepted Answer

LRU cache using a doubly linked list and hash map

Answer

An LRU cache combines a doubly linked list (for order tracking) and a hash map (for O(1) lookup) to achieve O(1) get and put operations.

Question 2

How do you check if a linked list is a palindrome in O(n) time and O(1) space?

Accepted Answer

Find the middle, reverse the second half, compare both halves

Answer

Reversing only the second half in place and comparing it with the first half achieves O(n) time and O(1) space palindrome detection.

Question 3

What is the purpose of a skip list and what is its average search time complexity?

Accepted Answer

A probabilistic structure with multiple levels enabling O(log n) average search

Answer

A skip list uses probabilistically built express lanes at multiple levels, achieving O(log n) average search time similar to balanced BSTs.

Question 4

Which linked list operation requires knowledge of the previous node in a singly linked list?

Accepted Answer

Deleting a specific node by value

Answer

Deleting a node by value in a singly linked list requires the previous node to update its next pointer to skip the deleted node.

Question 5

What is the XOR linked list technique used for?

Accepted Answer

Reducing doubly linked list memory by storing XOR of prev and next addresses

Answer

An XOR linked list stores XOR of previous and next node addresses in a single field, halving the pointer storage compared to a standard doubly linked list.

Data Structures Practice Test

Data Structures Practice Test

Data Structures Linked Lists 3