CareerCup

This can be done in two ways:

Approach 1: Construct the final line which takes O(2^k) time where k is the max row in all queries. Each query will only take O(1) time. The downside of this approach is it requires O(2^k) space.

Approach 2: Without construct the lines, it takes O(k) time for each query, and only takes O(1) space.

//Approach 1        
	public static List<Integer> build(List<Integer> list, int level){
		if(level == 0)return list;
		List<Integer> newList = new ArrayList<Integer>();
		for(int each:list){
			if(each == 0){
				newList.add(0);
				newList.add(1);
			}
			else{
				newList.add(1);
				newList.add(0);
			}
		}
		return build(newList,level-1);
	}

	//Approach 2
	public static int query(int ith, int left, int right, int bit){
		if(left == right){
			return bit;
		}
		else{
			int mid = left-(right-left)/2;
			if(left <= ith && mid >= ith){
				return query(ith,left,mid,bit);
			}
			else return query(ith,mid+1,right,1-bit);
		}
	}
	public static void main(String[] args){
		List<Integer> list = new ArrayList<Integer>();
		list.add(0);
		list = build(list,4);
		for(int each:list){
			System.out.print(each+" ");
		}
		System.out.println();
		for(int i=0;i<16;i++){
			System.out.print(query(i,0,15,0)+" ");
		}
	}

Use two pointers, O(n) time complexity, O(1) space:

////assume target is positive
public boolean hasContSum(List<Integer> list, int target)
{
	int tail = 0;
	int sum = 0;
	for(int i=0;i<list.size();i++)
	{
		sum+=list.get(i);
		while(sum>target){ 
			sum-=list.get(tail++);
		}
        if(sum == target) return true;
	}
	return false;	
}

My O(nlongn) solution (Worse case O(n^2), best case O(n)):
My approach:
1. Find the max value in the array, we will buy all the stocks before the max and sell it at the max price.
2. Treat all elements after the max as a new array and repeat the steps until there is one or no element left.

public int maxProfit(int[] prices) {
	return maxProfit(prices,0,prices.length);
}
public int maxProfit(int[] prices, int left, int right){
	if(right-left <=1)return 0;

	int[] cum = new int[prices.length];
	int maxPoint = -1;
	int maxPointIndex = -1;

	for(int i=left;i<right;i++){
		cum[i]+=prices[i];
                if(i>left)cum[i]+=cum[i-1];
		if(maxPoint<=prices[i]){
			maxPoint = prices[i];
			maxIndex = i;
		}
	}
	return (maxIndex-left+1)*maxPoint-cum[maxIndex]+maxProfit(prices,maxIndex+1,right);
}

Here is my approach O(n) time complexity and O(1) space:

1. Set two pointers (A and B) point at the beginning of the string.

2. Pointer A walks through the string and record the frequency of each character in count[26].

3. If the current character that pointer A points to appears more than K, save the substring between B (inclusive) and A (exclusive) if it is the longest substring so far.

4. Move the pointer B and subtract the pointing character from count[26] until we get the frequencies of all characters in count[26] no more than K.

5. Repeat the process from step 2 until it reaches the end of the string.

//Assume given string is all low case between [a-z]
public String longestSubstring(String str, int K)
{
	int A = 0;
	int B = 0;
	int[] count = new int[26];
	int longestLen = 0;
	String result;
	for(;A<str.length();A++)
	{
		if(++count[str.charAt(A)-'a'] > K)
		{
			if(longestLen < A-B)
			{
				result = str.substring(B,A);
			}
			for(;B<A;B++)
			{
				if(--count[str.charAt(B)-'a'] == K)
				{
					B++;
					break;
				}
			}
		}
		
	}
	//indicates none of the characters in given string appears more than K
	if(result == null) return str;
	return result;
}

It can be done in O(n) time complexity (save the list into a Hashset for fast look up).

Iterate each node in the list and check the following conditions:
1. Its left and right node are null.We move the node from the list to a hashset, called "lookForParent".

2. Its left or right node does not belong to the list nor appear in the "lookForParent",
It violates rule #1 or #2, we can simply return false.

