Facebook Interview Question for SDE1s


Country: United States




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

We can get O(Min(m,n)^2) if we do bit manipulation:
For each row ( or column depends M < N or N < M ) we do
( example with rows )
Ri & Rj = Rij
if Rij > 0 menas we have 1's at the same Col.
Now lets check if the number of 1's > 1
if (Rij and (Rij -1)) > 0 ( x & (x-1) removes the right most 1')
we have more than 1 '1' in the row. And we found a rectangle.

This will need a nested loop to check every Ri & Rj ( i< j ) i,j <= Number of rows ( or columns )

- incarose November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple brute-force solution with O(N^2*M^2) where N and M are matrix width and height, but O(1) memory complexity:

private static boolean isRectangle(byte[][] m) {
    int h=m.length,w=m[0].length; 
    for(int y1=0;y1<h;y1++)
      for(int x1=0;x1<w;x1++)
        if(m[y1][x1]==1)
          for(int y2=y1+1;y2<h;y2++)
            for(int x2=x1+1;x2<w;x2++)
              if(m[y1][x2]==1 && m[y2][x1]==1 && m[y2][x2]==1)
                return true;
    return false;
  }
  
  private static void doTest1Yes() {
    byte[][] m = {
      {1,0,0,1,0},
      {0,0,1,0,1},
      {0,0,0,1,0},
      {1,0,1,0,1}};
    System.out.println(isRectangle(m)?"YES":"NO");
  }

  private static void doTest2No() {
    byte[][] m = {
      {1,0,0,1,0},
      {0,0,0,0,1},
      {0,0,0,1,0},
      {1,0,1,0,1}};
    System.out.println(isRectangle(m)?"YES":"NO");
  }

  public static void main(String[] args) {
    doTest1Yes();
    doTest2No();
  }

More efficient solution be time possible, but it will require additional memory, so this one also have chance to exists.

- Matviy Ilyashenko November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Much more efficient solution is to store only 1-th cells somewhere and then review only them looking for rectangle. Also we can notice that to make up a rectangle we need to have 2 pairs of points with same x or y coordinate, so let's store them grouped by y or x coordinate. Finally we should not check individually each pair or lines in matrix, we can just intersect sets of points in each line to see if final intersection will have 2 or more points.
Store all 1-th cells into a map take O(N*M), where N and M are matrix width and heigh, then we enumerate all pairs of lines/columns (it can be O(N^2) or O(M^2) what is less) and then make intersection of two sets, that takes O(N) or O(M) time. Lets assume that total it will be O(N*M+N^2*M) or (ON*M+M^2*N) - we can choose smaller dimension to have smaller from those two. Additional space needed is O(K) where K - number of 1-th in matrix. Code:

private static boolean isRectangle(byte[][] m) {
    Map<Integer, Set<Integer>> yPoints = new HashMap<Integer, Set<Integer>>();

    int h=m.length,w=m[0].length; 
    for(int y=0;y<h;y++)
      for(int x=0;x<w;x++)
        if(m[y][x]==1)
          yPoints.computeIfAbsent(y,s->new HashSet<Integer>()).add(x);
    
    List<Map.Entry<Integer, Set<Integer>>> lines = 
      new ArrayList<Map.Entry<Integer, Set<Integer>>>(yPoints.entrySet());
    for(int i=0;i<lines.size();i++) 
      for(int j=i+1;j<lines.size();j++) {
        Set<Integer> points = new HashSet<Integer>(lines.get(i).getValue());
        points.retainAll(lines.get(j).getValue());
        if(points.size()>=2) return true;
      }
    
    return false;
  }
  
  private static void doTest1Yes() {
    byte[][] m = {
      {1,0,0,1,0},
      {0,0,1,0,1},
      {0,0,0,1,0},
      {1,0,1,0,1}};
    System.out.println(isRectangle(m)?"YES":"NO");
  }

  private static void doTest2No() {
    byte[][] m = {
      {1,0,0,1,0},
      {0,0,0,0,1},
      {0,0,0,1,0},
      {1,0,1,0,1}};
    System.out.println(isRectangle(m)?"YES":"NO");
  }

  public static void main(String[] args) {
    doTest1Yes();
    doTest2No();
  }

- Matviy Ilyashenko November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if bit operation can be consider as O(1) and n,m < 32
then we can use integer on every row/column for bit mask, and compare them
then it should be O(m*n)

- zyfo2 November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){
  
    int[][] arr = {{1, 0, 0, 1, 0}, {0, 0, 1, 0, 1}, {0, 0, 0, 1, 0}, {1, 0, 1, 0, 1}};
    rectangles(arr);
  
  }
 
  
  public static void rectangles(int[][] arr){
  	int n = arr.length;
    int m = arr[0].length;
    
    for(int i = 0; i < n; i++){
      int index1 = -1;
      int index2 = -1;
      for(int j = 0; j < m; j++){
      	if(arr[i][j] == 1 && index1 == -1)
          index1 = j;
        else if(arr[i][j] == 1 && index2 == -1)
          index2 = j;
   		
        if(index1 != -1 && index2 != -1){
        	check(arr, i, index1, i, index2);
          	index1 = index2;
          	index2 = -1;
        }
      }
    }
    
  }
  
  public static void check(int[][] arr, int i1, int j1, int i2, int j2){
  	int n = arr.length;
    int m = arr[0].length;
    
    for(int i = i1+1; i < n; i++){
      int[] row = arr[i];
      if(row[j1] == 1 && row[j2] == 1){
      	System.out.println("Corner 1 - " + i1 + ", " + j1);
        System.out.println("Corner 2 - " + i1 + ", " + j2);
        System.out.println("Corner 3 - " + i + ", " + j1);
        System.out.println("Corner 4 - " + i + ", " + j2);
        System.out.println();
      }
    }
  }

