Dynamo: Amazon’s Highly Available Key-value Store 论文笔记

Dynamo: Amazon’s Highly Available Key-value Store

  1. System Assumptions and Requirements in this case

    1. High write availability (this is based on their use cases like shopping carts, user should be able to update the shopping carts anytime). So the design is also writable and resolve conflicts when read.
    2. Query model is simple read and write operations to a data item which is uniquely identified by unique keys. No need for relational schemas. (Which is also based on the observation of some Amazon’s services.)
    3. ACID(Atomicity, Consistency, Isolation, Durability) are not strictly followed since it targets applications that tolerant weaker consistency, which is called eventually consistency.
  2. Design Considerations

    1. When to resolve update conflicts? Read or Write?
      1. Since it focus on high write availability, so it pushes conflict resolution to reads (which unlike many traditional DBs which execute conflict resolution during writes and has simple policy for reads)
    2. Who to resolve the conflicts? The data store or application?
      1. The application is responsible to resolve conflict updates. Since data store only has simple police like “last write wins” to resolve conflicts while application has more knowledge of each different situations and could have different strategy to resolve conflicts.
    3. Incremental scalability
      1. Add/Delete one node at a time without having a huge impact on both read/writes of the system.
    4. Symmetry
      1. No outstanding nodes. Each node should have the same responsibilities as its peers.
  3. Architecture

    Problem

    Technique

    Advantage

    Partitioning

    Consistent Hashing

    Incremental Scalability

    High Availability for writes

    Vector clocks with reconciliation during reads

    Version size is decoupled from update rates.

    Handling temporary failures

    Sloppy Quorum and hinted handoff

    Provides high availability and durability guarantee when some of the replicas are not available.

    Recovering from permanent failures

    Anti-entropy using Merkle trees

    Synchronizes divergent replicas in the background.

    Membership and failure detection

    Gossip-based membership protocol and failure detection.

    Preserves symmetry and avoids having a centralized registry for storing membership and node liveness information.

    sosp-figure2-small

    1. Partitioning (Consistent Hashing)
      1. Both node and key are mapped to the same hash space (eg. 00~FF)
      2. Key K is stored in B, which means B is responsible for K
      3. Pros:
        1. Load balance (each node would get roughly similar number of keys)
        2. Scalability (add/delete one nodes, only its neighbors would be affected)
    2. Replication  
      1. Dynamo is setup, N is assigned as a parameter indicating each data item is replicated on N nodes.
      2. Each key contains a list of nodes which is responsible for its read/write operation. Which is called Preference List. Length of the preference list should be larger than N just in case nodes failures.
      3. Using the consistent hashing, each node finds its coordinator, who is responsible to replicate the data to N-1 clockwise successor nodes.
    3. Versioningsosp-figure3-small
      1. Vector Clock is used to show if there are update conflicts. Mainly used in key-value storage which doesn’t have locks for writes to pursue better performance.
      2. D5([Sx, 3],[Sy, 1],[Sz,1]) means data item 5 which was updated by Sx 3 times, Sy 1 time, Sz 1time. Using the vector, it is easily to find out if two different version are parallel.
      3. When reads the data, the vector clock is also included in the data item.
      4. Deep understanding and examples, please check here
      5. Cons: Vector Clock some times could be too long if there are many different servers involved in writes. But in real cases it should not happen since writes are generally handled by top N nodes in the preference list of that key. Even if it happens, we can have a upper bound size of the vector clock and get rid of the old vectors depending on the timestamp, which might potentially cause problems when trying to resolve conflicts.
    4. Get() & Put() operation
      1. Only first N healthy nodes in the preference list are involved. (those are down and inaccessible are skipped)
      2. W + R > N (W/R: number of nodes which should success for writes/reads)
      3. When put(), the coordinator generates the vector clock with the new version and writes the new version locally. Then replicates the new version to first N reachable node in the preference list. Consider write successful as long as there is W-1 nodes respond.
      4. Similarly, for get(), the coordinates request the data from first N reachable nodes from the preference list and as long as there are R-1 response it will then returns all version of the data.
    5. Failure handling (Hinted Handoff)
      1. Check the Dynamo ring above, if node A is down, the data item which is supposed to written to A is now written to D (suppose N=3) along with the metadata (indicating which node it is supposed to be at) which is stored separately in D
      2. Once such hint is discovered, and A is recovered, D will send the replica to A and then delete the replica from itself.
      3. Hinted Handoff ensures read/writes won’t be rejected due to single node down or network failure.
    6. Recovering from permanent failures、Membership and failure detection待进一步整理。

