Here is the link.
Mock interview - C# - Hard to tell - add number more than once - Failed 114/115
Dec. 29, 2020
Introduction
I wrote the solution in Leetcode premium mock interview onsite from Facebook, I could not pass the test case 114/115. But I could not tell what it is wrong.
Failed test case
var test = new int[] { 4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, 16, 16, 16, 16, 16, 16, 20, 20, 20, 20, 20, 20, 20, 20, 24, 24, 24, 24, 24, 24, 24, 24, 28, 28, 28, 28, 28, 28, 28, 28, 32, 32, 32, 32, 32, 32, 32, 32, 36, 36, 36, 36, 36, 36, 36, 36, 40, 40, 40, 40, 40, 40, 40, 40, 44, 44, 44, 44, 44, 44, 44, 44, 48, 48, 48, 48, 48, 48, 48, 48, 52, 52, 52, 52, 52, 52, 52, 52, 56, 56, 56, 56, 56, 56, 56, 56, 60, 60, 60, 60, 60, 60, 60, 60, 64, 64, 64, 64, 64, 64, 64, 64, 68, 68, 68, 68, 68, 68, 68, 68, 72, 72, 72, 72, 72, 72, 72, 72, 76, 76, 76, 76, 76, 76, 76, 76, 80, 80, 80, 80, 80, 80, 80, 80, 84, 84, 84, 84, 84, 84, 84, 84, 88, 88, 88, 88, 88, 88, 88, 88, 92, 92, 92, 92, 92, 92, 92, 92, 96, 96, 96, 96, 96, 96, 96, 96, 97, 99 };
Hard to tell
Every time the number is considered, it is important to avoid the number to be added more than once.
For example, [1, 7, 4, 5],
dp[1] = true, since first number 1 is in the array;
dp[7] = true, since 7 is the second number in the array;
Also dp[8] should be true, since 1 + 7 = 8.
Next it is to work on index = 2, value 4,
dp[5] should be true, since 1 + 4 = 5, but it should not be updated right away.
The for loop in the following code is to iterate from 1 to 8.
Avoid setting dp[5 + 4] = 9.
Let me try to explain what it is wrong in the following statements:
for (int j = 1; j <= prefixSum; j++)
{
if (dp[j])
{
dp[j + current] = true;
}
}
The reason to set dp[9] = true is that dp[5] is set true right away, and then dp[5] + 4 = 9, but 4 is counted twice.
The following code has a bug but I could not tell in my mock interview. I spent over 5 minutes to think but failed to come out the idea.
The correct solution
The working solution is here.
The following code has a bug, could not pass online judge. But I like to remind myself to be humble, and will figure out how to avoid the bug quickly.
public class Solution {
public bool CanPartition(int[] nums) {
if(nums == null || nums.Length == 0)
return false;
var length = nums.Length;
var sum = nums.Sum();
if(sum % 2 == 1)
return false;
var target = sum / 2;
var dp = new bool[sum + 1]; // target + 1 optimal
Array.Sort(nums);
var prefixSum = 0;
for(int i = 0; i < nums.Length; i++)
{
var current = nums[i];
for (int j = 1; j <= prefixSum; j++)
{
if (dp[j])
{
dp[j + current] = true;
}
}
dp[current] = true;
prefixSum += current;
if (dp[target])
return true;
}
return dp[target];
}
}
