Recursive & DP - Binary Tree Maximum Path Sum

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        if(root == null){
            return 0;
        }
        int[] result = new int[2];
        result = maxPathSumTracker(root);
        return result[1];
    }
 
    private int[] maxPathSumTracker(TreeNode node){
        int[] result = new int[2];
        if(node == null){
            result[1] = Integer.MIN_VALUE;
            return result;
        }
        int[] resultLeft = maxPathSumTracker(node.left);
        int[] resultRight = maxPathSumTracker(node.right);
        result[0] = Math.max(Math.max(resultLeft[0], resultRight[0]) + node.val,  node.value);
        result[1] = Math.max(Math.max(resultLeft[1], resultRight[1]), Math.max(resultLeft[0] + node.val + resultRight[0], result[0]));
        return result;
    }
}

Bit Solution - Find missing element in an array *

There are few solutions: 

   1. Add from 1 to N, and minus each element from the array, the remaining is the result;

   2. Improved from solution 1, as the sum could be too large. Use the XOR for from 0 to N, and then XOR each element in the array, the remaining is the result. 

   3. But solution 1 and 2 are not good for duplicates, so another solution is proposed,as an array size of the biggest element in the array, loop the array then find the one(s) appear zero times.

   4. Improved from solution 3, as the integer array takes O(n) space, and bit is enough for this problem. Use integer which is 32 bits instead of array which could save 31 times space. 1 means appearance, and 0 otherwise. 

public class FindMissingK {

public static void main(String[] args) {

int[] input = { 3, 1, 2, 4, 0 };

System.out.println(findMissKValue(input, 5));

}

private static int findMissKValue(int[] inputs, int n) {

int process = 0;

for (int i = 1; i <= n; i++) {

process = process ^ i;

}

for (int i = 0; i < inputs.length; i++) {

// if (inputs[i] != 0) {

process = process ^ inputs[i];

// }

}

return process;

}

}

String Solution - Find positions of each word (in dictionary) in a given text *

http://en.wikipedia.org/wiki/Aho–Corasick_string_matching_algorithm, KMP are two optical ways to resolve this problem, but they are too complicated for a one hour interview. So the solution below is an acceptable solution. Loop the dict and find one a time in the pass in text.

public class FindInstrumentName {

public static void main(String[] args) {

String[] inputs = { "dog", "cat", "pig" };

String text = "a dogkcat pig playcat,pigdone";

Map<Integer, String> test = findInstruments(inputs, text);

Set<Integer> resSet = test.keySet();

Iterator it = resSet.iterator();

System.out.println(text.length());

while (it.hasNext()) {

int curIndex = (Integer) it.next();

System.out.println(curIndex + "->" + test.get(curIndex));

}

}

private static Map<Integer, String> findInstruments(String[] dict,

String text) {

Map<Integer, String> result = new HashMap<Integer, String>();

for (int i = 0; i < dict.length; i++) {

findInstrumentOps(dict[i], text, result);

}

return result;

}

private static void findInstrumentOps(String word, String text,

Map<Integer, String> result) {

for (int i = 0; i <= text.length() - word.length(); i++) {

int j = 0;

int index = i;

while (j < word.length()) {

if (!(isValiedCharacter(text.charAt(i)))) {

i++;

continue;

}

if (text.charAt(i) != word.charAt(j)) {

break;

}

if (j == word.length() - 1) {

result.put(index, word);

}

i++;

j++;

}

}

}

private static boolean isValiedCharacter(char c) {

if (c <= 'z' && c >= 'a') {

return true;

}

return false;

}

}

Loop Solution - Palindrome Number

public class Solution {
    public boolean isPalindrome(int x) {
     
        if(x < 0){
            return false;
        }
     
        // Stack<Integer> processStack = new Stack<Integer>();
        // Queue<Integer> processQueue = new LinkedList<Integer>();
        // //int divide = x / 10;
        // //int remain = x % 10;
        // while(x / 10 != 0 || x % 10 != 0){
        //     processStack.push(x % 10);
        //     processQueue.offer(x % 10);
        //     x = x / 10;
        // }
     
        // while(!processStack.isEmpty() && !processQueue.isEmpty()){
        //     if(processStack.pop() != processQueue.poll()){
        //         return false;
        //     }
        // }
     
        // if(!processStack.isEmpty() || !processQueue.isEmpty()){
        //     return false;
        // }
     
        // return true;
     
        int size = 0;
        int base = x;
        while(base / 10 != 0 || base % 10 != 0){
            ++size;
            base = base / 10;
        }
        int[] process = new int[size];
        while((x / 10 != 0 || x % 10 != 0) && size >= 0){
            process[--size] = x % 10;
            x = x / 10;
        }
        int lpS = 0;
        int lpE = process.length - 1;
        while(lpS < lpE){
            if(process[lpS] != process[lpE]){
                return false;
            }
            lpS++;
            lpE--;
        }
     
        return true;
    }
}

