Microsoft Interview Question: Given a 2D array of boolean v... | Glassdoor

Interview Question

Software Development Engineer In Test (SDET) Interview(Student Candidate) Redmond, WA

Given a 2D array of boolean values determine the largest

  square sub-array containing only 1s.
Tags:
algorithm
Answer

Interview Answer

2 Answers

0

Its a dynamic programming problem

Interview Candidate on Jun 5, 2014
0

int[][] arr = new int[][] { {0, 0, 0, 0}, {1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 0, 1} };
        int prev_len = 0;
        int index = 0;

        for(int i = 0; i < arr.length; i++)
        {
            int sq_rt = (int) Math.sqrt(arr[0].length);
            if(Math.sqrt(arr[0].length) - sq_rt == 0)
            {
                int count = 0;
                for(int j = 0; j < arr[i].length; j++)
                {
                    if(arr[i][j] == 1)
                    {
                        count++;
                        if(count == arr[i].length)
                        {
                            prev_len = arr[i].length;
                            index = i;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        System.out.println("The largest square sub-array containing 1s is at index " +index+ " and its length is " +prev_len);

Namrata on Feb 21, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.