Facebook Interview Question Software Developers
Country: United States
Interview Type: In-Person
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[0].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[0].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;
}
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
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).
//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[0].length][1];
//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[0].length;col++)
{
cache[row][col][0]=-1;
}
}
return getMax(m,0,0,cache);
}
private int getMax(int[][]m, int row, int col, int[][][] cache)
{
if(row==m.length && col==m[0].length)
{
return m[0][0];
}
if(cache[row][col][0]!=-1)
{
return cache[row][col][0];
}
int maxCoin=0;
for(int dx=1;row+dx<m.length;dx++)
{
for(int dy=1;col+dy<m[0].length;dy++)
{
maxCoin=Math.max(maxCoin,getMax(m,row+dx,col+dy,cache)));
}
}
maxCoin+=m[row][col];
cache[row][col][0]=maxCoin;
return maxCoin;
}
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).
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[4] = 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[1]].append(t[0])
for t in d.items():
t[1].sort()
l = [t[1] 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[0] = l[i][0]
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...
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
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
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
private static int mCoins(int[][] m, int i, int j) {
if (i >= m.length || j >= m[0].length) {
return 0;
}
int max = 0;
if (i + 1 < m.length) {
for (int k = j+1; k < m[0].length; k++) {
int next = mCoins(m, i + 1, k);
if (next > max) {
max = next;
}
}
}
if (j+1 < m[0].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;
}
}
//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)
{
pathContinued.add(p);
}
pathContinued.add(nextStep);
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))
{
result.add(point);
}
}
return result;
}
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
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.
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)
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)
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;
}
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[0].length == 0) return 0;
int[] lastCol = new int[grid.length];
for (int j=0; j < grid[0].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];
}
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;
}
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[0] == 1)
return max_coin + 1;
return max_coin;
}
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);
}
}
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.
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.
- jani April 05, 2016