How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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 jump maximization and palindromic path queries

Q: Solve jump maximization and palindromic path queries

This pair of problems evaluates algorithmic problem-solving skills: the first assesses array-based path optimization and stateful score maximization under constrained jumps, while the second assesses tree traversal combined with character-frequency parity checks for ancestor-path palindromic queries.

You are given two independent algorithmic problems.

Problem 1 — Jump game with special destinations (maximize score)

You are given an integer array arr of length n (0-indexed). You start at index 0 and must end exactly at index n-1.

Your score is the sum of arr[i] over all visited indices (including start and end).
From an index i , you may jump to:
1. i + 1 (if i + 1 < n ), or
2. any index j such that j > i and j is a positive integer whose ones digit is 3 (i.e., j ∈ {3, 13, 23, 33, ...} ) and j < n .

It is guaranteed that n-1 is reachable.

Task: Return the maximum possible score achievable.

Input: int[] arr

Output: long (or int if you can prove no overflow)

Problem 2 — Count ancestor endpoints forming a palindrome (tree queries)

You are given a rooted tree with root node 0.

treeNodes : number of nodes N (nodes are 0..N-1 )
nodes : char[] of length N , where nodes[i] is the lowercase letter ( 'a'..'z' ) stored on node i
nodeFrom , nodeTo : integer arrays of length N-1 describing directed edges nodeFrom[k] -> nodeTo[k] (parent to child). This forms a valid tree.
queries : integer array of query nodes.

For each query node u = queries[t], consider the unique path from u up to the root 0.

For every endpoint v on this path (where v is an ancestor of u, including u itself), form the multiset/string of characters on the nodes along the path from u to v (inclusive). The characters may be rearranged arbitrarily.

A path u -> ... -> v is counted if its characters can be rearranged into a palindrome (equivalently: at most one character has an odd frequency).

Task: For each query node u, return the number of ancestors v (including u) such that the path from u to v can be rearranged into a palindrome.

Output: int[] res where res[t] answers queries[t].

Example

N = 4
nodes = [ 'z', 'a', 'a', 'a' ]
nodeFrom = [0, 0, 1]
nodeTo   = [1, 2, 3]
queries = [3]

Tree edges: 0->1, 0->2, 1->3. Query u=3 has path to root: 3(a) -> 1(a) -> 0(z). Valid endpoints:

v=3 : "a" (palindrome)
v=1 : "aa" (palindrome)
v=0 : "aaz" can be rearranged to "aza" (palindrome) So the output is [3] .

Constraints (assume typical OA scale)

You should design an algorithm that is efficient for large n/N/|queries| (e.g., up to 10^5 or more).

You are given two independent algorithmic problems.

Problem 1 — Jump game with special destinations (maximize score)

You are given an integer array arr of length n (0-indexed). You start at index 0 and must end exactly at index n-1.

Your score is the sum of arr[i] over all visited indices (including start and end).
From an index i , you may jump to:
1. i + 1 (if i + 1 < n ), or
2. any index j such that j > i and j is a positive integer whose ones digit is 3 (i.e., j ∈ {3, 13, 23, 33, ...} ) and j < n .

It is guaranteed that n-1 is reachable.

Task: Return the maximum possible score achievable.

Input: int[] arr

Output: long (or int if you can prove no overflow)

Problem 2 — Count ancestor endpoints forming a palindrome (tree queries)

You are given a rooted tree with root node 0.

treeNodes : number of nodes N (nodes are 0..N-1 )
nodes : char[] of length N , where nodes[i] is the lowercase letter ( 'a'..'z' ) stored on node i
nodeFrom , nodeTo : integer arrays of length N-1 describing directed edges nodeFrom[k] -> nodeTo[k] (parent to child). This forms a valid tree.
queries : integer array of query nodes.

For each query node u = queries[t], consider the unique path from u up to the root 0.

A path u -> ... -> v is counted if its characters can be rearranged into a palindrome (equivalently: at most one character has an odd frequency).

Task: For each query node u, return the number of ancestors v (including u) such that the path from u to v can be rearranged into a palindrome.

Output: int[] res where res[t] answers queries[t].

Example

N = 4
nodes = [ 'z', 'a', 'a', 'a' ]
nodeFrom = [0, 0, 1]
nodeTo   = [1, 2, 3]
queries = [3]

Tree edges: 0->1, 0->2, 1->3. Query u=3 has path to root: 3(a) -> 1(a) -> 0(z). Valid endpoints:

v=3 : "a" (palindrome)
v=1 : "aa" (palindrome)
v=0 : "aaz" can be rearranged to "aza" (palindrome) So the output is [3] .

Constraints (assume typical OA scale)

You should design an algorithm that is efficient for large n/N/|queries| (e.g., up to 10^5 or more).

Solve jump maximization and palindromic path queries

Quick Overview

Problem 1 — Jump game with special destinations (maximize score)

Problem 2 — Count ancestor endpoints forming a palindrome (tree queries)

Example

Constraints (assume typical OA scale)

Submit Your Answer

Solve jump maximization and palindromic path queries

Quick Overview

Problem 1 — Jump game with special destinations (maximize score)

Problem 2 — Count ancestor endpoints forming a palindrome (tree queries)

Example

Constraints (assume typical OA scale)

Submit Your Answer