Quick Overview

This question evaluates binary tree traversal and leaf detection, calendrical date arithmetic and palindrome checking, discrete-time edge-detection/stateful sequence processing, and implementation of comparison-based sorting; category/domain: Coding & Algorithms. It is commonly asked to assess correctness and edge-case handling (e.g.

Solve mixed coding tasks from interviews

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Solve the following interview-style coding problems (you may choose any programming language unless specified). Provide correct logic and handle edge cases. 1) **Binary tree leaves**: Given the root of a binary tree, output the values of all **leaf nodes** (nodes with no children). Specify the traversal order you choose (e.g., left-to-right). 2) **Previous palindrome date**: Given a date (e.g., `YYYY-MM-DD`), find the **most recent earlier date** (strictly before the given date) whose representation is a palindrome when written as `YYYYMMDD`. You only need to describe the algorithm (no code required), but be precise about leap years and month lengths. 3) **Edge detector**: Implement a rising-edge detector for a boolean signal sampled on clock cycles. Given an array `x[0..n-1]` of 0/1 samples, output an array `edge[0..n-1]` where `edge[i]=1` iff `x[i-1]=0` and `x[i]=1` (assume `edge[0]=0`). 4) **Sorting**: Implement a sorting function for an array of integers (any correct O(n log n) sort is fine; if you choose bubble sort, state its complexity).

Quick Answer: This question evaluates binary tree traversal and leaf detection, calendrical date arithmetic and palindrome checking, discrete-time edge-detection/stateful sequence processing, and implementation of comparison-based sorting; category/domain: Coding & Algorithms. It is commonly asked to assess correctness and edge-case handling (e.g.

Part 1: Binary Tree Leaves

Given a binary tree represented as a level-order list, return the values of all leaf nodes from left to right. A leaf node is a node with no left child and no right child.

Constraints

  • 0 <= len(level_order) <= 10^4
  • Each element is either an integer or None
  • If the list is empty or the root is None, the tree is empty

Examples

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

Expected Output: [4, 5, 6]

Explanation: The leaf nodes are 4, 5, and 6, read from left to right.

Input: ([1],)

Expected Output: [1]

Explanation: A single-node tree has one leaf: the root itself.

Hints

  1. A node is a leaf only when both its left and right children are missing.
  2. If you reconstruct the tree from level order, visit the left subtree before the right subtree to preserve left-to-right leaf order.

Part 2: Previous Palindrome Date

Given a valid date string in the format YYYY-MM-DD, return the most recent date strictly earlier than it such that its compact form YYYYMMDD is a palindrome. Use Gregorian leap-year rules. If no such earlier palindrome date exists, return None.

Constraints

  • The input date is a valid Gregorian date from 0001-01-01 to 9999-12-31
  • Leap years follow the Gregorian rule: divisible by 400, or divisible by 4 but not by 100
  • Return the answer strictly earlier than the given date

Examples

Input: ('2021-12-03',)

Expected Output: '2021-12-02'

Explanation: 20211202 is a palindrome and is the closest earlier valid date.

Input: ('2021-12-02',)

Expected Output: '2020-02-02'

Explanation: The given date itself is palindromic, but the answer must be strictly earlier.

Hints

  1. If YYYYMMDD is a palindrome, then MMDD is completely determined by the 4 digits of YYYY.
  2. Generate at most one candidate per year by reversing the 4-digit year, then validate month and day.

Part 3: Rising Edge Detector

Given a sampled boolean signal x as an array of 0s and 1s, return an array edge of the same length where edge[i] = 1 exactly when x[i-1] = 0 and x[i] = 1. Assume edge[0] = 0.

Constraints

  • 0 <= len(x) <= 10^5
  • Each x[i] is either 0 or 1

Examples

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

Expected Output: [0, 0, 1, 0, 0, 1]

Explanation: Rising edges happen at indices 2 and 5.

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

Expected Output: [0, 0, 0]

Explanation: There is no 0-to-1 transition.

Hints

  1. Each output value depends only on the current sample and the previous sample.
  2. Handle index 0 separately, and do not forget the empty-array case.

Part 4: Sort Integers in Ascending Order

Implement a function that returns the integers of an array sorted in ascending order. Use an O(n log n) algorithm such as merge sort or heap sort. Do not rely on built-in sorting helpers in the intended solution.

Constraints

  • 0 <= len(nums) <= 10^5
  • Each integer fits in the standard 32-bit signed range

Examples

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

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

Explanation: A basic unsorted input.

Input: ([],)

Expected Output: []

Explanation: An empty list is already sorted.

Hints

  1. A divide-and-conquer approach works well here.
  2. After sorting the left and right halves, merge them by repeatedly taking the smaller front element.

Loading coding console...