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.

Solve tree, graph, sliding-window problems

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.

Hints

  1. A breadth-first search naturally processes the tree one level at a time.
  2. 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.

Hints

  1. Think of courses as nodes in a directed graph and prerequisites as directed edges.
  2. 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.

Hints

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

Loading coding console...