## Facebook Interview Question for Software Developers

• 0

Country: United States
Interview Type: In-Person

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

I can't believe i didn't realize it when posting my solution or reading the other comments, but this problem (and my previous solution) is essentially the LIS problem. Basically you can just sort all the locations of the coins primarily according to y-axis in ascending order and secondarily according to x-axis in descending order, and run the nlogn LIS algorithm. The secondary sorting by x-axis into a descending order guarantees that the ties you mentioned will be taken into account properly.

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

Solved this using DP.

``````private static int maxCoins(boolean[][] board) {
return maxCoinsHelper(board, 0, 0, new HashMap<>());
}

private static int maxCoinsHelper(boolean[][] board, int row, int col, HashMap<Point, Integer> cache) {
if (row == board.length || col == board.length)
return 0;
Point p = new Point(row, col);
if (cache.containsKey(p))
return cache.get(p);
int coinsCount = 0;
for (int dx = 1; dx + row < board.length; dx++) {
for (int dy = 1; dy + col < board.length; dy++) {
coinsCount = Math.max(coinsCount, maxCoinsHelper(board, row + dx, col + dy, cache));
}
}
coinsCount += board[row][col] ? 1 : 0;
cache.put(p, coinsCount);
return coinsCount;
}``````

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

LIS.(Longest increasing subsequence , in this case strictly increasing).

Sort/order points in x dimension. Find LIS wrt to "y" dimension.

Similarly sort/order points in Y dimension. Find LIS wrt to x "dimension"

Pick max LIS out of the two.

Time complexity ~ O(nlgn) ... That is nlgn for sorting. nlgn for LIS

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

Is there constraints about dx, dy? How many steps could you do?
If you start from 0,0, where will be next step , on (dx, dy) ?

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

Assuming next step from (x,y) are (x+dx,y+dy)

Do a bfs with (0,0) as the starting point. When you reach a cell which contains coin pick it. If u reach a cell which was already visited by BFS ,then stop it.

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

Use dynamic programming and track min in another 2d array. Min[i,j] = Math.Min(Min[i][j], Math.min(Min[i-dx][j]+1, Min[i]Min[j-dy])) where coin is present at Min[i][[j] and all steps are within first quadrant. Return Min[xlen-1][ylen-1]. Time:O(n^2), Space:O(X+Y)

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

Normalize the x and y coordinates to be integers in the range 0..N-1. This is done by sorting the x-coordinates and then replacing the x-coordinates by their position in the sorted array. Do the same for the y-coordinates.
Now create a NxN matrix where each cell has the count of coins with the corresponding x&y coordinates.
Now we use dynamic programming, starting with the top left (0,0) cell, and calling recursively on its right and down neighbors to find the max value.
Complexity is O(N^2), space used is also O(N^2).

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

@emb,to the clarification : are dx,dy,n given as an input ?

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

@krbchd, coudn't you modify algorithm for LIS to take into account ties , as @emb suggest

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

@krbchd couldn't LIS algorithm be modified to take into account ties which @emb show

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

``````//Assumptions: Input is a 2D Matrix of integers where 1 represents a coin being present and 0 represents no coin
//Approach: Dynamic programming with recursion and caching.
//Time Complexity:O(NM)
//Space complexity:O(NM);

public int maxCoins(int[][] m)
{
int[][][] cache=new int[m.length][m.length];
//Initialize cache to contain -1 to indicate that a cell has not been visited yet.
for(int row=0;row<m.length;row++)
{
for(int col=0;col<m.length;col++)
{
cache[row][col]=-1;
}
}

return getMax(m,0,0,cache);
}

private int getMax(int[][]m, int row, int col, int[][][] cache)
{
if(row==m.length && col==m.length)
{
return m;
}
if(cache[row][col]!=-1)
{
return cache[row][col];
}
int maxCoin=0;
for(int dx=1;row+dx<m.length;dx++)
{
for(int dy=1;col+dy<m.length;dy++)
{
maxCoin=Math.max(maxCoin,getMax(m,row+dx,col+dy,cache)));
}
}
maxCoin+=m[row][col];
cache[row][col]=maxCoin;
return maxCoin;
}``````

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

