Saturday, May 14, 2016

#coding exercise
Find the minimum number of steps to reach the end of array from start. Array values give how much we can move.
Int GetMin( List <int> arr, int start, int end )
{
If (start == end) return 1;
Return min (
1 + GetMin (Arr, start+ arr [start], end),
GetMin (arr, start+1,end));
}

median of a stream of two numbers:
Maintain two heaps max and min
on a new number
       if (total size is odd)
             if max_heap size is >0 && num > median
                       max_heap.push(num)
                        heapify
                        num = max_heap.pop_back()
                        heapify
             min_heap.add(num)
              heapify
        else
             if min_heap size is > 0 && num < median
                          min_heap.push(num)
                          heapify
                          num =  max_heap.pop_back()
                           heapify
              max_heap.add(num)
              heapify
median :
     heap_size is odd
                  min_heap[0]
     else
                  (max_heap[0] + min_heap[0] ) /2

It may be better to rename the heaps as left and right because one will be max heap and the other will be min heap and we merely extract the top and insert. In other words we balance.

Find the maximum difference in the values between a node and an ancestor in a  tree
int GetMin(Node root, ref int max)
{
if (root == null) return INT_MAX;
int min_left = GetMin(root.left);
int min_right = GetMin(root.right);
int min =  min(root.data, min_left, min_right);
if ( root.data - min > max)
   max = (root.data - min);
return min;
}

Given n eggs and k floors where any egg might break when dropped from a certain minimum height, find the minimum number of tries to find the answer
int W(int n, int k)
{
if (k == 1) return 1;
if( n== 1) return k;
int min = INT_MAX;
for (int i = i; i <= k; i++)
     int val = max(W(n-1,i-1), W(n, k-i))
if ( val < min)
    min = val;
return 1 + min;
}
#autocomplete : https://github.com/ravibeta/javascriptexamples/blob/master/Autocompleteextender
Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j]
int GetMax(List<int> A, int start, int end)
{
int max = 0;
for (int k = start; k <= end; k++)
{
 int ret = k;
 int maxindex = k;
for(int I = end; I > k; I--)
     if (A[I] > A[k]){
           maxindex = I;
           break;
   }
if (maxindex-k> max)
   max = maxindex-k;
}
return max;

No comments:

Post a Comment