3. Its left and/or right node belongs to the list or appears in 'lookForParent".
(a) Remove this node from the list.
(b) Check if this node's child(ren) are in the list or in the "lookForParent" recursively
(if not, it violates rule #1 or #2 and return false) and remove the node from the list
or from the "lookForParent".
(c) Move this node to "lookForParent".

At the end if the "lookForParent" hashset contains one node (it is the root), return true. Otherwise return false (violates rule #3).

public boolean isValidTree(List<Node> list){
	Set<Node> set = new HashSet<Node>(list);
	HashSet<Node> lookForParent = new HashSet<Node>();
	for(Node each:list){
		if(set.contains(each){
			if(each.left == null && each.right == null){
				set.remove(each);
				lookForParent.add(each);
			}
			else if(each.left != null || each.right != null){
				Node tmp = each;
				boolean good = checkChildren(each.left,set,lookForParent) &&
                                                                 checkChildren(each.right,set,lookForParent);
				if(good){
					lookForParent.add(tmp);
				}
				else{
					return false;
				}
			}
		}
	}
	if(lookForParent.size() == 1){
		return true;
	}
	return false;
}
public boolean checkChildren(Node node, HashSet<Node> set, HashSet<Node> lookForParent){
	if(node == null) return true;
	else if(lookForParent.contains(node)){
		lookForParent.remove(node);
		return true;
	}
	else if(set.contains(node)){
		set.remove(node);
		return checkChildren(each.left,set,lookForParent) && 
                               checkChildren(each.right,set,lookForParent);
	}
	return false;

}

Use two pointers to keep track the 'tail' and 'head' of the subarray. O(n) complexity:

public int countSubArrays(int[] array, int k){
		int head = 0;
		int tail = 0;
		int total = 1;
		int count = 0;
		for(;head<array.length;head++){
			total*=array[head];
			if(total < k){
				count+=head - tail + 1;
			}
			else{
				while(total>=k && head >= tail){
					total/=array[tail];
					tail++;
				}
				if(head>=tail){
					count+=head - tail + 1;
				}
			}
		}
		return count;
	}

Wow, without memorize the last state or modify the input array and return the index of next max number. It sounds like a computer runs without memory or cache. I would like know how it works.

1. I think -1-2-3 should be equals to -6, not 6.
2. Some people mentioned the answer should be equals to ZERO. Let's take a look at the simplest number "12" Here are all the possible combinations:
12 = 12
1+2 = 3
1-2 = -1
+12 = 12
+1+2 = 3
+1-2 = -1
-12 = -12
-1+2 = 1
-1-2 = -3

Sum = 14, so it is not equal to zero. If you look carefully, the final sum equals to the sum of the first three (the first number without the +/- sign). Let's check the number "123":
123 = 123
12+3 = 15
12-3 = 9
1+23 = 24
1+2+3 = 6
1+2-3 = 0
1-23 = -22
1-2+3 = 2
1-2-3 = -4
+123 = 123
+12+3 = 15
+12-3 = 9
+1+23 = 24
+1+2+3 = 6
+1+2-3 = 0
+1-23 = -22
+1-2+3 = 2
+1-2-3 = -4
-123 = -123
-12+3 = -9
-12-3 = -15
-1+23 = 22
-1+2+3 = 4
-1+2-3 = -2
-1-23 = -24
-1-2+3 = 0
-1-2-3 = -6

sum = 153. The final sum is same as the sum of the first nine line. Also I see the pattern that for number "ab", the sum equals to ab+a*2, and for number "abc", the sum equals to abc+ab*2+a*6. I think you get the idea now. The time complexity should be O(n) where n is the length of the string.

This problem seems very easy. If you use Hashmap, the time complexity is O(n) and space complexity is also O(n). Since you were interviewed by the mobile team, I bet they were looking for solutions with O(1) space complexity.

1. Find the largest number (I called it A) from the array and remember its index.
2. Find the next largest number (I called it B) from the array. If B comes before A, we're good, otherwise move B to the front, MoveToFront(B).
3. A = B, and repeat (2). it needs to loop n-2 times to check all other numbers.

It's not the fastest algorithm, but it should be very easy to understand. The time complexity is O(n^2).

Some people try to change one character from start[i] to end[i] at a time, and check if the the dictionary contains that word. It could be wrong in some cases for example, dictionary= [cut, cug, cog]

Do you mean by nlogn time?

note that the pattern can't start with "*", but
isMatch("aa","*")->true
isMatch("ab","*")->true
isMatch("ab","*")->true

start with "*" and end with "*".

1. find the smallest number in the first column and print it out.
2. remove the smallest number from its row, and shift all number to the left.
3. repeat.
Assume the max value in the matrix is smaller than 10^32-1

public void printSortedMatrix(int[][] matrix)
	{
		for(int a=0;a<matrix.length*matrix[0].length;a++){
			int min = Integer.MAX_VALUE;
			int index = 0;
			for(int i=0;i<matrix.length;i++){
				if(matrix[i][0] < min){
					min = matrix[i][0];
					index = i;
				}
			}
			System.out.print(min+",");
			for(int j=1;j<matrix[0].length;j++){
				matrix[index][j-1] = matrix[index][j];
			}
			matrix[index][matrix[0].length-1] = Integer.MAX_VALUE;
		}
	}

recursive dynamic programming

public static void findSteps(int N){calSteps(N,"");};
	public static void calSteps(int N, String stepsNow){
		if(N >2){
			calSteps(N-2,stepsNow+"2");
		}
		else if(N == 2){
			System.out.println(stepsNow+"2");
		}
		if(N>1){
			calSteps(N-1,stepsNow+"1");
		}
		else if(N == 1){
			System.out.println(stepsNow+"1");
		}
	}

Here is an example to print output without return anything and without worry about the performance.

public static void printPermutate(String[] listStr)
	{
		recPrint(listStr, "", 0);
	}
	public static void recPrint(String[] listStr, String current, int index)
	{
		
		if(index == listStr.length-1)
		{
			for(char ea : listStr[index].toCharArray())
			{
				System.out.println(current+ea);
			}
		}
		else 
		{
			for(char ea : listStr[index].toCharArray())
			{
				recPrint(listStr,current+ea,index+1);
			}
		}
	}

1. if the current node has right child node, and if the right child node has left child node, return the leaf of the left most node. If the the right child node has no left child, return its value.
2. if the current node has no right child node, and if the current node is the left child of its parent, return its parent node's value (parent node can be null). If the current node is the right child node of its parent, set the parent node as the current node, and repeat (2).

public Node{
		int value;
		Node left;
		Node right;
		Node parent;
	}
	public Node findInOrderSuccessor(Node currentNode)
	{
		if(currentNode.right != null)
		{
			Node leftNode = currentNode.right.left;
			if(leftNode  == null) return currentNode.right;
			while(leftNode.left != null)
			{
				leftNode = leftNode.left;
			}
			return leftNode;
		}
		else if(currentNode.parent != null)
		{
			while(currentNode.parent != null)
			{
				if(currentNode.parent.left.value == currentNode.value)return currentNode.parent;
				currentNode = currentNode.parent;
			}
			
		}
		return null;
	}

1. Insert same level node in a list, from left to right.
2. iterate the list and assign the element[i].next = element[i+1], the last element's next should be null
3. go down to the next level and repeat 1.

public void PopulateNext(Node node)
	{
		List<Node> listNodes = new ArrayList<Node>();
		node.next = null;
		listNodes.add(node);
		while(listNodes.size() > 0)
		{
			List<Node> newListNodes = new ArrayList<Node>();
			for(int i=0;i<listNodes.size()-1;i++)
			{
				listNodes.get(i).next = listNodes.get(i+1);
				if(listNodes.get(i).left != null)
				newListNodes.add(listNodes.get(i).left);
				if(listNodes.get(i).right != null)
				newListNodes.add(listNodes.get(i).right);
			}
			Node mostRightNode = listNode.get(listNodes.size()-1);
			mostRightNode.next = null;
			if(mostRightNode.left != null)
			newListNodes.add(mostRightNode.left);
			if(mostRightNode.right != null)
			newListNodes.add(mostRightNode.right);
			
			listNodes = newListNodes;
		}
	}

If the time is in integer and is military time, then we can use an array to keep track any overlaps (back to back not consider overlap)

public int findRooms(int[] startTime, int[] endTime)
	{
	int maxRoom = 1;
	int[] sch = new int[24];
for(int a=0;a<startTime.length;a++){
	for(int i=startTime[a];i<endTime[a];i++)
{
	sch[i]++;
maxRoom = Math.max(maxRoom,sch[i]);
}
}

return maxRoom;
	}

//Babylonian method

public double squareRoot(int x){
		double res = (600.0+x/600.0)/2;
		double lastResult = Double.NaN;
		while(res != lastResult){
			lastResult =res;
			res = (res+x/res)/2;
		}
		return res;
	}

Assume there are no parenthesis, the easy and neat solution would be use recursive function. Java code:

public static double cal(String expression){
		double ret = 0;
		if(expression.matches(".*\\+.*")){
			for(String ea:expression.split("\\+")){
				ret+=cal(ea);
			}
		}
		else if(expression.matches(".*\\-.*")){
			String[] sp = expression.split("\\-");
			ret = cal(sp[0]);
			for(int i=1;i<sp.length;i++){
				ret-=cal(sp[i]);
			}
		}
		else if(expression.matches(".*\\*.*")){
			ret = 1;
			for(String ea:expression.split("\\*")){
				ret*=cal(ea);
			}
		}
		else if(expression.matches(".*\\/.*")){
			String[] sp = expression.split("\\/");
			ret = cal(sp[0]);
			for(int i=1;i<sp.length;i++){
				ret/=cal(sp[i]);
			}
		}
		else ret = Double.parseDouble(expression);
		return ret;
	}

in Java

//rotate 90 degrees clockwise
	public int[][] rotate(int[][] a)
	{
		int row = a.length;
		int col = a[0].length;
		int[][] tmp = new int[col][row];
		for(int i=row;--i>=0;)
		{
			for(int j=0;j<col;j++)
			{
				tmp[j][row-i-1] = a[i][j];
			}
		}
		return tmp;
	}

You can remove any numbers greater than SUM, but should not remove zeros. for example, N = [0,1,2,3], M = 2, SUM=1. The only valid subset is [0,1], where zero is needed.