Coding questions encountered in the interview

Design class

1. Use Redis Realize a one minute lottery for a user 3 Time
2. Write a singleton pattern that you think is the best , Do you think there is any problem with this writing ？
   • Several ways to write the singleton pattern
     • Hungry Chinese style
     • Slacker type 、 Double check lock
     • Static inner class

public class Singleton {
    

    private Singleton(){
    }

    private static class SingletonHolder {
    
        private static final Singleton INSTANCE = new Singleton();
    }

    public static Singleton getInstance() {
    
        return SingletonHolder.INSTANCE;
    }

}

Enumeration class

	public enum SingletonEnum {
    
    	INSTANCE(1, "aa");
    	SingletonEnum(int value, String v) {
    
    	}
	}

-  How to destroy the singleton mode 

3. The strategy pattern demo
   my github Upper demo
4. Factory mode demo
   Design patterns demo
5. Write an observer pattern demo
   demo
6. Template method demo

Algorithm problem

1. Sort
   1. Bubble sort
   2. Merge sort
   3. Selection sort
   4. Insertion sort
   5. Quick sort

	public int[] sortArray(int[] nums) {
    
        if (nums == null) {
    
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quickSort(int[] numbers, int left, int right) {
    
        if (right <= left) {
    
            return;
        }
        int pivot = numbers[left];
        int start = left;
        int end = right;
        while (start < end) {
    
            while (start < end && pivot <= numbers[end]) {
    
                end--;
            }
            swapArr(numbers, start, end);
            while (start < end && numbers[start] <= pivot) {
    
                start++;
            }
            swapArr(numbers, start, end);
        }
        quickSort(numbers, left, start - 1);
        quickSort(numbers, start + 1, right);
    }

    private void swapArr(int[] numbers, int left, int right) {
    
        int temp = numbers[left];
        numbers[left] = numbers[right];
        numbers[right] = temp;
    }

2. The first, middle and last order traversal of the tree

    /* Depth first */
    /** *  The first sequence traversal  * @param root * @param linkedList */
    public static void preOrder(TreeNode root, List<TreeNode> linkedList) {
    
        if (root != null) {
    
            linkedList.add(root);
            preOrder(root.left, linkedList);
            preOrder(root.right, linkedList);
        }
    }

    /** *  In the sequence traversal  * @param root * @param linkedList */
    public static void inOrder(TreeNode root, List<TreeNode> linkedList) {
    
        if (root != null) {
    
            inOrder(root.left, linkedList);
            linkedList.add(root);
            inOrder(root.right, linkedList);
        }
    }

    /** *  After the sequence traversal  * @param root * @param linkedList */
    public static void postOrder(TreeNode root, List<TreeNode> linkedList) {
    
        if (root != null) {
    
            postOrder(root.left, linkedList);
            postOrder(root.right, linkedList);
            linkedList.add(root);
        }
    }

3. Restore the binary tree to the result of preorder and inorder traversal
4. Fiboracci series
5. Two points search

    public int search(int[] nums, int target) {
    
        if (nums == null) {
    
            return -1;
        }
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
    
            int middle = (low + high)/2;
            if (nums[middle] == target) {
    
                return middle;
            } else if (nums[middle] < target) {
    
                low = middle + 1;
            } else {
    
                high = middle - 1;
            }
        }
        return -1;
    }

6. Single list flip

    public ListNode reverseList(ListNode head) {
    
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
    
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

7. The number of occurrences of numbers in an array
8. Sum of two numbers 2sum

    public int[] twoSum(int[] nums, int target) {
    
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
    
            int temp = target - nums[i];
            if (map.containsKey(temp)) {
    
                return new int[]{
    map.get(temp), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }

9. Determine if the list has links

	//  Basic Edition   Advanced version can use speed pointer 
    public ListNode detectCycle(ListNode head) {
    
        Set<ListNode> nodeSet = new HashSet<ListNode>();
        ListNode item = head;
        int index = 0;
        while (item != null) {
    
            if (nodeSet.contains(item)) {
    
                return item;
            }
            nodeSet.add(item);
            item = item.next;
        }
        return null;
    }

10. Merge two ordered arrays

	//  Double pointer 
    public void merge(int[] nums1, int m, int[] nums2, int n) {
    
        int[] temp = new int[nums1.length];
        int mp = 0, np = 0;
        for (int i = 0; i < temp.length; i++) {
    
            if (mp < m && np < n) {
    
                if (nums1[mp] < nums2[np]) {
    
                    temp[i] = nums1[mp++];
                } else if (nums2[np] < nums1[mp]) {
    
                    temp[i] = nums2[np++];
                } else {
    
                    temp[i++] = nums1[mp++];
                    temp[i] = nums2[np++];
                }
                continue;
            }
            if (np < n) {
    
                temp[i] = nums2[np++];
                continue;
            }
            if (mp < m) {
    
                temp[i] = nums1[mp++];
            }

        }
        if (m >= 0) System.arraycopy(temp, 0, nums1, 0 ,temp.length);
    }

11. Merge two arrays
    You can sort it first , After the merger
12. Palindrome number
    Turn it over first , To determine
13. Flip integers

    public int reverse(int x) {
    
        long result = 0;
        while (x != 0) {
    
            result = result*10 + x%10;
            x = x/10;
        }
        //  Pay attention to the judgment of crossing the boundary 
        return result > 0x7fffffff || result < 0x80000000 ? 0 : (int)result;
    }

14. Delete the last from the list n Elements

    public ListNode removeNthFromEnd(ListNode head, int n) {
    
        int index = - n;
        ListNode item = head;
        while (item != null) {
    
            item = item.next;
            index++;
        }
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
    
            if (index-- == 0) {
    
                if (pre == null) {
    
                    return curr.next;
                }
                pre.next = curr.next;
                break;
            }
            pre = curr;
            curr = curr.next;
        }
        return head;
    }

15. Square , There are altogether three roads from the upper left corner to the lower right corner
16. Two ordered arrays , The first n Large number
17. One length n Array of , front k（k<n） Ascending order , Descending order after
18. Find the maximum depth of a binary tree