1
\$\begingroup\$

https://leetcode.com/problems/house-robber/

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

 Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and
 then rob house 3 (money = 3).
 Total amount you can rob = 1 + 3 = 4. Example 2:


Example 2:
Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

using System;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    /// <summary>
    ///  https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/576/
    /// </summary>
    [TestClass]
    public class HouseRobber
    {
        [TestMethod]
        public void HouseRobberTest()
        {
            int[] nums = {1, 2, 3, 1};
            HouseRobberClass robber = new HouseRobberClass();
            Assert.AreEqual(4, robber.Rob(nums));
        }


        [TestMethod]
        public void HouseRobber2Test()
        {
            int[] nums = { 1, 2, 3, 1 };
            HouseRobberClass robber = new HouseRobberClass();
            Assert.AreEqual(4, robber.Rob2(nums));
        }
    }

    public class HouseRobberClass
    {
        private int[] _mem;
        //option 1 for a solution - this is easier for me to think this way
        public int Rob(int[] nums)
        {
            _mem = Enumerable.Repeat(-1, nums.Length).ToArray();

            return Helper(nums,  0);
        }

        private int Helper(int[] nums, int index)
        {
            if (index >= nums.Length)
            {
                return 0;
            }

            if (_mem[index] >= 0)
            {
                return _mem[index];
            }

            _mem[index] = Math.Max(Helper(nums, index + 2) + nums[index], Helper(nums, index + 1));
            return _mem[index];
        }

       // option 2 for a solution
        public int Rob2(int[] nums)
        {
            if (nums.Length == 0)
            {
                return 0;
            }
            int[] memo = new int[nums.Length + 1];
            memo[0] = 0;
            memo[1] = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                int val = nums[i];
                memo[i + 1] = Math.Max(memo[i], memo[i - 1] + val);
            }

            return memo[nums.Length];
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

Your first solution's time complexity is non-trivial to determine, and it won't work for long lists because it'll run out of stack, while your second solution obviously needs linear time (optimal) and is unlikely to run out of memory, so I would scrap the first one right away.

The first solution is also inferior because of the _mem member. There is no reason to create this in Rob, and there is no reason to make it a member. Making it a member means: - this code can't be called concurrently - it leaves memory hanging around once the method exists - it is susceptible to interference by other members - it is hard to reason about than a variable because it is removed from the method that use it

One nice solution would be to make _mem a local variable, and Helper a local function in Rob: that way you don't have to pass nums and _mem around, and there is no way to mis-use the code. Then you can make all these methods static.

Naming

The naming could be better:

  • _mem and memo are both cryptic (_mem is providing memoisation, and memo is arguably not)
  • Rob and Rob2 convey almost nothing
  • Helper says nothing at all (what is it helping? what does it do?)

Documentation

  • Please take the time to add documentation. It doesn't matter if you are practising for an interview: real code needs documentation (so that it can be consumed and maintained), writing it is a skill worth practising, and doing so helps you to better reason about your code and solidify edge-case behaviour.

Tests

The tests are limited and not very good. They do not test the case where you need to 'skip' a pair (e.g. 9, 1, 1, 9) and do not cover any edge cases.

Both methods will throw on a NullReferenceException on null input, when they should probably throw a nice ArgumentException so that the caller knows immediately what they did wrong: ideally this would be tested.

\$\endgroup\$
  • \$\begingroup\$ I hope OP takes advice to heart and starts documenting a bit better next challenge. This is a recurring issue :) \$\endgroup\$ – dfhwze Sep 20 at 13:58
  • 1
    \$\begingroup\$ @dfhwze It's not like OP is under any obligation to to listen to all advices in the review, especially when it comes to documentation in a coding challenge. I know I wouldn't do it :p \$\endgroup\$ – IEatBagels Sep 20 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.