- sudip.innovates November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex came up with a cool idea in an other thread to solve this kind of question in O(n*m^2):
- scan from top to down, line by line
- for each line, remember each combination of 2 1's and push that into a hash-set
- if you ever find that combination again in a later line, you get your rectangle
I think the solution has a lot of charm, especially it's a sparse matrix

- ChrisK November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the 3 corners and calculate the last one

public static bool IsThereRectangle(int[,] a)
        {
            int n = a.GetLength(0);
            int m = a.GetLength(1);

            if (a[0, 0] == 1 && a[n - 1, m - 1] == 1 && a[0, m - 1] == 1 && a[n - 1, 0] == 1)
            {
                return true;
            }

            for (int i = 0; i < n; i++){

                int temp = i;
                for (int j = 0; j < m; j++)
                {
                    if (a[i, j] == 1)
                    {
                       int c1 = j;

                        while (++j < m)
                        {
                            int tmp = i;
                            if (a[i, j] == 1)
                            {
                                while (++i < n)
                                {
                                    if (a[i, j] == 1)
                                    {

                                        if (a[i, c1] == 1)
                                        {
                                            return true;
                                        }
                                    }
                                }
                            }
                            i = tmp;
                        }
                    }
                }
                i = temp;
            }
            return false;

        }

- Daniel November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool IsThereRectangle(int[,] a)
        {
            int n = a.GetLength(0);
            int m = a.GetLength(1);

            if (a[0, 0] == 1 && a[n - 1, m - 1] == 1 && a[0, m - 1] == 1 && a[n - 1, 0] == 1)
            {
                return true;
            }

            for (int i = 0; i < n; i++){

                int temp = i;
                for (int j = 0; j < m; j++)
                {
                    if (a[i, j] == 1)
                    {
                       int c1 = j;

                        while (++j < m)
                        {
                            int tmp = i;
                            if (a[i, j] == 1)
                            {
                                while (++i < n)
                                {
                                    if (a[i, j] == 1)
                                    {

                                        if (a[i, c1] == 1)
                                        {
                                            return true;
                                        }
                                    }
                                }
                            }
                            i = tmp;
                        }
                    }
                }
                i = temp;
            }
            return false;

        }

- Dan November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Found the brute force O(N^2 M^2) solution, and was able to find the O(N^2 M) one. The bitwise solution for the N, M < 32 case is pretty awesome!

Implementation in JavaScript.

function intersect(setA, setB){
  const intersection = new Set();
  
  setA.forEach((item) => {
    if (setB.has(item)){
      intersection.add(item);
    }
  });
  
  return intersection;
}

function hasRect(matrix){
  const N = matrix.length;
  const M = matrix[0].length;
  const H = new Map();
  for (let i = 0; i < N; i++){
    for (let j = 0; j < M; j++){
      if (matrix[i][j] === 1){
        if (!H.has(i)){
          H.set(i, new Set());
        }
        const columns = H.get(i);
        columns.add(j);
      }
    }
  }
  
  for (let i = 0; i < N; i++){
    for (let j = i + 1; j < N; j++){
      const firstColumn = H.get(i);
      const secondColumn = H.get(j);
      const intersection = intersect(firstColumn, secondColumn);

      if (intersection.size >= 2){
        const intersectionArray = Array.from(intersection);
        
        console.log(`Top Left (${i}, ${intersectionArray[0]})`);
        console.log(`Top Right (${i}, ${intersectionArray[1]})`);
        console.log(`Bottom Left (${j}, ${intersectionArray[0]})`);
        console.log(`Bottom Right (${j}, ${intersectionArray[1]})`);
        
        return true;
      }
    }
  }
  
  return false;
}

