Microsoft Interview Question for Interns


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you clarify more? How many jumps can we take?

- akaaa August 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- aka[1] August 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?)

- divm01986 August 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
	}
}

- jbaum517 August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- JoyZombie August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good catch! This man is correct, everyone. I should have not just been comparing locally, but comparing locally + what has already been calculated. Silly bug on my part. Thanks.

- jbaum517 August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I could only find a O(2^n) solution. Can anyone come up with anything faster?

- sex August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jim August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Indeed :-) But one should apply relevant 'SINGLE-PAIR' shortest path algo by assuming two dummy nodes at bottom and top of stairs.

- JoyZombie August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jason August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- JoyZombie August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@JoyZombie: Create one source node and put cost path from source to leftFirstStart =0 and rightFirstStair=0. Now apply dijkstra's algo. Both of the node will be in queue 2nd iteration.

- prodigy January 15, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Bhaskar August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Bhaskar August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }
    }
}

- jeetscoder August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous August 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Pyramid August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- vdPatel September 25, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More