CareerCup

Please correct me if I was wrong:
it is true that an input string matches the given pattern once satisfying:
1) pattern length equals with input string's length;
2) fixed characters in pattern match the ones in the same positions of input string

package org.wangbingold.datastructure.array;
/**
 * Question: 
Implement rotate function for forward-only iterators. 
Clarification: with O(1) additional memory. 
Rotate semantics should be that of std::rotate.
Example: 
Say the array was [1, 2, 3, 4, 5, a, b , c]. With middle pointing at 'a'. 
First at 1, and last at 'c', and we need to rotate so that it is [a, b, c, 1, 2, 3, 4, 5]. 
You make a copy of the First, Middle Iterators, say first', middle'.
*/

public class Rotation {
	
	private char[] array;
	
	public Rotation(char[] arrayIn){
		this.array = arrayIn;
	}
	
	/**
	 * Rotate the array in the range of [start, end] from the position of mid.
	 * */
	public void rotate(int start, int mid, int end){
		if(start>=end){
			return;
		}
		int numPart1 = mid-start;
		int numPart2 = end-mid+1;
		int p1 = start; 
		int p2 = mid; 
		if(numPart1==numPart2){
			while(p2<=end){
				char tmp = array[p1];
				array[p1] = array[p2];
				array[p2] = tmp;
				p1++;p2++;
			}
			System.out.println(this.toString());
		}
		else if(numPart1>numPart2){
			while(p2<=end){
				char tmp = array[p1];
				array[p1] = array[p2];
				array[p2] = tmp;
				p1++;p2++;
			}
			int newStart = p1;
			int newEnd = p2-1;
			int newMid = newStart+numPart1-numPart2;
			System.out.println(this.toString());
			rotate(newStart, newMid, newEnd);
		}
		else if(numPart1<numPart2){
			while(p1<mid){
				char tmp = array[p1];
				array[p1] = array[p2];
				array[p2] = tmp;
				p1++;p2++;
			}
			int newStart = p1;
			int newEnd = (p2==end)?p2:p2+1;
			int newMid = (p2>end)?p2-1:p2;
			System.out.println(this.toString());
			rotate(newStart, newMid, newEnd);
		}
	}
	
	public String toString(){
		String result="";
		for(Object obj: array){
			result+=obj.toString()+" ";
		}
		return result;
	}
	
	public static void main(String[] args){
		Rotation rotation = new Rotation(new char[]{'1','2','3','4','5','a','b','c'});
		rotation.rotate(0, 5, 7);
	}

}

it equals with finding the longest common subsequence between one word (e.g. XAYBZBA) and its reverse (e.g. ABZBYAX).

<pre lang="java" line="1" title="CodeMonkey30014" class="run-this">public static boolean is_match(String input, String pattern){
if(pattern=="*") return true;

int inputIndex=0;
int patternIndex = 0;

for(; inputIndex<input.length(); inputIndex++){
if(patternIndex==pattern.length()) break;
if(pattern.charAt(patternIndex)=='*'){
char nonStarChar = ' ';
while(++patternIndex<pattern.length()){
if(pattern.charAt(patternIndex)!='*'){
nonStarChar = pattern.charAt(patternIndex);
break;
}
}
if(nonStarChar==' ') return true;
while(inputIndex<input.length()){
if(input.charAt(inputIndex)==nonStarChar){
inputIndex--;
break;
}
inputIndex++;
}
if(inputIndex==input.length()) return false;
else continue;
}
else if(input.charAt(inputIndex)==pattern.charAt(patternIndex)){
patternIndex++;
continue;
}
else break;
}

if(inputIndex==input.length() && patternIndex==pattern.length()) return true;
return false;
}</pre><pre title="CodeMonkey30014" input="yes">
</pre>

In practice, it would be better assuming the start and end time would not be double num, should be like "15:30". And if we are talking about setting up appointment on calendar, the gap would be the times of 5 mins (e.g. "15:30 - 15:40"). So we can think of using baskets on a time line to indicate whether there have already had an appointment. That would be definitely O(n).

Thanks Sri. But why current aptn only compares with its decedent aptns?

<pre lang="java" line="1" title="CodeMonkey83982" class="run-this">/*
Only use StringBuilder to be the char buffer.
KMP idea
*/

public String filtering(){
StringBuilder resultBuilder = new StringBuilder();
StringBuilder buffer = new StringBuilder();
int point1=0, point2=0;
while(point1<input1.length()){
if(point2>=input2.length()){
buffer.delete(0, buffer.length());
point2=0;
}
if(input1.charAt(point1)!=input2.charAt(point2)){
if(buffer.length()!=0){
resultBuilder.append(buffer.toString());
buffer.delete(0, buffer.length());
point2=0;
}
resultBuilder.append(input1.charAt(point1++));
}
else if(input1.charAt(point1)==input2.charAt(point2)){
buffer.append(input1.charAt(point1));
point1++; point2++;
}
}
return resultBuilder.toString();
}</pre><pre title="CodeMonkey83982" input="yes">
</pre>

