Stack with getMin operation in O(1) time

This is a famous interview problem where the candidate is asked to design a stack so as to get minimum of the current elements present in the stack in O(1) time. I think having an auxiliary stack is the most general solution.

Found the following link to do it without using extra space obviously with some constraint on the data present in the stack, nonetheless solution deserves an "aha"!
http://stackoverflow.com/a/687945

Longest matching pattern

Given two strings find the longest matching pattern such that the pattern in the first string and the second string are permutation of each other.

Eg. - 
S1 = “ABCDEFG”
S2 = “DBCAPFG”
Then the output should be DBCA (length 4)
Assume there are no repeating characters.

Solution -
The idea is to transform S1 into clusters of indices of S2. So, for the example above we will get
Cluster 1 - 3, 1, 2, 0
Cluster 2 - 5, 6

Now, for each cluster find the longest portion (window) that satisfies the following property - 

• Max - Min + 1 = No of Elements

The longest portion (window) of the cluster will represent the indices of S2 that are contiguous and since the cluster itself is a a contiguous portion of transformed S1, the final solution will be the characters in S2 at the indices represented by such longest portion.

To find the longest portion satisfying the above property, we can recursively implement it as shown below in method getMaxCommonWindow. The idea is to find the maximum window starting with the first element satisfying the above property and then recusively find the maximum window not starting with the first element. The greater of these two windows will be the desired longest portion.

	/**
	* Author: Varun
	* Date: Apr 20, 2013
	*/
	import java.util.ArrayList;
	public class MaxCommonWindowForStrings {
	public static int[][] getContiguousIndicesOfS1InS2(String s1, String s2) {
	int[] s2Indices = new int[26];
	for(int i = 0; i < s2.length(); i++) {
	s2Indices[s2.charAt(i) - 'a'] = i +1;
	}
	ArrayList<int[]> indicesOfS1InS2 = new ArrayList<int[]>();
	ArrayList<Integer> curList = new ArrayList<Integer>();
	for(int i = 0; i < s1.length(); i++) {
	if(s2Indices[s1.charAt(i) - 'a'] != 0) {
	curList.add(s2Indices[s1.charAt(i) - 'a'] - 1);
	} else {
	if(!curList.isEmpty()) {
	indicesOfS1InS2.add(toIntArray(curList));
	curList.clear();
	}
	}
	}
	if(!curList.isEmpty()) {
	indicesOfS1InS2.add(toIntArray(curList));
	curList.clear();
	}
	return toInt2DArray(indicesOfS1InS2);
	}
	public static int[][] toInt2DArray(ArrayList<int[]> list) {
	int[][] ret = new int[list.size()][];
	for(int i = 0; i < ret.length; i++) {
	ret[i] = list.get(i);
	}
	return ret;
	}
	public static int[] toIntArray(ArrayList<Integer> list) {
	int[] ret = new int[list.size()];
	for(int i = 0; i < ret.length; i++) {
	ret[i] = list.get(i);
	}
	return ret;
	}
	public static int[] getMaxCommonWindow(int[] indicesOfS1InS2, int startIndexOfArray) {
	int maxIndexOfS2 = indicesOfS1InS2[startIndexOfArray];
	int minIndexOfS2 = indicesOfS1InS2[startIndexOfArray];
	int[] maxWindowStartingWithStartIndexOfArray = {startIndexOfArray, startIndexOfArray};
	if(startIndexOfArray == indicesOfS1InS2.length - 1) {
	return maxWindowStartingWithStartIndexOfArray;
	}
	for(int i = startIndexOfArray + 1; i < indicesOfS1InS2.length; i++) {
	if(indicesOfS1InS2[i] > maxIndexOfS2) {
	maxIndexOfS2 = indicesOfS1InS2[i];
	} else if(indicesOfS1InS2[i] < minIndexOfS2) {
	minIndexOfS2 = indicesOfS1InS2[i];
	}
	if((maxIndexOfS2 - minIndexOfS2) == (i - startIndexOfArray)) {
	maxWindowStartingWithStartIndexOfArray[1] = i;
	}
	}
	int[] maxWindowNotStartingWithStartIndexOfArray = getMaxCommonWindow(indicesOfS1InS2, startIndexOfArray + 1);
	return getGreaterWindow(maxWindowNotStartingWithStartIndexOfArray, maxWindowStartingWithStartIndexOfArray);
	}
	public static int[] getGreaterWindow(int[] win1, int[] win2) {
	if((win1[1] - win1[0]) > (win2[1] - win2[0])) {
	return win1;
	}
	return win2;
	}
	public static int findMinMax(int[] array, int startIndex, int endIndex, boolean findMin) {
	int ret = array[startIndex];
	for(int i = startIndex; i <= endIndex; i++) {
	if(findMin) {
	if(ret > array[i]) {
	ret = array[i];
	}
	} else {
	if(ret < array[i]) {
	ret = array[i];
	}
	}
	}
	return ret;
	}
	public static void main(String[] args) {
	String s1 = "abclmnoxyz";
	String s2 = "caboxleyzm";
	int[][] contiguousIndicesOfS1InS2 = getContiguousIndicesOfS1InS2(s1, s2);
	int[] maxWindow = {0, -1};
	int[] maxContiguousIndicesOfS1InS2 = null;
	for(int[] indicesOfS1InS2 : contiguousIndicesOfS1InS2) {
	int[] window = getMaxCommonWindow(indicesOfS1InS2, 0);
	maxWindow = getGreaterWindow(maxWindow, window);
	if(window == maxWindow) {
	maxContiguousIndicesOfS1InS2 = indicesOfS1InS2;
	}
	}
	System.out.print("Substring from S2 = ");
	if(maxWindow[1] - maxWindow[0] < 0) {
	System.out.println("No common window found");
	} else {
	System.out.println(s2.substring(findMinMax(maxContiguousIndicesOfS1InS2, maxWindow[0], maxWindow[1], true),
	findMinMax(maxContiguousIndicesOfS1InS2, maxWindow[0], maxWindow[1], false) + 1));
	}
	}
	}

