1
\$\begingroup\$

I am trying to solve running median problem in hackerrank https://www.hackerrank.com/challenges/ctci-find-the-running-median and below is my code

public class Solution {

   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        MinHeap minHeap = new MinHeap();
        MaxHeap maxHeap = new MaxHeap();
        float median = 0;
        for(int a_i=0; a_i < n; a_i++) {

            // Logic to add the running element
            int element = in.nextInt();
            if (minHeap.size == maxHeap.size) {
                if (element <= median) {
                    maxHeap.addItem(element);
                    median = maxHeap.peek();
                } else {
                    minHeap.addItem(element);
                    median = minHeap.peek();
                }
            } else if (maxHeap.size > minHeap.size) {
                if (element <= median) {
                    minHeap.addItem(maxHeap.poll());
                    maxHeap.addItem(element);
                } else {
                    minHeap.addItem(element);
                }
                median = (float)(maxHeap.peek() + minHeap.peek()) / 2;
            } else {
                if (element <= median) {
                    maxHeap.addItem(element);
                } else {
                    maxHeap.addItem(minHeap.poll());
                    minHeap.addItem(element);
                }
                median = (float)(maxHeap.peek() + minHeap.peek()) / 2;
            }
            System.out.println(median);
        } 
    }

    static abstract class Heap {
        int[] items = new int[10];
        int capacity = 10;
        int size = 0;


        boolean hasLeftChild(int parent) {
            int leftChildIndex = getLeftChildIndex(parent);
            if (leftChildIndex > size - 1) {
                return false;
            }
            return true;
        }

        boolean hasRightChild(int parent) {
            int rightChildIndex = getRightChildIndex(parent);
            if (rightChildIndex > size - 1) {
                return false;
            }
            return true;
        }

        boolean hasParent(int index) {
            if (index > 0) {
                return true;
            } else {
                return false;
            }
        }

        int getLeftChildIndex(int parent) {
            int leftChildIndex = parent * 2 + 1;
            return leftChildIndex;
        } 

        int getRightChildIndex(int parent) {
            int rightChildIndex = parent * 2 + 2;
            return rightChildIndex;
        }

        int getParentIndex(int index) {
            int parent = (index -1)/2;
            return parent;
        }

        int getLeftChild(int parent) {
            return items[getLeftChildIndex(parent)];    
        }

        int getRightChild(int parent) {
            return items[getRightChildIndex(parent)];    
        }

        int getParent(int index) {
            return items[getParentIndex(index)];
        }

        void ensureCapacity() {
            if (size == capacity) {
                items = Arrays.copyOf(items, capacity * 2);
                capacity = capacity * 2;
            }    
        }

        void addItem(int item) {
            ensureCapacity();
            items[size] = item;
            size = size + 1;
            heapifyUp();
        }

        int poll() {
            int topItem = items[0];
            items[0] = items[size - 1];
            size = size - 1;
            heapifyDown();
            return topItem;
        }

        int peek() {
            return items[0]; 
        }

        abstract void heapifyDown();

        abstract void heapifyUp();

        void swap(int indexA, int indexB) {
            int temp = items[indexA];
            items[indexA] = items[indexB];
            items[indexB] = temp;
        }
    }

    static class MinHeap extends Heap {
        void heapifyUp() {
            int index = size - 1;
            while(hasParent(index)) {
                if (getParent(index) <= items[index]) {
                    break;
                } else {
                    swap(getParentIndex(index), index);
                    index = getParentIndex(index);
                }
            }
        }

        void heapifyDown() {
            int parent = 0;
            while(hasLeftChild(parent) && getLeftChild(parent) <= items[parent]) {
                int smallerIndex = getLeftChildIndex(parent);
                if(hasRightChild(parent) && getRightChild(parent) <= getLeftChild(parent)) {
                    smallerIndex = getRightChildIndex(parent);
                }
                swap(parent, smallerIndex);
                parent = smallerIndex;
            }
        }
    }

    static class MaxHeap extends Heap {
        void heapifyUp() {
            int index = size - 1;
            while(hasParent(index)) {
                if (getParent(index) >= items[index]) {
                    break;
                } else {
                    swap(getParentIndex(index), index);
                    index = getParentIndex(index);
                }
            }
        }

        void heapifyDown() {
            int parent = 0;
            while(hasLeftChild(parent) && getLeftChild(parent) >= items[parent]) {
                int largerIndex = getLeftChildIndex(parent);
                if(hasRightChild(parent) && getRightChild(parent) >= getLeftChild(parent)) {
                    largerIndex = getRightChildIndex(parent);
                }
                swap(parent, largerIndex);
                parent = largerIndex;
            }
        }
    }
}

