CareerCup

you basically sort the intervals then merge them will be easy. O(nlogn)

the thing is, you calculate the max profit of the opponent. suppose you take it from the front, your opponent can choose from F(a+2, b), F(a+1, b-1) , and since the opponent plays optimally, he/she would choose max(F(a+2, b), F(a+1, b-1)), which left you min(F(a+2, b), F(a+1, b-1));

same logic, if you choose from the end, your opponent can choose from F(a, b-2), F(a+1,b-1), and he/she would choose max(F(a, b-2), F(a+1,b-1)), which left you min(F(a, b-2), F(a+1,b-1))

so you actually need the max left-over so you max whatever your opponent left to you, which is the first formula above.

the idea is use DP to find the height, left, right for each element.

if(matrix[i][j] == '0'){
height[i][j] = 0; left[i][j] = 0; right[i][j] = 0; //because it's an obstacle
}
else{
height[i][j] = 1 --- if matrix[i-1][j] == '0';
height[i][j] = matrix[i-1][j] + 1 --- otherwise

left[i][j] = max(left[i-1][j], the index of the first obstacle on the element's left);
right[i][j] = min(right[i-1][j], the index of the first obstacle on the element's right)
}

then we just go through the elements and find the max area, which is height*(right-left).

idea from: hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba

//oj.leetcode.com/problems/maximal-rectangle/
public int maximalRectangle(char[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0){
            return 0;
        }
        else{
            int row = matrix.length;
            int col = matrix[0].length;
            int[][] lefts = new int[row][col];
            int[][] rights = new int[row][col];
            int[][] heights = new int[row][col];
            int[] leftObs = new int[col];
            int[] rightObs = new int[col];
            
            findLeftRightObs(0, matrix, leftObs, rightObs);
            
            for(int i=0; i<col; i++){
                if(matrix[0][i] != '0'){
                    heights[0][i] = 1;
                    lefts[0][i] = leftObs[i];
                    rights[0][i] = rightObs[i];
                }
            }
            
            for(int i=1; i<row; i++){
                findLeftRightObs(i, matrix, leftObs, rightObs);
                for(int j=0; j<col; j++){
                    if(matrix[i][j] != '0'){
                        if(matrix[i-1][j] == '0'){
                            heights[i][j] = 1;
                            lefts[i][j] = leftObs[j];
                            rights[i][j] = rightObs[j];
                        }
                        else{
                            heights[i][j] = 1+heights[i-1][j];
                            lefts[i][j] = (int)Math.max(lefts[i-1][j], leftObs[j]);
                            rights[i][j] = (int)Math.min(rights[i-1][j], rightObs[j]);
                        }
                    }
                }
            }
            int max = 0;
            for(int i=0; i<row; i++){
                for(int j=0; j<col; j++){
                    if((rights[i][j]-lefts[i][j])*heights[i][j]>max){
                        max = (rights[i][j]-lefts[i][j])*heights[i][j];
                    }
                }
            }
            return max;
        }
    }
    
    public void findLeftRightObs(int row, char[][] matrix, int[] leftObs, int[] rightObs){
        int obs = 0;
        for(int i=0; i<matrix[0].length; i++){
            if(matrix[row][i] == '0'){
                leftObs[i] = i;
                obs = i+1;
            }
            else{
                leftObs[i] = obs;
            }
        }
        obs = matrix[0].length;
        for(int i=matrix[0].length-1; i>=0; i--){
            if(matrix[row][i] == '0'){
                rightObs[i] = obs;
                obs = i;
            }
            else{
                rightObs[i] = obs;
            }
        }
    }

no its not.
ie. you have sticks length 1,2,3
case 1:
you put 1 and 2 together first, cost1 = 1+2 = 3, and you have sticks length 3,3
then you put 3 in, cost2 = 3+3=6;
so the total cost = cost1+cost2 = 3+6 = 9;

case 2"
you put 2 and 3 together first, cost1 = 2+3 =5, and you have sticks length 1,5
then you put 1 in, cost2 = 1+5=6;
so the total cost =cost1+cost2 = 5+6 = 11;

there is simply NO NEED to sort it.

i agree, its just a modified version of sort 0,1,2s.

this is just a backtracking solution

public static ArrayList<ArrayList<Integer>> sumSubset(int[] a, int start, int target, 
            ArrayList<ArrayList<Integer>> result, ArrayList<Integer> cur){
        if(target==0){
            result.add(new ArrayList<Integer>(cur));
        }
        else if(target>0){
            int i = start;
            while(i<a.length && a[i]<=target){
                if(i==0 || i==start || a[i]!=a[i-1]){
                    cur.add(a[i]);
                    sumSubset(a, i+1, target-a[i], result, cur);
                    cur.remove(cur.size()-1);
                }
                i++;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        int[] a = new int[]{1,2,2,3,4,5};
        res = sumSubset(a,0,5,res, new ArrayList<Integer>());
    }

there's a way to do O(1) space tree traversal, which is called Morris Traversal. the idea is to add additional right link to a right leaf node's successor

my implementation based on this algorithm

static boolean anaStrStr (String needle, String haystack){
        Map<Character, Integer> needleMap = new HashMap<Character, Integer>();
        for(int i=0; i<needle.length(); i++){
            char c = needle.charAt(i);
            if(needleMap.get(c)!=null){
                needleMap.put(c, needleMap.get(c)+1);
            }
            else{
                needleMap.put(c, 1);
            }
        }
        int diff = needle.length();
        Map<Character, Integer> haystackMap = new HashMap<Character, Integer>();
        for(int i=0; i<needle.length(); i++){
            char c = haystack.charAt(i);
            if(haystackMap.get(c)!=null){
                haystackMap.put(c, haystackMap.get(c)+1);
            }
            else{
                haystackMap.put(c, 1);
            }
            if(needleMap.get(c)!=null && needleMap.get(c)>=haystackMap.get(c)){
                diff--;
            }
        }
        
        for(int i=needle.length(); i<haystack.length(); i++){
            if(diff==0){
                return true;
            }
            char c = haystack.charAt(i-needle.length());
            haystackMap.put(c, haystackMap.get(c)-1);
            if(needleMap.get(c)!=null && needleMap.get(c)>haystackMap.get(c)){
                diff++;
            }
            
            c = haystack.charAt(i);
            if(haystackMap.get(c)!=null){
                haystackMap.put(c, haystackMap.get(c)+1);
            }
            else{
                haystackMap.put(c, 1);
            }
            if(needleMap.get(c)!=null && needleMap.get(c)>=haystackMap.get(c)){
                diff--;
            }
        }
        return false;
    }

WOW!

sometimes it frustrates me when people just post so many question on the page and none of them seems like a real interview question (or he had that many interviews a day???)

the breaking point for {1,0,0,1} is {0,1,2} because
1 = 0+0+1
1+0 = 0 + 1
1+0+0 = 1

i think you can just turn both to all lowercase and compare? to use extra O(2^n) time and space just for finding if the hidden string matches a give string doesn't make any sense to me.

keep a map M of lists such that map.get(i) = lists of nodes that points to (i) minus the i-th node;
also keep a set S of good nodes, initialize with the tail node;
then starting from the list of nodes that point to the tail node, proceed the lists and mark every node a good node (put it in the set S); repeat this step with nodes in the list;
finish when every node in the list is already a good node or the list is empty;

it seems kind of impossible, especially in 40mins :(

word = "hirre";

this returns true but it should be false since you got 1 extra 'r'

just keep a count of the first char and compare to the others on the way through, reset the letters index when finish one check

public static boolean isValidWord(String word, char[] letters){
        if(word==null || word.isEmpty() || letters==null || letters.length==0){
            return false;
        }
        else{
            int index = 0;
            int count = 0;
            int tmpCount = 0;
            for(int i=0;  i<word.length(); i++){
                if(word.charAt(i)==letters[index]){
                    if(index==0){
                        count++;
                    }
                    tmpCount++;
                }
                else if(word.charAt(i)!=letters[index] && tmpCount!=count){
                    //not matching letters[index]
                    return false;
                }
                else if(word.charAt(i)!=letters[index] && index==letters.length-1){
                    //end of 1 valid word
                    index = 0;
                    i--;
                    tmpCount=0;
                    count = 0;
                }
                else if(word.charAt(i)!=letters[index]){
                    index++;
                    i--;
                    tmpCount=0;
                }
            }
            if(index==letters.length-1 && tmpCount==count){
                return true;
            }
            else{
                return false;
            }
        }
}

public static void main(String[] args) {
        System.out.println(isValidWord("HIREHHIIRREE", new char[]{'H','I','R','E'})); //true
        System.out.println(isValidWord("HIREHHIIRRREE", new char[]{'H','I','R','E'})); //false
        System.out.println(isValidWord("HIREHHIIRREEHIE", new char[]{'H','I','R','E'})); //false

}

if you see the number is N, not the number of bits in binary representation, then N can be divide by 2 at most log(N) times.

+1. this is very clean and easy to understand.

if you visit same destination (i.e. you go to city X to transfer more than 1 time), you cant really know the order anymore. (because i.e first time is X->Y and second time is X->Z you cant tell the order )

My idea is use map. it's O(n) time and O(n) space where n is the number is nodes
Given a list of nodes
1. put nodes in a hashmap
2. find the direct child nodes of each node and put it in a hash map
---1) make a new HashMap<Integer, ArrayList<Node>> (ie name it map)
---2) for each node, map.put(node.id, new ArrayList<Node>())
---3) for each node, map.get(node.parent.id).add(node.id)
3. make a new HashMap<Integer, Integer> (ie name it weight) which the id is key and weight is value
4. for each key->value in map,
for each subelement in value, process them

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution{
public static void main(String[] args){
        //10,30,1 
        //30,0,10 
        //20,30,2 
        //50,40,3 
        //40,30,4 
        ArrayList<Node> nodes = new ArrayList<Node>();
        nodes.add(new Node(10,30,1));
        nodes.add(new Node(30,0,10));
        nodes.add(new Node(20,30,2));
        nodes.add(new Node(50,40,3));
        nodes.add(new Node(40,30,4));
        Map<Node, Integer> weight =getSubTreeWeight(nodes);
                int i=1;

    }
    
    public static Map<Node, Integer> getSubTreeWeight(List<Node> nodes){
	Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
	for(int i=0; i<nodes.size();i++){
		nodeMap.put(nodes.get(i).id, nodes.get(i));
	}
	
	Map<Integer, ArrayList<Node>> childMap = new HashMap<Integer, ArrayList<Node>>();
	for(int i=0; i<nodes.size();i++){
		childMap.put(nodes.get(i).id, new ArrayList<Node>());
	}

	for(int i=0; i<nodes.size(); i++){
                if(childMap.get(nodes.get(i).parentId)!=null){
			childMap.get(nodes.get(i).parentId).add(nodes.get(i));
		}
        }

	Map<Node, Integer> weightMap = new HashMap<Node, Integer>();
	for(Node n : nodeMap.values()){
		if(weightMap.get(n)==null){
				calculateWeight(n, childMap, weightMap);
		}
	}

	return weightMap;
}

public static void calculateWeight(Node n, Map<Integer, ArrayList<Node>> childMap, Map<Node,Integer> weightMap){
	if(childMap.get(n.id).isEmpty()){//no child
		weightMap.put(n, n.weight);
	}
	else{
		int weight = n.weight;
		for(Node child : childMap.get(n.id)){
			if(weightMap.get(child)==null){
				calculateWeight(child, childMap, weightMap);
			}
			weight+= weightMap.get(child);
		}
		weightMap.put(n, weight);
	}

}
}

class Node {
   int id;
   int parentId;
   int weight;

   Node(int id, int parentId, int weight){
      this.id = id;
      this.parentId = parentId;
      this.weight = weight;
}
}

a recursive solution in java.
*assume denom is sorted or we can just sort it

public static void getForms(int n, ArrayList<Integer> denom, int start, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result){
        if(n==0){
            result.add(new ArrayList<Integer>(current));
        }
        else{
            for(int i=start; i<denom.size(); i++){
                if(n>=denom.get(i)){
                    current.add(denom.get(i));
                    getForms(n-denom.get(i), denom, i, current, result);
                    current.remove(current.size()-1);
                }
            }
        }
    }
    
    public static void main(String[] args){
        ArrayList<Integer> denom = new ArrayList<Integer>();
        denom.add(1); denom.add(2); denom.add(3);
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        getForms(5, denom, 0, new ArrayList<Integer>(), result);
        int i=1;

}

i think it's O(n) for the second method. you have to go to the left and right subarray anyways.

+1. usually they will accept the Hash Table answer (because of space problem) but this is more accurate.

for

s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i]+...+a[j]) == 0

