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.

Solve jumps and anagram-similarity problems

Quick Overview

This two-part question evaluates algorithmic problem-solving skills: Task A focuses on combinatorial optimization and cost-based sequencing under quadratic jump costs, while Task B assesses string multiset reasoning and character-frequency manipulation to determine anagram similarity.

Solve jumps and anagram-similarity problems

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

You are given two independent tasks. Task A (Maximize calories over jumps): - There are n blocks with integer heights height[i] ≥ 0. - You start on the ground at height 0. You must visit every block exactly once in any order. After the first jump from the ground to some block, you may only jump between blocks; you cannot return to the ground. - The calories consumed for a jump from a location of height x to a location of height y is (x − y)^2 (the ground’s height is 0). - Choose an order of visiting the n blocks that maximizes the total calories across all n jumps (ground → first block plus the n−1 subsequent block-to-block jumps). Return the maximum total as an integer. - Example: n = 3, height = [5, 2, 5] ⇒ 43. - Describe your algorithm and analyze its time and space complexity. Task B (Password similarity under character-removal): - For each test case, you are given two lowercase strings password1 and password2. - You may remove all occurrences of at most one chosen character from password1, and independently remove all occurrences of at most one chosen character from password2. You may also choose to remove nothing from either string. - After these removals, the strings are considered similar if they are anagrams (i.e., they have identical character multisets). - For each test case, return true if the strings can be made similar under this rule, otherwise return false. - Example: password1 = "safddadfs", password2 = "famafmss" ⇒ true (remove all 'd' from password1 and all 'm' from password 2). - Describe your algorithm and analyze its time and space complexity.

Quick Answer: This two-part question evaluates algorithmic problem-solving skills: Task A focuses on combinatorial optimization and cost-based sequencing under quadratic jump costs, while Task B assesses string multiset reasoning and character-frequency manipulation to determine anagram similarity.

Maximize Calories Over Jumps

