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

# Category Archives: Algorithms

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

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

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

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

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

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

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

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

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