Reference: http://blog.ddup.us/2011/11/07/amazon-dynamo/

FacebookTwitterGoogle+Share

Longest Palindromic Substring

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

Solution1. DP O(n^2)

定义函数
P[i,j] = 字符串区间[i,j]是否为palindrome.

首先找个例子,比如S=”abccb”,
S=    a  b  c  c  b
Index = 0  1  2  3  4

P[0,0] =1  //each char is a palindrome
P[0,1] =S[0] == S[1]    , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3],  P[3,3]=1
………………….
由此就可以推导出规律

P[i,j] = 1  if i ==j
=  S[i] ==S[j]   if j = i+1
=  S[i] == S[j] && P[i+1][j-1]  if j>i+1

实现如下:

public String longestPalindrome(String s) {
    if (s == null) {
        return "";
    }
    String res = "";
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (i - j <= 2) {
                dp[j][i] = s.charAt(i) == s.charAt(j);
            } else {
                dp[j][i] = s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1];
            }
            if (dp[j][i]) {
                if (i - j + 1 > res.length()) {
                    res = s.substring(j, i + 1);
                }
            }
        }
    }
    return res;
}

Solution2: Check both aba and abba 2 cases. O(n^2)

public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    String result = "";

    //1. if it is like 'aba'
    for (int i = 0; i < s.length(); i++) {
        int count = 0;
        while (i - count >= 0 && i + count < s.length() && s.charAt(i - count) == s.charAt(i + count)) {
            count++;
        }
        String palindrome = s.substring(i - count + 1, i + count);
        if (palindrome.length() > result.length()) {
            result = palindrome;
        }
    }

    //2. if it is like 'abba', the pivot would be the interval between i and i+1
    for (int i = 0; i < s.length() - 1; i++) {
        int count = 1;
        while (i - count + 1 >= 0 && i + count < s.length() && s.charAt(i - count + 1) == s.charAt(i + count)) {
            count++;
        }
        if (count > 1) {
            String palindrome = s.substring(i - count + 2, i + count);
            if (palindrome.length() > result.length()) {
                result = palindrome;
            }
        }
    }

    return result;
}

 

Longest Common Prefix

Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

Example

For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"

For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is "ABC"

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    String lcp = strs[0];
    for (int i = 1; i < strs.length; i++) {
        lcp = getLCP(lcp, strs[i]);
    }
    return lcp;
}

public String getLCP(String s1, String s2) {
    StringBuilder sb = new StringBuilder();
    int n = Math.min(s1.length(), s2. length());
    for (int i = 0; i < n; i++) {
        if (s1.charAt(i) == s2.charAt(i)) {
            sb.append(s1.charAt(i));
        } else {
            break;
        }
    }
    return sb.toString();
}

 

Implement rand7() using rand5()

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i.e., implement rand7() using rand5()).

解答

rand5可以随机生成1,2,3,4,5;rand7可以随机生成1,2,3,4,5,6,7。 rand5并不能直接产生6,7,所以直接用rand5去实现函数rand7似乎不太好入手。 如果反过来呢?给你rand7,让你实现rand5,这个好实现吗?

一个非常直观的想法就是不断地调用rand7,直到它产生1到5之间的数,然后返回。 代码如下:

<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand5</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">5</span><span class="p">)</span>
        <span class="n">x</span> <span class="o">=</span> <span class="n">Rand7</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>

