9 weeks ago

John 910

Hyderabad

Question 1

Given file1, file2 you need to print the modification made in file 1 to get file2. That is if an element is removed from file1 to make file2, you need to append -ve sign before it, if new element is added in file1 to make file2, you need to append +ve sign before it. (Similar to git diff)

Example:

File 1: A B C

File 2: B C D

Output:

-A B C +D

Question 2

You are given an m x n binary matrix grid where each cell is either 0 (empty) or 1 (occupied).

You are then given stamps of size stampHeight x stampWidth. We want to fit the stamps such that they follow the given restrictions and requirements:

1. Cover all the empty cells.
2. Do not cover any of the occupied cells.
3. We can put as many stamps as we want.
4. Stamps can overlap with each other.
5. Stamps are not allowed to be rotated.
6. Stamps must stay completely inside the grid.

Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.

Example 1:

Input:

grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3

Output:

true

Explanation: We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.

Example 2

Input:

grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2

Output:

false

Explanation: There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.

8 months ago

Akshay Sharma 990

Chandigarh

Question 2

Pre-Knowledge

Calculate the sub-matrix sum

Intituion/Algorithm

• As there are no restrictions on the number of stamps thus at each position, we put a stamp if possible. After putting the stamps and covering the grid with those stamps, we will check if we have covered the complete grid.

• How to check if we can put a stamp at a position (say [i,j]):

  • The submatrix starting at (i,j) and ending at (i + h - 1, j + w - 1) must be completely empty, where h = stampHeight and w = stampWidth
  • Naive algorithm for this will take O(h*w) for each (i,j).
  • We will use the concept of suffix sum on matrices to find the sum of the matrix starting at (i,j) and ending at (i + h - 1, j + w - 1). If this sum is 0, then we can put a stamp at (i,j).
  • We will set grid[i][j] = 2 if we can put a stamp at location (i,j).

  Covering Grid With Stamps

  • At this point, we have grid[i][j] marked with 2, if we can start a stamp at that location. This stamp then flows from the submatrix starting at (i,j) and ending at (i + h - 1, j + w - 1)
• Now say grid[i][j] = 2. See picture.
• Now flow from (i,j) is h = 3 downwards. Also from (i,j) this flow is introduced till column j + w - 1 because we are starting a stamp of width w = 4 from (i,j)
• Also note the flow coming from above for location (i+1, j) = 2, as we started a stamp of height h = 3 at location (i,j).
• To denote the pending flow, we will use negative numbers. That's why in code flow = -(h-1) instead of h-1.

• Now at each location we will check

  • if grid[i][j] == 2 ==> We are starting a stamp.
  • if till >= j ==> A stamp was started in the current row, but at some previous column.
  • if grid[i][j] < 0 ==> There is a pending flow at current location.

• Time Complexity:O(M*N)

Code

     int n = grid.size(), m = grid[0].size();
    vector<vector<int>> suff(n+1, vector<int>(m+1));
    for(int i = n-1; i >= 0; --i){
        for(int j = m-1; j >= 0; --j){    
            suff[i][j] = grid[i][j]+ (j+1 < m ? suff[i][j+1] : 0 )+ (i+1 < n ? suff[i+1][j] : 0 )
                - (j+1 < m && i+1 < n ? suff[i+1][j+1] : 0);

            //Check if we can put a stamp starting at this cell, that is, All h * w cells starting at (i,j) are empty.
            if(grid[i][j] == 0 && n - i >= h && m - j >= w && (suff[i][j] - suff[i+h][j] - suff[i][j+w] + suff[i+h][j+w]) == 0)
                grid[i][j] = 2; //2 indicates start a stamp from here



        }
    }

    int total = n*m - suff[0][0]; //total empty spots        
    for(int i = 0; i < n; ++i){
        for(int till = -1, j = 0, flow = 1; j < m; ++j){

            if(grid[i][j] == 2){
                //start a stamp here
                till = min(m-1, j + w - 1);
                flow = -h + 1 ;
                total--;
            }
            else if(till >= j) {
                flow = -h + 1;
                total--;                    
            }
            else if(grid[i][j] < 0){
                flow = grid[i][j]+1;
                total--;
            }

            if(i+1 < n && grid[i+1][j] != 2 && grid[i+1][j] != 1 && flow < 1)
                grid[i+1][j] = flow;

        }
    }

    return total == 0;

8 months ago

Akshay Sharma 990

Chandigarh

Question 1

Overview

We are given two strings str1 and str2 and we have to convert string 1 to string 2 by following two types of operation

• Delete a character

• Insert a character

  We are not given that we have to minimize the number of moves also we are not given the size of str1 and str2 let it be 10^5.

Approach/Solution

• This question can be solved using the greedy technique and two pointers
• We can make two pointers named one and two and start traversing the string1 and check if the str1[one]==str2[two] then we can increase both pointers and print str[one].
• if str1[one]!=str2[two] then we print the negative sign and str[one] as we need to delete that string and increase only one++.
• once we reach either str1.size() or str2.size() we will break the loop.
• In the last, we have to check if pointer two is equal to str2.size() or not. If not we can print all the characters with a positive sign.
• Time Complexity: O(N)

Pseudo Code

int i = 0, j = 0;
while (i != s1.size() && j != s2.size())
{
    if (s1[i] == s2[j])
    {
        cout << s1[i] << " ";
        i++;
        j++;
    }
    else
    {
        cout << "-" << s1[i] << " ";
        i++;
    }
}
if (j != s2.size())
{
    for (int k = j; k < s2.size(); k++)
    {
        cout << "+" << s2[k] << " ";
    }
}