Friday, October 10, 2014
No. 57 - Integer Identical to Index
Problem: Integers in
an array are unique and increasingly sorted. Please write a function/method to
find an integer from the array who equals to its index. For example, in the array
{-3, -1, 1, 3, 5}, the number 3 equals its index 3.
Analysis: If we scan
all integers in the array from beginning to end, we may check whether every
element equals its index. Obviously, this solution costs O(n) time.
Since
numbers are sorted in the array, let's try to utilize the binary search
algorithm to optimize. Supposing we reach the ith element in the array
at some step. If the value of element is also i,
it is a target integer and let's return it.
What
would happen when the value m is greater
than the index i? For any k (k>0),
the value of element with index i+k should be greater than or equal to m+k,
because integers are unique and increasingly sorted in the array. Additionally
because m>i, m+k>i+k. Therefore, every element on the right side
of index i should be greater than its
index in such a case.
Similarly,
when the value of element with index i
is less than i, every integer on the left
side should be less than its index. Please prove it if you are interested.
Therefore,
we could reduce the search scope to half for the next step, and it is a typical
process for binary search. The solution can be implemented with the following
Java code:
publicstaticint
getNumberSameAsIndex(int[] numbers) {
if(numbers == null || numbers.length == 0) {
return -1;
}
int left = 0;
int right = numbers.length - 1;
while(left <= right) {
int middle = left + ((right - left) >>> 1);
if(numbers[middle] == middle) {
return middle;
}
if(numbers[middle] > middle) {
right = middle - 1;
}
else {
left
= middle + 1;
}
}
return -1;
}
The
source code with unit test cases is shared at http://ideone.com/ZSd9kG.
More coding
interview questions are discussed in my book< Coding Interviews: Questions,
Analysis & Solutions>. You may find the details of this book on Amazon.com,
or Apress.
The author Harry He owns all the rights of
this post. If you are going to use part of or the whole of this article in your
blog or webpages, please add a reference to http://codercareer.blogspot.com/.
If you are going to use it in your books, please contact the author via
zhedahht@gmail.com . Thanks.
Labels:
Algorithm,
Binary Search,
Facebook,
Google,
Interview Question
Saturday, October 4, 2014
No. 56 - Maximal Value of Gifts
Question:
A board has n*m cells, and there is a gift with some value (value is greater than
0) in every cell. You can get gifts starting from the top-left cell, and move
right or down in each step, and finally reach the cell at the bottom-right
cell. What’s the maximal value of gifts you can get from the board?
For example, the maximal value of gift from the board above
is 53, and the path is highlighted in red.
Analysis:
It is a typical problem about dynamic programming. Firstly let’s analyze it
with recursion. A function f(i, j)
is defined for the maximal value of gifts when reaching the cell (i, j).
There are two possible cells before the cell (i, j) is reached: One is
(i - 1, j), and the other is the cell (i,
j-1). Therefore, f(i, j)= max(f(i-1,
j), f(i, j-1)) + gift[i, j].
Even though it’s a recursive equation, it’s not a good idea
to write code in recursion, because there might be many over-lapping
sub-problems. A better solution is to solve is with iteration. A 2-D matrix is
utilized, and the value in each cell (i,
j) is the maximal value of gift when
reaching the cell (i, j) on the board.
The iterative solution can be implemented in the following
Java code:
publicstaticint getMaxValue(int[][] values) {
int rows = values.length;int cols = values[0].length;
int[][] maxValues = newint[rows][cols];
for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
int left = 0;
int up = 0;
if(i > 0) {
up = maxValues[i - 1][j];
}
if(j > 0) {
left = maxValues[i][j - 1];
}
maxValues[i][j] = Math.max(left, up) + values[i][j];
}
}
return maxValues[rows - 1][cols - 1];
}
Optimization
The maximal value of gifts when reaching the cell (i, j)
depends on the cells (i-1, j) and (i, j-1) only, so it is
not necessary to save the value of the cells in the rows i-2 and above. Therefore, we can replace the 2-D matrix with an
array, as the following code shows:
publicstaticint getMaxValue(int[][] values) {
int rows = values.length;
int cols = values[0].length;
int[] maxValues = newint[cols];
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
int left = 0;
int up = 0;
if (i > 0) {
up = maxValues[j];
}
if (j > 0) {
left = maxValues[j - 1];
}
maxValues[j] = Math.max(left, up) +
values[i][j];
}
}
return maxValues[cols - 1];
}
The source code with unit test cases is shared at http://ideone.com/2vLRMk.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/ . If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.
Subscribe to:
Posts (Atom)