等等,这个函数可以等概率地产生1到5的数吗?首先,它确确实实只会返回1到5这几个数, 其次,对于这些数,都是由Rand7等概率产生的(1/7),没有对任何一个数有偏袒, 直觉告诉我们,Rand5就是等概率地产生1到5的。事实呢?让我们来计算一下, 产生1到5中的数的概率是不是1/5就OK了。比如说,让我们来计算一下Rand5生成1 的概率是多少。上面的函数中有个while循环,只要没生成1到5间的数就会一直执行下去。 因此,我们要的1可能是第一次调用Rand7时产生,也可能是第二次,第三次,…第n次。 第1次就生成1,概率是1/7;第2次生成1,说明第1次没生成1到5间的数而生成了6,7, 所以概率是(2/7)*(1/7),依次类推。生成1的概率计算如下:

<code>P(x=1)=1/7 + (2/7) * 1/7 + (2/7)^2 * 1/7 + (2/7)^3 * 1/7 + ...
      =1/7 * (1 + 2/7 + (2/7)^2 + ...) // 等比数列
      =1/7 * 1 / (1 - 2/7)
      =1/7 * 7/5
      =1/5
</code>

上述计算说明Rand5是等概率地生成1,2,3,4,5的(1/5的概率)。从上面的分析中, 我们可以得到一个一般的结论,如果a > b,那么一定可以用Randa去实现Randb。其中, Randa表示等概率生成1到a的函数,Randb表示等概率生成1到b的函数。代码如下:

<code class="language-cpp" data-lang="cpp"><span class="c1">// a &gt; b</span>
<span class="kt">int</span> <span class="nf">Randb</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">b</span><span class="p">)</span>
        <span class="n">x</span> <span class="o">=</span> <span class="n">Randa</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>

回到正题,现在题目要求我们要用Rand5来实现Rand7,只要我们将Rand5 映射到一个能产生更大随机数的Randa,其中a > 7,就可以套用上面的模板了。 这里要注意一点的是,你映射后的Randa一定是要满足等概率生成1到a的。比如,

<code>Rand5() + Rand5() - 1
</code>

上述代码可以生成1到9的数,但它们是等概率生成的吗?不是。生成1只有一种组合: 两个Rand5()都生成1时:(1, 1);而生成2有两种:(1, 2)和(2, 1);生成6更多。 它们的生成是不等概率的。那要怎样找到一个等概率生成数的组合呢?

我们先给出一个组合,再来进行分析。组合如下:

<code>5 * (Rand5() - 1) + Rand5()
</code>

Rand5产生1到5的数,减1就产生0到4的数,乘以5后可以产生的数是:0,5,10,15,20。 再加上第二个Rand5()产生的1,2,3,4,5。我们可以得到1到25, 而且每个数都只由一种组合得到,即上述代码可以等概率地生成1到25。OK, 到这基本上也就解决了。

套用上面的模板,我们可以得到如下代码:

