Sort and merge string lists by length
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given two unsorted lists of strings, return a single list sorted by ascending string length. Specify your tie-breaking rule for equal-length strings (e.g., preserve original relative order for stability). Analyze time and space complexity and whether your sort is stable. Follow-up: If each input list is already individually sorted by length with the same tie-breaker, design and implement an efficient merge to produce a globally length-sorted list. Discuss in-place versus extra-memory approaches and their complexities.
Quick Answer: This question evaluates understanding of sorting algorithms, stability, merging strategies, and time/space complexity analysis when ordering strings by length, and is categorized under Coding & Algorithms.
Return all strings sorted by ascending length. Ties preserve original relative order, treating list1 followed by list2 as the original order. If already_sorted=True, assume each input is already length-sorted with the same tie rule and merge them linearly.
Constraints
- Input strings may have equal lengths
- When already_sorted=True both lists are individually sorted by length
Examples
Input: (['pear', 'a', 'plum'], ['bb', 'apple'], False)
Expected Output: ['a', 'bb', 'pear', 'plum', 'apple']
Input: (['a', 'bb', 'cccc'], ['d', 'eee'], True)
Expected Output: ['a', 'd', 'bb', 'eee', 'cccc']
Hints
- Stable sorting solves the unsorted case.
- The follow-up is the merge step from merge sort.