Amazon Interview Question
Software Engineer / DevelopersI am not sure what the complexity would be. I am not able to figure it out.
BFS complexity is |V|+|E| and in this case, and |E| here is sum of contents of the array. But This graph is a special one. Not able to think what the worst case would be.
O(n) is possible.
Start from the left. You always have a sub-array A[0], A[1], ..., A[n_k] which is reachable in k or less steps.
i.e. A[0], A[1], .., A[n_1] is reachable after 1 step.
A[0], A[1], ..., A[n_2] is reachable in 1 or 2 steps, with A[n_1+1],..., A[n_2] being reachable only in 2 steps.
So to compute n_{k+2}, you simply consider max {A[n_k+1] + n_k , A[n_k+1], n_k+1, ..., A_[n_{k+1}] + n_{k+1}}
Since you consider each element A[j] only once, this is an O(n) time algorithm.
The O(n log n) time algorithm described is interesting. It computes the shortest path for each element!
Kind of like a single shortest path vs all pairs shortest path.
n_1 = n subscript 1. I believe this is latex like notation and is pretty standard in text based forums.
Maintain the minimum number of steps from a given index to the end.
For example, if input array is A = [2,3,2,1,4]
You start with the right end.
Min[4] = 0.
Now you consider element at index 3.
Min[3] = 1
Now consider element at index 2.
Since A[2] is 2, you find the the minimum among Min[3], Min[4] and set Min[2] = min{Min[3], Min[4]} + 1.
and so on.
In the end you end up with the Minimum steps starting from the first.
A naive algorithm will do O(n^2).
A tree can cut it down to O(n log n).
Seems like O(n) should be possible, but escapes me at the moment.
You need a data structure which supports the following:
1) insert(x): insert value x.
2) get_min(j): which gives the minimum of the last j elements that were inserted using insert.
Eg.
If we do insert(1); insert(0); insert(16); insert(12)
Now get_min(2) should return 12.
get_min(3) should return 0.
Now insert(11); followed by get_min(2) should return 11.
Using balanced trees with extra fields, we can support both (insert and get_min) in O(log n) time.
I will leave it to you to try it.
public final class OptimalJump {
public OptimalJump(int[] arr) {
super();
this.arr = arr;
}
public Jump determineJump(){
return findMinJump(0, 0);
}
//==== NESTED ====
public static class Jump implements Comparable<Jump> {
@Override
public int compareTo(Jump other) {
int size1 = elements.size();
int size2 = other.elements.size();
if( size1 > size2 ){
return 1;
}
else if( size1 < size2 ){
return -1;
}
return 0;
}
@Override
public String toString(){
return elements.toString();
}
private List<Integer> elements = new ArrayList<Integer>();
}
private static final class JumpKey {
JumpKey(int index, int offset) {
super();
this.index = index;
this.offset = offset;
}
int index;
int offset;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + index;
result = prime * result + offset;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
JumpKey other = (JumpKey) obj;
if (index != other.index)
return false;
if (offset != other.offset)
return false;
return true;
}
}
//==== PRIVATE ====
private final int[] arr;
private final Map<JumpKey, Jump> cache = new HashMap<JumpKey, Jump>();
private Jump findMinJump( int index, int offset ){
final JumpKey key = new JumpKey(index, offset);
Jump memJump = cache.get( key );
if( memJump != null ){
return memJump;
}
index = index + offset;
final int value = arr[index];
Jump minJump = null;
for( int i = 1; i < value+1 && index+i < arr.length; i++ ){
Jump jump = findMinJump(index, i);
if( minJump == null || jump.compareTo(minJump) < 0 ){
minJump = jump;
}
}
if( minJump == null ){
minJump = new Jump();
}
minJump.elements.add(0, index);
cache.put(key, minJump);
return minJump;
}
}
Let arraylength = N
keep mincount = N, patharray[N], minpatharray[N]
function jump (arr, int i, count)
{
if (i equals N)
{
check current patharray.
if count < mincount
{
save a copy of current patharray in minpatharray
mincount = count;
}
}
else
patharray[count++] = i;
for (j=1 to N)
jump (arr, i+j, count);
}
call jump as
jump (arr, 0, 0);
print minpatharray and mincount.
This has already been mentioned above: The naive O(n^2) method.
Why not make a post to add something new?
I think its Dijkstra where:
1. Adjacent vertices are all values at the index <= (current index+current value)
2. distance is the value at indices
3. weight is constant
4. Instead of min we have to extract max while doing BFS.
As we know that using priority heap it can be done in nlogn
Please correct me if my approach is wrong.
#include <iostream>
using namespace std;
int select_max(int arr[], int current_pos, int max_pos);
int main()
{
int arr[] = {3,3,2,2,4,8,2,1,10,9,5,2};
int jumps = 0;
int size = (int)(sizeof(arr)/sizeof(int));
for(int i = 0; i + arr[i] < size - 1;)
{
i = select_max(arr, i, i + arr[i]);
cout << "jump to " << i << "\n";
jumps++;
}
cout << "Number of jumps = " << jumps << endl;
}
int select_max(int arr[], int current_pos, int limit_pos)
{
int max_pos = current_pos;
int max_value = 0;
for(int i = current_pos; i <= limit_pos; ++i)
{
if(arr[i] >= max_value)
{
max_pos = i;
max_value = arr[i];
}
max_value--;
}
return max_pos;
}
Did I miss anything?
order is O(n) and space is O(1), IMO. Forgive if the solution is mentioned in above comments.
Thanks,
Yes, you missed a description of what you are trying to do.
How hard is it to describe your algorithm?
I am trying to solve the problem :P and description shouldn't be hard to write but might be hard to understand given how I will write.
I used the greedy approach. Starting with index 0, I find the position which has the maximum value where I can jump. But I consider the fact that {3, 2} lying in this order are equivalent by decreasing the value at any current index by 1 while checking for the max value. For example, {3, 3, 2, 2, 3, 4} I chose index 3 and not index 1 on first jump from index 0.
I do it iteratively until I reach the end.
HTH.
Yes for that there is no solution.
Nitin's solution in fact looks similar to the O(n) solution posted earlier.
@Nitin. Your approach fails for below input sequence :-
5,1,2,3,4,1,1,1,5,1,1,2,E
Intially your algo with select index 0 among 5,1,2,3,4 values. Thus from 0 you will go to index 5 having value 1. but instead of chosing index 0 you would hv choosen index 4 having value 4, then from index 4 you would hv got option of moving to index 8 having value 5, which will take u to end.
According to your algo :- 5,1,1,1,5,E
But the best solution is :- 5,4,5,E
@Nitin : Your approach will fail for sequence as below :
10,9,8,7,6,4,3,2,1,1,1..
when you are at 10, your algo with select 9 as next index to be used, although the current jump of 10 itself is good enough to move 10 steps ahead.
<pre lang="" line="1" title="CodeMonkey19107" class="run-this">@Nitin : Your approach will fail for sequence as below :
10,9,8,7,6,4,3,2,1,1,1..
when you are at 10, your algo with select 9 as next index to be used, although the current jump of 10 itself is good enough to move 10 steps ahead.</pre>
@Nitin. Your approach fails for below input sequence :-
5,1,2,3,4,1,1,1,5,1,1,2,E
Intially your algo with select index 0 among 5,1,2,3,4 values. Thus from 0 you will go to index 5 having value 1. but instead of chosing index 0 you would hv choosen index 4 having value 4, then from index 4 you would hv got option of moving to index 8 having value 5, which will take u to end.
According to your algo :- 5,1,1,1,5,E
But the best solution is :- 5,4,5,E
Similar to Djikstra
1. each ith element(or node) is connected to next a[i] elements(nodes)
2. Distance between any 2 nodes is 1
3. solution : shortest distance between a[0] and a[n-1]
MJ(i)
if(i == n)
return 0
min = 0
for each j from i+1 to i +a[i]
v = MJ(a[j])+1
if(v < min)
min = v
return min
A simple linear time solution.
public boolean canJump(int[] A) {
if(A.length <= 1) return true;
// the small index position that can jump to the end
int firstJump = A.length-1;
for(int i=A.length-2;i>=0;i--){
int j = i+A[i];
if(j >= A.length-1 || j>=firstJump){
firstJump=i;
break;
}
}
return firstJump == 0;
}
I think one way of doing it is by building a DAG. Have a DAG with each node representing each index of the array. So for array of size 'n' you'd get a DAG with 'n' nodes. Now connect the nodes which are reachable from each node. i.e. if A[i]=k then make directed edges from node representing 'i' to nodes i+1, i+2 ... i+k. Once you have built the graph, a simple BFS would fetch u the shortest path as well as the number of nodes in the path.
- pH August 11, 2011