<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand7</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">7</span><span class="p">)</span>
        <span class="n">x</span> <span class="o">=</span> <span class="mi">5</span> <span class="o">*</span> <span class="p">(</span><span class="n">Rand5</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">Rand5</span><span class="p">()</span> <span class="c1">// Rand25</span>
    <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>

上面的代码有什么问题呢?可能while循环要进行很多次才能返回。 因为Rand25会产生1到25的数,而只有1到7时才跳出while循环, 生成大部分的数都舍弃掉了。这样的实现明显不好。我们应该让舍弃的数尽量少, 于是我们可以修改while中的判断条件,让x与最接近25且小于25的7的倍数相比。 于是判断条件可改为x > 21,于是x的取值就是1到21。 我们再通过取模运算把它映射到1-7即可。代码如下:

<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand7</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">21</span><span class="p">)</span>
        <span class="n">x</span> <span class="o">=</span> <span class="mi">5</span> <span class="o">*</span> <span class="p">(</span><span class="n">Rand5</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">Rand5</span><span class="p">()</span> <span class="c1">// Rand25</span>
    <span class="k">return</span> <span class="n">x</span><span class="o">%</span><span class="mi">7</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span></code>

这个实现就比上面的实现要好,并且可以保证等概率生成1到7的数。

让我们把这个问题泛化一下,从特殊到一般。现在我给你两个生成随机数的函数Randa, Randb。Randa和Randb分别产生1到a的随机数和1到b的随机数,a,b不相等 (相等就没必要做转换了)。现在让你用Randa实现Randb。

通过上文分析,我们可以得到步骤如下:

  1. 如果a > b,进入步骤2;否则构造Randa2 = a * (Randa – 1) + Randa, 表示生成1到a2 随机数的函数。如果a2 仍小于b,继教构造 Randa3 = a * (Randa2 – 1) + Randa…直到ak > b,这时我们得到Randak , 我们记为RandA。
  2. 步骤1中我们得到了RandA(可能是Randa或Randak ),其中A > b, 我们用下述代码构造Randb:
<code class="language-cpp" data-lang="cpp"><span class="c1">// A &gt; b</span>
<span class="kt">int</span> <span class="nf">Randb</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">b</span><span class="o">*</span><span class="p">(</span><span class="n">A</span><span class="o">/</span><span class="n">b</span><span class="p">))</span> <span class="c1">// b*(A/b)表示最接近A且小于A的b的倍数</span>
        <span class="n">x</span> <span class="o">=</span> <span class="n">RandA</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">x</span><span class="o">%</span><span class="n">b</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span></code>

从上面一系列的分析可以发现,如果给你两个生成随机数的函数Randa和Randb, 你可以通过以下方式轻松构造Randab,生成1到a*b的随机数。

<code>Randab = b * (Randa - 1) + Randb
Randab = a * (Randb - 1) + Randa
</code>

如果再一般化一下,我们还可以把问题变成:给你一个随机生成a到b的函数, 用它去实现一个随机生成c到d的函数。有兴趣的同学可以思考一下,这里不再讨论。

全书题解目录:

Cracking the coding interview–问题与解答

 

reference: http://www.hawstein.com/posts/19.10.html

Sliding Window Maximum

Sliding Window Maximum

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Example

For array [1, 2, 7, 7, 8], moving window size k = 3. return [7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8] , return the maximum 7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum 7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum 8;

Challenge

o(n) time and O(k) memory

Solution:

1. 首先这道题最容易想到得是用heap做,维护一个heap,但是sliding window需要删除node,于是如果用HashHeap的话可以将时间复杂度降到O(nlogn). 即每次slide一次用logn时间添加结点再用logn时间删除结点。

2. 第二个方法是线性的 需要用到Deque即双端队列。比较难想到。

做法是:先考虑用stack,就是每次扫到新node时,先看stack.peek是不是比node小,如果小得话就把peek pop出去。直到peek比node小时,把node push进stack

然后此题因为需要每当slide window时,要把第一个数remove掉,这就需要用到deque,因为第一个数往往是在栈底。

public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    if (nums == null || nums.length == 0 || nums.length < k) {
        return result;
    }
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerLast(0);
    for (int i = 1; i < k; i++) {
        addElement(deque, i, nums);
    }
    result.add(nums[deque.peekFirst()]);
    for (int i = 1; i < nums.length + 1 - k; i++) {
        removeElement(deque, i - 1);
        addElement(deque, i + k - 1, nums);
        result.add(nums[deque.peekFirst()]);
    }
    return result;
}
//when adding a new element i,
//if nums[i]>=peakLast, we should keep popping the peak until the peak <nums[i]
//then we push nums[i]
public void addElement(Deque<Integer> deque, int index, int[] nums) {
    while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[index]) {
        //pop the peak element
        deque.pollLast();
    }
    deque.offerLast(index);
}

//when removing element, only check if the first of the deck is the same index
//then remove it. It is likely that it has already been popped out of the deque.
public void removeElement(Deque<Integer> deque, int index) {
    if (index == deque.peekFirst()) {
        deque.pollFirst();
    }
}

 

Sliding Window Median

Sliding Window Median

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example

For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]

At first the window is at the start of the array like this

[ | 1,2,7 | ,8,5] , return the median 2;

then the window move one step forward.

