Solve four classic algorithm problems
Overview
This set evaluates proficiency in core algorithms and data structures: tree traversal and order manipulation (zigzag level-order), dynamic programming and subsequence reasoning (longest palindromic subsequence), numeric algorithms and search/approximation (integer square root), and positional numeral systems/base conversion (spreadsheet column to number). These problems are commonly asked to assess algorithmic thinking, complexity analysis, and handling of edge cases in the Coding & Algorithms domain, testing both conceptual understanding of underlying principles and practical application of implementation techniques.
You are given four independent coding tasks. For each task, implement the required function.
Problem 1: Zigzag level-order traversal of a binary tree
Given the root of a binary tree, return the node values level by level, but alternate the traversal direction each level:
- Level 0 (root level): left → right
- Level 1: right → left
- Level 2: left → right
- … and so on.
Input: root (binary tree node)
Output: A list of lists, where each inner list contains the values for one level in the required order.
Example:
-
Tree:
1,2,3,4,5,null,6 -
Output:
[[1],[3,2],[4,5,6]]
Constraints: number of nodes up to ~10^4.
Problem 2: Longest palindromic subsequence length
Given a string s, return the length of the longest subsequence of s that is a palindrome.
- A subsequence can delete characters without changing the relative order of the remaining characters.
Input: string s
Output: integer length
Example:
-
Input:
s = "bbbab" -
Output:
4(one answer is subsequence"bbbb")
Constraints: 1 <= len(s) <= 1000.
Problem 3: Integer square root (floor)
Given a non-negative integer x, compute and return ⌊sqrt(x)⌋ (the integer part of the square root).
Input: integer x >= 0
Output: integer r such that r*r <= x < (r+1)*(r+1)
Example:
-
Input:
x = 8 -
Output:
2
Constraints: 0 <= x <= 2^31 - 1.
Problem 4: Spreadsheet column label to number
In a spreadsheet, columns are labeled A, B, ..., Z, AA, AB, ..., AZ, BA, ....
Given a column label string col consisting of uppercase English letters, return its 1-indexed column number.
Input: string col
Output: integer
Examples:
-
"A" -> 1 -
"Z" -> 26 -
"AA" -> 27 -
"ZY" -> 701
Constraints: 1 <= len(col) <= 7 (or any length that fits within 32-bit/64-bit integer, depending on language).