<pre lang="java" line="1" title="CodeMonkey72835" class="run-this">public void printALevel(Node root, int curHeight, int height){
if(root==null) return;
if (height==0) return;
if(curHeight==height){
System.out.print(root+" ");
return;
}

printALevel(root.left, curHeight+1, height);
printALevel(root.right, curHeight+1, height);
}</pre><pre title="CodeMonkey72835" input="yes">
</pre>

DFS solution

Does the question mean the following:

Sorted list:
abc
bcd
bcde
efghi

Encoded list:
bca
cdb
cdeb
fghie

Does this example make sense or not?

/*
Here is the complete code.

Assume that there is no duplicated element in the matrix.

If handling duplicated element, I will use a HashSet to record seen element.
*/
public class RowColumnSortedMatrix {
int[][] matrix;

public RowColumnSortedMatrix(int[][] matrix){
this.matrix = matrix;
}

public int[] findKthLargest(int k){
int[] result = new int[2];
if(k>matrix.length*matrix.length){//validate input
result[0] = -1; result[1] = -1;
return result;
}
int rowX=matrix.length-1, rowY = matrix.length-1;
int colX=matrix.length-1, colY = matrix.length-1;
int maxX=-1, maxY=-1;
int curRow = matrix.length-1, curCol = matrix.length-1;
int count=0;
while(count<k){
if(matrix[rowX][rowY]==matrix[colX][colY]){//pointed element equal, move both rowPointer and colPointer
count++;
maxX = rowX; maxY = rowY;
rowX = rowX-1;
if(rowX<0){ rowX = curRow-1; rowY = rowY-1; curRow--;}
colY = colY-1;
if(colY<0){colY = curCol-1; colX = colX-1; curCol--;}
}
else if(matrix[rowX][rowY]<matrix[colX][colY]){//element pointed by colPointer is bigger, move colPointer
count++;
maxX = colX; maxY = colY;
colY = colY-1;
if(colY<0){colY = curCol-1; colX = colX-1; curCol--;}
}
else{//element pointed by rowPointer is bigger, move rowPointer
count++;
maxX = rowX; maxY = rowY;
rowX = rowX-1;
if(rowX<0){ rowX = curRow-1; rowY = rowY-1; curRow--;}
}
}

result[0] = maxX; result[1]=maxY;
return result;
}

public static void main(String[] args){
int[][] matrix = {
{0,1,2,3},
{12,14,17,36},
{13,15,18,40},
{50,60,70,80}
};
RowColumnSortedMatrix sortedMatrix = new RowColumnSortedMatrix(matrix);
int[] xy = sortedMatrix.findKthLargest(11);
System.out.println("x= "+xy[0]+"; y= "+xy[1]+" element= "+matrix[xy[0]][xy[1]]);
}
}

O(k), in-place, no-extra data structure solution:

Initialization:
Use two pointers (row pointer and column pointer), both begin from the bottom-right corner of matrix (the maximum element).
Row pointer moves from bottom to top, and column pointer moves from right to left.

If the element pointed by row pointer is bigger than column pointer, row pointer moves to the next; else column pointer moves to the next.
If row pointer moves to the top (i.e. (0, Y), its next position will wrap inner-back (i.e. (preRow-1, Y-1)); if column pointer moves to the left-most (i.e. (X, 0)), it also moves back (i.e. (X-1, preCol-1));
Continue until count to k.

How about taking level-wide travels on two trees? If finding not same nodes, return false; return true until finishing the traveling. Worst case is O(nlogn), average case would be less than O(nlogn)

I believe that should be double circular linked list

<pre lang="java" line="1" title="CodeMonkey29109" class="run-this">boolean isBinarySearchTree(Node r){
if(r.isLeaf){
return true;
}
if(r.key>=r.left.key && r.key<r.right.key){
return (true && isBinaryTree(r.left) && isBinaryTree(r.right))
}
else{
return false;
}
}</pre><pre title="CodeMonkey29109" input="yes">
</pre>

Assume that there is no need of aux array, the number of B's empty slots just equal to A's length, and B is trailed by the empty slots

<pre lang="java" line="1" title="CodeMonkey57027" class="run-this">int[] mergeArrays(int[] a, int[] b){
int emptyIndex = b.length-1;
int curB = 0;
int curA = a.length-1;
for(int i=b.length-1;b>=0; b--){//find the first non-empty slots of b from end
if(b[i]!=null){
emptyIndex = i+1;
curB = i;
break;
}
}
while(curA>=0 && curB>=0){
if(a[curA]>b[curB]){
b[emptyIndex--] = a[curA--];
}
else{
b[emptyIndex--] = b[curB--];
}
}

if(curA!=0){
while(curA>=0){
b[emptyIndex--] = a[curA--];
}
}
return b;
}</pre><pre title="CodeMonkey57027" input="yes">
</pre>

O(logN)