CareerCup

1. initialize dp[m][n]
2. for i,j -> if(matrix[i][j] == 1) then dp[i][j] += Math.min(dp[i][j-1], Math.min(dp[i-1][j-1], dp[i-1][j]));
3. result = Math.max(result, dp[i][j])

Can also be achieved by initializing just dp[n] and two temp variables.

can be done in O(N). Single loop through AND previous result to current keeping track of max bit and consecutive changes ... something similar to this I suppose

using System;

namespace GridMaker
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var arr = new int[] { 0, 30, 15, 14, 0 };
            var bitGrid = new BitGrid();

            var result = bitGrid.GetGridSize(arr);
            Console.WriteLine("Grid size is {0}", result);
            Console.ReadLine();
        }
    }

    class BitGrid
    {
        int GetBitCount(int i)
        {
            i = i - ((i >> 1) & 0x55555555);
            i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
            return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
        }


        public int GetGridSize(int[] arr)
        {
            int maxCount = 0;
            for(var i=0; i < arr.Length - 1; i++)
            {
                int value = arr[i] & arr[i + 1];
                int bits = GetBitCount(value);
                if (bits > maxCount)
                {
                    maxCount = bits;
                }
            }
            return maxCount;
        }
    }
}

Can be done in O(N). Single loop through n items, AND previous, current and take maximum bit count on each iteration.

Just an update: after exploring on how to solve this problem, interviewer gave me hint for brute force and then because of time limit I was asked to code. And even though i thought my interview didn't go well, I just got email saying they just moved me forward for onsite interview. Just sharing my experience if it helps other people. its not necessary for people to come up with optimal solution everytime as long as you discuss your thought process and work as a team.