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 Day 79 starting from zero "1282. Group the People Given the Group Size They Belong To"

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 703. Kth Largest Element in a Stream The difficulty level is Easy.

The problem is, design a class that finds the kth largest element in the stream. Note that this is the kth largest element in the sorted order, not the kth different element.

KthLargest has a constructor that accepts an integer k and an array of integers nums containing the initial elements of the stream. Each time you call the KthLargest.add method, it represents the kth largest element in the stream. Returns the element.

Example:

int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8

The point is, please implement the constructor and the ʻadd` method.

I've dealt with this issue because it's in the Let Code exam questions recommended by those who have passed the Google coding interview.

Leet Code 60 questions you want to solve for coding interview preparation

It looks interesting, so I think I'll try to solve it. I've been solving only new problems lately, and it looks like it will be an interesting initiative for the first time in a while.

solution

Because of the heap problem, I use the heap quietly. It's also called a priority queue.

At first glance, this problem seems easy.

After adding an element every time, sort it and return the k-1 element from it, right? It seems that it will be, but since the process of sorting is heavy, I think that the time will run out normally.

For example, the processing is as follows.

def add(val):
    lists.append(val)
    self.lists.sort()
    return self.lists[self.num-1]

This will sort each time ʻadd` is called, and the more elements there are, the heavier it will be.

So when you add an element from the beginning, if you manage it using a priority queue, you don't have to sort it, right? That is.

I wrote the following code as using the heap.

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.lists,self.num = [],k
        for i in nums:
            self.add(i)

    def add(self, val: int) -> int:
        heapq.heappush(self.lists, val)
        if len(self.lists) > self.num: 
            heapq.heappop(self.lists)
        return self.lists[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
# Runtime: 136 ms, faster than 45.40% of Python3 online submissions for Kth Largest Element in a Stream.
# Memory Usage: 17.6 MB, less than 78.45% of Python3 online submissions for Kth Largest Element in a Stream.

By doing this, all the elements from the first given element are treated as a heap, and until the value of the length of lists becomes the same value as num, pop, that is, the minimum value is extracted from the list. The process is very smooth.

I thought I was writing it, but I feel that I had hardly written it on the heap, so it was a good study to review.

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

[PYTHON] Let Code Day 80 "703. Kth Largest Element in a Stream" starting from scratch

Overview

solution