Determine max remainders and anagram after deletions
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Part 1 (Array Remainders): Given an integer array A of length n with A[i] > 0. You may choose any integer array B of length n. Define C[i] = B[i] mod A[i] for 0 ≤ i < n. What is the maximum possible number of distinct values in C? Describe an efficient algorithm to compute this maximum for a given A and provide time/space complexities. Part 2 (String Similarity by Deleting One Letter Type): Given two lowercase strings s and t. In each string, you may select one letter (possibly a different letter in each string) and delete any number of occurrences of that letter (including zero). After these deletions, can s and t become anagrams (i.e., have identical letter-frequency vectors)? Design an algorithm to decide this and analyze its complexity.
Quick Answer: In the Coding & Algorithms domain, this two-part question evaluates modular arithmetic and combinatorial reasoning for maximizing distinct array remainders and frequency-vector manipulation for determining anagram feasibility after selective character deletions, while also testing algorithm design and time/space complexity analysis.
Maximum Distinct Remainders
Given an integer array A of length n where every A[i] > 0, you may choose any integer array B of length n (each B[i] can be any integer). Define C[i] = B[i] mod A[i] for 0 <= i < n. Return the maximum possible number of distinct values in C.
Key insight: because B[i] is unconstrained, C[i] = B[i] mod A[i] can be made equal to any value in the range [0, A[i] - 1]. So each index i lets you 'claim' exactly one value from {0, 1, ..., A[i]-1}, and you want to maximize how many distinct values you can claim across all indices.
Greedy strategy: sort A ascending and walk through it, keeping a counter cur starting at 0. For each a in the sorted array, if cur < a then the value cur is reachable by this index, so claim it and increment cur. The final value of cur is the answer.
Constraints
- 0 <= n
- A[i] > 0 for all i
- B[i] may be any integer, so C[i] can be any value in [0, A[i]-1]
Examples
Input: ([2, 7, 11, 15],)
Expected Output: 4
Explanation: Sorted [2,7,11,15]: claim 0 (from 2), 1 (from 7), 2 (from 11), 3 (from 15) -> 4 distinct values.
Input: ([1, 1, 1],)
Expected Output: 1
Explanation: Each A[i]=1 forces C[i] in [0,0], so only value 0 is ever possible -> 1 distinct value.
Hints
- Since B[i] is free, C[i] = B[i] mod A[i] can equal any value in [0, A[i]-1]. Reframe: each index lets you pick one value from a range starting at 0.
- To maximize distinct picks, process the smaller ranges first so they grab the small values they alone can reach, leaving larger ranges for larger values.
- Sort A ascending; keep a counter cur=0; for each a, if cur < a claim value cur and increment cur. The answer is cur.
Anagram After Deleting One Letter Type From Each String
Given two lowercase strings s and t. In s you may pick exactly one letter type x and delete any number of its occurrences (including zero). Independently, in t you may pick exactly one letter type y (possibly different from x) and delete any number of its occurrences (including zero). After these deletions, can s and t become anagrams, i.e. have identical letter-frequency vectors over all 26 letters?
Return true if it is possible, false otherwise.
Approach: A robust reference checks all 26x26 choices of (x in s, y in t). For a fixed (x, y), each letter c must reconcile: s's count of c can be reduced to anything in [0, count_s[c]] only when c == x (otherwise it is fixed at count_s[c]); likewise t's count of c is adjustable only when c == y. The two achievable ranges for letter c must overlap for every letter. If some (x, y) makes all 26 ranges overlap, the answer is true.
An O(26) characterization also works: let d[c] = count_s[c] - count_t[c]. Letters with d[c] != 0 must be 'fixed' by deleting from the heavier side; a positive d[c] (s heavier) must be fixed by choosing x = c (delete in s), a negative d[c] (t heavier) by choosing y = c (delete in t). You have at most one x and one y, so at most one positive-diff letter and one negative-diff letter can be repaired.
Constraints
- s and t contain only lowercase English letters
- You delete from at most one letter type in each string
- Deleting zero occurrences is allowed, so 'no deletion' is always an option
Examples
Input: ("a", "a")
Expected Output: True
Explanation: Already anagrams; delete zero of any letter.
Input: ("abc", "abc")
Expected Output: True
Explanation: Already identical frequency vectors.
Hints
- Deleting any number of one chosen letter only lets you DECREASE that single letter's count in each string; you can never increase a count.
- Compare frequency vectors. Any letter where s and t already differ must be repaired by deleting from whichever side is heavier.
- You get one deletion-letter in s and one in t. So you can repair at most one letter where s is heavier (delete in s) and at most one letter where t is heavier (delete in t). All other letters must already match.