InternDoor

Collect without neighbours

Mediumdynamic programming · arrays

Reported in interviews at (where)

Houses stand in a row and coins[i] is what house i holds. You may take the coins from any houses you like, as long as you never take from two houses that stand next to each other.

Return the most coins you can collect.

Example 1
Input
coins = [6,1,2,9,3]
Output
15

Take houses 0 and 3: 6 + 9. Adding house 4 would touch house 3.

Example 2
Input
coins = [4,4]
Output
4

The two houses are neighbours, so only one of them.

Limits

  • 1 <= coins.length <= 100000
  • 0 <= coins[i] <= 10000

Hints

Hint 1

The best up to house i either skips house i, or takes it and adds the best up to house i - 2.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.