Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
I don't see how to post a solution. So I post it as a reply. Sorry about that.
Below is the pseudo code. The idea is that just get the optimal case. (step every time.) If it does not step on K, good. That should be the optimal solution.
If it happens to step on Kth stair, the optimal case must be all the steps without the first step(1st step).
Why? Proof below:
Proof :
If we step on Kth stairs, there must be a case without Ith step, we cannot reach K.
We always avoid Kth stair by not stepping the 1st step since K != (K-1).
For an arbitrary I, I >= 1 is always true,
thus SumFrom1ToN - 1 >= SumFrom1ToN - I is always true.
Thus, skipping the 1st step is always optimal.
Solution :
long long sum = 0;
for(int i = 0 ; i < k ; i++)
{
sum += i;
if( sum > K ) {
return SumFrom1ToN(N); //Because this is optimal case. Just stepping every time does happen to step on Kth stair.
}
else if( sum == K ) { // Stepping on K, so we could just not step the first step.
return SumFrom1ToN(N) - 1;
}
}
return -1; // error. impossible to get here.
Here is the working code and output:
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
private int maxStep(int currentStep, int totalMoves, int brokenStep, int currentMove) {
if(totalMoves == 0) {
return currentStep;
}
if(currentMove > totalMoves) {
return currentStep;
}
if(currentStep + currentMove == brokenStep)
return maxStep(currentStep, totalMoves, brokenStep, currentMove+1);
else
return Math.max(maxStep(currentStep, totalMoves, brokenStep, currentMove+1), maxStep(currentStep+currentMove, totalMoves, brokenStep, currentMove+1));
}
public static void main (String[] args) throws java.lang.Exception {
Ideone one = new Ideone();
System.out.println(one.maxStep(0, 4, 10, 1));
System.out.println(one.maxStep(0, 3, 1, 1));
System.out.println(one.maxStep(0, 3, 2, 1));
}
}
Success time: 0.09 memory: 320320 signal:0
9
5
6
Do you consider condition, that no step is taken?
General question: why there is a such condition, that at n action, step might or might not be taken?
return Math.max(maxStep(currentStep, totalMoves, brokenStep, currentMove+1), maxStep(currentStep+currentMove, totalMoves, brokenStep, currentMove+1));
First part is for the case when no step is taken. Steps are not taken when
1) You end up stepping on the broken step.
2) Not taking some particular step could help you taking a later longer step
abishek, maybe I'm missing something or misunderstanding the question.
In the second output how can there be 5 total steps when the broken step is at 1?
Shouldn't the output be the total steps you can take before you reach the broken step? My impression was that you cannot go at or beyond the broken step.
I don't see how to post a solution. So I post it as a reply. Sorry about that.
Below is the pseudo code. The idea is that just get the optimal case. (step every time.) If it does not step on K, good. That should be the optimal solution.
If it happens to step on Kth stair, the optimal case must be all the steps without the first step(1st step).
Why? Proof below:
Proof :
If we step on Kth stairs, there must be a case without Ith step, we cannot reach K.
We always avoid Kth stair by not stepping the 1st step since K != (K-1).
For an arbitrary I, I >= 1 is always true,
thus SumFrom1ToN - 1 >= SumFrom1ToN - I is always true.
Thus, skipping the 1st step is always optimal.
Solution :
long long sum = 0;
for(int i = 0 ; i < k ; i++)
{
sum += i;
if( sum > K ) {
return SumFrom1ToN(N); //Because this is optimal case. Just stepping every time does happen to step on Kth stair.
}
else if( sum == K ) { // Stepping on K, so we could just not step the first step.
return SumFrom1ToN(N) - 1;
}
}
return -1; // error. impossible to get here.
Everytime we take a step, we need to ensure that we won't be resting on the 'k'th step which is broken. All other steps we can take. Please check the solution below.
int fnMaxSteps(int n,int k){
int steps = 0;
for (int i=1;i<=n;i++){
if(steps+i==k)
continue;
else
steps+=i;
}
return steps;
}
You know that you will reach k by following the pattern 1,2,3,4,... if 1 + 2 + 3 + 4 + 5 +...a = k
What does this remind us of?
1 + 2 + 3 + 4 + 5 +...x = (x)(x + 1)/2
So, we can work from here and see if there's an x such that this case is true. If not, then our answer is (n)(n+1)/2
If so, we do
(x-1)(x)/2 + remaining steps starting from x +1.
remaining steps starting from x + 1 would be (n + 1)(n + 2)/2 - (x)(x+1)/2
So our final answer would be
(x - 1)(x)/2 + (n + 1)(n + 2)/2 - (x)(x+1)/2
public int numSteps(int k, int n) {
if (!integerSolutionExists(k)) {
return getSum(n);
}
int x = (int) solveQuadratic(k);
return getSum(x - 1) + getSum(n) - getSum(x);
}
public int getSum(int x) {
return (x * (x + 1))/2
}
public boolean integerSolutionExists(int k) {
return(Math.floor(solveQuadratic(k)) == solveQuadratic(k));
}
public double solveQuadratic(int k) {
return (-1 + Math.sqrt(1 - 4 * (-2 * k)))/2;
}
The question is to find the maximum steps we can go.
If there exists an integer solution to quadratic equation(as you mentioned), then we can skip the first step to escape on landing kth step.
Then the solution would be something like follows.
1+2+...x = k --> solve this, if there exists integer solution, answer would be n(n+1)/2 -1 else, n(n+1)/2
Answer to this question is Either sumof(N) -1 orr Sumof(N) depends if sum of initial A steps sumof(A) is Equal to K of not. If we can jump off the Kth step.
- sanjay.2812 May 03, 2015If not i.e. if we can't cross the kth step as it is broken..
So at max we can reach upto k-1 step
we can start subtracting k with the step starting from n then n-1 and so on. when the value is less then 0, Don't take that step and move to next.