Interview questions · Meta

Solve palindrome-check and vertical-order traversal

This prompt evaluates string-processing and tree-traversal competencies by asking whether a string can become a palindrome after at most one deletion and by requiring a vertical-order traversal of a binary tree, testing understanding of palindrome properties, node ordering, and handling of edge cases in the coding and algorithms domain.

You are asked to solve two separate coding questions. You do not need to run code; be prepared to explain your approach and walk through examples.

Question 1: Near-palindrome with one deletion

Given a string s, determine whether it can become a palindrome after deleting at most one character.

Input: a string s (consisting of lowercase English letters)
Output: true if s can be made a palindrome by removing 0 or 1 character; otherwise false
Constraints (typical): 1 <= len(s) <= 1e5

Example:

s = "abca" → true (delete 'b' or 'c')
s = "abc" → false

Question 2: Binary tree vertical order traversal

Given the root of a binary tree, return its vertical order traversal.

Define a node’s column as follows:

Root is at column 0
Left child is column col - 1
Right child is column col + 1

Return a list of columns from leftmost to rightmost. Within each column, list nodes in top-to-bottom order. If multiple nodes share the same row and column, order them in the same order they would appear in a level-order (BFS) traversal from left to right.

Input: root of a binary tree
Output: List[List[int]] (values grouped by column)
Constraints (typical): up to 1e4–1e5 nodes

Example: For the tree:

3 as root
left child 9, right child 8
9 has children 4 and 0
8 has children 1 and 7

Vertical order output:

[[4], [9], [3, 0, 1], [8], [7]]

Explain your algorithm and its time/space complexity.

Community answers

Nothing here yet.

Join in on CSWork →