# Confusing problem in DE Shaw interview

I want to share a coding question which was recently asked by D.E.shaw company as part of recruitment in india.

I don’t remember the exact question but i will tell u the outline.

which was :

In the question there is a girl and she had to cross a series of land mines ,she cannot step on consecutive land mines but she can skip any number of land mines ,if she steps on a land mine then she loses a certain score.

For each land mine there is certain integer denoting the score she loses on stepping that landmine.if she steps on more than one land mines then she loses score which is the sum of those corresponding integers .

inputs are: n-number of land mines

``````              array of  n integers  denotes scores which she loses on corresponding land mine
``````

we need to output a single integer which is the minimum score she will lose

example:

5

8 1 4 6 9

ans:

1+6=7

I am so confused on seeing the question then I did it by summing up of odd indexed and even indexed numbers and printed the minimum of them but using this approach I am able to pass only 4 testcases out of 13

Thank you.

1 Like

This was a Dynamic Programming Question.

Bro your quest doesn’t make any sense.If she can skip any no of land mines they I will skip the whole array first of all.
Plz post the original question.

2 Likes

We have to find minimum score without skipping whole array.
In the question they have not mentioned this Because I tried by putting zeros still it doesnt paased any test cases

Yes Bro,
I’ve also thought it must be a DP question.
Can u help me to Solve this ?
Thanks

This is quite similar.

I managed to brute force a few cases, that’s it.

Try learning DP but.

I think there should be an integer ‘K’ which denotes maximum land mines she can skip…then it is just dynamic programming:
dp[i] = a[i] + \min\limits_{j=2}^{K+1}dp[i-j] , dp[0] = 0
The final Answer would be dp[n+1]. Although it is O(N*K) but it can be optimized to O(N*log(K)) with help of sets.

1 Like

It’s actually a common question.The same question was asked in fb hackercup also(with little modification).

This is the exact same question,they have just changed the language.I solved that question in their test which happened on 8th Aug through same code given in above question.