## Capgemini Interview Question

- 1of 1 vote

AnswerYou and your friends are pilots in the Clone army.You are facing the aerial fleet of the Droid army.Droid planes move while maintaining a long line so that their shields interact making it impossible to shoot down planes in the middle of the line.Thus,your only option is to keep shooting down planes at the edges of the line.

- shukad333 September 11, 2014 in United States

You and your friend have decided to make a game of it.Each Droid plane has an importance level IMP[i].Since the droid planes don't advertise their importance levels, both of you must follow a mixed strategy and shoot down either the first plane or the last plane with 50% chance each.If there is a single plane,the shooter with the turn will shoot it down for sure.The two of you take turns to shoot down enemy planes.You have the first turn.What is the expected sum of importance levels you will shoot down?

Input format:

# The number of droid planes

input1=N(1<=N<=1000)

# An array containing the importance levels of droid planes.

input2=IMP(for 0<i<=N,1<=IMP[i]<=100)

Output format:

A string containing your expected sum of importance levels of shot down planes,rounded to 3 places of decimal.

Example:

Input:

2

10 20

Output:

15.000| Report Duplicate | Flag | PURGE

Capgemini

**Country:**United States

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Sounds like 3-dimensional dynamic programming. The dp function is as follows:

dp[i][j][k] = ((dp[i + 1][j][!k] + num[i]) + (dp[i][j - 1][!k] + num[j] )) / 2;

This idea can be easily implemented using 3 loops which I believe any of you can do:)

Here I just provide my implementation

- ravio September 13, 2014