Implement tree traversals, BFS, and subsets generation
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
1) Define a TreeNode class for a binary tree with an integer value and left/right pointers. Implement preorder, inorder, and postorder traversals:
(a) recursive versions;
(b) iterative versions using an explicit stack (you may use two stacks for postorder). Return the traversal orders as lists and analyze time and space complexity.
2) Given an unweighted graph as an adjacency list and a source node s, implement BFS to return the visitation order, a distance map of minimum edge distances from s, and a parent map to reconstruct shortest paths. Handle disconnected graphs by describing how to traverse all components and produce results for each.
3) Given an array of distinct integers nums, generate the power set (all subsets). Provide
(a) a backtracking solution; and
(b) an iterative solution using for-loops only (no recursion), explaining how subsets are built layer by layer. Return subsets in any order and analyze complexity.
Quick Answer: This question evaluates proficiency with fundamental data structures and algorithms—binary tree traversals (preorder, inorder, postorder), breadth-first search on unweighted graphs, and power-set/subset generation—emphasizing implementation choices between recursive and iterative approaches and required time and space complexity reasoning.