Water Cooler v2 Water Cooler v2 - 1 month ago 8
C# Question

Which corner case unit test would this fail?

I tried the Fish problem on Codility and I secured 75% marks for correctness because the results reported that my code failed one simple test case. The results do not report what input was provided for the test case.

Could you please help me find out what is wrong with my code and what corner case it would fail?

using System;

public class Solution
{
// Time complexity: O(N X M)
// Space complexity: O(N)
public int solution(int[] sizes, int[] direction)
{
if (sizes == null || direction == null)
throw new ArgumentNullException();

var sizesLen = sizes.Length;
var directionLen = direction.Length;

if (sizesLen != direction.Length)
throw new ArgumentException();

var len = sizesLen;

if (len <= 1) return len;

var survivors = new Fish[len];
survivors[0] = new Fish(sizes[0], direction[0]);
var curr = 0;

for (int i = 1; i < len; i++)
{
var fish = new Fish(sizes[i], direction[i]);

if (survivors[curr].Direction == 1 && fish.Direction == 0)
{
if (fish.Size < survivors[curr].Size) continue;

while(curr >= 0 &&
fish.Size > survivors[curr].Size &&
survivors[curr].Direction == 1)
{
curr--;
}
}

survivors[++curr] = fish;
}

return ++curr;
}
}

public class Fish
{
public Fish(int size, int direction)
{
Size = size;
Direction = direction;
}

public int Size { get; set; }
public int Direction { get; set; }
}

Answer

As mentioned in your code, your Solution is O(M*N). As stated in the problem link, the code should run in linear time. Hence, I will not correct your solution as it will eventually fail on bigger test cases. I will provide you a linear algorithm that you can easily implement.

Keep a Stack S, empty initially.

Iterate over the array A, i from 0 to n-1

When you encounter an element, say A[i], do the following

  • If the stack S is empty, then push both (A[i], B[i]) as a pair
  • Else, extract the top pair from the stack S and compare the value of B[top] and B[i].

    While B[top] is 1 and B[i] is 0, then one of the fishes will eat the other one. So pop from stack S, the top element. Now, compare which fish is bigger with values A[top] and A[i]. Whichever is bigger, that fish stays alive. Push that pair in the stack S, that corresponds to the fish that stays alive. Continue the while loop till the condition fails If B[top] is not 1 and B[i] is not 0, then simply push the new pair (A[i],B[i])

The size of the stack S at the end, is your answer.

Note: You might not be passing that test case, for which your solution times out. For example, for N=100000, your solution will time out.

In my solution, the worst case time complexity is O(N+N) = O(2N) = O(N). N times because of the iteration over array A and another N times worst case, due to the Stack if it keeps shrinking, for the while condition holds true.

Hope it helps!!!

Edit: suppose A = [ 99, 98, 92, 91, 93 ], and B = [1, 1, 1, 1, 0]. Your code gives answer as 3. Expected answer = 2

Edit-2: This is your modified code that will pass every test case

public int solution(int[] sizes, int[] direction)
    {
        if (sizes == null || direction == null)
            throw new ArgumentNullException();

        var sizesLen = sizes.Length;
        var directionLen = direction.Length;

        if (sizesLen != direction.Length)
            throw new ArgumentException();

        var len = sizesLen;

        if (len <= 1) return len;

        var survivors = new Fish[len];
        survivors[0] = new Fish(sizes[0], direction[0]);
        var curr = 0;

        for (int i = 1; i < len; i++)
        {
            var fish = new Fish(sizes[i], direction[i]);

            if (survivors[curr].Direction == 1 && fish.Direction == 0)
            {
                if (fish.Size < survivors[curr].Size) continue;

                while(curr >= 0 && 
                    fish.Size > survivors[curr].Size && 
                    survivors[curr].Direction == 1)
                {
                    curr--;
                }

                if (curr >= 0)
                {
                    if (fish.Size < survivors[curr].Size && 
                         survivors[curr].Direction == 1) 
                               continue;
                }
            }

            survivors[++curr] = fish;
        }

        return ++curr;
    }

}

public class Fish
{
    public Fish(int size, int direction)
    {
        Size = size;
        Direction = direction;
    }

    public int Size { get; set; }
    public int Direction { get; set; }
}