Uber Interview Question for Software Engineers

• 0

Team: ATG
Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Thanks I am gonna try to understand this one :)

Comment hidden because of low score. Click to expand.
0

Your code returns 3 with this grid:
00000
11110
01111
00000
00000
Which is not true because the largest black square for above grid would be 2x2.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.