#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;
}
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