Multiply Two Big Integers

Given two big integers represented as strings, Multiplication them and return the production as string.

For example, given a=2343324 and b=232232 then retiurn c = a*b = 23433242334323342 * 23223233232434324 = 544195652122144709711313995190808

Min subarray (or sublist) to sort to make an unsorted array (or list) sorted

Give a list of unsorted number, find the min window or min sublist or min subarray of the input, such as if sublist is sorted, the whole list is sorted too.

For example, given array a={1,2,3,5,4,4,3,3,7,8,9} then min subarray to sort the complete array sorted is {5,4,3,3}. More example : for a={1,2,3,5,6,4,2,3,3,7,8,9} then min subarray is {2,3,5,6,4,2,3,3}, for a={1,2,3,5,6,4,3,3,7,8,9,2} then min subarray is {2,3,5,6,4,2,3,3,7,8,9,2} etc.

Find k such that kth row is all zero and kth col is all one in a matrix

Given a Boolean Matrix, find k such that all elements in k’th row are 0 and k’th column are 1. Do it in O(n) time

Given a binary matrix mat[n][n], find k such that all elements in k’th row are 0 and all elements in k’th column are 1. The value of mat[k][k] can be anything (either 0 or 1). If no such k exists, return -1.

Permuting Lists of Lists – Print all possible words from phone digits

Given a list of arraylists containing elements, write a function that prints out the permutations of of the elements such that, each of the permutation set contains only 1 element from each arraylist and there are no duplicates in the list of permutation sets.

For example: consider the following lists

Min Sum Path in a Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Find Missing Number

1. Given a set of positive numbers less than equal to N, where one number is missing. Find the missing number efficiently.
2. Given a set of positive numbers less than equal to N, where two numbers are missing. Find the missing numbers efficiently.
3. Given a sequence of positive numbers less than equal to N, where one number is repeated and another is missing. Find the repeated and the missing numbers efficiently.
4. Given a sequence of integers (positive and negative). Find the first missing positive number in the sequence.

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 the CEO) to two employees. You may assume that all employees eventually report up to the CEO. Assume the following class which you can’t change –

Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Minimum Substring of S Containing Elements in T

Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T.

For example:
S=adobecodebanc
T=abc
answer=’banc’

Process, Threads and Synchronization

Given n, print numbers from zero to n sequentially using two threads such that one thread prints only odds and other prints only evens.

This is a simple classical thread synchronization problem. Before moving to the solution I would like revise basic process, thread, and synchronization/concurrency concepts. Some of the figures in this article are taken from this Silberschatz OS book.

Generate Parentheses

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: {((())), (()()), (())(), ()(()), ()()()}

How do we solve this problem? Let’s start with base cases.

  • n=0 : result set is empty (no solution)

K-th permutation sequence

Given n and k, return the k-th permutation sequence of permutations of numbers {1,2,..,n}.

Note: Given n will be between 1 and 9 inclusive.

By listing and labeling all of the permutations in order, we get the following sequence (ie, for n = 3):
“123”
“132”
“213”
“231”
“312”
“321”

Print All Factors Of a Number

Given a positive number. Find all unique combinations of factors that constitute the number.

Note that we are not asking for only prime factors but any factors including primes. For example, given number n=12 can be factorize into 12 * 1, 6 * 2, 4 * 3, 3 * 2 * 2.

The 
Maximum
 Gap
 Problem : 
Pigeonhole 
Principle


Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n)?

For example, we have a unsorted array, a=[5, 3, 1, 8, 9, 2, 4] of size n=7 then the sorted version is
[1, 2, 3, 4, 5, 8, 9]. The output of the algorithm should be 8-5 = 3.

Duplicates Within K Distance in Array/Matrix/2D Array

Given an array of integer, find duplicates which are within k indices away. Find duplicates within K manhattan distance away in a matrix or 2D array. Return true or false if such elements exists.