Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region. For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give? public class Solution { public int candy(int[] ratings) { int[] candies = new int[ratings.length]; for(int i=0;

A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12). The number of ways decoding “12” is 2. Solution: public class Solution { public int numDecodings(String s) { if(s==null || s.length()==0 || s.charAt(0)=='0') return 0; int[] dp = new int[s.length()+1]; dp[0] = 1; dp[1] = 1; for(int i=1; i<s.length(); i++){ int a = Integer.valueOf(s.substring(i,i+1)); int ba = Integer.valueOf(s.substring(i-1,i+1)); if(a!=0) dp[i+1] = dp[i]; if(ba>=10 && ba<=26) dp[i+1] += dp[i-1]; } return dp[s.length()]; } } Solution: public class Solution { public int numDecodings(String s) { if(s.length()==0) return 0; int[] dp = new int[s.length()+1]; dp[0] = 1; dp[1] = s.charAt(0)=='0' ?

Given a binary tree, return the postorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class

Given a binary tree, return the preorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 2 / 3 return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? Solution 1: recursive /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); preorderTraversal(root, ans); return ans; } public void preorderTraversal(TreeNode root, List<Integer> list) { if(root==null) return; list.add(root.val); preorderTraversal(root.left, list); preorderTraversal(root.right, list); } } Solution 2: iterative /** * Definition for a binary tree node.

Invert a binary tree. 4 / 2 7 / \ / 1 3 6 9 to 4 / 7 2 / \ / 9 6 3 1 Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode invertTree(TreeNode root) {

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1: 2 / 1 3 Binary tree [2,1,3], return true.

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation – it essentially peek() at the element that will be returned by the next call to next(). Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3]. Call next() gets you 1, the first element in the list. Now you call peek() and it returns 2, the next element.

Given a binary tree, return the inorder traversal of its nodes’ values. For example: Given binary tree [1,null,2,3], 1 2 / 3 return [1,3,2]. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ans =

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree. Solution: /** * Definition for binary tree * public class TreeNode { * int val; *