Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day69 "279. Perfect Squares" starting from zero

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!

problem

295. Find Median from Data Stream

The difficulty level is Hard. Excerpt from Top 100 Liked Questions.

The problem is the implementation of the class.

The median is the middle value of an ordered list of integers. If the list size is even, there is no median. Therefore, the median is the average of the two intermediate values.

For example [2,3,4] Median is 3

[2,3] The median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum (int num) --Adds an integer value from the data stream to the data structure. double findMedian () --Returns the median of all previous elements.

Example:

addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2

solution

Keeping in mind that it is the median rather than the mean, how to implement that part seems to be a very important part.

The other parts don't seem to be that hard for anyone who wants to solve this problem.

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.sorted_list = []
        self.length = 0
        

    def addNum(self, num: int) -> None:
        low,high = 0,self.length-1
        while high >= low:
            mid = (high+low)//2
            if self.sorted_list[mid] > num:
                high = mid-1
            else:
                low = mid+1
        self.sorted_list.insert(low,num)
        self.length += 1
        

    def findMedian(self) -> float:
        if self.length % 2 == 0:
            median = self.length//2
            return (self.sorted_list[median]+self.sorted_list[median-1])/2.0
        else:
            return self.sorted_list[self.length//2]


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
# Runtime: 296 ms, faster than 30.86% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 25.2 MB, less than 18.26% of Python3 online submissions for Find Median from Data Stream.

By using binary search in the ʻaddNumpart and saving the length of the list, I decided to write smoothly using that length infindMedian`. Looking back, it feels like a set problem of basic things.

You can write it if you remember each piece of knowledge firmly, but it is a type that falls into the dilemma that speed does not come out so much. Regarding how to improve from here, you can see from the following answer example that the binary search part has become a little heavier.

from heapq import *

class MedianFinder:

    def __init__(self):
        self.heaps = [], []

    def addNum(self, num):
        small, large = self.heaps
        heappush(small, -heappushpop(large, num))
        if len(large) < len(small):
            heappush(large, -heappop(small))

    def findMedian(self):
        small, large = self.heaps
        if len(large) > len(small):
            return float(large[0])
        return (large[0] - small[0]) / 2.0
# Runtime: 200 ms, faster than 82.39% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 24.6 MB, less than 98.20% of Python3 online submissions for Find Median from Data Stream.

https://leetcode.com/problems/find-median-from-data-stream/discuss/74044/Very-Short-O(log-n)-%2B-O(1)

We have prepared two lists and treated each as a heap to reduce weight.

I wish I had the ability to convert from the previous answer like this, but this time I pulled it from discussus because I didn't understand.

So that's it for this time. Thank you for your hard work.

Let Code Day70 Starting from Zero "295. Find Median from Data Stream"

Overview

problem

solution