It successfully passes for the first basic test case but fails for all other test cases on submitting code. It seems to be correct when i debugged it with some samples of the test input. Can someone review my code and help me understand what the issue is with respect to the current implementation ?

\$\endgroup\$

closed as off-topic by alecxe, ChrisWue, Jamal Aug 11 '17 at 2:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – ChrisWue, Jamal
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ why not consider using Priority Queue (the built-in Java heap implementation)? \$\endgroup\$ – Angela Pan Aug 10 '17 at 16:24
  • \$\begingroup\$ @AngelaPan I haven't thought about other solutions as heap implementation is very simple and straight-forward. I am not sure what the problem is wrt this implementation that the test cases are failing. Can you help me with that ? \$\endgroup\$ – Aarish Ramesh Aug 10 '17 at 16:27
  • \$\begingroup\$ implementation is very simple and straight-forward we've been there. \$\endgroup\$ – greybeard Aug 10 '17 at 23:25
  • \$\begingroup\$ people who marked this off-topic should really distinguish "broken code" vs "code that the author sees nothing wrong with." When I first read it, for a long time, I didn't see what's wrong either. \$\endgroup\$ – Angela Pan Aug 11 '17 at 15:15
  • \$\begingroup\$ @AngelaPan: Then, there is To the best of [the coder's] knowledge, does the code work as intended? and [This code …] fails for all other test cases. \$\endgroup\$ – greybeard Aug 13 '17 at 4:16
1
\$\begingroup\$

I would offer a test case here. It's a shortened version of test case 1.

24
94455
20555
20535
53125
73634
148
63772
17738
62995
13401
95912
13449
92211
17073
69230
22016
22120
78563
16571
1817
41510
74518
81638
89659

The median of the 24 numbers is 47317.5 But your program produces 52252.5

Hope this test case will help you find out the issue. There is a built-in Java implementation of Heap: PriorityQueue. If you want to try that out to test your logic.

\$\endgroup\$
1
\$\begingroup\$

There is a bug with respect to the logic in heapifyDown() methods which caused the incorrect median values

So the corrected heapifyDown methods are below

For MinHeap

void heapifyDown() {
            int parent = 0;
            while(hasLeftChild(parent)) {
                int smallerIndex = getLeftChildIndex(parent);
                if(hasRightChild(parent) && getRightChild(parent) < getLeftChild(parent)) {
                    smallerIndex = getRightChildIndex(parent);
                }
                if (items[parent] < items[smallerIndex]) {
                    break;
                } else {
                    swap(parent, smallerIndex);
                }
                parent = smallerIndex; 
            }
        }

For MaxHeap

oid heapifyDown() {
            int parent = 0;
            while(hasLeftChild(parent)) {
                int largerIndex = getLeftChildIndex(parent);
                if(hasRightChild(parent) && getRightChild(parent) > getLeftChild(parent)) {
                    largerIndex = getRightChildIndex(parent);
                }
                if (items[parent] > items[largerIndex]) {
                    break;
                } else {
                    swap(parent, largerIndex);
                }
                parent = largerIndex;
            }
        }
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.