Implement merge sort and largest 1-rectangle
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
The coding round included two algorithm questions:
1. Implement merge sort for an array of integers. Return the sorted array and explain its time and space complexity.
2. Given an `m x n` binary matrix containing only `0` and `1`, find the area of the largest rectangular submatrix consisting entirely of `1`s.
Assume standard input sizes and focus on correctness and efficiency.
Quick Answer: This question evaluates proficiency in implementing and analyzing classic algorithms, specifically merge sort for array sorting and techniques for computing the largest all-ones rectangular submatrix in a binary matrix, testing algorithmic thinking, data structure manipulation, and time/space complexity reasoning.