First N Fibonacci Terms Filtered Against a Linked List

viaGlassdoor

Problem: Given a number N and a linked list of length L (which may contain duplicates), find the first N terms of the Fibonacci series; then, for any Fibonacci term that appears in the linked list, remove all occurrences of that value from the list.

Constraints: Linked list may contain duplicate values; N and L are independent sizes.

Example: N=5 -> Fibonacci terms [0,1,1,2,3]; if the list contains multiple nodes with value 2, all of them should be removed.

Approach: Generate the first N Fibonacci numbers iteratively into a set for O(1) membership checks. Traverse the linked list once, removing any node whose value exists in the Fibonacci set (standard linked-list-node-deletion-while-traversing pattern using a dummy head to simplify edge cases). O(N + L) time.

Add a follow-up question they asked
No follow-ups yet. Be the first to add one.
asked …
LeaderboardSalary
Language
Account