Katkat
Back

Implement merge sort and largest 1-rectangle

Two SigmaData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

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.

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 1s.

Assume standard input sizes and focus on correctness and efficiency.