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;
}