79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) return true;
        if (board == null || board.length == 0 || board[0].length == 0) return false;
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if (board[row][col] == word.charAt(0) && dfs(board, word, 0, row, col)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, String word, int level, int row, int col) {
        if (level == word.length()) return true;
        if (row < 0 || row >= board.length || col < 0 || col >= board[row].length) return false;
        if (board[row][col] != word.charAt(level)) return false;
        board[row][col] = '#';  // Must mark item visited on the board.
        boolean result = dfs(board, word, level + 1, row - 1, col) ||
                         dfs(board, word, level + 1, row + 1, col) ||
                         dfs(board, word, level + 1, row, col - 1) ||
                         dfs(board, word, level + 1, row, col + 1);
        board[row][col] = word.charAt(level);   // Remember to recovery the altered item on the board.
        return result;
    }
}

132. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

// Solution 1: DP
public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        int len = s.length();
        boolean dp[][] = new boolean[len][len];
        int result[] = new int[len];
        for (int i = 0; i < len; i++) {
            result[i] = i;
            for (int j = i; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j) && (i - j <= 1 || dp[i - 1][j + 1])) {
                    dp[i][j] = true;
                    if (j > 0) {
                        result[i] = Math.min(result[j - 1] + 1, result[i]);
                    } else {
                        result[i] = 0;
                    }
                    
                }
            }
        }
        return result[len - 1];
    }
}
// Solution 2: Similar to Palindrome Partition 1, use backtracking, however, time limited exceeded.
/*
public class Solution {
    
    private int result = Integer.MAX_VALUE;
    
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        dfs(s, 0, -1);
        return result;
    }
    
    public void dfs(String s, int start, int min) {
        if (start == s.length()) {
            result = Math.min(result, min);
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                min += 1;
                dfs(s, i + 1, min);
                min -= 1;
            }
        }
    }
    
    public boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}
*/

131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]
public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if (s == null || s.length() == 0) return result;
        dfs(s, 0, result, new ArrayList<String>());
        return result;
    }
    
    public void dfs(String s, int start, List<List<String>> result, List<String> path) {
        if (s.length() == start) result.add(new ArrayList<>(path)); // Must use new to allocate memory other than path.
        for (int i = start; i < s.length(); i++) {
            String sub = s.substring(start, i + 1);
            if (isPalindrome(sub)) {
                path.add(sub);
                dfs(s, i + 1, result, path);
                path.remove(path.size() - 1);
            }
        }
    }
    
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) return true;
        int start = 0;
        int end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}

355. Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

  1. postTweet(userId, tweetId): Compose a new tweet.
  2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
  3. follow(followerId, followeeId): Follower follows a followee.
  4. unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);
public class Twitter {

    public class Tweet {
        private int tweetId;
        private int timeStamp;
        private Tweet next;
        public Tweet(int tweetId, int timeStamp) {
            this.tweetId = tweetId;
            this.timeStamp = timeStamp;
            this.next = null;
        }
        public Tweet(int tweetId, int timeStamp, Tweet next) {
            this(tweetId, timeStamp);
            this.next = next;
        }
    }

    public class User {
        private int userId;
        private Set<Integer> followed;
        private Tweet tweetHead;
        public User(int id) {
            this.userId = id;
            followed = new HashSet<>();
            follow(id); // Must follow the user himself.
            tweetHead = null;
        }

        public void post(int tweetId) {
            tweetHead = new Tweet(tweetId, timeStamp++, tweetHead);
        }

        public void follow(int id) {
            followed.add(id);
        }

        public void unfollow(int id) {
            if (userId == id) return;   // Should always follow the user himself.
            followed.remove(id);
        }
    }

    private int timeStamp;
    private Map<Integer, User> userIds;

    /** Initialize your data structure here. */
    public Twitter() {
        timeStamp = 0;
        userIds = new HashMap<>();
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if (!userIds.containsKey(userId)) userIds.put(userId, new User(userId));
        userIds.get(userId).post(tweetId);
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> result = new LinkedList<>();
        if (!userIds.containsKey(userId)) return result;
        Set<Integer> users = userIds.get(userId).followed;
        PriorityQueue<Tweet> pq = new PriorityQueue<Tweet>((a, b)->(b.timeStamp - a.timeStamp)); // Changed timestamp to int due to conversion issue. Also removed users.size() argument.
        for (int user : users) {
            Tweet t = userIds.get(user).tweetHead;
            if (t != null) pq.add(t);   // Must check t != null.
        }
        int count = 0;
        while (!pq.isEmpty() && count < 10) {
            Tweet t = pq.poll();
            result.add(t.tweetId);
            count++;
            if (t.next != null) pq.add(t.next);
        }
        return result;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if (!userIds.containsKey(followerId)) userIds.put(followerId, new User(followerId));
        if (!userIds.containsKey(followeeId)) userIds.put(followeeId, new User(followeeId));
        userIds.get(followerId).follow(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if (!userIds.containsKey(followerId) || !userIds.containsKey(followeeId)) return;
        userIds.get(followerId).unfollow(followeeId);
    }
}

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 */

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
 public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (!map.containsKey(num)) { map.put(num, 1); } else { map.put(num, map.get(num) + 1); } } List<Integer>[] bucket = new List[nums.length + 1]; for (int key : map.keySet()) { if (bucket[map.get(key)] == null) { bucket[map.get(key)] = new ArrayList<>(); } bucket[map.get(key)].add(key); } List<Integer> result = new ArrayList<>(); for (int i = bucket.length - 1; i >= 0; i--) { if (result.size() >= k) { return result; } if (bucket[i] != null) { result.addAll(bucket[i]); } } return result; } } 

