Delete Fibonacci-Valued Nodes from a Doubly Linked List

Problem: Given an integer N and the head & tail of a doubly linked list (DLL), delete all nodes whose value falls in the Fibonacci sequence bounded above by N.

Constraints: Fibonacci sequence here is 0, 1, 1, 2, 3, 5, 8, 13, 21, ... up to the largest term <= N.

Example: N=25 -> Fibonacci set = {0,1,2,3,5,8,13,21}. DLL: head -> 9 <-> 10 <-> 8 <-> 21 <-> 6 <- tail -> after removing 8 and 21: head -> 9 <-> 10 <-> 6 <- tail.

Approach: (1) Generate the Fibonacci terms up to N (O(log N) terms) and store them in a hash set for O(1) membership checks. (2) Traverse the DLL once; for each node whose value is in the Fibonacci set, unlink it by updating its predecessor's next and successor's prev pointers (handling head/tail edge cases). O(n) time, O(log N) extra space for the Fibonacci set. The interviewer asked for 4-5 different solution approaches (discussing time/space tradeoffs) before letting the candidate pick one to code -- the candidate deliberately chose a less-optimal-but-more-readable approach, which the interviewer praised.