microsoft _screen_onsite.java

// hello, Frank


//input: "this is a test"
//output: "test a is this"

// "hello " -> " hello"
// "  hello " -> " hello  "

public String reverseString(String s) {
    StringBuilder sb = new StringBuilder();
    
    int start = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ' ') {
            sb.insert(0, ' ').insert(0, s.substring(start, i));
            start = i + 1;
        }
    }
    sb.insert(0, s.substring(start, s.length()));
    return sb.toString();
} 

"this is a test"
"tset a si siht"
"test a is this"

public String reverseString2(String s) {
    char[] arr = s.toCharArray();
    reverseArr(arr, 0, s.length()-1);
    int start = 0;
    for (int end = 0; end < s.length(); end++) {
        if (arr[end] == ' ') {
            reverseArr(arr, start, end-1);
            start = end+1;
        }
    }
    reverseArr(arr, start, s.length()-1);
    return arr.toString();    
}

private void reverseArr(char[] arr, int start, int end) {
    while (start < end) {
        char tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
        start++;
        end--;
    }
}

// Given a binary Tree, find if it is symmtric tree
TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

public boolean isSymmtric(TreeNode root) {
    if (root == null) return true;
    return isSymmtric(root.left, root.right);
}

private boolean isSymmtric(TreeNode rootLeft, TreeNode rootRight) {
    if (rootLeft == null && rootRight == null) return true;
    if (rootLeft == null || rootRight == null) return false;
    if (rootLeft.val != rootRight.val) return false;
    return isSymmtric(rootLeft.left, rootRight.right) && isSymmtric(rootLeft.right, rootRight.left);
}