1. Hanoi:

public  void move(int n,char a,char b,char c){  

    if(n==1){  
        System.out.println("move from "+a+" to "+c);  
    }else{  
        move(n-1, a,c,b);  
        move(1, a, b, c);  
        move(n-1, b, a, c);  
    }  
}  

1. Queue:

These days, I have been asked by some questions in interviews. These are not quite difficult questions, but I suppose I didn’t behavior well. There are some reasons I think, and I have to improve it:

1. I am not familiar with the simple and basic question so that I’m not very sure about the solution’s correctness and I have to review it again and again.
2. My code is not so effienct and some of the interviewers had to remind me that. That’s really terrible but I think they are very nice to let me know that.
3. My code is not so clean because I didn’t keep a clean mind that time. I suppose it’s kind of nervous that time though I didn’t realize that and I want to solve that problem too hurry. I need to relax my minds next time.
4. What’s worse, I didn’t have nice communication with interviewers. Because of my bad English and bad preperation for interview. Sorry about that.

And below are some questions I have to review:

1. How to realize a queue or stack using array or linkedlist
2. Binary search and whenever mentioning the sorted array, I think it should come into my mind immediately the binary search
3. Graph theory about the DFS and BFS
4. What’s difference between .equals and == in Java
5. Heap and stack in java
6. Some detials and desing thoughts of my projects
7. ood object oriented design principles (https://scotch.io/bar-talk/s-o-l-i-d-the-first-five-principles-of-object-oriented-design)
8. The comparasion between the methods of shortest path (http://developer.51cto.com/art/201105/262170.htm)
9. Hanoi (http://blog.csdn.net/zhutulang/article/details/7491390)
10. Maze (http://baobaoyangzhou.blog.163.com/blog/static/11783125020104147195273/)
11. The realization of DFS not using recursive (http://blog.csdn.net/lalor/article/details/6845788) which use stack

Question:

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.

Hint:

How many majority elements could it possibly have?

Thinking:

This question is similar with Majority Element which can be solved by Boyer–Moore majority vote algorithm.

Solution:

public List<Integer> majorityElement(int[] nums) {
    List<Integer> res = new ArrayList<Integer>();
    int count1 = 0, count2 = 0, can1 = 0, can2 = 1;

    for (int num: nums){
        if (num == can1)
            count1++;
        else if (num == can2)
            count2++;
        else if (count1 == 0){
            can1 = num;
            count1 = 1;
        }
        else if (count2 == 0){
            can2 = num;
            count2 = 1;
        }
        else{
            count1--;
            count2--;
        }
    }
    count1 = 0;
    count2 = 0;
    for (int num: nums){
        if (num == can1)
            count1++;
        else if (num == can2)
            count2++;
    }

    if (count1 > nums.length / 3)
        res.add(can1);
    if (count2 > nums.length / 3 && can1 != can2)
        res.add(can2);

    return res;
}

Question:

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Thinking:

I assume every node has no val, but edges do. So I keep a HashMap for everynode. What’s more, in order to determine whether this node is a leave, I add another boolean value.

Solution:

import java.util.HashMap;

class TrieNode {
    HashMap<Character, TrieNode> edges = new HashMap<Character, TrieNode>();
    boolean leave = false;
    // Initialize your data structure here.
    public TrieNode() {
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode cur = root;
        for (char c: word.toCharArray()){
            if (!cur.edges.containsKey(c)){
                TrieNode newNode = new TrieNode();
                cur.edges.put(c, newNode);
                cur = newNode;

            }
            else {
                cur = cur.edges.get(c);
            }
        }
        cur.leave = true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode cur = root;
        for (char c: word.toCharArray()){
            if (!cur.edges.containsKey(c)){
                return false;
            }
            else{
                cur = cur.edges.get(c);
            }
        }
        return cur.leave;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c: prefix.toCharArray()){
            if (!cur.edges.containsKey(c)){
                return false;
            }
            else{
                cur = cur.edges.get(c);
            }
        }
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

Question:

Implement int sqrt(int x).

Compute and return the square root of x.

Thinking:

We can get the answer using bianry search from the range of integer.

Solution:

public int mySqrt(int x) {
    if ( x <= 1 )
        return x;
    int low = 1;
    int high = Integer.MAX_VALUE;
    while (true){
        int mid = low + (high - low) / 2; //in order to avoid overflow
        if (mid > x / mid){
            high = mid - 1;
        }else{
            if ( (mid+1) > x/(mid+1))
                return mid;
            low = mid + 1;
        }
    }
}