Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space. Solution: public class Solution { public List<Integer> majorityElement(int[] nums) { int num1=0, num2=1, count1=0, count2=0; for(int i=0; i<nums.length; i++){ if(nums[i]==num1) count1++; else if(nums[i]==num2) count2++; else if(count1==0){ num1 = nums[i]; count1 = 1; } else if(count2==0){ num2 = nums[i]; count2 = 1;

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Solution: public class Solution { public int majorityElement(int[] nums) { int num=0, count=0; for(int n : nums){ if(n==num) count++; else if(count==0){ num = n; count = 1; } else

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right;

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. For example, given s = “aab”, Return 1 since the palindrome partitioning [“aa”,“b”] could be produced using 1 cut. Solution: public class Solution { public int minCut(String s) { if(s.length()==0) return 0; int[] dp = new int[s.length()+1]; for(int i=0; i<=s.length(); i++) dp[i] =

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] Solution: /** * Definition for a binary tree node. * public class TreeNode

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area. For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 6. Solution: public class Solution { public int maximalRectangle(char[][] matrix) { if(matrix.length==0) return 0; int m = matrix.length, n = matrix[0].length; int[]

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 4. Solution: public class Solution { public int maximalSquare(char[][] matrix) { if(matrix.length==0) return 0; int[][] dp = new int[matrix.length+1][matrix[0].length+1]; int max =

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST’s. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 Solution: public class Solution { public int numTrees(int n) { int[] dp = new int[n+1]; dp[0] =

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n. For example, Given n = 3, your program should return all 5 unique BST’s shown below. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 Solution: /** * Definition for a binary tree node. * public class TreeNode

Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero. You may assume that the given expression is always valid. Some examples: "3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5 Note: Do not use the eval built-in library function. Solution: