When I wrote code for these two questions, I first write the Maximum depth of a BST, pretty neat and simple. Code is as following:
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int ldepth = maxDepth(root.left);
int rdepth = maxDepth(root.right);
return (ldepth > rdepth ? ldepth:rdepth)+1;
}
However, intuitively I continued to write the min depth of a BST. Then I encountered problems.
The following code is wrong!!!! Buggy!!!!
public int minDepth(TreeNode root) {
if(root == null) return 0;
int ldepth = minDepth(root.left);
int rdepth = minDepth(root.right);
return (ldepth < rdepth ? ldepth:rdepth)+1;
}
Actually, I made a mistake since I didn’t notice the exit point for recursion is not the same as the maximum depth of BST. If a tree is really empty, then the minDepth should be 0; but for the exit of recursion in the function minDepth, it should be return a relative large number… I saw a great deal code online are totally wrong with ignorance of exit point of recursion. So be careful.
The following should be the right code:
public int minDepth(TreeNode root) {
if(root == null)
return 0;
return minD(root);
}
int minD(TreeNode root){
if(root == null){
return 9999999;
}
if(root.left == null && root.right == null)
return 1;
int ld = minD(root.left);
int rd = minD(root.right);
return Math.min(ld,rd)+1;
}
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
How do you find an element in the rotated array efficiently?
You may assume no duplicate exists in the array.
// this is more general than binary search
// as it works for both rotated and non-rotated arrays.
// 10/17/13
public class sortedRotatedArray {
static boolean searchinsortedRotatedArray(int[] a,int key){
int start = 0;
int end = a.length -1;
while(start <= end){
//for the following loops, really really be careful about all the "=" sign...
//to avoid overflow concerns same result as (start+end)/2;
int mid = start + (end-start)/2;
if(a[mid] == key) return true;
//the left half is sorted
if(a[start] <= a[mid]){
if(a[start] <= key && key <= a[mid]){
end = mid - 1;
}
else{
start = mid +1;
}
}
else{
if(a[mid] <= key && key <= a[end]){
start = mid+1;
}
else{
end = mid - 1;
}
}
}
return false;
}
// Input – List<String> [“star”, “rats”, “ice”, “cie”, “arts”]
// print all anagrams in buckets:
// [“star”, “rats”, “arts”]
// [“ice”, “cie”]
package String;
import java.util.*;
public class anagramInBucket {
static void anagrams(ArrayList<String> a){
Hashtable<String, ArrayList<String>> h = new Hashtable<>();
for(String s:a){
char[] array = s.toCharArray();
Arrays.sort(array);
String sortedS = String.valueOf(array);
if( !h.keySet().contains(sortedS)){
ArrayList<String> value = new ArrayList<String>();
value.add(s);
h.put(sortedS, value);
}
else{
ArrayList<String> existingVal = h.get(sortedS);
existingVal.add(s);
h.put(sortedS, existingVal);
}
}
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>> ();
result.addAll(h.values());
for(ArrayList<String> ad:result){
System.out.print(ad);
}
}
public static void main(String[] args){
ArrayList<String> s = new ArrayList<String>();
s.add("star");
s.add("rats");
s.add("ice");
s.add("cie");
s.add("arts");
anagramInBucket.anagrams(s);
}
}
Write a function that calculates input strings with operators +,-,*,/ eg.
“5+5*6” should output 35
I had this interview question in my interview with EBay(Feb. 2013) – which is also my first technical interview writing code on white board in my life.
IT’S not easy to write clean code during 30min for the interview. For this question, I messed up that “*” and “/” have higher priority than “+” and “-“.
When I went back home, I worked on this question another time, but still didn’t find a neat way solving it… until today when I was trying to solve some stacks questions.
SO the answer is using two stacks – one for operands and one for operators. Keep pushing in operator as long as the newly pushed operator has higher precedence than the “top of stack ” operator. if not, pop out 2 operands and calculate result and again push it on stack…
I will put my code here after tomorrow’s interview with Facebook. For now, I need some sleep… 😉
GOOD Night, Emma. GOOD Night, Seattle.
This problem is pretty interesting since this is my first time to hear about Gray Code concepts. The details could be found in Wiki.
Let’s go through some examples here:
n=1 0, 1
n=2 00, 01, 11, 10
n=3 000, 001, 011, 010, 111, 110, 101, 100
We can see when n=3, the value of first four numbers are unchanged from n=2. The second four numbers are computed by adding the numbers(n=2) to 100. 100 is a kind of highest digit, which could get from 1<<(n-1).
Thus, we could have the recursion.
n=0 return a list with only 0
n=1 return a list with 1 and 0
n>1 return a list with: 1. the previous(n-1) list 2. for each element in previous list add the highest bit with each number and store in the new result.
Cod is as:
public static ArrayList<Integer> code(int n) {
ArrayList<Integer> resultList = new ArrayList<Integer>();
if (n <= 1) {
resultList.add(0);
if (n == 1) resultList.add(1);
return resultList;
}
ArrayList<Integer> prevList = code(n - 1);
int highest_bit = 1 << (n - 1);
for (int i = prevList.size() - 1; i >= 0; i--) {
resultList.add(prevList.get(i) + highest_bit);
}
prevList.addAll(resultList);
return prevList;
}
Check if two strings are anagrams or not.
Two ways to check:
1. Sort two strings and compare if they are the same string after sorting.
2. Check if the frequency of each char in the string is same.
The following is method 2:
class Anagram{
static boolean Ana(String s1, String s2){
if(s1.length() != s2.length())
return false;
int[] a1 = new int[256];
int[] a2 = new int[256];
for(char c1:s1.toCharArray()){
a1[c1] = a1[c1] + 1;
}
for(char c2:s2.toCharArray()){
a2[c2] = a2[c2] + 1;
}
for(int j=0; j<a1.length; j++){
if(a1[j] != a2[j]) return false;
}
return true;
}
public static void main(String [] args)
{
String s1 = "abcded";
String s2 = "ddecab";
String s3 = "aaaaaa";
System.out.println(Anagram.Ana(s1,s2));
System.out.println(Anagram.Ana(s1,s3));
}
}
Using the thought of binary search and you could get the value closed to mid value.
class Sqrroot{
static double sqroot (double i)
{
if( i == 0 || i == 1) return i;
if(i < 0 ) return -1;
double start = 0;
double end = i;
double pre = 0.00001;
while(start < end - pre)
{
double mid = (start + end)/2 ;
double midSqr = mid * mid;
//we need to consider this situation as well
if(i < 1) end = 1;
if(midSqr == i) return mid;
//this means mid < real sqr root
//put the start from mid
else if(midSqr < i){
start = mid;
}
else{
end = mid;
}
}
return (start+end)/2;
}
public static void main(String[] args){
System.out.println(Sqrroot.sqroot(0.5));
System.out.println(Sqrroot.sqroot(5));
System.out.println(Sqrroot.sqroot(500));
}
}
The Binary Search algorithm is pretty neat and the efficiency is O(nlogn). It requires that the array should be sorted.
public class binarySearch{
static Boolean search(int [] a, int t){
if(a.length == 0) return false;
int low = 0;
int high = a.length - 1;
while( low <= high)
{
int mid = (low+high)/2;
if(a[mid] == t) return true;
if(a[mid] < t){
low = mid + 1;
}
else{
high = high -1 ;
}
}
return false;
}
public static void main(String[] args)
{
int[] a = {1,2,3,4,4,5,5,6,7,7,8};
System.out.println(binarySearch.search(a, 0));
}
}
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,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
if(root == null){
ArrayList<Integer> a = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
return result;
}
int cur = 0;
int next = 0;
Queue<TreeNode> q = new LinkedList<TreeNode>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> a = new ArrayList<Integer>();
a.add(root.val);
result.add(a);
q.add(root);
cur++;
ArrayList<Integer> array = new ArrayList<Integer>();
while(!q.isEmpty()){
TreeNode n = q.remove();
cur --;
if(n.left != null){
q.add(n.left);
next++;
array.add(n.left.val);
}
if(n.right != null){
q.add(n.right);
next++;
array.add(n.right.val);
}
if(cur == 0){
if(!array.isEmpty()){
result.add(array);
}
cur = next;
next = 0;
//if we use clear here, the array in the result list will also be cleared.
array = new ArrayList<Integer>();
}
}
return result;
}
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
public boolean searchMatrix(int[][] matrix, int target) {
int col = matrix[0].length-1;
int row = 0;
while(row <= matrix.length -1 && col >= 0){
if(matrix[row][col] == target) return true;
else if(matrix[row][col] < target) row++;
else col--;
}
return false;
}
Emma's coding practice 