Amazon Interview Question
Software Engineer / Developers<pre lang="" line="1" title="CodeMonkey52805" class="run-this">#include <iostream>
#include <vector>
using namespace std;
int find_min_steps(vector<int>& input) {
int start, end, next_start;
vector<int> result;
start = end = 0;
int n = input.size();
while (end < n-1){
int max = -1;
for(int w = 0; start<= end ; w++, start++){
if(input[start] + w > max) {
max = input[start] + w ;
next_start = start;
}
}
if(input[next_start] == 0) {
cout << endl << "not possible to traverse the array ..stuck at input index : " << next_start << endl;
return -1;
}
start = end + 1;
end = next_start + input[next_start];
result.push_back(input[next_start]);
}
cout << endl << "steps are : ";
for(int i =0; i< result.size(); ++i)
cout << endl << result[i];
cout << endl;
return result.size();
}
int main() {
vector<int> input;
int t = -1;
cout << endl << "enter input values.. (-1) to end" << endl;
do {
cin >> t;
input.push_back(t);
}while(t != -1);
input.resize(input.size() -1); //remove last pushed -1.
cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
return 0;
}
</pre><pre title="CodeMonkey52805" input="yes">
</pre>
Dijkstra's algorithm or BFS
-> consider each element is a node.
-> each node value represents connections to the next k nodes. so connect edges to next k nodes.
-> edge weights are '1'.
-> find the shortest path after constructing the graph
(or maybe mapreduce can be used?)
@above
Read the soln properly
Here decison is based on the max value of i+a[i] not on max value of a[i]
According to greedy
while(i!=n){
maxindex=i;
for(int j=i;j<i+a[i];j++)
if(j+a[j]>maxindex+a[maxindex])
maxindex=j;
}
i=j;
minjmp++;
}
If the array is given, and we have to start from the first one, then why we can choose the elements? Everything is determined when the array is generated.
like 1,2,3,4,5,6,7, we can only start from 1, and 1 lead us to 2, 2 lead use to 4, et.
what on earth is the question asking?
vector<int> FindMinimumJumpsInArray(vector<int> a)
{
vector<int> jumpArray;
int maxIndex = 0;
bool bDestReached = false;
while(true)
{
jumpArray.push(maxIndex);
nextLevel = a[maxIndex];
int maxValue = 0;
for(int i=maxIndex+1; i<=nextLevel; ++i)
{
if(i == a.size())
{
bDestReached = true;
break;
}
if(maxValue <= i + a[i])
{
maxValue = i + a[i];
maxIndex = i;
}
}
if(bDestReached)
{
break;
}
}
if(bDestReached)
return jumpArray;
else
return vector<int>();
}
int min_selections(int arr[],int n)
{
int i,j;
int dp[n],min;
dp[n-1]=1;
for(int i=n-2;i>=0;i--)
{
dp[i]=1;
min=10000;
for(j=1;j<=arr[i]&&(i+j)<n;j++)
if(dp[i+j]<min)
min=dp[i+j];
dp[i]+=min;
}
return dp[0];
}
int main(void)
{
int n,arr[20];
cout<<"Size: ";
cin>>n;
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<min_selections(arr,n);
}
It is more like dynamic programming
we know that we have to reach the last element
Now take another array of the same size and set the last element value to 0
This is because the last element can reach to itself in ZERO steps
we use memorization in dynamic programming
1. Let jump[n] be the resultant array
//is the array specifying number of jumps required by each element to reach the last element
2. Set jump[n-1] = 0. //if we have to reach the last element
3. for each element in the jump array starting fromt the last but one element to the first element
jump[n-i] = min(1+min( jump[n-i+1] to jum[input[n-i]])//where input is the i/p array with the possible jumps
Special case 1:
if the element can reach the last element from imput[n-i] i.e
if the element is 7th element in the 10 element array with input[7]=5 then it can directly reach last element
Therefore jump[7] = 1
Special case 2:
if the input[i]=0 for an element then jump[i] = INTEGER.MAX//so that we don't use this element to jump
4. At the end jump[0] would give us the minimum number of jumps required to reach last element from the first
example:
index: 0 1 2 3 4 5 6 7 8 9 10
input: 1 3 5 8 9 2 0 7 6 8 9
step 1: set jump[n-1]=0
index: 0 1 2 3 4 5 6 7 8 9 10
jump : 0
step2: now 9 can directly reach 10 as it can have 8 jumps from 9.
So is index 8, it has 6 jumps from 8 and it requires only 2 to reach 10
for 6 it would be a different story as it cannot go ahead
index: 0 1 2 3 4 5 6 7 8 9 10
jump : INF 1 1 1 0
5 can reach only 6 and 7 so it has to choose minimum between 1+INF and 1+1, adn so it selects 1+1=2
3 and 4 can reach directly to 10 with 8 and 9 jumps respectively so their values are 1 and 1
index 2 can go from index 3 to 7 and selects minimum from it and adds 1 to it and so has a value of 2
index 1 can select either 2 or 3 or 4 whose values are 2, 1 and 1 resp. so it selects either 1 in it and adds its own 1
therefore jump[1]=2
index 0 can only go to 1 and so has jump[1]=3
which is the minimum number of jumps
index: 0 1 2 3 4 5 6 7 8 9 10
jump : 3 2 2 1 1 2 INF 1 1 1 0
<pre lang="" line="1" title="CodeMonkey12499" class="run-this">#include <iostream>
#include <vector>
using namespace std;
int find_min_steps(vector<int>& input) {
int start, end, next_start;
vector<int> result;
start = end = 0;
int n = input.size();
while (end < n-1){
int max = -1;
for(int w = 0; start<= end ; w++, start++){
if(input[start] + w > max) {
max = input[start] + w ;
next_start = start;
}
}
if(input[next_start] == 0) {
cout << endl << "not possible to traverse the array ..stuck at input index : " << next_start << endl;
return -1;
}
start = end + 1;
end = next_start + input[next_start];
result.push_back(input[next_start]);
}
cout << endl << "steps are : ";
for(int i =0; i< result.size(); ++i)
cout << endl << result[i];
cout << endl;
return result.size();
}
int main() {
vector<int> input;
int t = -1;
cout << endl << "enter input values.. (-1) to end" << endl;
do {
cin >> t;
input.push_back(t);
}while(t != -1);
input.resize(input.size() -1); //remove last pushed -1.
cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
return 0;
}
</pre><pre title="CodeMonkey12499" input="yes">
</pre>
int FindMax(int range, int current, int *source)
{
int tmp;
int currentMax = source[current+1] - (range + 1);
int maxPosition = current+1;
for (int i=2; i<range; i++)
{
tmp = source[current+i] - (range + i);
if ( tmp > currentMax )
{
currentMax = tmp;
maxPosition = current + i;
}
}
return maxPosition;
}
int FindJumpCount()
{
int source[11] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
int arrayEnd = 11;
int jumpCount = 0;
int currentPosition = 0;
while ( (source[currentPosition] + currentPosition) < arrayEnd )
{
currentPosition = FindMax(source[currentPosition], currentPosition, source);
jumpCount++;
}
jumpCount++;
printf("Jump Count is %d ", jumpCount);
return jumpCount;
}
This code will not work.
e.g.
source[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1};
output is JumpCount = 6 and the jumps are
[1]->[3]->[8]->[9]->[6]->[7]->[1]
But the actual jumps should be
[1]->[3]->[5]->[7]->[1]
For source[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1};
the jumps should be
[1]->[3]->[9]->[1] which has 4 elements in the sequence, not 5
This can be done greedily.
- nitin November 23, 2010Your greedy selection will be based on max(i+a[i ]).
So at any index j,you can take a jump of size a[j], so consider an index 'k' in the interval
j to j+a[j] such that k+a[k] is maximum and jump to that.
Time : O(n)
Space : O(1)