Create a graph of the traversible paths and then do a DFS Traversal to find the longest path.

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

I think the solution is fairly simple. Essentially you are allowed to move only in one line starting from coordinate (0,0). Slope of this line is dy/dx. Now, any point with coordinate x,y becomes a part of the solution set if it satisfies the following equation.
(y/x == dy/dx) && ((x%dx) == 0).

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

I think the answer is fairly simple. Essentially you are allowed to move on the line passing through the center and slope dy/dx. Hence any point/coordinate(x,y) which satisfies the following equation is a part of the solution set.

"(y/x == dy/dx) && ((x%dx) == 0)"

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

Ok I think this works in nlogn time. Took me a while to get this without segment trees, I didn't want to use them since it's supposed to be an interview question.

The idea is to start iterating each "layer" of coins, starting from the lowest, and update an array "ans" which keeps track of the smallest value of x-coordinate where we've seen a sequence of n coins end. That is, if we have ans = 3, it means that we've seen a chain of coins of length 3 which ends with a coin at x-coordinate 4. The idea is somewhat similar to the nlogn LIS algorithm.

``````from collections import defaultdict

# binary search, gets the largest index from list "l" where the value isn't larger than "num"
def get(l, num):
acc = len(l)
ans = -1
while acc > 0:
while ans+acc < len(l) and l[ans+acc] < num:
ans += acc
acc /= 2
return ans

def solve(coins):
d = defaultdict(lambda: [])
for t in coins:
d[t].append(t)
for t in d.items():
t.sort()
l = [t for t in sorted(d.items())]
ans = [10**9]*len(coins) # ans[n] is the smallest x-coordinate where we have seen a sequence of n coins end
actualAns = 0
for i in xrange(len(l)):
upd = {}
if i == 0:
ans = l[i]
continue
for n in l[i]:
idx = get(ans, n)
upd[idx+1] = min(ans[idx+1], n)
for k,v in upd.items():
ans[k] = v
actualAns = max(actualAns, k)
upd.clear()
return actualAns + 1

l = [(0,0),(0,1),(2,3), (1,7)]
print solve(l)``````

Originally i wanted to use c++ but... so much extra code...

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

Isn't it just o( number of points ) a small modification to what @pravash pointed out. You start at input (a,b) now for all points calculate the slope with (a,b) and keep count of number of points that share the same slope with (a,b) [ meaning they are all in the same line starting from (a,b) ]. The slope that has the maximum points is the dx and dy value we want to take and the number of points in that slope is the number of coins we can collect.
psuedocode:

``````def maxCoins( Points, a, b ):
max = 0
hash = dict()
for Px, Py in Points:
slope = abs( Py - b ) // abs( Px - a )
if slope in hash:
hash[ slope ] += 1
else:
hash[ slope ] = 1
if hash[ slope ] > max:
max = hash[ slope ]
return max``````

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

Isn't it just o( number of points ) a small modification to what @pravash pointed out. You start at input (a,b) now for all points calculate the slope with (a,b) and keep count of number of points that share the same slope with (a,b) [ meaning they are all in the same line starting from (a,b) ]. The slope that has the maximum points is the dx and dy value we want to take and the number of points in that slope is the number of coins we can collect.
psuedocode:

``````def maxCoins( Points, a, b ):
max = 0
hash = dict()
for Px, Py in Points:
slope = abs( Py - b ) // abs( Px - a )
if slope in hash:
hash[ slope ] += 1
else:
hash[ slope ] = 1
if hash[ slope ] > max:
max = hash[ slope ]
return max``````

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

Isn't it just O(number of points). Just calculate all the slope with (a,b) and the points and see which slope is shared by maximum number of points and choose that slope.

``````def maxCoinsPossible( Points, a, b ):
hash = dict()
maxCoins = 0
for px, py in Points:
slope = abs( py - b ) // abs( px - a )
if slope in hash:
hash[ slope ] += 1
else:
hash[ slope ] = 1
maxCoins = max( maxCoins, hash[ slope ] )
return maxCoins``````

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

