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 Technical Screen 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 tree, graph, sliding-window problems

Quick Overview

This set of problems evaluates proficiency in core data structures and algorithms, specifically binary tree traversals (including zigzag/level-order patterns), directed graph cycle detection and topological ordering, and sliding-window techniques for substring analysis.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question LeetCode 103. Binary Tree Zigzag Level Order Traversal – given a binary tree root, return its zigzag level-order traversal. LeetCode 207. Course Schedule – given course prerequisites, determine if all courses can be finished by detecting cycles with topological sort. LeetCode 340. Longest Substring with At Most K Distinct Characters – given string s and integer k, return the length of the longest substring containing at most k distinct characters. https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/ https://leetcode.com/problems/course-schedule/description/ https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/

Quick Answer: This set of problems evaluates proficiency in core data structures and algorithms, specifically binary tree traversals (including zigzag/level-order patterns), directed graph cycle detection and topological ordering, and sliding-window techniques for substring analysis.

Part 1: Binary Tree Zigzag Level Order Traversal

You are given a binary tree in level-order array form, where each element is either an integer or None for a missing child. Return the zigzag level-order traversal of the tree's node values. In a zigzag traversal, the first level is read from left to right, the second from right to left, the third from left to right, and so on.

Constraints

0 <= len(root) <= 2000
Each non-None node value is an integer in the range [-10^4, 10^4]
The input list represents a valid binary tree in level-order form

Examples

Input: ([3, 9, 20, None, None, 15, 7],)

Expected Output: [[3], [20, 9], [15, 7]]

Explanation: Level 1 is read left-to-right, level 2 right-to-left, and level 3 left-to-right.

Input: ([1],)

Expected Output: [[1]]

Explanation: A single-node tree has only one level.

Input: ([],)

Expected Output: []

Explanation: An empty tree has no levels to traverse.

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

Expected Output: [[1], [3, 2], [4, 5]]

Explanation: The second level is reversed, while the first and third remain left-to-right.

Hints

A breadth-first search naturally processes the tree one level at a time.
You can collect each level left-to-right, then reverse every other level before appending it to the answer.

Part 2: Course Schedule

There are num_courses courses labeled from 0 to num_courses - 1. You are given a list of prerequisite pairs [a, b], meaning you must take course b before course a. Determine whether it is possible to finish all courses. This is equivalent to checking whether the prerequisite graph contains a cycle.

Constraints

1 <= num_courses <= 10^5
0 <= len(prerequisites) <= 2 * 10^5
Each prerequisite pair has length 2
0 <= course, prerequisite < num_courses

Examples

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

Expected Output: True

Explanation: Course 0 can be taken first, then course 1.

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

Expected Output: False

Explanation: The two courses depend on each other, forming a cycle.

Input: (1, [])

Expected Output: True

Explanation: With one course and no prerequisites, finishing is always possible.

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

Expected Output: True

Explanation: A valid order is 0, 1, 2, 3 or 0, 2, 1, 3.

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

Expected Output: False

Explanation: Courses 0 and 1 form a cycle, so not all courses can be completed.

Hints

Think of courses as nodes in a directed graph and prerequisites as directed edges.
If you repeatedly take courses with indegree 0 and cannot process all nodes, a cycle exists.

Part 3: Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Constraints

0 <= len(s) <= 2 * 10^5
0 <= k <= len(s)
s may contain any standard characters

Examples

Input: ("eceba", 2)

Expected Output: 3

Explanation: The longest valid substring is 'ece', which has length 3.

Input: ("aa", 1)

Expected Output: 2

Explanation: The whole string contains only one distinct character.

Input: ("", 3)

Expected Output: 0

Explanation: An empty string has no substrings, so the answer is 0.

Input: ("a", 0)

Expected Output: 0

Explanation: With k = 0, no non-empty substring is allowed.

Input: ("abaccc", 2)

Expected Output: 4

Explanation: The longest valid substring is 'accc', which contains only 'a' and 'c'.

Hints

A sliding window can maintain a valid substring while expanding to the right.
Keep character counts in the current window, and shrink from the left whenever the number of distinct characters exceeds k.

Quick Overview