Uber Interview Question
Software EngineersTeam: ATG
Country: United States
Interview Type: Phone Interview
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;
}
}
}
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.
1. initialize dp[m][n]
- Popeye April 30, 20192. 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.