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 Take-home Project rounds at Amazon.

What role is this question designed for?

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

Determine max remainders and anagram after deletions

Quick Overview

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.

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.

Input: ([5],)

Expected Output: 1

Explanation: Single index can claim exactly one value (e.g. 0). Max distinct = 1.

Input: ([],)

Expected Output: 0

Explanation: Empty array yields no values -> 0 distinct.

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

Expected Output: 3

Explanation: Claim 0 (from 1), 1 (from 2), the second 2 can't add a new value below 2, 2 (from 3) -> distinct {0,1,2} = 3.

Input: ([3, 3, 3, 3],)

Expected Output: 3

Explanation: Each range is [0,2]; you can claim 0,1,2 but the fourth index has no new reachable value -> 3.

Input: ([1, 1, 5],)

Expected Output: 2

Explanation: First 1 claims 0; second 1 can't reach a new value; 5 claims 1 -> {0,1} = 2.

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.

Input: ("aab", "ab")

Expected Output: True

Explanation: Delete one 'a' from s -> {a:1,b:1} = t.

Input: ("aabb", "ab")

Expected Output: False

Explanation: s is heavier on both a and b; only one letter type can be deleted in s, so you cannot fix both.

Input: ("abc", "abd")

Expected Output: True

Explanation: Delete 'c' from s and 'd' from t; both become {a:1,b:1} -> anagrams.

Input: ("", "")

Expected Output: True

Explanation: Two empty strings are trivially anagrams.

Input: ("a", "")

Expected Output: True

Explanation: Delete the single 'a' from s -> empty = t.

Input: ("ab", "cd")

Expected Output: False

Explanation: Four mismatched letters (a,b on s side; c,d on t side); only one deletion-letter per string can repair at most one per side.

Input: ("aab", "abb")

Expected Output: True

Explanation: s heavier on a, t heavier on b; delete one 'a' in s and one 'b' in t -> both {a:1,b:1}.

Input: ("xyz", "x")

Expected Output: False

Explanation: s is heavier on both y and z, but you can only delete one letter type from s.

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.

Quick Overview