My Learning Journey & a Game-Changing Data Structure

Posted
9 Oct 2025
413 reads

Summary

I recently encountered LeetCode 480, Sliding Window Median, which I also learned was asked in a Walmart R1 interview. I initially tried a brute-force approach but optimized it significantly using Python's SortedList data structure, achieving an efficient solution crucial for interviews.

How it went

Today I solved LeetCode 480: Sliding Window Median and wanted to share my learning journey, especially for interview preparation. My first attempt involved a simple brute-force approach using Python’s built-in sorted(). While this worked for small inputs, it unfortunately failed with a Time Limit Exceeded error on larger test cases. The reason was its O(nk log k) time complexity, making it not scalable for real-world interview scenarios.

My breakthrough came when I discovered SortedList from the sortedcontainers Python module. This powerful data structure maintains elements in sorted order automatically, offering efficient O(log n) insertion and deletion, O(1) access by index, and O(log n) search operations. By implementing SortedList, I was able to optimize my solution significantly, reducing the overall time complexity to O(n log k). This makes SortedList an ideal choice for problems requiring dynamic median finding, sliding window min/max, or finding the Kth largest/smallest element in a stream. I also learned that this exact problem, LeetCode 480, was recently asked in a Walmart R1 interview, which truly emphasized the importance of knowing such optimized techniques.

Questions asked (1)

  1. 01

    Sliding Window Median

    Data Structures & Algorithms · Hard

    You are given an array of integers nums and an integer k. A sliding window of size k moves from the very left to the very right. For each window, you need to find the median of the elements within it. The median is the middle element in a sorted list. If the list has an even number of elements, the median is the average of the two middle elements. Return an array of medians for each window.

    Example: nums = [1,3,-1,-3,5,3,6,7], k = 3

    Output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]

    Open the problem

How they prepared

My preparation involves continuously optimizing solutions for common LeetCode patterns. Discovering and mastering data structures like SortedList from the sortedcontainers module has been a game-changer for efficiently tackling problems involving dynamic median finding and sliding windows. This technique is crucial for setting oneself apart in technical interviews, as evidenced by its applicability to problems asked in interviews like Walmart's R1.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Walmart recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!