#codingexercise
Question : A robot starts at cell (0,0) of a grid with m
rows and n columns. It can move to the left, right, up and down, and moves one
cell for a step. It cannot enter cells where the digit sum of the row index and
the col index are greater than a threshold k.
For example, when k is 18, the robot can reach cell (35, 37)
because 3 + 5 + 3 + 7 = 18. But it
cannot reach cell ( 35, 38) because 3 +
5 + 3 + 8 = 19
Solution :
Int GetCountOfMoves( int threshold, int rows, int cols)
{
Var visited = new bool[rows, cols];
For (int I = 0; I < rows; I++)
For (int j = 0; j
< rows; j ++)
Visited[i][j] =
false;
Return Move(threshold, rows, cols, 0, 0, ref visited);
}
Int Move(int threshold, int rows, int cols, int row, int
col, ref bool [,] visited)
{
Int count = 0;
If (check(threshold, rows, cols, row, col, ref visited)) {
Visited[row, col] =
true;
Return 1 + Move(threshold, rows, cols, row-1, col, ref
visited)
+ Move(threshold, rows, cols, row, col+1, ref visited)
+ Move(threshold, rows, cols, row+1, col, ref visited)
+ Move(threshold, rows, cols, row, col-1, ref visited) ;
}
Return count;
}
bool Check(int threshold, int rows, int cols, int row, int
col, ref bool [,] visited)
{
If ( row < 0 || col < 0 || row >= rows || col >=
cols || getDigitsSum(row) + getDigitsSum(col) >= threshold ||
visited[row,col] ) return false;
Return true;
}
Int getDigitsSum(int number)
{
Int sum = 0;
While (number)
{
Sum += number % 10;
Number /= 10;
}
Return sum;
}
1 / 4
Interview Questions:
Question : A robot starts at cell (0,0) of a grid with m rows and n columns. It can move to the left, right, up and down, and moves one cell for a step. It cannot enter cells where the digit sum of the row indexand the col index are greater than a threshold k.
For example, when k is 18, the robot can reach cell (35, 37) because 3 + 5 + 3 + 7 = 18. But it cannot reach cell ( 35, 38) because 3 + 5 + 3 + 8 = 19
Solution :
Int GetCountOfMoves( int threshold, int rows, int cols)
{
Var visited = new bool[rows, cols];
For (int I = 0; I < rows; I++)
For (int j = 0; j < rows; j ++)
Visited[i][j] = false;
Return Move(threshold, rows, cols, 0, 0, ref visited);
}
Int Move(int threshold, int rows, int cols, int row, int col, ref bool [,] visited)
{
Int count = 0;
If (check(threshold, rows, cols, row, col, ref visited)) {
Visited[row, col] = true;
Return 1 + Move(threshold, rows, cols, row-1, col, ref visited)
+ Move(threshold, rows, cols, row, col+1, ref visited)
+ Move(threshold, rows, cols, row+1, col, ref visited)
+ Move(threshold, rows, cols, row, col-1, ref visited) ;
}
Return count;
}
2 / 4
bool Check(int threshold, int rows, int cols, int row, int col, ref bool [,] visited)
{
If ( row < 0 || col < 0 || row >= rows || col >= cols || getDigitsSum(row) + getDigitsSum(col) >= threshold || visited[row,col] ) return false;
Return true;
}
Int getDigitsSum(int number)
{
Int sum = 0;
While (number)
{
Sum += number % 10;
Number /= 10;
}
Return sum;
}
Question: How do you find the median from a stream of numbers? The median of a set of numbers is the middle one when they are arranged in order. If the count of numbers is even, the median is defined as the average value of the two numbers in the middle.
Answer: we could keep two heaps – one for the lower half of the series and the other for the higher half of the series. The heaps should differ in their sizes by at most one node. In such a case we can insert the new number into the max heap first, then pop the greatest number from the max heap and push it into the min heap Since the number pushed is greater than the max heap, all the numbers in the min heap are still greater than the numbers in the max heap
This is true even if the count of numbers encountered so far is odd.
If the count of numbers is odd, then the median is the first element from the minheap otherwise it’s the average of the min and max heaps.
void Insert ( int num)
{
if ((minHeap.size() + maxHeap.size()) %2 == 1) {
if(maxHeap.size() > 0 && num < maxHeap[0]) {
maxHeap.push_back(num);
push_heap(maxHeap.begin(), maxHeap.end(), less<int>());
num = maxHeap[0];
pop_heap(maxHeap.begin(), maxHeap.end(), less<int>());
maxHeap.pop_back();
}
minHeap.push_back(num);
push_heap(minHeap.begin(), minHeap.end(), greater<int>());
}
else
{
if(minHeap.size()> 0 && minHeap[0] < num) {
minHeap.push_back(num);
push_heap(minHeap.begin(). minHeap.end(), greater<int>());
num = minHeap[0];
pop_heap(minHeap.begin(), minHeap.end(), greater<int>());
minHeap.pop_back();
}
maxHeap.push_back(num);
push_heap(maxHeap.begin(), maxHeap.end(), less<int>());
}
}
4 / 4
int GetMedian()
{
int size = minHeap.size() + maxHeap.size();
if (size == 0)
throw exception;
int median == 0;
if (size % 2 == 1)
median = minHeap[0];
else
median = (minHeap[0] + maxHeap[0])/2;
return median;
}
No comments:
Post a Comment