Recent file tracker with date and insertion order

Two different orders are asked for, so keep two structures and never derive one from the other:

• Insertion order for return_all_files. A plain list of names, appended on first store. A dict maps each name to its current date so a re-store can be detected.
• Recency order for get_kth_recent_files. Sort key (date descending, name ascending).

ISO dates (yyyy-MM-dd) compare correctly as strings, but a string cannot be negated to flip the direction. Convert the date to an integer day number (date.fromisoformat(d).toordinal()) and use the key (-day, name). Ascending order on that key is exactly "newest first, ties alphabetical".

Brute force. Keep only the insertion list and sort it on every query: O(n log n) per get_kth_recent_files. Fine to say out loud first; it is also what you fall back to if stores vastly outnumber queries.

Better. Keep a list of keys that is always sorted. A store does a binary search for the slot and inserts there (bisect.insort). A query slices the first k entries. Queries become O(k); a store costs O(log n) to find the slot plus O(n) to shift the list. With a balanced tree or sortedcontainers.SortedList the store drops to O(log n); say this, but the stdlib version is what most interviewers expect for an Easy problem.

Re-storing a name. The prompt treats a name as one file. If it is stored again with a new date, remove its old key from the sorted list (binary search finds it), insert the new key, and keep its original place in insertion order.

Invariants:

• sorted_keys is sorted and holds exactly one key (-day, name) per stored file.
• order holds each stored name exactly once, in first-insertion order.
• dates[name] is the date encoded in that name's key.

from bisect import bisect_left, insort
from datetime import date


class FileStorageSystem:
    def __init__(self) -> None:
        self._dates: dict[str, int] = {}         # name -> day ordinal
        self._order: list[str] = []              # first-insertion order
        self._sorted: list[tuple[int, str]] = [] # (-day, name), ascending

    @staticmethod
    def _day(date_str: str) -> int:
        # Rejects malformed dates such as "2024-13-01".
        return date.fromisoformat(date_str).toordinal()

    def store_file(self, file: str, date_str: str) -> None:
        day = self._day(date_str)
        if file in self._dates:
            old_key = (-self._dates[file], file)
            i = bisect_left(self._sorted, old_key)
            del self._sorted[i]                  # key is guaranteed present
        else:
            self._order.append(file)
        self._dates[file] = day
        insort(self._sorted, (-day, file))

    def get_kth_recent_files(self, k: int) -> list[str]:
        if k <= 0:
            return []
        return [name for _, name in self._sorted[:k]]

    def return_all_files(self) -> list[str]:
        return list(self._order)


if __name__ == "__main__":
    fs = FileStorageSystem()
    assert fs.get_kth_recent_files(3) == []
    assert fs.return_all_files() == []

    fs.store_file("notes.txt", "2024-03-01")
    fs.store_file("budget.xlsx", "2024-05-10")
    fs.store_file("alpha.md", "2024-05-10")
    fs.store_file("old.log", "2023-12-31")

    assert fs.get_kth_recent_files(2) == ["alpha.md", "budget.xlsx"]
    assert fs.get_kth_recent_files(3) == ["alpha.md", "budget.xlsx", "notes.txt"]
    assert fs.get_kth_recent_files(10) == ["alpha.md", "budget.xlsx", "notes.txt", "old.log"]
    assert fs.get_kth_recent_files(0) == []
    assert fs.return_all_files() == ["notes.txt", "budget.xlsx", "alpha.md", "old.log"]

    # Re-store moves the file in recency order, not in insertion order.
    fs.store_file("old.log", "2024-06-01")
    assert fs.get_kth_recent_files(2) == ["old.log", "alpha.md"]
    assert fs.return_all_files() == ["notes.txt", "budget.xlsx", "alpha.md", "old.log"]

    # Year boundary compares by date, not by string length or month alone.
    fs2 = FileStorageSystem()
    fs2.store_file("b", "2023-12-31")
    fs2.store_file("a", "2024-01-01")
    assert fs2.get_kth_recent_files(1) == ["a"]
    print("all tests passed")

With n stored files:

• store_file: O(log n) to find the slot, O(n) worst case to shift the list on insert or delete. O(log n) with a balanced BST or SortedList.
• get_kth_recent_files(k): O(min(k, n)) time and output space.
• return_all_files: O(n) to copy the list (return a copy so callers cannot corrupt state).
• Space: O(n) overall; each file appears once in each of the three structures.

• Empty system: get_kth_recent_files(3) → []; return_all_files() → [].
• Store notes.txt@2024-03-01, budget.xlsx@2024-05-10, alpha.md@2024-05-10, old.log@2023-12-31:
  • get_kth_recent_files(2) → ["alpha.md", "budget.xlsx"] (same date, alphabetical).
  • get_kth_recent_files(3) → ["alpha.md", "budget.xlsx", "notes.txt"].
  • get_kth_recent_files(10) → all four, newest first (fewer than k available).
  • get_kth_recent_files(0) → [].
  • return_all_files() → ["notes.txt", "budget.xlsx", "alpha.md", "old.log"].
• Re-store old.log@2024-06-01: get_kth_recent_files(2) → ["old.log", "alpha.md"]; return_all_files() unchanged.
• Year boundary: b@2023-12-31, a@2024-01-01 → get_kth_recent_files(1) → ["a"].
• Malformed date "2024-13-01" → ValueError from store_file.

• Delete a file. Pop the name from dates, binary-search and delete its key from the sorted list, and remove it from order. Removing from the middle of order is O(n); use an insertion-ordered dict (dict keys in Python) instead of a list to make it O(1).
• Queries far outnumber stores, or the reverse. If queries dominate, the sorted list is right. If stores dominate and k is small, store in O(1) and answer each query with heapq.nsmallest(k, ...) in O(n log k). If only one fixed k is ever asked, keep a size-k heap of the current top k.
• Timestamps instead of dates, or many files per day. The key becomes (-timestamp, name); nothing else changes. With seconds, ties are rare but the name tiebreak still makes the order deterministic.
• Range query: files stored between two dates. The sorted list already supports it: two binary searches on (-end_day, "") and (-start_day + 1, "") give the slice in O(log n + m).
• Scale to millions of files or many users. Keep a per-user index; persist in a database with an index on (user_id, stored_at DESC, name) and answer with ORDER BY ... LIMIT k. Insertion order is a monotonically increasing sequence column.

Mid-level (L4)

• Correct ordering: date descending, then name ascending, and correct handling of k larger than the count.
• Keeps insertion order separate from recency order.
• Working code with a reasonable structure; a sort per query is acceptable if explained.

Senior (L5)

• Asks how to treat a repeated file name and invalid dates before coding.
• Maintains a sorted structure so queries do not re-sort; states the O(n) shift cost of insort and names a balanced tree as the fix.
• Returns copies, handles k <= 0, and tests the tie and year-boundary cases.

Staff (L6+)

• Chooses the data structure from the read/write ratio and explains the heap alternative.
• Extends cleanly to delete, range queries, and timestamps without rewriting the core.
• Discusses the persisted version: indexes, per-user partitioning, and pagination for "next k".