If you are only allowed to move dx units on the x axis, and dy units on the Y axis, it's fair to say that you can only visit the points whose x coordinate is a multiple of dx, and y coordinate is a multiple of dy. Just find such points in the array, and print them out.

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

``````private static int mCoins(int[][] m, int i, int j) {
if (i >= m.length || j >= m.length) {
return 0;
}
int max = 0;
if (i + 1 < m.length) {
for (int k = j+1; k < m.length; k++) {
int next = mCoins(m, i + 1, k);
if (next > max) {
max = next;
}
}
}
if (j+1 < m.length) {
for (int k = i + 2; k < m.length; k++) {
int next = mCoins(m, k, j+1);
if (next > max) {
max = next;
}
}
}
return  m[i][j] == 0 ?
max : max + 1;
}
}``````

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

``````//starting at (0,0), and can only move in positive (dx,dy) movements, get the path that gets most coins
public List<Point> GetPathWithMostCoins(Set<Point> coinsList)
{
List<Point> emptyPath = new ArrayList<>();
return GetPathWithMostCoinsRec(emptyPath, new ArrayList<Point>(coinsList), new Point(0,0), emptyPath);
}

public List<Point> GetPathWithMostCoinsRec(List<Point> currentPath, List<Point> currPossibilities, Point currPoint, List<Point> currLongest)
{
if (currPossibilities.isEmpty())
{
if (currLongest.size() < currentPath.size())
{
currLongest = currentPath;
}

return currLongest;
}

for (Point nextStep : currPossibilities)
{
List<Point> pathContinued = new ArrayList<>();

for (Point p : currentPath)
{
}

List<Point> longestPathMaybe = GetPathWithMostCoinsRec(pathContinued, getNextXPossibiliteisList(nextStep, currPossibilities), nextStep, currLongest);

if (currLongest.size() < longestPathMaybe.size())
{
currLongest = longestPathMaybe;
}
}

return  currLongest;
}

private List<Point> getNextXPossibiliteisList(Point minPoint, List<Point> currList)
{
List<Point> result = new ArrayList<Point>();

for (Point point : currList)
{
if (point.getX() >= minPoint.getX() && point.getY() >= minPoint.getY() && !point.equals(minPoint))
{
}
}

return  result;
}``````

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

example:
{{3,5}, {0,1}, {2,3}, {6,4}, {7,8}, {2,4}, {3,7}, {2,9}, {13,10}, {11,12}, {5,8}, {4,5}}

1. Sort the given coordinate list by x-coordinate in decreasing order
{13,10},{11,12},{7,8},{6,4},{5,8},{4,5},{3,5},{3,7},{2,9},{2,3},{2,4},{0,1}

2. Starting from the first element, compare all the points it can reach traveling to the right and traveling upwards, and create a map
{13,10} -> {}
{11,12} -> {}
{7,8}->{13,10},{11,12}
{6,4}->{13,10},{11,12},{7,8}
...
...
...
{2,9}->{13,10},{11,12}
{0,1}->{13,10},{11,12},{7,8},{6,4}...{2,3},{2,4},{2,9}

3. Now for each point from the sorted coordinates
consolidate the map into {max number of points that can be reached from that point + 1}
so the map becomes
{13,10} -> {}->{0+1}
{11,12} -> {}->{0+1}
{7,8}->{13,10},{11,12}-> max({13,10},{11,12}) + 1 -> max(1,1) + 1 -> 2
{6,4}->{13,10},{11,12},{7,8}->max({13,10},{11,12},{7,8}) + 1 -> max(1,1,2) + 1 -> 3
...
...
...
{2,9}->{13,10},{11,12} -> 3
{0,1}->{13,10},{11,12},{7,8},{6,4}...{2,3},{2,4},{2,9} -> 7

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

``````Assume co-ordinates are as follows:
(1,1), (2,2), (3,2), (4,3), (5,2),(6,3),(7,4)

Now, you can see that the input is assumed to be sorted on x co-ordinates.
If it is not first sort the input in increasing x co-ordinates.

