---
# System prepended metadata

title: Untitled

---

Sample code for google interview preparation

    /**
     * 1.1 Find Popular Element.
     * Given an array of size n, find all elements in array that appear more than n/k times.
     * input: k = 4, arr = [3,1,2,2,2,1,4,3,3]
     * output: [2,3]
     *
     * Time: O(n) Space: O(n)
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] findPopularElements(int[] arr, int k) {
        int target = arr.length / k;
        List<Integer> li = new ArrayList<Integer>();

        HashMap<Integer, Integer> popMap = new HashMap<>();

        // Count the frequency of each element
        for (int i = 0; i < arr.length; i++) {
            if (popMap.containsKey(arr[i])) {
                int cur = popMap.get(arr[i]);
                popMap.put(arr[i], cur + 1);
            } else {
                popMap.put(arr[i], 1);
            }
        }

        // Iterate over each element in the hash table
        // and check their frequency, if it is more than
        // n/k, add them to the result

        for (Map.Entry ent : popMap.entrySet()) {
            int frq = (int)ent.getValue();
            if (frq > target) {
                li.add((int)ent.getKey());
            }
        }

        int[] result = new int[li.size()];
        for (int j=0; j<li.size(); j++) {
            result[j] = li.get(j);
        }

        return result;
    }

    /**
     * 1.2 Follow up: Find popular in a sorted array
     * Write a function in Java that takes a sorted array and returns any popular element
     * A popular element: x in array of size n is such that the number of occurrence of x > n/4
     * In other words, the element must be repeated in the array more than a quarter of the time
     *
     * Time: O(log n); Space: O(1)
     *
     * @param arr
     * @return
     */
    public int findPopular(int[] arr) throws Exception {
        int len = arr.length;
        int target = len/4;

        if (countOccurances(arr, arr[len/4]) > target) return arr[len/4];
        else if (countOccurances(arr, arr[len/2]) > target) return arr[len/2];
        else if (countOccurances(arr, arr[(3*len)/4]) > target) return arr[(3*len)/4];
        else throw new Exception();
    }

    /**
     * Find the first and last occurrence of the target number
     * @param array
     * @param num
     * @return the number of the occurrence
     */
    private int countOccurances(int[] array, int num) {
        int first = binarySearch(array, num, true);
        int last = binarySearch(array, num, false);
        return last - first + 1;
    }

    /**
     * Binary search to look for the first or last occurrence of target number
     * @param array
     * @param target
     * @param searchFirst
     * @return
     */
    private int binarySearch(int[] array, int target, boolean searchFirst) {
        int left = 0;
        int right = array.length;
        int result = -1;
        while (left <= right) {
            int mid = (left + right)/2;
            if (array[mid] == target) {
                result = mid;
                if (searchFirst) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }

            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }

    /**
     * 2. LC 1610 Maximum Number of Visible Points
     *
     * 这道题需要考虑 end超过angle list里面点的数量的情况，因为可以被套圈
     *
     * @param points
     * @param angle
     * @param location
     * @return
     */
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> angles = new ArrayList<Double>();
        int myposition = 0;

        // 将每一个点转化为一个角度的数值，然后把它加入到angles这个list里面
        for (List<Integer> point : points) {
            double y = (double)(point.get(1) - location.get(1));
            double x = (double)(point.get(0) - location.get(0));

            // The current point is in my location
            if (x==0 && y==0) {
                myposition++;
                continue;
            }
            double thisAngle = 180*Math.atan(y/x)/Math.PI;
            if (x < 0) {
                thisAngle = 180.0 + thisAngle; // 该point在第二和第三象限
            } else if (y < 0) {
                thisAngle = 360.0 + thisAngle; // 该point在第四象限
            }
            angles.add(thisAngle);
        }

        Collections.sort(angles);

        int max = 0;
        int start = 0;
        int end = 0;
        int size = angles.size();

        // start的初始位置是正东(y=0)，因此start回到正东方向的时候，end会大于size
        while (start < size) {
            while ((end<size?angles.get(end) : angles.get(end%size)+360) - angles.get(start) <= angle) {
                end++;
            }
            if (end > start) {
                max = Math.max(end - start, max);
            }
            start++;
        }
        return max+myposition;
    }

/**
 *3.1 Leetcode 295 Find Median from Data Stream
 */
 