208. Implement Trie (Prefix Tree)

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

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

public class Trie {

    public class TrieNode {
        public char val;
        public boolean isWord;
        public TrieNode[] children = new TrieNode[26];
        public TrieNode () {};
        public TrieNode (char c) {
            TrieNode node = new TrieNode();
            node.val = c;
        }
    }

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode(' ');
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode(c);
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) return false;
            node = node.children[c - 'a'];
        }
        return node.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i ++) {
            char c = prefix.charAt(i);
            if (node.children[c - 'a'] == null) return false;
            node = node.children[c - 'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

582. Kill Process

Given n processes, each process has a unique PID (process id) and its PPID (parent process id).

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

Example 1:

Input: 
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation: 
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

Note:

  1. The given kill id is guaranteed to be one of the given PIDs.
  2. n >= 1.
Show Company Tags
Show Tags
public class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> result = new ArrayList<>();
        if (pid == null || ppid == null) return result;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < pid.size(); i++) {
            if (!map.containsKey(ppid.get(i))) {
                map.put(ppid.get(i), new LinkedList<>());
            }
            map.get(ppid.get(i)).add(pid.get(i));
        }
        Queue<Integer> q = new LinkedList<>();
        q.offer(kill);
        while (!q.isEmpty()) {
            int id = q.poll();
            result.add(id);
            if (map.containsKey(id)) q.addAll(map.get(id));
        }
        return result;
    }
}

463. Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:
public class Solution {
    
    private int result = 0;
    private final int[] dx = new int[]{-1,0,1,0};
    private final int[] dy = new int[]{0,1,0,-1};
    private boolean[][] visited;
    
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    bfs(i, j, grid);
                }
                
            }
        }
        return result;
    }
    
    private void bfs(int x, int y, int[][] grid) {
        visited[x][y] = true;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] pos = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = pos[0] + dx[i];
                int ny = pos[1] + dy[i];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length) {
                    if (grid[nx][ny] == 1 && !visited[nx][ny]) {
                        q.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                    else if (grid[nx][ny] == 0) result++;
                } else {
                    result++;
                }
            }
        }
    }
}

// DFS
public class Solution {
    
    private int result = 0;
    private final int[] dx = new int[]{-1,0,1,0};
    private final int[] dy = new int[]{0,1,0,-1};
    private boolean[][] visited;
    
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    dfs(i, j, grid);
                    return result;
                }
                
            }
        }
        return result;
    }
    
    private void dfs(int x, int y, int[][] grid) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length) {
                if (grid[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    dfs(nx, ny, grid);
                } else if (grid[nx][ny] == 0) result++;
            } else result++;
        }
    }
}

210. Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

  1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.
public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // set to store courses, map to store in/outDegree
        Map<Integer, Set<Integer>> inDegree = new HashMap<>();
        Map<Integer, Set<Integer>> outDegree = new HashMap<>();
        // Init course
        for (int i = 0; i < numCourses; i++) {
            inDegree.put(i, new HashSet<>());
            outDegree.put(i, new HashSet<>());
        }
        // set in/outDegree
        for (int i = 0; i < prerequisites.length; i++) {
            int cur = prerequisites[i][0];
            int pre = prerequisites[i][1];
            inDegree.get(cur).add(pre);
            outDegree.get(pre).add(cur);
        }
        // queue to store nodes without indegree
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree.get(i).size() == 0) q.offer(i);
        }
        // add q.poll to result
        int[] result = new int[numCourses];
        int index = 0;
        while (!q.isEmpty()) {
            Integer course = q.poll();
            result[index++] = course;
            for (Integer next : outDegree.get(course)) {
                inDegree.get(next).remove(course);
                if (inDegree.get(next).size() == 0) q.offer(next);
            }
        }
        // return result
        if (index == numCourses) return result;
        else return new int[]{};
    }
}