Susquehanna Software Engineering Intern - Online Assessment

I gave an OA for Susquehanna for the Software Engineering Intern role. There were 2 questions in total. I asked Claude to re-construct the questions for me: Q1: You are given a grid of integers with RR R rows and CC C columns, called the input grid. You are also given a smaller pattern grid with rr r rows and cc c columns. Each cell of the pattern is either an integer or an uppercase letter. Your task is to find a sub-grid of the input (a contiguous block of rr r rows and cc c columns) that matches the pattern, and report its position. A sub-grid matches the pattern if, for every cell of the pattern, the following hold: If the pattern cell is an integer, the corresponding cell of the sub-grid must contain exactly that integer. If the pattern cell is a letter, it acts as a variable. Equal letters must cover equal values, and equal values must be covered by equal letters. In other words, the correspondence between letters and the values they cover must be a one-to-one mapping: a letter always maps to the same value, and a value is always described by the same letter. (Consequently, two different letters cannot cover the same value.) The integer cells and the letter cells are checked independently of each other. If several sub-grids match, output the one with the smallest row index, and among those the smallest column index. If no sub-grid matches, output -1 -1. Input The first line contains two integers RR R and CC C: the dimensions of the input grid. The next RR R lines each contain CC C integers describing the input grid. The next line contains two integers rr r and cc c: the dimensions of the pattern. The next rr r lines each contain cc c tokens describing the pattern. Each token is either an integer or a single uppercase letter (A–Z). Output Print two integers: the row and column (0-indexed) of the top-left corner of the matching sub-grid, or -1 -1 if there is none. Constraints 1≤r≤R≤3001 \le r \le R \le 300 1≤r≤R≤300 1≤c≤C≤3001 \le c \le C \le 300 1≤c≤C≤300 Every integer in the input grid is between 11 1 and 10910^9 109. Every integer appearing in the pattern is between 11 1 and 10910^9 109. Pattern letters are uppercase English letters. Example 1 Input: 4 4 1 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6 2 2 A A A B Output: 0 0 Explanation: The top-left 2×22 \times 2 2×2 block is 1 1 1 2 Letter A consistently covers the value 11 1 (all three of its positions), and B covers 22 2. The mapping is one-to-one, so it matches. No earlier position works, so the answer is 0 0. Example 2 Input: 2 2 7 7 7 7 2 2 A B B A Output: -1 -1 Explanation: The only candidate block is the whole grid, where every value is 77 7. The pattern uses two different letters A and B, which would both have to cover the value 77 7. That violates the one-to-one rule, so nothing matches. ------------------------------------------- Q2: You process a sequence of nn n operations. Each operation describes a rectangle by two side lengths and is one of two types: Type 0 aa a bb b: store a container of size a×ba \times b a×b. Type 1 aa a bb b: ask whether a box of size a×ba \times b a×b fits inside every container stored so far. A box fits inside a container if the box can be placed inside it, possibly after rotating the box by 90 degrees. That is, a box a×ba \times b a×b fits a container w×hw \times h w×h if either a≤wa \le w a≤w and b≤hb \le h b≤h, or a≤ha \le h a≤h and b≤wb \le w b≤w. For a type 1 operation, the answer is YES if the box fits inside all containers stored so far, and NO otherwise. If no containers have been stored yet, every box fits trivially, so the answer is YES. Input The first line contains an integer nn n: the number of operations. Each of the next nn n lines contains three integers tt t, aa a, bb b describing one operation, where t∈{0,1}t \in \{0, 1\} t∈{0,1}. Output For each type 1 operation, print YES or NO on its own line, in order. Constraints 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5 1≤n≤2⋅105 1≤a,b≤1091 \le a, b \le 10^9 1≤a,b≤109 Example 1 Input: 4 0 3 3 0 5 2 1 2 4 1 2 3 Output: NO YES Explanation: Two containers are stored, 3×33 \times 3 3×3 and 5×25 \times 2 5×2. The box 2×42 \times 4 2×4 does not fit inside the 3×33 \times 3 3×3 container in either orientation, so the first query is NO. The box 2×32 \times 3 2×3 fits inside both containers, so the second query is YES. Example 2 Input: 1 1 1 1 Output: YES Explanation: No container has been stored, so the box fits trivially. Example 3 Input: 1 0 10000 10000 Output: Explanation: There are no queries, so nothing is printed.