git config/remote add/

$ git config --global user.name "John Doe"
$ git config --global user.email johndoe@example.com

$ git remote set-url origin git@github.com:username/repo.git

$ git remote add origin https://github.com/user/repo.git
# Set a new remote
$ git remote -v
# Verify new remote

$ git remote show origin

211. Add and Search Word – Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

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

public class WordDictionary {

    public class TrieNode {
        // We do not need this value stroed in the trie node.
        // char c;
        TrieNode[] children;
        boolean isWord;
        public TrieNode() {
            children = new TrieNode[26];
            isWord = false;
        }
    }
    
    private TrieNode root;
    
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        if (word == null || word.length() == 0) return;
        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();
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return helper(word, 0, root);
    }
    
    public boolean helper(String word, int level, TrieNode node) {
        if (level == word.length()) return node.isWord;
        char c = word.charAt(level);
        if (c == '.') {
            for (int i = 0; i < node.children.length; i++) {
                if (node.children[i] != null && helper(word, level + 1, node.children[i])) {
                    return true;
                }
            }
            return false;
        } else if (node.children[c - 'a'] != null) {
            return helper(word, level + 1, node.children[c - 'a']);
        } else return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

498. Diagonal Traverse

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

Note:

  1. The total number of elements of the given matrix will not exceed 10,000.
/**
public class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new int[0];
        int row = 0;
        int col = 0;
        int tag = 1;
        int m = matrix.length;
        int n = matrix[0].length;
        int[] result = new int[m * n];
        for (int i = 0; i < m * n; i++) {
result[i] = matrix[row][col];
row -= tag;
col += tag;
// Should pay attention to the other of checking 0 and m/n bound.
// Should check m/n bound first, or tag willl be reversed twice.
// row/col should plus 2 rather than 1 in this case.
if (row > m - 1) {row = m - 1; col += 2; tag = -tag;}
            if (col > n - 1) {col = n - 1; row += 2; tag = -tag;}
            if (row < 0) {row = 0; tag = -tag;}
            if (col < 0) {col = 0; tag = -tag;}
        }
        return result;
    }
}
*/
// Solution 2: instead using tag directly, we can also use a dictionary.
public class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];
        int m = matrix.length;
        int n = matrix[0].length;
        int row = 0;
        int col = 0;
        int tag = 0;
        int[][] dict = {{-1, 1}, {1, -1}};
        int[] result = new int[m * n];

        for (int i = 0; i < m * n; i++) {
result[i] = matrix[row][col];
row += dict[tag][0];
col += dict[tag][1];
if (row > m - 1) {row = m - 1; col += 2; tag = 1 - tag;}
             if (col > n - 1) {col = n - 1; row += 2; tag = 1 - tag;}
             if (row < 0) {row = 0; tag = 1 - tag;}
             if (col < 0) {col = 0; tag = 1 - tag;}
}
return result;
}
}

/* In the onsite inteview from Bloomberg, I came across a similar problem, instead of traverse with two directions,
the oder in the problem I came across is from bottom left to upper right for each diagnal traversal,
the code can be like the following: */
public class Solution {     // The order of each diagonal traversal is bottom left -> upper right.
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];
        int m = matrix.length - 1;
        int n = matrix[0].length - 1;
        int[] result = new int[(m + 1) * (n + 1)];
        int row = 0;
        int col = 0;
        int index = 0;
        for (int sum = 0; sum <= m + n; sum++) {
// row = sum > m ? m : sum;
            row = Math.min(sum, m);
            col = sum - row;
            while (row >= 0 && col <= n) {
                result[index++] = matrix[row--][col++];
                // The following lines can be combined to the single line above.
//                 result[index] = matrix[row][col];
//                 row -= 1;
//                 col += 1;
//                 index++;
            }
        }
        return result;
    }
}

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);
 */