Katkat
Back

Solve four classic algorithm problems

MicrosoftSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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).