should it be

(s[j]-s[i])%7 == ((a[1]+...+a[j]) - (a[1]+...+a[i]))%7 == (a[i]+...+a[j])%7 == 0

and also need to consider the case when the a[0]%7==0 but that's trivial.
good algorithm

good job

this code will create a loop

public static int findNumOfPalindromes(String s) {
//        Find number of palindromes in a string
        if (s == null || s.isEmpty()) {
            return 0;
        } else if (s.length() == 1) {
            return 1;
        } else {
            int res = s.length();
            for (int i = 0; i < s.length() - 1; i++) {
                boolean broke = false;
                int dif = 1;
                while (!broke && i - dif >= 0 && i + dif < s.length()) {
                        if (s.charAt(i - dif) == s.charAt(i + dif)) {
                            res++;
                        } else {
                            broke = true;
                        }
                        dif++;
                }
                if (s.charAt(i) == s.charAt(i + 1)) {
                    dif = 1;
                    broke = false;
                    res++;
                    while (!broke && i - dif >= 0 && i + 1 + dif < s.length()) {
                            if (s.charAt(i - dif) == s.charAt(i + 1 + dif)) {
                                res++;
                            } else {
                                broke = true;
                            }
                        dif++;
                    }
                }
            }
            return res;
        }
    }

i was asked this once. that's the exact solution the interviewers were looking for. :)

i think this really should be sub array too... hmmm

public static String maxSubStringWithoutDuplicate(String s){
    //    Given s string, Find max size of a sub-string, in which no duplicate chars present.
        if(s==null || s.isEmpty()){
            return s;
        }
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        String max = "";
        int curLen = 0;
        int start = 0;
        for(int i=0; i<s.length(); i++){
            if(map.get(s.charAt(i))==null || map.get(s.charAt(i))==-1 || map.get(s.charAt(i)) <start){
                map.put(s.charAt(i), i);
                curLen++;
                
            }
            else{
                if(curLen > max.length()){
                    max = s.substring(start, start+curLen);
                }
                if(curLen > map.get(s.charAt(i))-i){
                    curLen-= map.get(s.charAt(i))-start;
                    start = map.get(s.charAt(i))+1;

                }
                else{
                    start = i;
                    curLen = 0;
                }
                map.put(s.charAt(i), i);
                
            }
        }
        return max;
        
    }