Quick Overview

This question evaluates a candidate's understanding of frequency counting, custom sorting with lexicographic tie-breaking, string manipulation, and time/space complexity analysis. It is commonly asked in the Coding & Algorithms domain to assess practical algorithmic implementation and efficiency trade-offs, and it primarily tests practical application rather than purely conceptual understanding.

Sort characters by frequency

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an ASCII string s, reorder its characters in decreasing order of frequency. If multiple characters share the same frequency, break ties by ascending lexicographic order. Return the resulting string. Analyze time and space complexity and provide code.

Quick Answer: This question evaluates a candidate's understanding of frequency counting, custom sorting with lexicographic tie-breaking, string manipulation, and time/space complexity analysis. It is commonly asked in the Coding & Algorithms domain to assess practical algorithmic implementation and efficiency trade-offs, and it primarily tests practical application rather than purely conceptual understanding.

Given an ASCII string `s`, reorder its characters in decreasing order of frequency. If multiple characters share the same frequency, break ties by ascending lexicographic (ASCII) order. Return the resulting string. For example, given `"tree"`, the character `'e'` appears twice and `'r'`, `'t'` appear once each, so the result is `"eert"` ('r' before 't' because 'r' < 't'). Note: tie-breaking is by ASCII value, so uppercase letters (A-Z, 65-90) sort before lowercase letters (a-z, 97-122), and digits (48-57) sort before letters.

Constraints

  • 0 <= len(s) <= 10^5
  • s consists of ASCII characters (codes 0-127)
  • Tie-breaking is by ascending ASCII value, so 'A' (65) sorts before 'a' (97)

Examples

Input: ('tree',)

Expected Output: 'eert'

Explanation: 'e' appears twice (most frequent), then 'r' and 't' each appear once; 'r' < 't' so 'r' comes first.

Input: ('cccaaa',)

Expected Output: 'aaaccc'

Explanation: 'a' and 'c' both appear 3 times; tie broken by ascending order so 'a' (the smaller char) comes first.

Hints

  1. Count the frequency of every character first using a hash map or a fixed-size array of length 128.
  2. Sort the distinct characters by a compound key: primary key is frequency descending, secondary key is the character itself ascending.
  3. Build the result by repeating each character by its count, in the sorted order.

Loading coding console...