Now the problem gets reduced to finding LIS for y co-ordinates:
1,2,2,3,2,3,4

Result can be : 1,2,3,4 i.e. (1,1) (2,2) (4,3) (7,4)
So largest coins collected can be 4.``````

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

``````Assume co-ordinates are as follows:
(1,1), (2,2), (3,2), (4,3), (5,2),(6,3),(7,4)

Now, you can see that the input is assumed to be sorted on x co-ordinates.
If it is not first sort the input in increasing x co-ordinates.

Now the problem gets reduced to finding LIS for y co-ordinates:
1,2,2,3,2,3,4

Result can be : 1,2,3,4 i.e. (1,1) (2,2) (4,3) (7,4)``````

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

Assume co-ordinates are as follows:
(1,1), (2,2), (3,2), (4,3), (5,2),(6,3),(7,4)

Now, you can see that the input is assumed to be sorted on x co-ordinates.
If it is not first sort the input in increasing x co-ordinates.

Now the problem gets reduced to finding LIS for y co-ordinates:
1,2,2,3,2,3,4

Result can be : 1,2,3,4 i.e. (1,1) (2,2) (4,3) (7,4)

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

input value Board where TRUE means there is a coin.
Like dx > 0 and dy > 0 the least we can move is dx = 1 and dy = 1 so the minimum position we came from is [i-1, j-1]
We skyp the coins from first row and firs col because is not posible to get them.
O(MxN)

``````public int GetMaxCoins(bool[,] board)
{
int[,] dp = new int[board.GetLength(0), board.GetLength(1)];
dp[0, 0] = board[0,0] ? 1 : 0;
int max = dp[0, 0];

for (int i=1; i < board.GetLength(0); i++)
{
for (int j= 1; j < board.GetLength(1); j++)
{
int n = board[i, j] ? 1 : 0;
dp[i, j] = n + dp[i - 1, j - 1];
max = Math.Max(max, dp[i, j]);
}
}

return max;
}``````

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

The question is a DP problem. Take a 2D array of size row X column. For any row r, column c, the value is the maximum possible points starting from that point.
So,
For all points with x >= c or y >= r
DP[r][c] = Math.max(DP[x][y])+1

The solution is DP.

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

This is standard dynamic programing problem. You can reach any cell (x,y) from either (x-1, y) or (x, y-1).

f(x, y) = val[x,y] + Max(f(x-1, y), f(x, y-1))
If you code it recursively you can solve it in O(nm) time and O(nm) space as mentioned by divm01986. If you solve it iteratively you can do it in O(n) space. If you solve column by column, you can store last computed column. So for any (x,y) you just need to keep track of last val (x-1, y).

``````int max(int[][] grid) {
if (grid == null || grid.length == 0 || grid.length == 0) return 0;
int[] lastCol = new int[grid.length];
for (int j=0; j < grid.length; j++) {
int lastVal = 0;
for (int i=0; i < grid.length; i++) {
lastVal = Math.max(lastCol[i], lastVal) + grid[i][j];
lastCol[i] = lastVal;
}
}
return lastCol[grid.length - 1];
}``````

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

Solution in Objective-C

``````#import <Foundation/Foundation.h>

NSInteger maxFromPosition(NSArray *grid, NSInteger xPos, NSInteger yPos, NSMutableDictionary *cache){

NSString *key = [NSString stringWithFormat:@"%ld-%ld",xPos, yPos];

if([cache objectForKey:key]){
return [[cache objectForKey:key] integerValue];
}

NSInteger maxCoins = 0;

if(xPos > grid.count - 1 || yPos > [grid[xPos] count] - 1){
return 0;
}

for(int i = xPos; i < [grid count]; i++){
for(int e = yPos; e < [grid[i] count]; e++){
NSInteger total = maxFromPosition(grid, i+1, e+1, cache);
maxCoins = MAX(total, maxCoins);
}
}

if([grid[xPos][yPos] isEqualToString:@"C"]){
maxCoins++;
}

[cache setObject:@(maxCoins) forKey:key];

return maxCoins;

}

