PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

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.

  • easy
  • Whatnot
  • Coding & Algorithms
  • Software Engineer

Solve Adjacent-Deletion and Sorted-Square Problems

Company: Whatnot

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

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]`

Quick Answer: 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.

Part 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. Removing one pair may create a new adjacent pair, so the process must continue until the string is stable.

Constraints

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

Examples

Input: "abbaca"

Expected Output: "ca"

Explanation: Remove `bb` to get `aaca`, then remove `aa` to get `ca`.

Input: "azxxzy"

Expected Output: "ay"

Explanation: Removing `xx` creates `azzy`, then removing `zz` leaves `ay`.

Input: ""

Expected Output: ""

Explanation: Edge case: an empty string stays empty.

Input: "aaaa"

Expected Output: ""

Explanation: Remove the first `aa`, then the remaining `aa`.

Hints

  1. Try processing the string from left to right while keeping the characters that have not been canceled yet.
  2. If the current character matches the most recent kept character, both should disappear.

Part 2: Remove Adjacent Groups of Size k

Given a string `s` and an integer `k`, repeatedly remove any contiguous group of exactly `k` equal characters whenever such a group is formed. Return the final string after no more deletions are possible. A deletion can cause new removable groups to appear across the gap.

Constraints

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

Examples

Input: ("deeedbbcccbdaa", 3)

Expected Output: "aa"

Explanation: Delete `eee`, then `ccc`, then `bbb`, then `ddd`, leaving `aa`.

Input: ("pbbcggttciiippooaais", 2)

Expected Output: "ps"

Explanation: Repeated deletions of adjacent pairs eventually reduce the string to `ps`.

Input: ("abcd", 2)

Expected Output: "abcd"

Explanation: No adjacent group of size 2 is ever formed.

Input: ("aaa", 3)

Expected Output: ""

Explanation: The whole string is one removable group.

Input: ("a", 2)

Expected Output: "a"

Explanation: Edge case: a single character cannot form a group of size 2.

Hints

  1. Instead of storing every character separately, track each run as `(character, current_count)`.
  2. When a run reaches size `k`, remove it immediately so earlier runs can potentially connect.

Part 3: Merge Sorted Arrays into Sorted Squares (Nonnegative Inputs)

You are given two integer arrays `a` and `b`, each sorted in nondecreasing order. In this version, all values are nonnegative. Return one sorted array containing the square of every value from both arrays. Your algorithm should aim for linear time in the total number of elements.

Constraints

  • 0 <= a.length, b.length <= 200000
  • Each array is sorted in nondecreasing order
  • All values in `a` and `b` are nonnegative
  • The result must be sorted in nondecreasing order

Examples

Input: ([1, 3, 5], [2, 4])

Expected Output: [1, 4, 9, 16, 25]

Explanation: Square each array and merge the results.

Input: ([], [])

Expected Output: []

Explanation: Edge case: both arrays are empty.

Input: ([], [0, 2, 2])

Expected Output: [0, 4, 4]

Explanation: Only the second array contributes values.

Input: ([0, 1, 2], [3])

Expected Output: [0, 1, 4, 9]

Explanation: All squared values remain in sorted order after merging.

Hints

  1. Because all numbers are nonnegative, squaring does not change the order inside each array.
  2. Think of this as merging two already sorted arrays, except the values you compare are squares.

Part 4: Merge Sorted Arrays into Sorted Squares (Negative Numbers Allowed)

You are given two integer arrays `a` and `b`, each sorted in nondecreasing order. Unlike the base version, values may now be negative. Return one sorted array containing the square of every value from both arrays. Your algorithm should aim for linear time in the total number of elements.

Constraints

  • 0 <= a.length, b.length <= 200000
  • Each array is sorted in nondecreasing order
  • Values may be negative, zero, or positive
  • The result must be sorted in nondecreasing order

Examples

Input: ([-4, -1, 3], [-2, 0, 5])

Expected Output: [0, 1, 4, 9, 16, 25]

Explanation: After squaring and sorting, the merged result is `[0, 1, 4, 9, 16, 25]`.

Input: ([-7, -3, -1], [])

Expected Output: [1, 9, 49]

Explanation: Edge case: only one array is non-empty, and all values are negative.

Input: ([-2, -2, 0], [1, 2])

Expected Output: [0, 1, 4, 4, 4]

Explanation: Duplicates and zero must be handled correctly.

Input: ([], [])

Expected Output: []

Explanation: Edge case: both arrays are empty.

Input: ([-1], [0])

Expected Output: [0, 1]

Explanation: Single-element arrays still need correct ordering after squaring.

Hints

  1. Within a single sorted array, the largest square comes from one of the two ends.
  2. You can first compute the sorted squares of each array in linear time, then merge the two sorted results.
Last updated: May 23, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Count User Journey Prefixes - Whatnot (easy)
  • Build a Tic-Tac-Toe App - Whatnot (medium)
  • Build User Journey Path Summary - Whatnot (hard)