const matrix = [
[1, 0, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[1, 0, 1, 0, 1]
];

console.log(hasRect(matrix));

- Anonymous November 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Based on ChrisK's idea :

bool isRectangle( const vector<vector<int>>&  matrix )
{
	int rows = matrix.size();
	if(rows == 0 ) return false;
	int columns = matrix[0].size();
	
	unordered_map<int, unordered_set<int>> table;
	
	for( int i=0; i<rows; ++i)
	{
		
		for( int j=0; j<columns-1; ++j)
		{
			for(int k=j+1; k<columns; ++k)
			{
				if( matrix[i][j]==1 && matrix[i][k]==1)
				{
					if( table.find(j) != table.end() && table[j].find(k) != table[j].end() )
					{
						return true;
					}
					if( table.find(k) != table.end() && table[k].find(j) != table[k].end() )
					{
						return true;
					}
					table[j].insert(k);
					table[k].insert(j);
				}
			}
		}
	}
	return false;
}

- mr.robot.fun.society November 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in o(m*n*(max(m,n)))

you basically need to check whether the top left corner can make a square.

public static void main(String[] args) {
        boolean[][] m = new boolean[][]{
                {true, false, false, true, false},
                {false, false, true, false, true},
                {false, false, false, true, false},
                {true, false, true, false, true}
        };

        System.out.println(hasRectangleInMatrix(m));

    }

    static boolean hasRectangleInMatrix(boolean[][] matrix) {
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                if (matrix[row][col] && canFormTriangle(matrix, row, col)) {
                    return true;
                }
            }
        }
        return false;
    }

    static boolean canFormTriangle(boolean[][] matrix, int leftRow, int leftCol) {
        int maxSize = Math.min(matrix.length - leftRow, matrix[0].length - leftCol);
        while (maxSize > 1) {
            if (matrix[leftRow + maxSize - 1][leftCol] && matrix[leftRow + maxSize - 1][leftCol + maxSize - 1] && matrix[leftRow][leftCol + maxSize - 1]) {
                System.out.println("top left corner at: (" + leftRow + "," + leftCol + ")" + " with Size: " + maxSize);
                return true;
            }
            maxSize--;
        }
        return false;
    }

- Modernphysics November 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_rect(maze):
	# print maze
	rows = len(maze)
	cols = len(maze[0])
	sq_len = min(rows, cols)
	if not sq_len%2==0:
		sq_len = sq_len-1

	all_ones = []

	for i in range(0, rows):
		for j in range(0, cols):
			if maze[i][j]==1:
				all_ones.append((i,j))
	# print all_ones

	rects = []
	small_maze = []
	for (x,y) in all_ones:
		for inc in range(1, sq_len):
			if ((x,y+inc)in all_ones) and ((x+inc,y+inc) in all_ones) and ((x+inc,y) in all_ones):
				for i in range(x, x+inc+1):
					for j in range(y, y+inc+1):
						small_maze.append(maze[i][j])
	print small_maze

- ronj November 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static String isRectangle(int[][] arr) {
        int row = 0;
        int col = 0;
        int result = 0;
        while(row < arr.length - 2) {
            if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
               return "YES";
            }
            row++;
        }
        row = 0;
        while(col < arr.length - 2) {
            if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
                return "YES";
            }
            col++;
        }
        return "NO";

}

- Anonymous November 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static String isRectangle(int[][] arr) {
        int row = 0;
        int col = 0;
        int result = 0;
        while(row < arr.length - 2) {
            if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
               return "YES";
            }
            row++;
        }
        row = 0;
        while(col < arr.length - 2) {
            if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
                return "YES";
            }
            col++;
        }
        return "NO";

    }

- Nandini November 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static String isRectangle(int[][] arr) {
        int row = 0;
        int col = 0;
        int result = 0;
        while(row < arr.length - 2) {
            if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
               return "YES";
            }
            row++;
        }
        row = 0;
        while(col < arr.length - 2) {
            if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
                return "YES";
            }
            col++;
        }
        return "NO";

    }

- nandinicbit November 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CheckMatrix {
        
        public static void main(String[] args) {
                int m[][]= {{1, 0, 0, 1, 0}, 
                                {0, 0, 1, 0, 1},
                                {0, 0, 0, 1, 0},
                                {1, 0, 1, 0, 1}};
                                
                System.out.println(checkInternal(m,0,0,2));
        
        }
        
        private static boolean checkInternal(int[][] m, int dx,int dy,int s) {
                
                if(m[dy][dx] == 1 && m[dy][dx+s] == 1 && m[dy+s][dx] == 1 && m[dy+s][dx+s] == 1) return true;
                if(dx+s == m[dy].length -1) {
                        dx=0;
                        if(dy+s == m.length -1) {
                                dy=0;
                                if(s == m.length -1) {
                                        return false;
                                }
                                 else s ++;
                        } else {
                                dy++;
                        }
                } dx++;
                
                return checkInternal(m,dx,dy,s);
        }
}

- thatfernando@yahoo.com November 20, 2017 | Flag Reply


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