Katkat
Back

Implement a custom list with iterator and map

SnapchatSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your understanding of linked list internals, the Iterator design pattern, and the application of higher-order functions in a custom data structure.

Custom List Implementation

Design a custom doubly-linked list class MyList that stores integers. Your implementation must include the following functionalities:

  1. append(val): Adds an integer to the end of the list.
  2. iterator(): Returns an object that allows for sequential traversal of the list.
  3. map(func): Returns a new list where each element is the result of applying the provided function func to the original elements.

Requirements

  • The iterator should support hasNext() and next() methods.
  • The map operation should not mutate the original list.
  • Assume integers are within the range [-10^6, 10^6].

Examples

# Example 1
L = MyList()
L.append(1)
L.append(2)

# Map: multiply by 2
mapped_list = L.map(lambda x: x * 2)
# Result: [2, 4]

# Iterator usage
it = L.iterator()
while it.hasNext():
    print(it.next()) # Output: 1, 2

Edge Cases

  • Calling next() on an empty list or after the last element.
  • Empty list map operations.
  • Chains of map operations (e.g., L.map(f).map(g)).

Hints

Hint 1

Use a helper Node class with 'prev' and 'next' pointers to simplify doubly-linked list operations.

Hint 2

Implement the Iterator as a separate class that keeps track of the current node pointer.

Hint 3

For the map function, create a new instance of MyList, iterate through the existing list, apply the function, and append the result to the new list.

Follow-up questions

  • How would you modify your implementation to make the list generic so it can store types other than integers?
  • What are the time and space complexity trade-offs of your map implementation?
  • How would you implement a 'remove(iterator)' method, and what challenges arise if the iterator is invalidated during a removal?