Confusing problem in DE Shaw interview

general
1

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

please help me in solving this and also if there are any similar questions please let me know

Thank you.

1 Like
2

This was a Dynamic Programming Question.

3

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
4

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

5

Yes Bro,
I’ve also thought it must be a DP question.
Can u help me to Solve this ?
If u had already solved quetions similar to this please let me know
Thanks

6

This is quite similar.

7

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

Try learning DP but.

8

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
9

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

10

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.