## Uber Interview Question for Software Engineers

• 0
of 0 votes

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
of 0 votes

Yes that was the answer.

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

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

Thanks I am gonna try to understand this one :)

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

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.

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More