Katkat
Back

Implement cache and merge intervals

MicrosoftMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to implement a fixed-capacity Least Recently Used (LRU) cache using hash maps and doubly-linked lists, followed by a classic interval processing algorithm to merge overlapping segments.

Part 1: LRU Cache

Design and implement a data structure for a Least Recently Used (LRU) cache. It should support the following operations:

  • get(key): Get the value of the key if it exists, otherwise return -1.
  • put(key, value): Update or insert the value if the key exists. If the capacity is exceeded, evict the least recently used item.

The operations must run in O(1) average time complexity.

Part 2: Merge Intervals

You are given a list of intervals where each interval is represented as [start, end]. Write a function merge(intervals) that merges all overlapping intervals and returns an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1 (Cache)

capacity = 2 put(1, 1) -> cache: {1:1} put(2, 2) -> cache: {1:1, 2:2} get(1) -> returns 1, cache updates 1 to most recent. put(3, 3) -> evicts 2 (least recent), cache: {1:1, 3:3}

Example 2 (Intervals)

Input: [[1,3], [2,6], [8,10], [15,18]] Output: [[1,6], [8,10], [15,18]] Explanation: Since [1,3] and [2,6] overlap, merge them into [1,6].

Constraints

  • Cache capacity will be between 1 and 1000.
  • Interval coordinates are integers between 0 and 10,000.
  • Handle empty interval lists and cache capacity edge cases.

Hints

Hint 1

For the LRU cache, use a combination of a hash map to store keys and a doubly-linked list to track the order of usage.

Hint 2

For merging intervals, first sort the list by the start time of each interval to ensure you only need to compare adjacent intervals.

Hint 3

When merging, initialize the result with the first interval and iteratively check if the start of the current interval is less than or equal to the end of the last merged interval.

Follow-up questions

  • How would you modify the LRU cache to be thread-safe in a multi-threaded environment?
  • If the intervals were dynamic and arriving as a stream, what data structure would you use to maintain merged intervals efficiently?
  • What are the space complexity implications of your LRU cache implementation?