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

Least Recently Used cache using an array and binary search

Answer

Most recently used cache using a stack

Answer

Least frequently used cache using a min-heap

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

Copy to array and use two pointers

Answer

Reverse the whole list and compare

Answer

Use a stack to store first half then compare

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

To skip duplicate values; O(1)

Answer

A sorted list with binary search; O(log n) guaranteed

Answer

A list that skips even-indexed nodes; O(n/2)

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

Reading a node's value

Answer

Inserting after a given node

Answer

Traversing to the end

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

Detecting cycles using XOR comparison

Answer

Sorting a linked list in O(n log n)

Answer

Merging two sorted lists without extra space

Question 6

How does partitioning a linked list around a value x (like in quicksort) work?

Accepted Answer

Maintain two separate lists for < x and >= x nodes, then concatenate

Answer

Sort all nodes less than x to the left using a stable sort

Answer

Use the middle element as pivot and swap values

Answer

Reverse the list then split at x