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 Onsite rounds at Google.

What role is this question designed for?

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

Solve Quickselect, Tree Distance, and Prefix Substrings

Quick Overview

This multi-part question evaluates algorithmic problem-solving across selection algorithms, graph/tree traversal, and string processing, testing competencies such as Quickselect behavior and pivot reasoning, computation of node distances in a tree, and prefix-based substring counting.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given three independent coding tasks. 1. **Implement Quickselect** - Given an unsorted integer array `nums` and an integer `k`, return the `k`-th smallest element, where `k` is 1-indexed. - Duplicates may appear in the array. - Discuss different approaches, their time complexities, and how you would choose a pivot for Quickselect. - Implement one valid approach. 2. **Find the distance between two nodes in a tree** - You are given an undirected tree as a list of edges and two target nodes `u` and `v`. - Return the number of edges on the unique path between `u` and `v`. - If `u == v`, return `0`. - If either node does not exist, return `-1`. - You may assume the input edges form a valid tree unless otherwise specified. Be prepared to discuss how you would validate duplicate edges or invalid tree input. 3. **Count substrings with a given prefix** - Given a string `s` and a non-empty string `target`, count how many substrings of `s` have `target` as their prefix. - A substring `s[i:j]` is valid if its first `len(target)` characters exactly equal `target`. - Return the count as a 64-bit integer. - Follow-up: return the length of the shortest valid substring. If no valid substring exists, return `-1`.

Quick Answer: This multi-part question evaluates algorithmic problem-solving across selection algorithms, graph/tree traversal, and string processing, testing competencies such as Quickselect behavior and pivot reasoning, computation of node distances in a tree, and prefix-based substring counting.

Part 1: Implement Quickselect

Given an unsorted list of integers nums and a 1-indexed integer k, return the k-th smallest element in nums. Duplicates count as separate elements. If nums is empty or k is outside the range 1 to len(nums), return -1. A full sort would work, but this problem is intended to test selection-style thinking.

Constraints

0 <= len(nums) <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
k may be invalid in hidden tests; return -1 in that case
Duplicates may appear

Examples

Input: ([7, 10, 4, 3, 20, 15], 3)

Expected Output: 7

Explanation: The sorted order is [3, 4, 7, 10, 15, 20], so the 3rd smallest element is 7.

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

Expected Output: 3

Explanation: The sorted order is [1, 2, 2, 3, 4, 5], so the 4th smallest element is 3.

Input: ([1], 1)

Expected Output: 1

Explanation: A single-element array always returns that element for k = 1.

Input: ([], 1)

Expected Output: -1

Explanation: The array is empty, so no valid k-th smallest element exists.

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

Expected Output: 9

Explanation: The sorted order is [7, 8, 9], so the 3rd smallest element is 9.

Hints

Partition the array around a pivot like Quicksort, but only continue into the side that can contain the answer.
A 3-way partition is especially helpful when many elements are equal to the pivot.

Part 2: Find the Distance Between Two Nodes in a Tree

You are given an undirected tree as a list of edges and two target nodes u and v. Return the number of edges on the unique path between u and v. If u and v are the same, return 0 only if that node exists in the tree; otherwise return -1. If either node does not exist, return -1. You may assume the edge list describes a valid tree for normal cases.

Constraints

0 <= len(edges) <= 2 * 10^5
Each edge is a pair of distinct integers
Node labels are integers
Assume the input is a valid tree unless otherwise stated

Examples

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

Expected Output: 2

Explanation: The unique path is 2 -> 1 -> 3, which uses 2 edges.

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

Expected Output: 0

Explanation: The two targets are the same existing node, so the distance is 0.

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

Expected Output: -1

Explanation: Node 4 does not appear in the tree.

Input: ([], 1, 1)

Expected Output: -1

Explanation: With no edges, there are no known nodes in the tree.

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

Expected Output: 1

Explanation: The nodes are directly connected by one edge.

Hints

Convert the edge list into an adjacency list so you can traverse the tree efficiently.
Because all edges have equal weight, a BFS from u gives the shortest edge distance to every reachable node.

Part 3: Count Substrings With a Given Prefix

Given a string s and a non-empty string target, count how many substrings of s have target as their prefix. A substring is valid if its first len(target) characters exactly equal target. Return the total as a 64-bit integer.

Constraints

0 <= len(s) <= 2 * 10^5
1 <= len(target) <= 2 * 10^5
s and target consist of comparable characters
The answer fits in a signed 64-bit integer

Examples

Input: ('ababa', 'aba')

Expected Output: 4

Explanation: Target appears at starts 0 and 2. These contribute 3 and 1 valid substrings, for a total of 4.

Input: ('aaaa', 'aa')

Expected Output: 6

Explanation: Target appears at starts 0, 1, and 2. These contribute 3, 2, and 1 substrings.

Input: ('xyz', 'a')

Expected Output: 0

Explanation: There is no occurrence of target, so there are no valid substrings.

Input: ('', 'a')

Expected Output: 0

Explanation: An empty source string contains no substrings.

Input: ('abc', 'abc')

Expected Output: 1

Explanation: The only valid substring is the full string itself.

Hints

If target occurs starting at index i, then every substring starting at i and ending at any position from i + len(target) - 1 to the end is valid.
Use a linear-time string matching algorithm such as KMP or Z-algorithm to find all occurrences efficiently.

Part 4: Follow-up - Return the Length of the Shortest Valid Substring

Given a string s and a non-empty string target, return the length of the shortest substring of s whose prefix is exactly target. If no such substring exists, return -1.

Constraints

0 <= len(s) <= 2 * 10^5
1 <= len(target) <= 2 * 10^5
s and target consist of comparable characters

Examples

Input: ('ababa', 'aba')

Expected Output: 3

Explanation: Since target appears in s, the substring 'aba' itself is valid and has length 3.

Input: ('aaaa', 'aa')

Expected Output: 2

Explanation: The shortest valid substring is exactly 'aa'.

Input: ('xyz', 'a')

Expected Output: -1

Explanation: Target never appears, so no valid substring exists.

Input: ('', 'a')

Expected Output: -1

Explanation: An empty source string cannot contain target.

Input: ('abc', 'abc')

Expected Output: 3

Explanation: The full string matches target, so the shortest valid substring has length 3.

Hints

What is the minimum possible length of any substring whose prefix is target?
After that observation, the problem becomes checking whether target appears anywhere in s.

Quick Overview