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 hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

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

Solve two online assessment problems

Quick Overview

This two-part prompt evaluates algorithmic problem-solving skills: the first problem tests optimization under index-based movement and number-theoretic constraints (prime indices ending with digit 3), while the second assesses tree traversal and multiset/path frequency reasoning for palindrome-anagram checks on rootward paths.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

An online assessment contained two coding problems: 1. **Maximize skipped positions** You are given an array of length `n` indexed from `0` to `n - 1`. Start at index `0` and reach index `n - 1`. At any index `i`, you may: - move to `i + 1`, if it exists; or - jump to any index `j > i` such that `j` is a prime number and the decimal representation of `j` ends with `3`. If you jump from `i` to `j`, you gain `j - i - 1` points, equal to the number of positions skipped. Moving one step to the right gives `0` points. Compute the maximum total score achievable when you reach the last index. 2. **Count palindromic-anagram ancestors in a rooted tree** An undirected tree with `tree_nodes` nodes is rooted at node `0`. The nodes are numbered from `0` to `tree_nodes - 1`. Each node `i` stores a lowercase character `arr[i]`. You are also given an array `queries` of length `m`. For each query node `q = queries[i]`, consider every node `v` on the path from `q` to the root, including `q` itself. Count how many such nodes `v` have the property that the characters on the path from `q` up to `v` can be rearranged to form a palindrome. Return an integer array of length `m`, where the `i`-th value is the answer for `queries[i]`. Example: - `tree_nodes = 4` - `arr = ['z', 'a', 'a', 'a']` - edges: `(0, 1)`, `(0, 2)`, `(1, 3)` - `queries = [3]` Output: `[3]` Explanation: For query node `3`, the path segments ending at nodes `3`, `1`, and `0` all have character counts that can be rearranged into a palindrome.

Quick Answer: This two-part prompt evaluates algorithmic problem-solving skills: the first problem tests optimization under index-based movement and number-theoretic constraints (prime indices ending with digit 3), while the second assesses tree traversal and multiset/path frequency reasoning for palindrome-anagram checks on rootward paths.

Part 1: Maximize Skipped Positions

You stand at index 0 of an array of length n and want to reach index n - 1. From index i, you may either move to i + 1 (if it exists) or jump to any index j > i such that j is prime and its decimal representation ends with 3. A jump from i to j earns j - i - 1 points, equal to the number of skipped positions. Moving one step earns 0 points. Compute the maximum total score possible by the time you reach index n - 1. The array values themselves do not matter, so the function receives only n.

Constraints

1 <= n <= 10^6
Indices are 0-based: 0 to n - 1
A jump destination must be prime and must end with digit 3

Examples

Input: (1,)

Expected Output: 0

Explanation: You start at the last index already, so no movement is needed.

Input: (3,)

Expected Output: 0

Explanation: The only indices after 0 are 1 and 2; neither is a prime ending in 3.

Input: (4,)

Expected Output: 2

Explanation: Index 3 is prime and ends with 3, so jump directly from 0 to 3 and skip indices 1 and 2.

Input: (20,)

Expected Output: 12

Explanation: Valid jump destinations below 20 are 3 and 13. Jumping directly from 0 to 13 gives 12 points, which is optimal.

Input: (44,)

Expected Output: 42

Explanation: Index 43 is prime and ends with 3. Jump from 0 to 43 for 42 points, then you are already at the last index.

Hints

If you write the total score for several jumps in a row, most terms cancel out.
Because you can jump to any valid later index directly, ask whether making extra jumps can ever improve the score.

Part 2: Count Palindromic-Anagram Ancestors in a Rooted Tree

You are given an undirected tree with tree_nodes nodes, rooted at node 0. Node i stores a lowercase character arr[i]. For each query node q, consider every node v on the path from q up to the root, including q itself. For each such v, look at the characters on the path segment from q up to v, inclusive. Count how many of those path segments can be rearranged to form a palindrome. Return an array of answers in the same order as queries. A multiset of characters can be rearranged into a palindrome if at most one character has odd frequency.

Constraints

1 <= tree_nodes <= 2 * 10^5
0 <= len(queries) <= 2 * 10^5
arr[i] is a lowercase English letter
edges forms a valid tree rooted at node 0

Examples

Input: (1, ['a'], [], [0])

Expected Output: [1]

Explanation: The only path segment is ['a'], which is already a palindrome.

Input: (4, ['z', 'a', 'a', 'a'], [(0, 1), (0, 2), (1, 3)], [3])

Expected Output: [3]

Explanation: For query node 3, the segments 3->3, 3->1, and 3->0 all have at most one odd character count.

Input: (3, ['a', 'b', 'a'], [(0, 1), (1, 2)], [2, 1, 0])

Expected Output: [2, 1, 1]

Explanation: For node 2, segments 'a' and 'aba' work. For node 1, only 'b' works. For node 0, only 'a' works.

Input: (5, ['a', 'b', 'b', 'a', 'c'], [(0, 1), (0, 2), (1, 3), (1, 4)], [3, 4, 2])

Expected Output: [2, 1, 1]

Explanation: Query 3 has valid segments 'a' and 'aba'. Query 4 has only 'c'. Query 2 has only 'b'.

Input: (4, ['a', 'a', 'b', 'b'], [(0, 1), (1, 2), (2, 3)], [3, 3])

Expected Output: [4, 4]

Explanation: All four ancestor segments for node 3 can be rearranged into palindromes, and the query is repeated.

Hints

A string can be permuted into a palindrome iff at most one character count is odd. Represent odd/even counts with a 26-bit mask.
During a DFS from the root, maintain counts of prefix masks along the current root-to-node path so each query can be answered from the current path state.

Quick Overview