Question: GOOGLE OA | SWE Internship 2023 | Triangles | Maximize Collection | 22nd July (SET - 2)

Entering edit mode

Question 1:

Maximise Collection

Given N toys in a shop, each with a price represented by an array A. You have a certain amount of money, C, that you can use to buy toys. There are also K toys that are broken and you don't want to buy them.
For each Q query, find the maximum number of toys you can buy with the amount you have while avoiding broken toys.
Notes
• Use 1-based indexing.
•Query definition:
--> The first element represents an integer C, where C =Query[i][0].
-->The second element represents an integer K, where K = Query[i][1].
• The next K integers represent the indices of broken
toys which are Query[i][j] for all j > 1.
• Treat each query independently.

Function description
Complete the solve function. This function takes the following 4 parameters and returns an array of an answer to the query:
• N: Represents the size of array A
• A: Represents the array of costs of each toy
• Q: Represents the number of queries
• Query: Represents the query array
Input format for custom testing
Note: Use this input format if you are testing against custom
input or writing code in a language where we don't provide
boilerplate code.
• The first line contains T, which represents the number of
test cases.
• For each test case:
-->The first line contains a single integer N representing
the size of array. -->The second line contains N space-seperated integers representing the cost of toys. -->The third line contains an integer Q representing the number of queries. -->The next Q lines contain the query array.

Output format
For each test case, print Q space-separated integers representing the maximum number of toys you can purchase in a new line.
Constraints
1<T < 10
1 < N < 105
1 < A; < 106 Vi € [1, M]
1 < Q < 101
1 < C < 10°
0 ≤ K < 10
1 < Query[i][j] < =N for every j>1

Sample Input

1
10
7 3 6 8 2 1 4 9 5 10
4
10 3 3 5

Sample Output

3 5 5 10

Question 2:

Triangles

You are given a matrix M with n rows and m columns. The matrix only consists of
either 0 or 1.
A right-angled isosceles triangle is defined as:
• The hypotenuse has to be parallel to the x-axis.
• The length of hypotenuse should be odd and greater than or equal to three.
• All the cells on and inside the triangle should be 0.
Task
Determine the total number of right-angled isosceles triangles, which are formed by
0.
Example
Assumptions
The grid is given as:

1	1	1	1
1	0	1	1
0	0	0	1

Approach

You can see that there is one right-angles isoceles triangle,and the length of the hypotenuse is 3(the three 0s as the hypotenuse).Therefore ans is 1.

Function Description

Complete the find_triangles function provided in the editor.This function takes the following 3 parameters and returns the total number of isoceles right-angles angles:

Pi : Represents the number of rows in the matrix
m :Represents the number of columns in the matrix
M :Represents the matrix

Input Format
Note:This is the input format you must use to provide custom input
pile and Test button)

The first line contains one integer T denoting the number of test cases.T also specifies the number of times you have to run the find_triangles function on a different set of inputs.
For each test case:

-->The first line contains an integer n representing the number of rows of the
matrix. -->The second line contains an integer m representing the number of
columns of the matrix.
-->The next n lines contain a string of length m representing a row,
Output format
For each test case, print an integer in a new line representing the number of right
angled isosceles triangles.

Sample Input