Katkat
Back

Implement string/matrix simulations and counting pairs

Capital OneMachine Learning Engineer · Online Assessment
MediumMachine Learning EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests string manipulation, simulation of grid-based gravitational collapse, and efficient combinatorial counting of string combinations.

Part 1: String Search

Given a string text and a pattern, return the starting indices of all occurrences of pattern in text, ignoring case.

Part 2: Grid Gravity Simulation

Given a 2D character grid, implement a function that processes a single 'collapse'.

  1. Identify all 2x2 squares where all characters are identical (e.g., all 'A').
  2. Mark these squares for removal.
  3. Remove the marked characters and apply 'gravity': all characters above an empty space drop down to fill the gap.

Part 3: Combinatorial Counting

Given a list of strings words and an integer k, count the number of ordered pairs (i, j) such that i != j and the concatenation words[i] + words[j] has a length exactly equal to k.

Constraints

  • text length <= 10^5, pattern length wait, "abc" is length 3,

so ("abc", "") is valid if empty strings are allowed.

Output: 2 (("de", "f"), ("f", "de"))


### Function Signatures
```python
def find_substrings(text: str, pattern: str) -> list[int]: ...
def apply_gravity(grid: list[list[str]]) -> list[list[str]]: ...
def count_k_concatenations(words: list[str], k: int) -> int: ...

Hints

Hint 1

For string searching, normalize both strings to lowercase and use a standard rolling hash or sliding window approach.

Hint 2

For grid gravity, use a set to track cells to be cleared, then iterate column-wise from bottom to top, 'shifting' characters down whenever an empty space is encountered.

Hint 3

For counting pairs, group words by length in a hash map to achieve O(N) complexity rather than O(N^2) checking all pairs.

Follow-up questions

  • How would you optimize the grid simulation if the grid size were 10,000x10,000?
  • If the strings contain Unicode characters, how does your case-insensitive matching change?
  • Can you modify the concatenation count to handle cases where the total length must be >= k?