Loop Solution - Minimum Window Substring ***??

class Solution {
public:
    string minWindow(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (S.size()<T.size()){return "";}
           
        map<char,int>mp; // store chars occurrence of T
        for(int i=0;i<T.size();i++){mp[T[i]]++;}
       
        int res_len=INT_MAX; // result length
        int res_p=0;//result start posiion
       
        int p=0; //pointer start
        int q=S.size()-1; //pointer end
       
        while (mp[S[p]]==0){if(p>=S.size()){return "";} p++;} //remove irralevent starting chars
        while (mp[S[p]]==0){q--;if(q<0){return "";}} // remove irralevent ending chars
       
        map<char,int> tab; //store chars occurrence of S[p:q]
        for (int i=p;i<=q;i++){tab[S[i]]++;}
                   
        while (tab[S[q]]>mp[S[q]] || mp[S[q]]==0){ // move q to left find the 1st covered substring
           tab[S[q]]--;
           q--;
        }
           
        for (int i=0;i<T.size();i++){  // if no covered substring found, return ""
            if (tab[T[i]]<mp[T[i]]){return "";}
        }
   
        if (q-p+1<res_len){res_len=q-p+1; res_p=p;} //store the result
       
       
        while (p<q){
            if (q-p+1<res_len){res_len=q-p+1; res_p=p;} //store the result
            if (mp[S[p]]==0){p++;continue;} // if current char is not in T, go next
            if (tab[S[p]]>mp[S[p]]){tab[S[p]]--;p++;continue;} // if more chars in this substring, go next
           
            q++;
            while (q<S.size() && S[q]!=S[p]){ if (mp[S[q]]>0){tab[S[q]]++;} q++;} //move q to find a substring covers T
            if (q>=S.size()){q=S.size()-1;}else{tab[S[q]]++;}
           
            if (S[q]==S[p]){ tab[S[p]]--; if (tab[S[p]]<mp[S[p]]){break;} p++;continue;}      
            break;
        }
       
        return S.substr(res_p,res_len);
    }
};

Bit Operation Solution - Divide Two Integers ??

public class Solution {
    public int divide(int dividend, int divisor) {
        long a = Math.abs((long) dividend), b=Math.abs((long) divisor);
        long[] res= dividePos(a,b);
        long temp = dividend>0&&divisor<0||dividend<0&&divisor>0?-res[0]:res[0];
        return (int) temp;
    }
   
    public long[] dividePos(long a, long b){
        long[] res = new long[2];
        if(a<b){
            res[0]=0;
            res[1]=a;
        }else if(a==b){
            res[0]=1;
            res[1]=0;
        }else{
            long[] temp=dividePos(a>>1,b);
            res[0] = temp[0]<<1;
            res[1] = temp[1]<<1;
            if((a & 1)==1) res[1]+=1;
            if(res[1]>=b){
                res[0]+=1;
                res[1]-=b;
            }
        }
        return res;
    }
}

N Queen II ?

class Solution {
public:
    int res;
     
    bool isValid(int A[], int r){
        for (int i=0;i<r;i++){
            if ( (A[i]==A[r])||(abs(A[i]-A[r])==(r-i))){
                return false;
            }
        }
        return true;
    }
    void nqueens(int A[], int cur, int n){
        if (cur==n){ res++;return;}
        else{
            for (int i=0;i<n;i++){
                A[cur]=i;
                if (isValid(A,cur)){
                    nqueens(A,cur+1,n);
                }
            }
        }
    }
    int totalNQueens(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        res=0;
        int *A = new int[n];
        nqueens(A,0,n);
        return res;
    }
};