Word Break Problem

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. For example, Given a dictionary { i, like, ili, kesa, msun, sam, sung, mobile} then text “ilikemobile” is breakable into [“i”,”like”,”mobile”] text “ilikesamobile” is breakable into [“ili”,”kesa”,”mobile”] text “ilikesammobile” is […]

Wildcard or Regex Matching

Implement wildcard pattern matching with support for ‘.’ and ‘*’. ‘.’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Some examples: isMatch(“aa”,”a”) ? false isMatch(“aa”,”a.”) ? true isMatch(“aaa”,”ab*”) ? false isMatch(“aa”, “.*”) ? true isMatch(“aa”, “a*”) ? true isMatch(“ab”, […]

Who is our Boss? LCA for n-array Tree

In a company which has CEO Bill and a hierarchy of employees. Employees can have a list of other employees reporting to them, which can themselves have reports, and so on. An employee with at least one report is called a manager. Please implement the closestCommonManager method to find the closest manager (i.e. farthest from […]

Weighted job/interval scheduling – Activity Selection Problem

Given N jobs where every job is represented by following three elements of it. 1) Start Time 2) Finish Time. 3) Weight representing Profit or Value Associated. Find the maximum profit subset of jobs such that no two jobs in the subset overlap. Example: Number of Jobs n = 4 Job Details {Start Time, Finish […]

Uniform Random sampling of Unbalanced Binary Tree

Given an unbalanced binary tree, write code to select k sample node at random straightforward solution would be to list all the nodes in any traversal order (BFS, DFS, etc) and find random k index from the n nodes in the list. But how this approach would behave if n is very large and k […]

Transformation between Binary Tree and Linked Lists

Given a Binary Tree (or BST). 1. Flatten the BT into a single link in the order of inorder traversal. 2. Flatten the BT into a single link in the order of preorder traversal. 3. Flatten the BST to sorted single linked list. 4. Flatten a BST to Double Linked List 5. Flatten a BST […]