You are using a fitness tracker for a jumping workout. There are n blocks with integer heights height[i] >= 0. You start on the ground at height 0 and must jump onto every block exactly once, in any order. After the first jump from the ground onto some block, you may only jump between blocks; you cannot return to the ground. The calories consumed for a jump from a location of height x to a location of height y is (x - y)^2 (the ground's height is 0). Choose an order of visiting the n blocks that **maximizes** the total calories across all n jumps (ground -> first block, plus the n-1 subsequent block-to-block jumps). Return the maximum total as an integer. Example: height = [5, 2, 5]. A best order is ground -> 5 -> 2 -> 5, giving (0-5)^2 + (5-2)^2 + (2-5)^2 = 25 + 9 + 9 = 43. Return 43. Because the cost is a *squared* difference, the usual linear 'arrange extremes' trick for maximizing sum of absolute adjacent differences does not apply, so a Hamiltonian-path DP over subsets is used.

Constraints

0 <= n (number of blocks); n is small (the squared-cost objective makes the exact optimum NP-hard in general, so the bitmask DP targets small n typical of interviews).
height[i] >= 0 and fits in a 32-bit integer.
The ground is a fixed start at height 0 and is visited first only.
Every block must be visited exactly once; you cannot return to the ground.

Examples

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

Expected Output: 43

Explanation: Order ground->5->2->5: 25 + 9 + 9 = 43.

Input: ([],)

Expected Output: 0

Explanation: No blocks, no jumps, total 0.

Input: ([7],)

Expected Output: 49

Explanation: Only jump is ground->7: (0-7)^2 = 49.

Input: ([4, 0],)

Expected Output: 32

Explanation: ground->4->0: 16 + 16 = 32 (ground->0->4 also gives 0 + 16 = 16, so 32 is best).

Input: ([0, 8],)

Expected Output: 128

Explanation: ground->8->0... order ground->0->8 gives 0+64=64; ground->8->0 gives 64+64=128.

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

Expected Output: 187

Explanation: Optimal subset ordering found by the DP.

Input: ([0, 3, 9, 8, 9],)

Expected Output: 304

Explanation: Optimal ordering alternates extremes where the squared gain is largest.

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

Expected Output: 11

Explanation: ground->3->... best total is 11.

Hints

The cost (x - y)^2 is NOT linear in the values, so the standard 'sort and place extremes at the ends' technique for sum of |x - y| does not maximize this objective.
Model it as a Hamiltonian path that starts at a fixed node (the ground, height 0) and visits every block once. Use a bitmask DP: dp[mask][last] = best total cost having visited the blocks in 'mask' and currently standing on block 'last'.
Initialize dp[{i}][i] = (0 - height[i])^2 (the jump from the ground). Transition by jumping to an unvisited block, adding (height[last] - height[nxt])^2. Answer = max over dp[full][i].

Password Similarity Under Character Removal

You are given two lowercase strings password1 and password2. You may remove **all** occurrences of at most one chosen character from password1, and independently remove all occurrences of at most one chosen character from password2. You may also choose to remove nothing from either string. After these removals, the strings are considered *similar* if they are anagrams (i.e., they have identical character multisets). Return true if the strings can be made similar under this rule, otherwise false. Example: password1 = "safddadfs", password2 = "famafmss". Remove all 'd' from password1 -> "safafs", and all 'm' from password2 -> "faafss". Both have the multiset {a:2, f:2, s:2}, so they are anagrams. Return true.

Constraints

password1 and password2 consist of lowercase English letters (a-z); either may be empty.
You may remove all copies of at most one distinct character from each string, independently, or remove nothing.
'Similar' means the resulting strings are anagrams (equal character multisets).

Examples

Input: ('safddadfs', 'famafmss')

Expected Output: True

Explanation: Drop 'd' from p1 -> 'safafs', drop 'm' from p2 -> 'faafss'; both are {a:2,f:2,s:2}.

Input: ('', '')

Expected Output: True

Explanation: Two empty strings are anagrams already.

Input: ('a', '')

Expected Output: True

Explanation: Remove 'a' from p1 to get '' which matches the empty p2.

Input: ('ab', '')

Expected Output: False

Explanation: You can remove all of only one character from p1; 'ab' can drop 'a' OR 'b' but not both, so it can never become empty.

Input: ('abc', 'abc')

Expected Output: True

Explanation: Already anagrams; remove nothing.

Input: ('aab', 'abb')

Expected Output: False

Explanation: Counts differ on both a and b; zeroing one char on each side cannot equalize both.

Input: ('xxyy', 'zzyy')

Expected Output: True

Explanation: Drop 'x' from p1 -> 'yy', drop 'z' from p2 -> 'yy'.

Input: ('abc', 'def')

Expected Output: False

Explanation: Disjoint letters; removing one char from each still leaves mismatched multisets.

Hints

Removing 'all occurrences of one character' is the same as setting that one character's count to 0 in the frequency map. So you only ever zero out at most one entry per string.
Build frequency counts a and b for the two strings. You want to pick an optional character x to zero in a and an optional character y to zero in b so that the two count vectors become equal.
There are at most 26 choices (plus 'none') for each side, so just try every (x, y) pair and compare the two 26-length count vectors. A smarter O(A) check looks at where a and b already differ, but the brute pair-check over a fixed alphabet is already constant time.

Quick Overview

Solve jumps and anagram-similarity problems

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Maximize Calories Over Jumps

Constraints

0 <= n (number of blocks); n is small (the squared-cost objective makes the exact optimum NP-hard in general, so the bitmask DP targets small n typical of interviews).
height[i] >= 0 and fits in a 32-bit integer.
The ground is a fixed start at height 0 and is visited first only.
Every block must be visited exactly once; you cannot return to the ground.

Examples

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

Expected Output: 43

Explanation: Order ground->5->2->5: 25 + 9 + 9 = 43.

Input: ([],)

Expected Output: 0

Explanation: No blocks, no jumps, total 0.

Input: ([7],)

Expected Output: 49

Explanation: Only jump is ground->7: (0-7)^2 = 49.

Input: ([4, 0],)

Expected Output: 32

Explanation: ground->4->0: 16 + 16 = 32 (ground->0->4 also gives 0 + 16 = 16, so 32 is best).

Input: ([0, 8],)

Expected Output: 128

Explanation: ground->8->0... order ground->0->8 gives 0+64=64; ground->8->0 gives 64+64=128.

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

Expected Output: 187

Explanation: Optimal subset ordering found by the DP.

Input: ([0, 3, 9, 8, 9],)

Expected Output: 304

Explanation: Optimal ordering alternates extremes where the squared gain is largest.

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

Expected Output: 11

Explanation: ground->3->... best total is 11.

Hints

The cost (x - y)^2 is NOT linear in the values, so the standard 'sort and place extremes at the ends' technique for sum of |x - y| does not maximize this objective.
Model it as a Hamiltonian path that starts at a fixed node (the ground, height 0) and visits every block once. Use a bitmask DP: dp[mask][last] = best total cost having visited the blocks in 'mask' and currently standing on block 'last'.
Initialize dp[{i}][i] = (0 - height[i])^2 (the jump from the ground). Transition by jumping to an unvisited block, adding (height[last] - height[nxt])^2. Answer = max over dp[full][i].

Password Similarity Under Character Removal

Constraints

password1 and password2 consist of lowercase English letters (a-z); either may be empty.
You may remove all copies of at most one distinct character from each string, independently, or remove nothing.
'Similar' means the resulting strings are anagrams (equal character multisets).

Examples

Input: ('safddadfs', 'famafmss')

Expected Output: True

Explanation: Drop 'd' from p1 -> 'safafs', drop 'm' from p2 -> 'faafss'; both are {a:2,f:2,s:2}.

Input: ('', '')

Expected Output: True

Explanation: Two empty strings are anagrams already.

Input: ('a', '')

Expected Output: True

Explanation: Remove 'a' from p1 to get '' which matches the empty p2.

Input: ('ab', '')

Expected Output: False

Explanation: You can remove all of only one character from p1; 'ab' can drop 'a' OR 'b' but not both, so it can never become empty.

Input: ('abc', 'abc')

Expected Output: True

Explanation: Already anagrams; remove nothing.

Input: ('aab', 'abb')

Expected Output: False

Explanation: Counts differ on both a and b; zeroing one char on each side cannot equalize both.

Input: ('xxyy', 'zzyy')

Expected Output: True

Explanation: Drop 'x' from p1 -> 'yy', drop 'z' from p2 -> 'yy'.

Input: ('abc', 'def')

Expected Output: False

Explanation: Disjoint letters; removing one char from each still leaves mismatched multisets.

Hints

Removing 'all occurrences of one character' is the same as setting that one character's count to 0 in the frequency map. So you only ever zero out at most one entry per string.
Build frequency counts a and b for the two strings. You want to pick an optional character x to zero in a and an optional character y to zero in b so that the two count vectors become equal.
There are at most 26 choices (plus 'none') for each side, so just try every (x, y) pair and compare the two 26-length count vectors. A smarter O(A) check looks at where a and b already differ, but the brute pair-check over a fixed alphabet is already constant time.