Microsoft Interview Question
InternsCountry: India
Interview Type: Phone Interview
Let p[steps] be the minimum penalty to reach "steps", same goes for q[steps] which runs in parallel.
So we can write recursive solution as:
p[steps] = min(p[steps-1]+p1, q[steps -1]+q1)
where p1 is the penalty for moving 1 step from previous step to current step.
and q1 is the penalty for moving 1 step across from previous step to current step.
We can write similarly for q[steps].
In the end, to reach the top we have to probably go to some common step:
minimum penalty = min(p[steps-1]+p1, q[steps-1]+q2)
where q2 is the penalty for moving in 'q' staircase from previous to current step.
Could you clarify a little more about jumping between the two staircases-is the penalty higher then just moving upwards on one staircase? Also, when moving across does the destination step have to be the same level as the origin step or can it be higher (ie. can you move from step 1 of staircase A to step 3 of staircase B?)
Here's a solution where the staircase is a 4xN array as follows:
Cost to move up left | cost to move right | cost to move left | cost to move up right
level 1
level 2
..
..
Now, starting from the bottom of the array we hold a size-2 array that denotes the minimum path thus far. This gives us a solution with O(n) time and O(1) space.
public class StairClimber {
public static void main(String args[]){
int stairs[][] = {
{3,5,7,9,10,12,4,6}, //cost of moving up the left side
{1,1,12,13,14,14,5,6}, //cost of moving to the right
{4,6,10,10,1,10,9,8}, //cost of moving to the left
{1,5,7,9,3,12,8,2} //cost of moving up the right side
};
System.out.println(minCostPath(stairs));
}
public static int minCostPath(int stairs[][]){
int curLevel = 0;
int costOption = 0;
int minCostThusFar[] = new int[2];
while (curLevel < stairs[0].length-1){
//Is it better to move up the left side, or move up the right side and go across?
costOption = stairs[3][curLevel] + stairs[2][curLevel+1];
if (stairs[0][curLevel] <= costOption){
minCostThusFar[0] += stairs[0][curLevel];
}
else{
minCostThusFar[0] += costOption;
}
//Is it better to move up right right side, or move up the left side and go across?
costOption = stairs[0][curLevel] + stairs[1][curLevel+1];
if (stairs[3][curLevel] <= costOption ){
minCostThusFar[1] += stairs[3][curLevel];
}
else{
minCostThusFar[1] += costOption;
}
curLevel++;
}
//Of the 2 final solutions, which is the smaller?
if (minCostThusFar[0] <= minCostThusFar[1]) return minCostThusFar[0];
else return minCostThusFar[1];
}
}
This approach is like being greedy at each step and not taking into account minCostThusFar at each step. Hence, it will not give optimal answer all the time.
You can modify your algo by NOT just comparing 'move up' or 'move up and cross'; instead you should compare 'cost of move up + minCostThusFar for same side' and 'cost of move up(other side) + minCostThusFar on other side + cost of crossing'. This will give you optimal result. Applying this technique, you are actually doing Dynamic Programming from Bottom-up approach.
Isn't it just a shortest path algo where there is a penalty from one step to another and also from one stair case to another.
Because of the 'cost' for each move, this can be reduced to a weighted graph traversal where you want to find the min cost path. Each node is a position on either staircase and has at most 2 outgoing and 2 incoming edges. At that point, something like Dijkstra would work nicely.
Dijkstra would be inefficient in comparison to Dynamic programming unless it is tweaked a little bit to find SINGLE-PAIR shortest path because generally Dijkstra is applied for SINGLE-SOURCE shortest path situations.
case there are N integers where ith integer represents penalty of step A[i]. On the third line of each test there are N integers where ith integer represents penalty of step B[i].
Output Format
For each test case, output a single line containing the minimum penalty you can accumulate on your path starting from { A[1] or B[1] } and ending on { A[N] or B[N] }.
Sample Input
1
4 1 0
1 2 3 4
1 2 3 4
------------------------------------------------------------
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int readInt() {
string input;
cin >> input;
return atoi(input.c_str());
}
class TestCase {
int _N, _K, _P;
int* _A;
int* _B;
int* _AHelper;
int* _BHelper;
int _count;
const int MAX = 10000000;
public:
TestCase(int N, int K, int P, int* A, int* B)
: _N(N), _K(K), _P(P), _A(A), _B(B), _count(0) {
_AHelper = new int[_N];
_BHelper = new int[_N];
for (int i = 0; i < _N; ++i) {
_AHelper[i] = -1;
_BHelper[i] = -1;
}
}
~TestCase() {
delete[] _AHelper;
delete[] _BHelper;
}
int execute(int N, int* X, int* helper) {
//cout << "N = " << N;
_count++;
if (N < 0) return MAX;
if (N == 0) return X[0];
if (helper[N] != -1) { cout << "found " << N << endl; return helper[N];}
int result = X[N];
int minValue = MAX;
for (int j = 1; j <= _K; j++) {
int temp = execute (N-j, _A, helper);
//cout << "minValue " << minValue << " temp " << temp << endl;
minValue = min(minValue, temp);
temp = execute (N-j, _B, helper) + _P;
minValue = min(minValue, temp);
}
helper[N] = result + minValue;
return helper[N];
}
void execute() {
if (_N < 1) {
cout << 0 << endl;
return;
}
cout << min(execute(_N-1, _A, _AHelper), execute(_N-1, _B, _BHelper)) << endl;
cout << "count " <<_count;;
}
};
int main() {
// read number of test cases
int numTestCases = readInt();
//cout << numTestCases << endl;
while (numTestCases) {
// read N
int N = readInt();
int K = readInt();
int P = readInt();
//cout << N << " " << K << " " << P << endl;
int* A = new int[N];
int* B = new int[N];
for (int i = 0; i < N; ++i) {
A[i] = readInt();
//cout << A[i] << " ";
}
//cout << endl;
for (int j = 0; j < N; ++j) {
B[j] = readInt();
//cout << B[j] << " ";
}
//cout << endl;
TestCase t1 (N, K, P, A, B);
t1.execute();
delete[] A; delete[] B;
numTestCases--;
}
return 0;
}
case there are N integers where ith integer represents penalty of step A[i]. On the third line of each test there are N integers where ith integer represents penalty of step B[i].
Output Format
For each test case, output a single line containing the minimum penalty you can accumulate on your path starting from { A[1] or B[1] } and ending on { A[N] or B[N] }.
Sample Input
1
4 1 0
1 2 3 4
1 2 3 4
--------------------------------------
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int readInt() {
string input;
cin >> input;
return atoi(input.c_str());
}
class TestCase {
int _N, _K, _P;
int* _A;
int* _B;
int* _AHelper;
int* _BHelper;
int _count;
const int MAX = 10000000;
public:
TestCase(int N, int K, int P, int* A, int* B)
: _N(N), _K(K), _P(P), _A(A), _B(B), _count(0) {
_AHelper = new int[_N];
_BHelper = new int[_N];
for (int i = 0; i < _N; ++i) {
_AHelper[i] = -1;
_BHelper[i] = -1;
}
}
~TestCase() {
delete[] _AHelper;
delete[] _BHelper;
}
int execute(int N, int* X, int* helper) {
//cout << "N = " << N;
_count++;
if (N < 0) return MAX;
if (N == 0) return X[0];
if (helper[N] != -1) { cout << "found " << N << endl; return helper[N];}
int result = X[N];
int minValue = MAX;
for (int j = 1; j <= _K; j++) {
int temp = execute (N-j, _A, helper);
//cout << "minValue " << minValue << " temp " << temp << endl;
minValue = min(minValue, temp);
temp = execute (N-j, _B, helper) + _P;
minValue = min(minValue, temp);
}
helper[N] = result + minValue;
return helper[N];
}
void execute() {
if (_N < 1) {
cout << 0 << endl;
return;
}
cout << min(execute(_N-1, _A, _AHelper), execute(_N-1, _B, _BHelper)) << endl;
cout << "count " <<_count;;
}
};
int main() {
// read number of test cases
int numTestCases = readInt();
//cout << numTestCases << endl;
while (numTestCases) {
// read N
int N = readInt();
int K = readInt();
int P = readInt();
//cout << N << " " << K << " " << P << endl;
int* A = new int[N];
int* B = new int[N];
for (int i = 0; i < N; ++i) {
A[i] = readInt();
//cout << A[i] << " ";
}
//cout << endl;
for (int j = 0; j < N; ++j) {
B[j] = readInt();
//cout << B[j] << " ";
}
//cout << endl;
TestCase t1 (N, K, P, A, B);
t1.execute();
delete[] A; delete[] B;
numTestCases--;
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
Assume that the penalty attached to the steps of the two stairs is given in two integer array stair_a[] and stair_b[] of the same size (n).
Iterate through the both array to find out the steps to be taken by comparing the penalty value of each index (steps) individually.
#include <iostream>
using namespace std;
int main()
{
int stair_a[] = {3,4,6,1,2};
int stair_b[] = {1,0,7,5,3};
printSteps(stair_a, stair_b, sizeof(stair_a)/sizeof(int));
return 0;
}
void printSteps(int stair_a[], int stair_b[], int n)
{
if (n <= 0)
{
return;
}
int p1 = 0;
int p2 = 0;
for(int i=0;i<n;++i)
{
if (stair_a[i] <= stair_b[i])
{
cout<<"climb step "<<i+1<<" on stair_a"<<endl;
}
else
{
cout<<"climb step "<<i+1<<" on stair_b"<<endl;
}
}
}
You can write a solution based on dynamic programming. Let F (i, j) be the cheapest path from the starting point to step i on staircase j, and let C (i, j) be the cost of the i-th step on staircase j. Then,
F (i,j) = C (i,j) + min (F(i-1, j), F (i-1, 0) + S, ... ,F (i-1, j-1) + S, F (i-1, j+1) + S, ..., F (i-1, numStaircases -1) + S)
In other words, to get to step i on staircase j, you must come from step i-1 on some staircase and then pay C (i, j). If it's not the same staircase, pay the switching cost S. The cheapest way to get to step i on staircase j is the cheapest way to get to one the places from where you can reach it after considering you will have to pay the switching cost if it's not the same staircase.
The OP provided a link which is supposed to be identical to the interview problem. The following code solves the problem in HackerRank.
Linear (time,space) complexity. Two memoir arrays are used for two stairs respectively.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T = 0;
int N, K, P;
int *A, *B, *PA, *PB; // PA[i]: minimum total penalty after arriving at A[i]
int costAA=999999, costAB=999999, costBA=999999, costBB=999999;
cin >> T;
for (int testIndex=0; testIndex<T; testIndex++)
{
costAA=999999, costAB=999999, costBA=999999, costBB=999999;
cin >> N >> K >> P;
A = new int [N]; B = new int [N];
PA = new int [N]; PB = new int [N];
for (int i=0; i<N; i++)
cin >> A[i];
for (int i=0; i<N; i++)
cin >> B[i];
if (K>=N)
{
costAA = A[0]+A[N-1];
costBB = B[0]+B[N-1];
costAB = A[0]+B[N-1]+P;
costBA = B[0]+A[N-1]+P;
costAA = min(costAA,costBB);
costAA = min(costAA,costAB);
costAA = min(costAA,costBA);
cout << costAA << '\n';
}
else
{
PA[N-1] = A[N-1]; PB[N-1] = B[N-1];
for (int i=1; i<=K; i++)
{
PA[N-1-i] = A[N-1-i]+min(P+PB[N-1],PA[N-1]);
PB[N-1-i] = B[N-1-i]+min(P+PA[N-1],PB[N-1]);
}
for (int i=N-1-K-1; i>=0; i--)
{
costAA=costAB=costBA=costBB=999999;
for (int step=1; step<=K; step++)
{
costAA = min(costAA,PA[i+step]);
costBB = min(costBB,PB[i+step]);
costAB = min(costAB,PB[i+step]);
costBA = min(costBA,PA[i+step]);
}
PA[i] = min(costAA,costAB+P)+A[i];
PB[i] = min(costBB,costBA+P)+B[i];
}
cout << min(PA[0],PB[0]) << '\n';
}
delete [] A; delete [] B;
delete [] PA; delete [] PB;
}
return 0;
}
Passed all tests on hackerrank.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t;
cin >> t;
int n, k, p;
while (t--) {
cin >> n >> k >> p;
int a[n], b[n];
int a1[n], b1[n];
for(int i = 0; i < n; i++) {
a1[i] = 100000000;
cin >> a[i];
}
for(int i = 0; i < n; i++) {
b1[i] = 100000000;
cin >> b[i];
}
a1[0] = 0; b1[0] = 0;
for( int i = 0; i < n; i++ ) {
for(int j = i+1; j <= i + k; j++) {
if(j >= n) break;
a1[j] = min(a1[j], a1[i] + a[i]);
b1[j] = min(b1[j], a1[i] + a[i] + p);
b1[j] = min(b1[j], b1[i] + b[i]);
a1[j] = min(a1[j], b1[i] + b[i] + p);
}
}
int ans = min(a1[n-1] + a[n-1], b1[n-1] + b[n-1]);
cout << ans << "\n";
}
return 0;
}
Can you clarify more? How many jumps can we take?
- akaaa August 06, 2015