How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Solve frequency sort and all-pairs sum

Quick Overview

Solve frequency sort and all-pairs sum evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Task 1 — Frequency-based string reorder: Given a string s containing ASCII characters, return a new string whose characters are ordered by decreasing frequency; when two characters share the same frequency, order them by ascending character code. Describe your chosen data structures and provide time and space complexity. Task 2 — All unique two-sum pairs in sorted array: Given a nondecreasing sorted integer array nums and an integer target, return all unique index pairs (i, j) with i < j such that nums[i] + nums[j] == target. Avoid duplicate pairs when values repeat. Achieve O(n) time and O( 1) extra space (excluding the output) using a two-pointer method. Explain your deduplication strategy and analyze complexity.

Quick Answer: Solve frequency sort and all-pairs sum evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Frequency-Based String Reorder

Given a string `s` containing ASCII characters, return a new string whose characters are ordered by **decreasing frequency**. When two characters share the same frequency, order them by **ascending character code** (i.e., ASCII value). Each character must appear in the output exactly as many times as it appears in the input. This is the classic "sort characters by frequency" problem (LeetCode 451) with a deterministic tie-break: equal-frequency characters are emitted in ascending ASCII order. **Example 1** ``` Input: s = "tree" Output: "eert" ``` Explanation: 'e' appears twice, 'r' and 't' once each. 'e' (freq 2) comes first; 'r' and 't' tie at freq 1, so they are ordered by ascending char code: 'r' (114) then 't' (116). **Example 2** ``` Input: s = "Aabb" Output: "bbAa" ``` Explanation: 'b' has freq 2 → first. 'A' (65) and 'a' (97) tie at freq 1; ascending char code puts 'A' before 'a'. Describe your chosen data structures and provide the time and space complexity.

Constraints

0 <= len(s) <= 10^5
s consists of printable ASCII characters
Equal-frequency characters MUST be emitted in ascending ASCII order
Each character appears in the output exactly as many times as in the input

Examples

Input: ('tree',)

Expected Output: 'eert'

Explanation: 'e' freq 2 first; 'r'(114) and 't'(116) tie at 1 → ascending char code.

Input: ('cccaaa',)

Expected Output: 'aaaccc'

Explanation: 'a'(97) and 'c'(99) both freq 3 → tie broken by ascending char code, 'a' before 'c'.

Input: ('Aabb',)

Expected Output: 'bbAa'

Explanation: 'b' freq 2 first; 'A'(65) before 'a'(97) on the freq-1 tie.

Input: ('',)

Expected Output: ''

Explanation: Empty input → empty output (edge case).

Input: ('a',)

Expected Output: 'a'

Explanation: Single character (edge case).

Input: ('aabbcc',)

Expected Output: 'aabbcc'

Explanation: All three characters tie at freq 2 → emitted in ascending char-code order a,b,c.

Hints

Count each character's frequency with a hash map (or a fixed-size array of length 256 indexed by char code).
Sort the distinct characters by the key (-frequency, char_code): negative frequency gives descending frequency, char_code gives the ascending-ASCII tie-break.
Reconstruct the answer by repeating each character by its count in sorted order.

All Unique Two-Sum Pairs in a Sorted Array

Given a **nondecreasing** sorted integer array `nums` and an integer `target`, return all **unique** pairs of values `[nums[i], nums[j]]` with `i < j` such that `nums[i] + nums[j] == target`. Avoid duplicate pairs when values repeat (e.g., if `nums` contains several equal values, each distinct value-pair should appear at most once). Return the pairs ordered by their left value ascending (which the two-pointer scan produces naturally). Achieve **O(n)** time and **O(1)** extra space (excluding the output) using a two-pointer method. This generalizes the classic "Two Sum II — sorted input" (LeetCode 167): instead of stopping at the first matching pair, collect every distinct value-pair. **Example 1** ``` Input: nums = [1, 2, 3, 4, 4, 9, 56, 90], target = 8 Output: [[4, 4]] ``` Explanation: 4 + 4 = 8 is the only pair. Even though 4 appears twice, the value-pair [4,4] is reported once. **Example 2** ``` Input: nums = [1, 1, 2, 2, 3, 3], target = 4 Output: [[1, 3], [2, 2]] ``` Explanation: 1+3 and 2+2 both equal 4; duplicates of 1 and 3 are skipped so [1,3] appears once. Explain your deduplication strategy and analyze complexity.

Constraints

0 <= len(nums) <= 10^5
nums is sorted in nondecreasing order
-10^9 <= nums[i], target <= 10^9
Report each distinct value-pair at most once (dedup on repeated values)
Required: O(n) time, O(1) extra space (excluding output), two-pointer method

Examples

Input: ([1, 2, 3, 4, 4, 9, 56, 90], 8)

Expected Output: [[4, 4]]

Explanation: 4+4=8; the duplicate 4 is skipped so [4,4] is reported once.

Input: ([2, 7, 11, 15], 9)

Expected Output: [[2, 7]]

Explanation: Classic single pair, 2+7=9.

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

Expected Output: [[1, 3], [2, 2]]

Explanation: 1+3 and 2+2 both equal 4; repeated 1/2/3 skipped to avoid duplicate pairs.

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

Expected Output: []

Explanation: No pair sums to 100 (no-solution edge case).

Input: ([], 5)

Expected Output: []

Explanation: Empty array (edge case).

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

Expected Output: [[-3, 6], [-1, 4]]

Explanation: -3+6=3 and -1+4=3; two distinct pairs with negatives.

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

Expected Output: [[0, 0]]

Explanation: All zeros; the single value-pair [0,0] is reported once, not C(4,2) times.

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

Expected Output: [[-3, -1]]

Explanation: -3 + -1 = -4 (negatives, single pair).

Hints

Place one pointer at the start and one at the end. If the sum is too small, advance the left pointer; if too large, retreat the right pointer.
When you find a match, record the value-pair, then skip over ALL further equal values on both sides before continuing — this is the deduplication step.
Because the array is sorted, equal values are contiguous, so skipping them with while-loops keeps the scan O(n) overall and prevents duplicate pairs.

Quick Overview