Question

12:31 PM 45 n— Q1: There are N patients (numbered from 0 to 1) who want to visit the doctor. The doctor has S possible appointment slots, numbered from 1 to S. Each of the patients has two preferences. Patient k would like to visit the doctor during either slot A[k] or slot B[k]. The doctor can treat only one patient during each slot. Is it possible to assign every patient to one of their preferred slots so that there will be at most one patient assigned to each slot? Input: Two arrays A and B, both of N integers, and an integer S 1 <= N <= 10^6 1 <= S <= 2*10^6 1 <= A[i] <= 5 1 <= B[i]< <= S no patient has two preference for the same slot i.e. A[i] != B[i] Output: print "true" if it is possible to assign every patient to one of their preferred slots, one patient to one slot, and "false" otherwise. Q2: Given an mxn binary matrix filled with O's and I's, find the two similar size non overlapping square of maximum number of cell containing only 1's and return maximum no of cell.Opo09-1

Answer 1

Q1: Assigning Patients to Preferred Slots

#include <iostream>

#include <vector>

#include <unordered_set>

using namespace std;

bool canAssignSlots(const vector<int>& A, const vector<int>& B, int S) {

unordered_set<int> assignedSlots;

for (int i = 0; i < A.size(); ++i) {

// Check if the first preference can be assigned

if (assignedSlots.find(A[i]) == assignedSlots.end()) {

assignedSlots.insert(A[i]);

}

// Check if the second preference can be assigned

else if (assignedSlots.find(B[i]) == assignedSlots.end()) {

assignedSlots.insert(B[i]);

}

// If neither preference can be assigned, return false

else {

return false;

}

}

return true;

}

int main() {

// Example Usage

vector<int> A = {1, 2, 3};

vector<int> B = {4, 5, 6};

int S = 6;

if (canAssignSlots(A, B, S)) {

cout << "true" << endl;

} else {

cout << "false" << endl;

}

return 0;

}

2. the Python implementation is:

python

def max_size_squares(matrix):

m, n = len(matrix), len(matrix[0])

# Calculate the side length of the square submatrix ending at each cell

for i in range(1, m):

for j in range(1, n):

if matrix[i][j] == 1:

matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1

# Find the two largest non-overlapping squares

max1, max2 = 0, 0

for i in range(m):

for j in range(n):

if matrix[i][j] > max1:

max2 = max1

max1 = matrix[i][j]

elif matrix[i][j] > max2:

max2 = matrix[i][j]

return max1 * max2

# Example

matrix = [

[1, 1, 0, 1],

[1, 1, 1, 1],

[0, 1, 1, 0],

[1, 1, 1, 1]

]

result = max_size_squares(matrix)

print(result)