Katkat
Back

Solve Adjacent-Deletion and Sorted-Square Problems

WhatnotSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates skills in string manipulation and pattern-removal algorithms for adjacent duplicates and k-sized group deletions, as well as array processing and merging techniques for producing sorted squares; it tests understanding of relevant data-structure concepts and merging/two-pointer strategies within the Coding & Algorithms domain. It is commonly asked to assess algorithmic efficiency, correctness under large input constraints and tricky edge cases (such as cascading deletions and negative values), and is primarily a practical implementation task that emphasizes complexity analysis over purely theoretical reasoning.

Solve the following coding problems. Discuss the approach and complexity before implementation.

Problem 1: Remove adjacent duplicate pairs

Given a string s, repeatedly remove any pair of adjacent equal characters until no such pair remains. Return the final string.

The deletion of one pair can cause new adjacent pairs to form.

Example:

  • Input: s = "abbaca"
  • Output: "ca"

Constraints:

  • 0 <= s.length <= 200000
  • s contains lowercase English letters.

Follow-up 1: Remove adjacent groups of size k

Given a string s and an integer k, repeatedly remove a contiguous group of k equal characters whenever such a group is formed. Return the final string.

Example:

  • Input: s = "deeedbbcccbdaa", k = 3
  • Output: "aa"

Constraints:

  • 1 <= s.length <= 200000
  • 2 <= k <= 100000
  • s contains lowercase English letters.

Problem 2: Merge sorted arrays into sorted squares

You are given two integer arrays a and b, each sorted in nondecreasing order. In the base version, all values are nonnegative. Return a single sorted array containing the square of every value from both arrays.

Example:

  • Input: a = [1, 3, 5], b = [2, 4]
  • Output: [1, 4, 9, 16, 25]

Constraints:

  • 0 <= a.length, b.length <= 200000
  • The result should be sorted in nondecreasing order.
  • Aim for linear time in the total input size.

Follow-up 2: Inputs may contain negative numbers

Now a and b are still sorted in nondecreasing order, but either array may contain negative numbers. Return the sorted squares of all values from both arrays.

Example:

  • Input: a = [-4, -1, 3], b = [-2, 0, 5]
  • Output: [0, 1, 4, 9, 16, 25]