public class MedianFinder {
    private List<Integer> stream;

    public MedianFinder() {
        this.stream = new ArrayList<>();
    }

    public void addNum(int num) {
        stream.add(num);
    }

    public double findMedian() {

        if (stream.isEmpty()) {
            return 0.0;
        }

        if (stream.size() == 1) {
            return stream.get(0);
        }

        Collections.sort(stream);

        if (stream.size()%2 == 0) {
            return (stream.get(stream.size()/2 - 1) + stream.get(stream.size()/2))/2.0;
        }
        return stream.get(stream.size()/2);
    }
}

// 3.2 Faster than 98% || Two heap approach
public class MedianFinder {

    PriorityQueue<Integer> min;
    PriorityQueue<Integer> max;

    public MedianFinder() {
        min = new PriorityQueue<>();
        max = new PriorityQueue<>(Comparator.reverseOrder());
    }

    public void addNum(int num) {
        if (min.isEmpty() && max.isEmpty()) {
            max.add(num);
        } else if (num > max.peek()) {
            min.add(num);
            if (min.size() - max.size() >= 2) {
                max.add(min.poll());
            }
        } else {
            max.add(num);
            if (max.size() - min.size() >= 2) {
                min.add(max.poll());
            }
        }
    }

    public double findMedian() {
        if (max.size() == min.size()) {
            return (max.peek() + min.peek())/2.0;
        }

        if (min.size() > max.size()) {
            return (double)min.peek();
        }

        return (double)max.peek();
    }
}

Follow Up: No idea how to resolve it

If all integer numbers from the stream are between 0 and 100, how would you optimize it?
If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

// 4. Codec design for Tree

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return dfs(root, "");
    }

    private String dfs(TreeNode root, String output) {
        if (root == null) {
            output += "null";
        } else {
            output += String.valueOf(root.val) + ",";
            output = dfs(root.left, output);
            output = dfs(root.right, output);
        }
        return output;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] data_array = data.split(",");
        List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
        return helper(data_list);
    }

    private TreeNode helper(List<String> dataList) {
        if (dataList.get(0).equals("null")) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);

        root.left = helper(dataList);
        root.right = helper(dataList);

        return root;

    }
}

/**
     * 5.1 Leetcode 269 Alien Dictionary (BFS method)
     * @param words
     * @return
     */
    public String alienOrderI(String[] words) {

        // Step 0: Create data structures and find all unique letters.
        Map<Character, List<Character>> adjList = new HashMap<>();
        Map<Character, Integer> counts = new HashMap<>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                counts.put(c, 0);
                adjList.put(c, new ArrayList<>());
            }
        }

        // Step 1: Find all edges.
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            // Check that word2 is not a prefix of word1.
            if (word1.length() > word2.length() && word1.startsWith(word2)) {
                return "";
            }
            // Find the first non match and insert the corresponding relation.
            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
                if (word1.charAt(j) != word2.charAt(j)) {
                    adjList.get(word1.charAt(j)).add(word2.charAt(j));
                    counts.put(word2.charAt(j), counts.get(word2.charAt(j)) + 1);
                    break;
                }
            }
        }

        // Step 2: Breadth-first search.
        StringBuilder sb = new StringBuilder();
        Queue<Character> queue = new LinkedList<>();
        for (Character c : counts.keySet()) {
            if (counts.get(c).equals(0)) {
                queue.add(c);
            }
        }
        while (!queue.isEmpty()) {
            Character c = queue.remove();
            sb.append(c);
            for (Character next : adjList.get(c)) {
                counts.put(next, counts.get(next) - 1);
                if (counts.get(next).equals(0)) {
                    queue.add(next);
                }
            }
        }

        if (sb.length() < counts.size()) {
            return "";
        }
        return sb.toString();
    }
    
    /**
     * 7.Leetcode 392 Is Subsequence
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) {
            return true;
        }

        if (s.length() > t.length()) {
            return false;
        }

        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();

        int slow = 0;
        int fast = 0;
        int flag = 0;

        while (slow < sarr.length && fast < tarr.length) {
            while (fast < tarr.length) {
                if (sarr[slow] == tarr[fast]) {
                    slow++;
                    flag++;
                    if (flag == sarr.length) {
                        return true;
                    }
                }
                fast++;
            }
        }

        return false;
    }


