← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
You are given an integer array nums representing the amount of money in each house in a row. A robber wants to steal the maximum amount of money without robbing two adjacent houses (which would trigger an alarm). Return the maximum amount of money that can be stolen.
In the onsite round at Databricks, this classic House Robber problem is extended into two variants:
Linear street (House Robber I): Houses are in a straight line; implement the standard DP recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Circular street (House Robber II): The first and last houses are also adjacent. Solve by running the linear algorithm twice—once excluding the first house and once excluding the last house—and return the maximum of the two results.
You are expected to derive the recurrence, handle base cases (empty array, single house, two houses), and optimize space to O(1) by keeping only the previous two values.