## 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”, […]

## Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]…. For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4], another could be [3, 5, 1, 6, 2, 4]. Basically, A[0] <= A[1] >= A[2] <= A[3] […]

## 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 […]

## Water Trapped Between Towers

You are given an array with element represents the height of a tower with width equal to one unit. It started to rain. Find the amount of water trapped between towers? For example, tower = [0, 1, 2, 1, 3, 2, 0, 2, 3] – then answer is 6 units between towers 3 and 7. […]

## Walls and Gates – find shortest escape paths

You are given a m x n 2D grid initialized with these three possible values. -1 – A wall or an obstacle. 0 – A gate. INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate […]

## Vertical and Zigzag Traversal of Binary Tree

Given a binary tree. Print the nodes in vertical and zigzag manner. <strong?vertical traversal<=”” strong=””></strong?vertical> For example, we have binary tree below: 1 / \ 2 3 / \ / \ 4 5 6 7 vertical traversal will output: 4 2 1 5 6 3 7 We can clearly see that we are printing the […]

## 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 […]