NSInteger findMaxCoins(NSArray *grid){
return maxFromPosition(grid, 0, 0, [NSMutableDictionary new]);
}

int main(int argc, const char * argv[]){

@autoreleasepool{

NSArray *grid = @[
@[@"N",@"N",@"N",@"N"],
@[@"N",@"C",@"N",@"N"],
@[@"C",@"N",@"C",@"N"],
@[@"N",@"N",@"C",@"N"]
];

NSInteger max = findMaxCoins(grid);
NSLog(@"Max coins: %ld", max);

}

return 0;

}``````

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

``````int do_count_coin(int *a, int sx, int sy, int x, int y)
{
int max_coin;
int base_x = x, base_y = y;
int ret = 0;

if (x == sx || y == sy)
return 0;

max_coin = do_count_coin(a, sx, sy, x + 1, y + 1);

for (; x < sx; x++) {
if (a[base_y * sy + x] == 1) {
ret = do_count_coin(a, sx, sy, x + 1, base_y + 1);
if (max_coin < ret + 1)
max_coin = ret + 1;
}
}

for (; y < sy; y++) {
if (a[y * sy + base_x] == 1) {
ret = do_count_coin(a, sx, sy, base_x + 1, y + 1);
if (max_coin < ret + 1)
max_coin = ret + 1;
}
}

return max_coin;
}

int get_max_coin(int *a, int sx, int sy)
{
int max_coin = do_count_coin(a, sx, sy, 1, 1);

if (a == 1)
return max_coin + 1;

return max_coin;
}``````

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

A dynamic solution is implemented.
Given position C1, C2, ..., Cn, which has a coin on it at position (Xi, Yi).
- f(C1, ..., Cn) = max(1 + f(C1, ..., Ci-1, Ci+1, Cn) ), where i with range of [1, n]

Details: cpluspluslearning-petert.blogspot.co.uk/2016/07/dynamic-programming-pick-maximal-coins.html

Test

``````void TestPickMaximalCoins()
{
{
const std::vector<Position> coins;
assert(PickMaximalCoins_R(coins) == 0);
}
{
const std::vector<Position> coins = { { 5, 5 }, { 1.5, 3.5 }, { 2, 2 }, { 2.0, 4.0 },
{ 4, 4 }, { 5.0, 2.0 }, { 3, 3 }, { 4.0, 1.0 }, { 1, 1 }};
assert(PickMaximalCoins_R(coins) == 5);
}
{
const std::vector<Position> coins = {
{ 6.1, 2.1 }, { 2.2, 6.2 }, { 5.2, 5.2 }, { 6.2, 2.2 },
{ 2.3, 6.3 }, { 5.3, 5.3 }, { 6.3, 2.3 }, { 5.4, 5.4 },
{ 1.0, 1.0 }, { 2.0, 6.0 }, { 5.0, 5.0 }, { 6.0, 2.0 },
{ 2.1, 6.1 }, { 5.1, 5.1 } };
assert(PickMaximalCoins_R(coins) == 6);
}
{
const std::vector<Position> coins = {
{ 6.1, 2.1 }, { 2.2, 6.2 }, { 5.2, 5.2 }, { 6.2, 2.2 },
{ 2.3, 6.3 }, { 5.3, 5.3 }, { 6.3, 2.3 }, { 4.0, 5.3 },
{ 5.4, 5.4 }, { 1.0, 1.0 }, { 2.0, 6.0 }, { 5.0, 5.0 },
{ 6.0, 2.0 }, { 2.1, 6.1 }, { 5.1, 5.1 }, { 5.3, 4.0 } };
assert(PickMaximalCoins_R(coins) == 6);
}
}``````

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

This is a DP problem with the following expression:

``dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + coins[i][j]]))``

so basically you at each cell you are calculating the maximum # of coins you can get so far

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

I don't understand the question. Is there a x by y matrix? What does the N coins mean? Are N coins randomly spreaded on the matrix? I don't know how to get the max coins without the locations of coins.
For example, 2 coins (1,0) (0,1) this case maximum coin to get is one. But 2 coins (1,0)(1,1) the answer is 2.

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.