Facebook Interview Question Software Engineers
Country: United States
Interview Type: In-Person
/*
1) Burute force, go to every square and check how much left, right, up and down one can go, at most which gives O(n*m*n + n*m*m) runtime
which is O(n³) if n = m
2) Hint to use DFS/BFS hints that O(n*m) is best conceivable worst case runtime unless some heuristic is used to accellerate the search,
which wouldn't increase worst case runtime. Such a heursitic could draw the search towards the center of the matrix where the largest
crosses are expected but I don't really think this is wanted or advantegous here.
3) While there is certainly an approach with BFS and DFS, anyway we need to store the length into each direction, without storing that
information how far to the left, right, top, down one can go from one point, there is not much of subproblem reuse possible.
At this point I suggest an easier to implement approach than BFS/DFS using some sort of dynamic programming:
let's say, left(x, y) is an integer denoting how much we can go left from a certain point, then left(x + 1, y) = left(x, y) + 1
if matrix(x + 1, y) is 1 or 0 if matrix(x + 1, y) is 0.
we can create a left, right, top and down matrix. Creating each of those will cost at max O(n^2)
Maximizing over all n² the min(right(x, y), top(x, y), ...) will lead to the desired result in O(n^2)
So, runtime is O(5*n²) which is O(n²) as is the upper bound on space
This will lead to the best conceivable runtime.
Note: One can save one of the 4 matrices, at the last step, but for simplicity and readability I didn't implement it that way, besides
it wouldn't make the O(n*m)
*/
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
pair<int, pair<int, int>> findBiggestPlus(const vector<vector<bool>>& field)
{
pair<int, pair<int, int>> result(-1, pair<int, int>(-1, -1));
int m = field.size();
if(m == 0) return result;
int n = field[0].size();
if(n == 0) return result;
vector<vector<int>> left(m, vector<int>(n));
vector<vector<int>> right(m, vector<int>(n));
vector<vector<int>> up(m, vector<int>(n));
vector<vector<int>> down(m, vector<int>(n));
for(int y = 0; y < m; y++)
{
left[y][0] = field[y][0] ? 1 : 0;
for(int x = 1; x < n; x++) left[y][x] = field[y][x] ? left[y][x - 1] + 1 : 0;
right[y][n - 1] = field[y][n - 1] ? 1 : 0;
for(int x = n - 2; x >= 0; x--) right[y][x] = field[y][x] ? right[y][x + 1] + 1 : 0;
}
for(int x = 0; x < n; x++)
{
up[0][x] = field[0][x] ? 1 : 0;
for(int y = 1; y < m; y++) up[y][x] = field[y][x] ? up[y - 1][x] + 1 : 0;
down[m - 1][x] = field[m - 1][x] ? 1 : 0;
for(int y = m - 2; y >= 0; y--) down[y][x] = field[y][x] ? down[y + 1][x] + 1 : 0;
}
for(int x = 0; x < n; x++)
{
for(int y = 0; y < m; y++)
{
int s = min(left[y][x], min(right[y][x], min(up[y][x], down[y][x])));
if(s > result.first) result = pair<int, pair<int,int>>(s, pair<int, int>(x, y));
}
}
return result;
}
int main()
{
vector<vector<bool>> m {
{0, 0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1},
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}
};
auto result = findBiggestPlus(m);
cout << "side length: " << result.first << " x:" << result.second.first << " y:" << result.second.second << endl;
}
private class Counts{
int above;
int down;
int left;
int right;
private Counts(){
above = 0;
down = 0;
left = 0;
right = 0;
}
}
// Time Complexity: O(N*M) where N is the number of rows, M is the number of columns. Space: O(N * M).
public int maxPlus(int[][] mat){
if(mat == null || mat.length == 0 || mat[0].length == 0){
throw new IllegalArgumentException();
}
Counts[][] countData = new Counts[mat.length][mat[0].length];
for(int r = 0; r < countData.length; r++){
for( int c = 0; c< countData[0].length; c++){
countData[r][c] = new CountData();
}
}
//across first and last row
for(int c = 1; c < mat[0].length; c++){
countData[0][c] = countData[0][c - 1] == 1? countData[0][c - 1].left + 1: 0;
countData[mat.length][mat[0].length - c - 1] = countData[mat.length][mat[0].length - c] == 1? countData[mat.length][mat[0].length - c].right + 1: 0;
}
//across first and last columns
for(int r = 1; r < mat.length; r++){
countData[r][0] = countData[r - 1][0]==1?countData[r - 1][0].above + 1: 0;
countData[mat.length - r - 1][mat[0].length - 1] = countData[mat.length - r][mat[0].length - 1] == 1? countData[mat.length - r][mat[0].length - 1] + 1: 0;
}
// start from (1,1)
for(int r = 1; r < mat.length; r++){
for(int c = 1; c< mat[0].length; c++){
if(mat[r - 1][c] == 1){
countData[r][c].above = countData[r - 1][c].above + 1;
}
if(mat[r][c - 1] == 1){
countData[r][c - 1].left = countData[r][c - 1].left + 1;
}
}
}
for(int r = mat.length - 2; r >= 0; r--){
for(int c = mat[0].length - 2; c >= 0; c--){
if(mat[r + 1][c] == 1){
countData[r][c].down = countData[r + 1][c].down + 1;
}
if(mat[r][c + 1] == 1){
countData[r][c].right = countData[r][c + 1].right + 1;
}
}
}
int maxLen = 0;
for(int r = 0; r < mat.length; r++){
for(int c = 0; c < mat[0].length; c++){
if(mat[r][c] == 1){
int minPlus = Math.min(countData[r][c].above,countData[r][c].down);
minPlus = Math.min(countData[r][c].left, countData[r][c].right);
maxLen = math.max(maxLen,minPlus);
}
}
}
return maxLen;
}
Sparse matrices should almost never be represented with matrices because the space requirement is quadratic with dimension. In this case we only need to track the non-zero values on the board, which takes us down to O(n) space where 'n' is the number of non-zero values in the sparse matrix.
From the set of non-zero values we can construct an undirected graph with an underlying adjacency list implementation. To do so we sort values by location, and look for two values on the same axis that are one unit away from each other.
Once the graph is constructed, which takes O(nlogn) time because of sorting, the 'big plus' calculation is then DFS per each non-zero value. So space is O(n) for DFS using a queue. Amortized time - remember the matrix is sparse - comes out to O(n). In both cases 'n' is the number is entries. We completely ignore the dimensions of the board.
/*
* 'Largest Plus'
*
* Implement points as an undirected graph with underlying adjacency list implementation.
*
* O(n) running time for sparse arrays and O(n) space where n is the number
* of '1's regardless of the number of '0' or board dimensionality.
*
* Spare matrix implies adjacency list as opposed to a direct matrix
* representation; latter is not scalable as space grows quadratically
* with dimension.
*/
import java.util.Arrays;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Comparator;
public class Point {
public int x, y;
public int i; // Graph vertices index
public Point(int x, int y)
{
this.x = x; // Board X coordinate
this.y = y; // Board Y coordinate
}
public String toString()
{
return "(" + x + ", " + y + ")";
}
}
public class LargestPlus {
private ArrayList<Integer>[] adj; // Graph adjacency list
private Point[] points; // Points representing '1's
private int V; // Number of '1's
// Compare points by X coordinate first
private class PointCompareX implements Comparator<Point>
{
public int compare(Point a, Point b)
{
if (a.x < b.x)
return -1;
else if ((a.x == b.x) && (a.y == b.y))
return 0;
else if ((a.x == b.x) && (a.y < b.y))
return -1;
else
return 1;
}
}
// Compare points by Y coordinate first
private class PointCompareY implements Comparator<Point>
{
public int compare(Point a, Point b)
{
if (a.y < b.y)
return -1;
else if ((a.y == b.y) && (a.x == b.x))
return 0;
else if ((a.y == b.y) && (a.x < b.x))
return -1;
else
return 1;
}
}
// Conditionally connect two graph nodes if they are adjacent
private void condConnect(Point a, Point b)
{
if ((a.y == b.y && Math.abs(a.x - b.x) == 1) ||
(a.x == b.x && Math.abs(a.y - b.y) == 1)) {
adj[a.i].add(b.i);
adj[b.i].add(a.i);
}
}
// Build adjacency representation of undirected graph
private void createGraph()
{
// Vertical connections
Arrays.sort(points, new PointCompareX());
points[0].i = 0;
for (int i = 0; i < V-1; i++) {
// Assume X ordering is used for vertices-to-point mapping
points[i+1].i = i+1;
condConnect(points[i], points[i+1]);
}
// Horizontal connections - maintain the previous ordering
Point[] yPoints = new Point[V];
for (int i = 0; i < V; i++)
yPoints[i] = points[i];
Arrays.sort(yPoints, new PointCompareY());
for (int i = 0; i < V-1; i++)
condConnect(yPoints[i], yPoints[i+1]);
}
// Check that two points are on the same X or Y axis
private boolean checkLine(int i, int j)
{
if (points[i].x == points[j].x || points[i].y == points[j].y)
return true;
else
return false;
}
// Breadth First Search
private int bfs(int s)
{
if (adj[s].size() != 4)
return -1;
LinkedList<Integer> q = new LinkedList<Integer>();
boolean[] marked = new boolean[V];
q.add(s);
marked[s] = true;
int count = 0;
boolean expand = true;
// Each node can only have one viable expansion edge
while (!q.isEmpty() && expand) {
expand = false;
int v = q.remove();
for (int w : adj[v]) {
// Don't backtrack and check plus alignment
if (!marked[w] && checkLine(v, s)) {
marked[w] = true;
q.add(w);
expand = true;
count++;
}
}
}
// We increase count in each direction so divide by 4 for the size
return count / 4;
}
// Return 'plus size' for a given vertices index
public int plusSize(int s)
{
return bfs(s);
}
// Return a point for given vertices index. Needed because we sort the points.
public Point point(int s)
{
return points[s];
}
public LargestPlus(Point[] points)
{
if (points == null)
throw new NullPointerException();
this.points = points;
this.V = points.length;
adj = (ArrayList<Integer>[]) new ArrayList[V];
for (int i = 0; i < V; i++)
adj[i] = new ArrayList();
createGraph();
}
public static void main(String[] args){
Point[] points = {
new Point(0, 1),
new Point(0, 2),
new Point(1, 2),
new Point(2, 0),
new Point(2, 1),
new Point(2, 3),
new Point(2, 4),
new Point(3, 2),
new Point(4, 1),
new Point(4, 2),
new Point(5, 2),
new Point(6, 1),
new Point(6, 2),
new Point(5, 0),
new Point(2, 2),
new Point(1000000, 1000000),
};
LargestPlus lp = new LargestPlus(points);
int max = 0;
Point maxPoint = null;
for (int v = 0; v < points.length; v++) {
int size = lp.plusSize(v);
if (size > max) {
max = size;
maxPoint = lp.point(v);
}
}
System.out.println("Size " + max + ", Position " + maxPoint);
}
}
private static void findPlusInMatrix() {
int[][] mat = {
{ 0, 0, 1, 0, 0, 1, 0 },
{ 1, 0, 1, 0, 1, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 } };
int maxEdge = -1;
int[] maxCenter = { -1, -1 };
for (int y = 1; y < mat[0].length - 1; y++) {
for (int x = 1; x < mat.length - 1; x++) {
if (mat[x][y] == 1) {
int left = x - 1;
int up = y - 1;
int down = y + 1;
int right = x + 1;
int length = 0;
while (mat[left][y] == 1 && mat[right][y] == 1
&& mat[x][up] == 1 && mat[x][down] == 1) {
length++;
left--;
up--;
down++;
right++;
}
if (length >= maxEdge) {
maxEdge = length;
maxCenter[0] = x;
maxCenter[1] = y;
}
}
}
}
if (maxEdge >= 1)
System.out.println("Biggest plus found, center at x="
+ maxCenter[0] + " y=" + maxCenter[1] + " edge length="
+ maxEdge);
}
Uncompleted, but you get the idea. Maybe, as the matrix is sparse, we can save some space by doing DFS/BFS as it indicates the problem.
public Coordinate biggestCross(boolean[][] matrix){
int n = matrix.length;
if(n == 0)
return null;
int m = matrix[0].length;
if(m == 0)
return null;
Edge[][] edges = new Edge[n][m];
//Here we count 1s to the left
//We must do the same for top, right and bottom (I did not code it)
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = 0; j < n; j++){
edges[i][j] = new Edge();
edge.left = sum;
if(matrix[i][j])
sum++;
else
sum = 0;
}
}
//Then it is just a matter of selecting the biggest one
//...
}
I guess a simple way to do it could be as follows. Please let me know if there is any mistake
package com.program.Matrix;
public class LongestPlusSign {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] sparse = new int[][]{
{0,0,1,0,1,1,0},
{1,0,1,0,1,0,1},
{1,1,1,1,1,1,1},
{0,0,1,0,1,0,0},
{0,0,0,0,1,0,0}};
int currlength=0;
String position="";
for(int i=1;i<sparse.length-1;i++){
for(int j=1;j<sparse[0].length-1;j++){
if(sparse[i][j]==1){
int length=getLength(sparse, i, j);
if(length>0 && length>currlength){
position=i+","+j;
currlength=length;
}
}
}
}
System.out.println("Length is: "+currlength+" and position is: "+position);
}
public static int getLength(int[][]sparse,int row,int column){
int left = column-1;
int right = column+1;
int top = row-1;
int bottom = row+1;
int length=0;
if(left<0 || top <0 || right>sparse.length || bottom>sparse[0].length){
return length;
}
else{
while(sparse[row][left]==1 && sparse[row][right]==1
&& sparse[top][column]==1 && sparse[bottom][column]==1){
length++;
left--;
right++;
top--;
bottom++;
if(left<0 || top <0 || right>sparse[0].length || bottom>sparse.length){
break;
}
}
}
return length;
}
}
import java.io.*;
import java.util.*;
class Solution {
static String source = "5 7"+ "\n"
+ "0 0 1 0 0 1 0" + "\n"
+ "1 0 1 0 1 0 1" + "\n"
+ "1 1 1 1 1 1 1" + "\n"
+ "0 0 1 0 0 0 0" + "\n"
+ "0 0 0 0 0 0 0";
private int M, N;
private int rootx, rooty;
private int[][] matrix;
public Solution(int M, int N) {
this.M = M;
this.N = N;
this.matrix = new int[M][N];
}
public static void main(String[] args) {
Scanner in = new Scanner(source);
int M = in.nextInt();
int N = in.nextInt();
System.out.println(M + " " + N);
Solution s = new Solution(M, N);
for(int x = 0; x < M; x++) {
for(int y = 0; y < N; y++) {
s.matrix[x][y] = in.nextInt();
System.out.print(s.matrix[x][y] + " ");
}
System.out.println("");
}
int size = s.run();
System.out.println("Max length of "+size+" starting from "+s.rootx+" "+s.rooty);
}
/*
*/
public boolean isValid(int i, int j) {
if(i<0 || i>=M || j<0 || j>=N) return false;
if(matrix[i][j] == 0) return false;
return true;
}
/**/
public int run() {
int max = 0;
for(int i =1; i<M; i++) {
for(int j = 1; j<N; j++) {
if(isValid(i, j) == false) continue;
int length = 0;
while(length < Math.min(i, j)) {
length++;
if(!(isValid(i+length, j) || isValid(i, j+length) || isValid(i-length, j) || isValid(i, j-length)))
break;
}
if(length > max) {
max = length;
rootx = i;
rooty = j;
}
}
}
return max;
}
}
import javafx.util.Pair;
/**
* Finds Max cross
*
* @author al fatykhov
*/
public class MaxCross {
private final int[][] board;
protected MaxCross(int[][] board) {
this.board = board;
}
protected Pair<Integer, Integer> biggestCross() {
Pair<Integer, Integer> maxCross = null;
int maxWeight = 0;
for (int y = 1; y < board.length - 2; y++) {
for (int x = 1; x < board[y].length - 2; x++) {
if (board[y][x] == 1 && board[y][x - 1] == 1 && board[y - 1][x] == 1
&& board[y][x + 1] == 1 && board[y + 1][x] == 1) {
Pair<Integer, Integer> cross = new Pair(x, y);
int weight = getWeightHor(cross);
weight += getWeightVer(cross);
if (weight > maxWeight) {
maxWeight = weight;
maxCross = cross;
}
}
}
}
return maxCross;
}
private int getWeightHor(Pair<Integer, Integer> cross) {
int weight = 0;
for (int direction = -1; direction < 3; direction += 2) {
for (int i = (cross.getKey() + direction);
i >= 0 && i <= board[cross.getKey()].length - 1;
i += direction) {
if (board[cross.getValue()][i] == 0) {
break;
}
weight++;
}
}
return weight;
}
private int getWeightVer(Pair<Integer, Integer> cross) {
int weight = 0;
for (int direction = -1; direction < 3; direction += 2) {
for (int i = (cross.getValue() + direction);
i >= 0 && i <= board.length - 1;
i += direction) {
if (board[i][cross.getKey()] == 0) {
break;
}
weight++;
}
}
return weight;
}
public static void main(String[] args) {
// TODO code application logic here
int[][] board = {
{0, 0, 0, 0, 0, 1, 0},
{1, 0, 1, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1},
{0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0}};
MaxCross app = new MaxCross(board);
Pair<Integer, Integer> biggestCross = app.biggestCross();
System.out.println("Max cross x=" + biggestCross.getKey() + ", y=" + biggestCross.getValue());
}
}
import javafx.util.Pair;
/**
* Finds Max cross
*
* @author al fatykhov
*/
public class MaxCross {
private final int[][] board;
protected MaxCross(int[][] board) {
this.board = board;
}
protected Pair<Integer, Integer> biggestCross() {
Pair<Integer, Integer> maxCross = null;
int maxWeight = 0;
for (int y = 1; y < board.length - 2; y++) {
for (int x = 1; x < board[y].length - 2; x++) {
if (board[y][x] == 1 && board[y][x - 1] == 1 && board[y - 1][x] == 1
&& board[y][x + 1] == 1 && board[y + 1][x] == 1) {
Pair<Integer, Integer> cross = new Pair(x, y);
int weight = getWeightHor(cross);
weight += getWeightVer(cross);
if (weight > maxWeight) {
maxWeight = weight;
maxCross = cross;
}
}
}
}
return maxCross;
}
private int getWeightHor(Pair<Integer, Integer> cross) {
int weight = 0;
for (int direction = -1; direction < 3; direction += 2) {
for (int i = (cross.getKey() + direction);
i >= 0 && i <= board[cross.getKey()].length - 1;
i += direction) {
if (board[cross.getValue()][i] == 0) {
break;
}
weight++;
}
}
return weight;
}
private int getWeightVer(Pair<Integer, Integer> cross) {
int weight = 0;
for (int direction = -1; direction < 3; direction += 2) {
for (int i = (cross.getValue() + direction);
i >= 0 && i <= board.length - 1;
i += direction) {
if (board[i][cross.getKey()] == 0) {
break;
}
weight++;
}
}
return weight;
}
public static void main(String[] args) {
// TODO code application logic here
int[][] board = {
{0, 0, 0, 0, 0, 1, 0},
{1, 0, 1, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1},
{0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0}};
MaxCross app = new MaxCross(board);
Pair<Integer, Integer> biggestCross = app.biggestCross();
System.out.println("Max cross x=" + biggestCross.getKey() + ", y=" + biggestCross.getValue());
}
}
Looks like n^2 solution, but also with n^2 space requirement.
I'm creating 2 matrixes with max number of '1' available to the left/right or top/bottom of item. And then just searching for the max in these matrixes.
#include <iostream>
#include <vector>
using namespace std;
void fillDeltaY(vector<vector<int>>& map, int x, int y, int count){
for(int j =0; j <count; j++){
map[x][y-j] = min(j, (count - 1)-j);
}
}
void fillDeltaX(vector<vector<int>>& map, int x, int y, int count){
for(int i =0; i < count; i++){
map[x-i][y] = min(i, (count - 1)-i);
}
}
int maxCross(vector<vector<int>> map, int n, int m){
vector<vector<int>> maxDeltaX(n, vector<int>(m));
vector<vector<int>> maxDeltaY(n, vector<int>(m));
//fill delta X
for(int j =0; j < m; j++){
int xCount = 0;
for(int i =0; i < n; i++){
if(map[i][j] == 1){
xCount++;
}else if (xCount > 0){
fillDeltaX(maxDeltaX, i-1, j, xCount);
xCount = 0;
}
}
if(xCount > 0){
fillDeltaX(maxDeltaX, n-1, j, xCount);
}
}
//fill delta Y
for(int i =0; i < n; i++){
int yCount = 0;
for(int j =0; j < m; j++){
if(map[i][j] == 1){
yCount++;
}else{
fillDeltaY(maxDeltaY, i, j-1, yCount);
yCount = 0;
}
}
if(yCount > 0){
fillDeltaY(maxDeltaY, i, m-1, yCount);
}
}
int maxCross = 0;
for(int i =0; i < n; i++){
for(int j =0; j < m; j++){
int cross = min(maxDeltaY[i][j], maxDeltaX[i][j]);
maxCross = max( maxCross, cross);
}
}
return maxCross;
}
void test(){
vector<vector<int>> matrix {
{0, 0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1},
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}
};
int result = maxCross(matrix, matrix.size(), matrix[0].size());
printf("%d\n", result);
int i = 0; i++;
}
int main(int argc, const char * argv[]) {
// insert code here...
std::cout << "Hello, World!\n";
test();
return 0;
}
private class CrossHelper
{
public int Left;
public int Right;
public int Up;
public int Down;
}
public static int FindMaxCross(int[,] a)
{
var matrix = new CrossHelper[a.GetLength(0), a.GetLength(1)];
for (int i=0; i < a.GetLength(0); i++)
for (int j=0; j < a.GetLength(1); j++)
matrix[i,j] = new CrossHelper();
// Update values from Left-Up to Right-Bottom
for (int i=0; i < a.GetLength(0); i++)
for (int j=0; j < a.GetLength(1); j++)
{
if (a[i,j] == 0)
continue;
// Update Left
matrix[i,j].Left = (j > 0) ? matrix[i,j-1].Left + 1 : 1;
// Update Right
matrix[i,j].Up = (i > 0) ? matrix[i-1,j].Up + 1 : 1;
}
// Update values from Right-Down to Left-Up
for (int i=a.GetLength(0)-1; i >- 0; i--)
for (int j=a.GetLength(1)-1; j >= 0; j--)
{
if (a[i,j] == 0)
continue;
// Update Left
matrix[i,j].Right = (j < a.GetLength(1)-1) ? matrix[i,j+1].Right + 1 : 1;
// Update Right
matrix[i,j].Down = (i < a.GetLength(0)-1) ? matrix[i+1,j].Down + 1 : 1;
}
for (int i=0; i < a.GetLength(0); i++)
{
for (int j=0; j < a.GetLength(1); j++)
Console.Write(matrix[i,j].Right + ", ");
Console.WriteLine();
}
int maxCross = 0;
for (int i=1; i < a.GetLength(0)-1; i++)
for (int j=1; j < a.GetLength(1)-1; j++)
{
if (a[i,j] == 0)
continue;
int minHor = Math.Min(matrix[i,j-1].Left, matrix[i,j+1].Right);
int minVer = Math.Min(matrix[i-1,j].Up, matrix[i+1,j].Down);
int min = Math.Min(minHor, minVer);
maxCross = Math.Max(maxCross, min);
}
return maxCross;
}
int findplus(vector<vector<int>> input, int i , int j, int direction)
{
if(i >= input.size() || i < 0)
return 0;
if(j >= input[0].size() || j < 0)
return 0;
if(input[i][j] == 0)
return 0;
int sum = 1;
if(direction == flat){
sum += findplus(input, i, j+1, horizright) + findplus(input, i, j-1, horizleft) +
findplus(input, i-1, j, verticalup) + findplus(input, i+1, j, verticaldown);
}
else if (direction == horizleft)
sum += findplus(input, i, j-1, horizleft);
else if (direction == horizright)
sum += findplus(input, i, j+1, horizright);
else if(direction == verticalup)
sum += findplus(input, i-1, j, verticalup) ;
else
sum+= findplus(input, i+1, j, verticaldown);
return sum;
}
int main (int argc, char *argv[])
{
vector<vector<int>> matrix= {
{0, 0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 1, 0, 1 },
{1, 1, 1, 1, 1, 1, 1 },
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}
};
int retval = 0; int maxretval = INT_MIN;
int maxindexx = -1; int maxindexy = -1;
for(int i = 1; i < matrix.size() -1; i++) // rows
for(int j = 1; j < matrix[0].size() -1; j++) //columns
{
if(matrix[i][j] == 1 && matrix[i-1][j] ==1 && matrix[i+1][j] ==1 && matrix[i][j-1] ==1 && matrix[i][j+1] ==1) {
retval = findplus(matrix, i, j, flat);
if(retval > maxretval)
{ maxretval = retval;
maxindexx = i;
maxindexy = j;
}
}
}
cout << "Largest Plus Sign In The Sparse Matrix is = " << retval << " At ( " << maxindexx << " " <<maxindexy << " )" << endl;
return 0;
}
int findplus(vector<vector<int>> input, int i , int j, int direction)
{
if(i >= input.size() || i < 0)
return 0;
if(j >= input[0].size() || j < 0)
return 0;
if(input[i][j] == 0)
return 0;
int sum = 1;
if(direction == flat){
sum += findplus(input, i, j+1, horizright) + findplus(input, i, j-1, horizleft) +
findplus(input, i-1, j, verticalup) + findplus(input, i+1, j, verticaldown);
}
else if (direction == horizleft)
sum += findplus(input, i, j-1, horizleft);
else if (direction == horizright)
sum += findplus(input, i, j+1, horizright);
else if(direction == verticalup)
sum += findplus(input, i-1, j, verticalup) ;
else
sum+= findplus(input, i+1, j, verticaldown);
return sum;
}
int main (int argc, char *argv[])
{
vector<vector<int>> matrix= {
{0, 0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 1, 0, 1 },
{1, 1, 1, 1, 1, 1, 1 },
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}
};
int retval = 0; int maxretval = INT_MIN;
int maxindexx = -1; int maxindexy = -1;
for(int i = 1; i < matrix.size() -1; i++) // rows
for(int j = 1; j < matrix[0].size() -1; j++) //columns
{
if(matrix[i][j] == 1 && matrix[i-1][j] ==1 && matrix[i+1][j] ==1 && matrix[i][j-1] ==1 && matrix[i][j+1] ==1) {
retval = findplus(matrix, i, j, flat);
if(retval > maxretval)
{ maxretval = retval;
maxindexx = i;
maxindexy = j;
}
}
}
cout << "Largest Plus Sign In The Sparse Matrix is = " << retval << " At ( " << maxindexx << " " <<maxindexy << " )" << endl;
return 0;
}
int findplus(vector<vector<int>> input, int i , int j, int direction)
{
if(i >= input.size() || i < 0)
return 0;
if(j >= input[0].size() || j < 0)
return 0;
if(input[i][j] == 0)
return 0;
int sum = 1;
if(direction == flat){
sum += findplus(input, i, j+1, horizright) + findplus(input, i, j-1, horizleft) +
findplus(input, i-1, j, verticalup) + findplus(input, i+1, j, verticaldown);
}
else if (direction == horizleft)
sum += findplus(input, i, j-1, horizleft);
else if (direction == horizright)
sum += findplus(input, i, j+1, horizright);
else if(direction == verticalup)
sum += findplus(input, i-1, j, verticalup) ;
else
sum+= findplus(input, i+1, j, verticaldown);
return sum;
}
int main (int argc, char *argv[])
{
vector<vector<int>> matrix= {
{0, 0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 1, 0, 1 },
{1, 1, 1, 1, 1, 1, 1 },
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}
};
int retval = 0; int maxretval = INT_MIN;
int maxindexx = -1; int maxindexy = -1;
for(int i = 1; i < matrix.size() -1; i++) // rows
for(int j = 1; j < matrix[0].size() -1; j++) //columns
{
if(matrix[i][j] == 1 && matrix[i-1][j] ==1 && matrix[i+1][j] ==1 && matrix[i][j-1] ==1 && matrix[i][j+1] ==1) {
retval = findplus(matrix, i, j, flat);
if(retval > maxretval)
{ maxretval = retval;
maxindexx = i;
maxindexy = j;
}
}
}
cout << "Largest Plus Sign In The Sparse Matrix is = " << retval << " At ( " << maxindexx << " " <<maxindexy << " )" << endl;
return 0;
}
def check_next_level(arr, i, j, depth):
if depth > i or depth > i \
or depth > len(arr)-1-i or depth > len(arr[0])-1-j:
return False
if arr[i-depth][j] and arr[i+depth][j] \
and arr[i][j-depth] and arr[i][j+depth]:
return True
return False
a = [[0,0,1,0,0], [0,0,1,0,0],[1,1,1,1,1],[0,0,1,0,0],[0,0,1,0,0]]
max_depth = 0
max_loc = None
for i in xrange(len(a)):
for j in xrange(len(a[0])):
depth = 1
while check_next_level(a, i, j, depth):
if depth > max_depth:
max_depth = depth
max_loc = (i, j)
depth += 1
print max_depth, max_loc
#! /usr/bin/env ruby
solutions = []
# inputs = [ %w(0 1 1), %w(1 1 1), %w(1 1 1) ]
inputs = [ %w(0 0 1 0 0 1 0),
%w(1 0 1 0 1 0 1),
%w(1 1 1 1 1 1 1),
%w(0 0 1 0 0 0 0),
%w(0 0 0 0 0 0 0) ]
def get_largest_plus(inputs, row, col, try_len = 1)
unless ((row - try_len) >= 0 && inputs[row - try_len][col] == '1' && #top
(row + try_len) < inputs.size && inputs[row + try_len][col] == '1' && #bottom
(col - try_len) >= 0 && inputs[row][col - try_len] == '1' && #left
(col + try_len) < inputs[row].size && inputs[row][col + try_len] == '1') #right
return try_len - 1
end
return get_largest_plus(inputs, row, col, try_len + 1)
end
(0...inputs.size).each do |row|
(0...inputs[row].size).each do |col|
next unless inputs[row][col] == '1'
plus_size = get_largest_plus(inputs, row, col)
next unless plus_size > 0
solutions.push([[row, col], plus_size])
end
end
largest_i = nil
size = 0
solutions.each_with_index do |sol, i|
next if largest_i && size > sol[1]
largest_i = i
size = sol[1]
end
puts "#{size}, #{solutions[largest_i][0]}"
I wonder:
Is this a plus?
0 0 0 0 1 0 0 0 0
0 1 1 0 1 0 1 1 0
0 0 0 0 1 0 1 1 0
0 0 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 1 0
1 0 0 0 1 0 0 0 0
that is to say a "plus" would be defined as one horizontal segment of only 1s of size 2*i+1 and one vertical segment of only 1s of size 2*i+1 intersecting at their center.
Or only that kind of stuff is a plus?
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
If that's the second, it is a bit more complicated with a sparse matrix... So I'll assume it is the first.
I represent the sparse matrix simply as the set of positions where the 1s are.
package exercices;
import java.util.*;
public class LargestPlusFinder {
public static Plus findLargestPlus(Set<Position> board) throws NoPlusFoundException {
AdjacencyGraph adjacencyGraph = new AdjacencyGraph(board);
return adjacencyGraph.findLargestPlus();
}
private static class AdjacencyGraph {
Map<Position, Vertex> vertices;
Set<Vertex> potentialPlusCenters;
public AdjacencyGraph(Set<Position> board) {
vertices = new HashMap<>();
potentialPlusCenters = new HashSet<>();
for (Position position: board) {
addPosition(position);
}
}
private void addPosition(Position position) {
if (vertices.containsKey(position)) {
return;
}
Vertex newVertex = new Vertex(position);
makeEdgesForNewVertex(newVertex);
if (newVertex.isPotentialPlusCenter()) {
potentialPlusCenters.add(newVertex);
}
vertices.put(position, newVertex);
}
private void makeEdgesForNewVertex(Vertex newVertex) {
Position position = newVertex.getPosition();
for (Direction direction: Direction.values()) {
if (vertices.containsKey(position.getAdjacentPosition(direction))) {
Vertex adjacentVertex = vertices.get(position.getAdjacentPosition(direction));
makeBidirectionalEdge(newVertex, direction, adjacentVertex);
if (adjacentVertex.isPotentialPlusCenter()) {
potentialPlusCenters.add(adjacentVertex);
}
}
}
}
private void makeBidirectionalEdge(Vertex v1, Direction direction, Vertex v2) {
v1.add(direction, v2);
v2.add(opposite(direction), v1);
}
public Plus findLargestPlus() throws NoPlusFoundException {
if (vertices.isEmpty()) {
throw new NoPlusFoundException();
}
int maxEdgeLength = 0;
Position maxPlusCenter = vertices.keySet().iterator().next();
for (Vertex v: potentialPlusCenters) {
Plus plus = getPlusAt(v); // there is at least a plus of edge size 0 at v
if (plus.getEdgeLength() > maxEdgeLength) {
maxEdgeLength = plus.getEdgeLength();
maxPlusCenter = plus.getCenter();
}
}
return new Plus(maxPlusCenter, maxEdgeLength);
}
private Plus getPlusAt(Vertex v) {
Queue<Exploration> q = new LinkedList<>();
for (Direction d: Direction.values()) {
q.add(new Exploration(d, v.getAdjacent(d), 1));
}
Exploration e = q.poll();
while (e != null) {
Direction direction = e.getDirection();
Vertex exploredVertex = e.getVertex();
int currentEdgeLength = e.getReachedEdgeLength();
if (exploredVertex.getAdjacent(direction) != null) {
q.add(new Exploration(direction, exploredVertex.getAdjacent(direction), currentEdgeLength + 1));
} else {
// Exploration stops here
return (new Plus(v.getPosition(), currentEdgeLength));
}
e = q.poll();
}
throw new ProgrammingErrorException();
}
private static class Vertex {
final Position position;
Map<Direction, Vertex> adjacentVertices;
public Vertex(Position position) {
this.position = position;
adjacentVertices = new HashMap<>();
}
public void add(Direction d, Vertex v) {
adjacentVertices.put(d, v);
}
public boolean isPotentialPlusCenter() {
return adjacentVertices.size() == Direction.values().length;
}
public Position getPosition() {
return position;
}
public Vertex getAdjacent(Direction d) {
return adjacentVertices.get(d);
}
}
private static class Exploration {
Direction direction;
Vertex vertex;
int reachedEdgeLength;
public Exploration(Direction direction, Vertex vertex, int reachedEdgeLength) {
this.direction = direction;
this.vertex = vertex;
this.reachedEdgeLength = reachedEdgeLength;
}
public Direction getDirection() {
return direction;
}
public Vertex getVertex() {
return vertex;
}
public int getReachedEdgeLength() {
return reachedEdgeLength;
}
}
}
private static class Position {
int i;
int j;
public Position(int i, int j) {
this.i = i;
this.j = j;
}
public Position getAdjacentPosition(Direction d) {
switch (d) {
case UP:
return new Position(i-1, j);
case DOWN:
return new Position(i+1, j);
case LEFT:
return new Position(i, j-1);
case RIGHT:
return new Position(i, j+1);
default:
throw new ProgrammingErrorException();
}
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Position position = (Position) o;
return i == position.i &&
j == position.j;
}
@Override
public int hashCode() {
return Objects.hash(i, j);
}
@Override
public String toString() {
return "Position{" +
"i=" + i +
", j=" + j +
'}';
}
}
private static class Plus {
private Position center;
private int edgeLength;
public Plus(Position center, int edgeLength) {
this.center = center;
this.edgeLength = edgeLength;
}
public Position getCenter() {
return center;
}
public int getEdgeLength() {
return edgeLength;
}
@Override
public String toString() {
return "(" + i + ", " + j + ")";
}
}
private enum Direction {UP, DOWN, RIGHT, LEFT}
private static Direction opposite(Direction d) {
switch (d) {
case UP:
return Direction.DOWN;
case DOWN:
return Direction.UP;
case LEFT:
return Direction.RIGHT;
case RIGHT:
return Direction.LEFT;
default:
throw new ProgrammingErrorException();
}
}
private static class NoPlusFoundException extends Exception {}
private static class ProgrammingErrorException extends RuntimeException {}
public static void main(String[] args) {
Set<Position> board = new HashSet<>();
board.add(new Position(100, 100));
board.add(new Position(101, 100));
board.add(new Position(102, 100));
board.add(new Position(99, 100));
board.add(new Position(98, 100));
board.add(new Position(100, 101));
board.add(new Position(100, 102));
board.add(new Position(100, 99));
board.add(new Position(100, 98));
board.add(new Position(99, 98));
try {
Plus maxPlus = findLargestPlus(board);
System.out.println(maxPlus);
} catch (NoPlusFoundException e) {
System.out.println("No plus in board.");
}
}
}
Can we do some thing like this ?.
1. visit matrix[i][j] != 0 then
keeping counting the number of ones seen
before this like row two will have (8,2) and
column 3 will have (1,4) and rowID of this > than
rowID of (8,2) then we have and remember
this max row and column 1’s count with rowID constraint
then we can solve this in O(M*N) right ?.
Can we do some thing like this ?.
1. visit matrix[i][j] != 0 then
keeping counting the number of ones seen
before this like row two will have (8,2) and
column 3 will have (1,4) and rowID of this > than
rowID of (8,2) then we have and remember
this max row and column 1’s count with rowID constraint
then we can solve this in O(M*N) right ?.
- spcht2016 November 19, 2016import java.util.*; public class LargestPlus { HashMap<String, Integer> hm; int hitCount; public enum Direction { LEFT, RIGHT, UP, DOWN; } private class Position { int i; int j; public Position(int i, int j){ this.i = i; this.j = j; } } public ArrayList<Position> getCandidates(int[][] board){ ArrayList<Position> candidates = new ArrayList<Position>(); for (int i = 1; i < board.length-1; i++){ for (int j = 1; j < board[0].length-1; j++){ if (board[i][j] ==1 && board[i-1][j] == 1 && board[i+1][j] == 1 && board[i][j-1]== 1 && board[i][j+1] == 1) candidates.add(new Position(i, j)); } } return candidates; } public int getMaxSize(Position p, int[][] board){ int min = Integer.MIN_VALUE; int left = getMaxSize(p.i, p.j-1, Direction.LEFT, board); int right = getMaxSize(p.i, p.j-1, Direction.RIGHT, board); int up = getMaxSize(p.i-1, p.j, Direction.UP, board); int down = getMaxSize(p.i+1, p.j, Direction.DOWN, board); return Math.min(left, Math.min(right, Math.min(up, down))); } public int getMaxSize(int i, int j, Direction d, int[][] board){ if (i< 0 || i >=board.length || j < 0 || j >= board[0].length || board[i][j] == 0) return 0; String key = i+""+j+""+d; hitCount++; if (hm.containsKey(key)) return hm.get(key); int size = 1; switch(d){ case LEFT: size+= getMaxSize(i, j-1, d, board); break; case RIGHT: size+= getMaxSize(i, j+1, d, board); break; case UP: size+= getMaxSize(i-1, j, d, board); break; case DOWN: size+= getMaxSize(i+1, j, d, board); break; } hm.put(key, size); return size; } public void getMaxPlus(int[][] board){ ArrayList<Position> candidates = getCandidates(board); hm = new HashMap<String, Integer>(); hitCount = 0; int maxSize = Integer.MIN_VALUE; Position maxPosition = null; for (Position p: candidates){ int size = getMaxSize(p, board); if (size > maxSize){ maxSize = size; maxPosition = p; } } System.out.println("hitCount: "+hitCount); if (maxPosition!= null) System.out.println("The max plus is rooted at: ("+ maxPosition.i+", "+maxPosition.j+")"); else System.out.println("No plus found"); } public static void main(String[] args){ LargestPlus lp = new LargestPlus(); int[][] board = { {0,0,0,0,0,1,0}, {1,0,1,1,1,0,1}, {1,1,1,1,1,1,1}, {0,0,1,1,0,0,0}, {0,0,0,1,0,0,0}}; /* { {0,0,0,1,0,1,0}, {1,0,1,1,1,0,1}, {1,1,1,1,1,1,1}, {0,0,1,1,0,0,0}, {0,0,0,1,0,0,0}}; */ lp.getMaxPlus(board); } }