view raw MaxCommonWindowForStrings.java hosted with ❤ by GitHub

Count the number of six digit numbers possible

The problem is to calculate the number of 6-digit numbers that you can create using the following scheme of things.

0-9 digits are arranged like a phone keypad.
1 2 3
4 5 6
7 8 9
   0

The 6-digit number cannot start with 0. A digit can follow any other digit in the 6-digit number only if both the numbers are in the same row or column.
For eg. in a 6-digit number:
2 can follow 0
0 can follow 8
9 can follow 7
5 can follow 4
4 can follow 1
1 can follow 7
...
...
9 cannot follow 5
1 cannot follow 6
0 cannot follow 1
...
...

The idea of the solution is to use dynamic programming. A possible implementation is given below. To further optimize we can do memoization.

	/**
	* Author: Varun
	* Date: Apr 17, 2013
	*/
	public class SixDigitNumbers {
	static int[][] reachableNodes = {
	{0,0,1,0,0,1,0,0,1,0},
	{0,0,1,1,1,0,0,1,0,0},
	{1,1,0,1,0,1,0,0,1,0},
	{0,1,1,0,0,0,1,0,0,1},
	{0,1,0,0,0,1,1,1,0,0},
	{1,0,1,0,1,0,1,0,1,0},
	{0,0,0,1,1,1,0,0,0,1},
	{0,1,0,0,1,0,0,0,1,1},
	{1,0,1,0,0,1,0,1,0,1},
	{0,0,0,1,0,0,1,1,1,0}
	};
	public static int countNDigitNumbers(int n, int startWith) {
	int count = 0;
	if(n == 1) {
	return 1;
	}
	for(int i = 0; i <= 9; i++) {
	if(reachableNodes[startWith][i] == 1) {
	count += countNDigitNumbers(n-1, i);
	}
	}
	return count;
	}
	public static void main(String[] args) {
	int sixDigitNumberCount = 0;
	for(int i = 1; i <= 9; i++) {
	sixDigitNumberCount += countNDigitNumbers(6, i);
	}
	System.out.println("The Total: " + sixDigitNumberCount);
	}
	}

view raw SixDigitNumbers.java hosted with ❤ by GitHub