[개발자매일영어] Heap & Median - Cracking Coding Interview
이번에는 Heap & Median Interview Question에 대한 내용 입니다.
앞으로는 코딩 인터뷰 문제도 한문제씩 같이 풀어보도록 하겠습니다. 제일 아래에 기출문제가 있습니다. 같이 풀어봐요!
개발자매일영어는 당분간은 Cracking Coding Interview의 저자로 유명한 Gayle Laakmann McDowell저자의 강좌를 지속적으로 공부해보도록 하겠습니다.
전체 분량은 너무 길어서 주요부분 한 두 군데만 1분 이하로 발췌하여 mp3파일로 만들고 있습니다.
즉 한 주제당 1분 이하 분량의 mp3파일이 한 두개씩 제공되겠습니다. 나머지 부분은 리스닝 연습 하시면 되겠습니다.
이번에는 따라하기 쉽도록 최대한 짧게 잘랐습니다.
공부하는 4단계 방법은 아래와 같습니다.
1분 이하 분량을 번역
전체 듣기 두번
문장 듣고 따라 말하기 두번
한국어로 듣고 영어로 말하기 한번 => 제일 중요 합니다!!!!
하루에 한시간 이상 들으면서 말하기 연습하면 좋을 것 같습니다.
*** 개발자 매일 영어는 제가 개인적으로 공부하기 위해 만든 mp3파일을 혹시 다른 분에게도 도움이 될까 해서 공유하고 있는 것입니다. 제 목소리도 포함되어 있고, 부족한 영어 실력으로 번역한 것이라 잘못되었을 수도 있습니다. 제 목소리에 놀라지 마시고 이상한 부분은 댓글로 알려 주시면 감사하겠습니다. ***
mp3 파일 다운로드: https://drive.google.com/open?id=15LCaW6EDOQQ4ocK50hVnfAL2J10xLTC9
----- mp3 script -----
Let's remember that a median is the number which half numbers are below half the numbers are above, so rather than keeping everything sorted which is kind of unnecessary,
let's actually just keep two buckets of numbers, 1 which is the lower half of
numbers and one which is the upper half of numbers.
Then when a number comes in look at its value and determine whether it's in the lower half or the upper half.
We want to keep these two buckets pretty balanced too so they shouldn't be ever
different in size by more than one.
So we want to be roughly half on each side.
Then to get the median we just need to pull out the appropriate value.
If the buckets are different sizes, then take the bigger bucket and pick either the
min or max depending on whether it's the lower half or the upper half.
If the buckets are the same size then take the biggest element from the lower half and
the smallest element from the upper half and average those.
Well that's all well and good but how do we actually do this efficiently?
A heap is the perfect data structure for this problem because it allows us to very efficiently pull out the biggest element from a bucket or the smallest element from a bucket.
So what we can do is we can keep a max heap of the lower part of the numbers and a min heap of the upper part of the numbers.
And then we can very efficiently add numbers as well as pull out the min or the max.
-- 번역 예 (직접번역 해보세요) --
Median은 아래의 반의 숫자들과 위의 반의 숫자들 사이에 있는 숫자입니다. 모든 숫자가 정렬될 필요는 없습니다. 두개의 바구니에 숫자들이 있다고 합시다. 하나는 낮은 숫자들 반이, 하나는 높은 숫자들 반이 있습니다. 한 숫자가 들어올때 값을 보고 낮은 반인지 높은 반인지 결정하면 됩니다.
우리는 하나이상 크기가 차이나지 않도록 꽤 균형있게 바구니를 유지하려고 합니다. 각각에 대충 반씩 있길 원합니다. 그리고 적당한 값을 꺼내어 Median을 얻을 수 있습니다.
바구니 크기가 틀리면 큰 바구니에서 그것이 낮은값 반인지 높은값 반인지에 따라 최소값 또는 최대값을 꺼냅니다.
바구니 크기가 같으면 최대값을 낮은 반에서 최소값을 큰값 반에서 꺼내고 둘의 평균을 냅니다.
다 좋은 것 같습니다. 하지만 어떻게 실제로 효율적으로 할 수 있을까요?
Heap은 이 문제를 풀기에 완벽한 데이터 구조입니다. 왜냐면 매우 효율적으로 최대값과 최소값을 바구니에서 꺼낼 수 있습니다.
우리는 낮은값들에서 최대값 heap을 높은값들에서 최소값 heap을 유지할 수 있습니다.
우리는 매우 효율적으로 숫자들을 추가하고 최소 최대값을 꺼낼 수 있습니다.
----- 이주의 Interview Question (같이 풀어 봐요!) -----
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example,
[2,3,4] , the 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) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
Example:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
Link: https://leetcode.com/problems/find-median-from-data-stream/description/