Coding Problems and Solutions — 1

[1] Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

`          1         / \        2   3       / \           4   5`

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Approach — Diameter of a tree = max(Diameter of left sub-tree, Diameter of right sub-tree, depth of left sub-tree + depth of right sub-tree + 2)

[2] Find the diameter of a N-ary tree.

Approach — Use heap to maintain the largest 2 depths of children sub-trees.

[3] Given a non-empty string ‘s’ and a dictionary ‘wordDict’ containing a list of non-empty words, add spaces in ‘s’ to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

`Input:s = "pineapplepenapple"wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]Output:[  "pine apple pen apple",  "pineapple pen apple",  "pine applepen apple"]`

Approach — Use DFS and caching of intermediate results.

[4] Given a collection of candidate numbers candidates and a target number target, find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

`Input: candidates = [10,1,2,7,6,1,5], target = 8,A solution set is:[  [1, 7],  [1, 2, 5],  [2, 6],  [1, 1, 6]]`

Approach — Use DFS and caching of intermediate results.

[5] Given two strings s and t of length N, find the maximum number of possible matching pairs in strings s and t after swapping exactly two characters within s.

A swap is switching s[i] and s[j], where s[i] and s[j] denotes the character that is present at the ith and jth index of s, respectively. The matching pairs of the two strings are defined as the number of indices for which s[i] and t[i] are equal. This means you must swap two characters at different indices.

s = “abcd”
output = 4

[6] Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

`[  "((()))",  "(()())",  "(())()",  "()(())",  "()()()"]`

Approach — Use DP to compute cache[left][right] i.e. sequences with ‘left’ left parenthesis and ‘right’ right parenthesis using cache[left-1][right] and cache[left][right-1].

Also in cache[left][right] right should range from 0 to left.

[7] Count the unique elements in an sorted array.

Example

`Input: [1, 1, 1, 1, 2, 2, 2, 2, 5, 5, 5, 7, 7, 8, 8, 10]Output = 6`

O(K*logN) solution where K is the number of unique elements. Is optimal only when K << N.

Approach — Take the first index of a unique number and do binary search to find the last index j of the number. Then repeat from the next index j+1.

[8] Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Approach — Use stack.

[9] Implement an preorder iterator over a binary tree. Your iterator will be initialized with the root node of the tree.

Approach — Use stack.

[10] Clone Graph — Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

`class Node {    public int val;    public List<Node> neighbors;}`

Approach — Do BFS traversal and create a map from the value of a node to a copy of the Node pointer and also an adjacency list from the value of a node to the values of its children nodes.

[11] Given a directed graph remove redundant edges and return minimum number of edges to keep all paths i.e. remove as many edges as possible such that for any 2 vertices u and v if there is an edge in the original graph, there will be a path from u to v in the updated graph.

Example:

`Input: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] Output: 3Explanation: Minimum number of edges is 3 (1 2, 2 3, 3 4)`

Approach — Transitive reduction:
Do DFS from each vertex u and if we encounter a vertex v which is not a direct descendant of u but there is an edge between u and v then that edge is a redundant edge.

Written by