[1, | 2,7,8 | ,5], return the median 7;

then the window move one step forward again.

[1,2, | 7,8,5 | ], return the median 7;

Challenge

O(nlog(n)) time

Solution: 用分别用两个heap来维护这个median结构,左边一个maxHeap,右边一个minHeap,在加上当中一个median数值,两个Heap的size差最多为1,即leftSize==rightSize||leftSize+1==rightSize.

首先是要先初始化这个结构,把前k个数放进去,接下里window每向右移一格,等于是加上第nums[i+k-1] 然后 remove nums[i-1]。

注意的是:java里有heap的实现,可用PriorityQueue然后可以定义Comparator, 默认是minHeap, 如果要用maxHeap要自己写一个comparator传入constructor. 但是PriorityQueue的remove方法是O(n)的 即每次remove需要遍历一遍这个Heap找到那个数再Remove,面试时可以和面试官讨论,这一步可以用HashHeap来做,这样remove变成了O(logn), (找到这个数是O(1), remove相当于和最后一个数swap 然后siftdown操作所以是O(logn)).

如果用HashHeap的话,整个Time Complexity就是O(nlogn).

 

public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    if (nums == null || nums.length == 0 || nums.length < k) {
        return result;
    }
    PriorityQueue<Integer> leftMaxHeap = new PriorityQueue<>(1, new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            if (a < b) {
                return 1;
            } else if (a == b) {
                return 0;
            } else {
                return -1;
            }
        }
    });
    PriorityQueue<Integer> rightMinHeap = new PriorityQueue<>();
    int median = nums[0];
    //init the two heaps for the first k elements
    for (int i = 1; i < k; i++) {
        median = addElement(nums, i, median, leftMaxHeap, rightMinHeap);
    }
    result.add(median);
    //start moving the window forward
    for (int i = 1; i <= nums.length - k; i++) {
        //add nums[i+k-1]
        median = addElement(nums, i + k - 1, median, leftMaxHeap, rightMinHeap);
        //remove nums[i-1]
        median = removeElement(nums, i - 1, median, leftMaxHeap, rightMinHeap);
        result.add(median);
    }

    return result;
}

public int addElement(int[] nums, int index, int median,
                      PriorityQueue<Integer> leftMaxHeap, PriorityQueue<Integer> rightMinHeap) {
    //the left heap can only be the same size as the right heap
    //or left size + 1 = right size
    if (leftMaxHeap.size() == rightMinHeap.size()) {
        if (nums[index] < median) {
            leftMaxHeap.offer(nums[index]);
            rightMinHeap.offer(median);
            median = leftMaxHeap.poll();
        } else {
            rightMinHeap.offer(nums[index]);
        }
    } else {
        if (nums[index] <= median) {
            leftMaxHeap.offer(nums[index]);
        } else {
            leftMaxHeap.offer(median);
            rightMinHeap.offer(nums[index]);
            median = rightMinHeap.poll();
        }
    }
    return median;
}

public int removeElement(int[] nums, int index, int median,
                         PriorityQueue<Integer> leftMaxHeap, PriorityQueue<Integer> rightMinHeap) {
    //the left heap can only be the same size as the right heap
    //or left size + 1 = right size
    if (leftMaxHeap.size() == rightMinHeap.size()) {
        if (nums[index] == median) {
            median = leftMaxHeap.poll();
        } else if (nums[index] < median) {
            leftMaxHeap.remove(nums[index]);
        } else {
            rightMinHeap.remove(nums[index]);
            if (!leftMaxHeap.isEmpty()) {
                rightMinHeap.offer(median);
                median = leftMaxHeap.poll();
            }
        }
    } else {
        if (nums[index] == median) {
            median = rightMinHeap.poll();
        } else if (nums[index] <= median) {
            leftMaxHeap.remove(nums[index]);
            if (!rightMinHeap.isEmpty()) {
                leftMaxHeap.offer(median);
                median = rightMinHeap.poll();
            }
        } else {
            rightMinHeap.remove(nums[index]);
        }
    }
    return median;
}