adaxjin

// @Trie @Prefix Tree

class TrieNode{
    char val;
    boolean isWord = false;
    TrieNode[] children;
    
    public TrieNode(char val){
        this.val = val;
        isWord = false;

adaxjin

/*
@HashMap+Heap

Time complexity : O(Nlogk) if k<N and O(N) in the particular case of N=k. That ensures time complexity to be better than O(NlogN).
Space complexity : O(N+k) to store the hash map with not more N elements and a heap with k elements.
*/

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // cc

adaxjin

/*
@DP

Clarify: 页面查重，是什么样的页面，是文字多/图片多/视频/股票相关 etc
需要注意string idx和dp idx的转化：string_idx = dp_idx + 1

*/

class Solution {
    public int minDistance(String word1, String word2) {

adaxjin

// Heap & lamda expression 
Queue<Integer> minHeap = new PriorityQueue<>(((o1, o2) -> o1 - o2)); // 小的在顶上
Queue<Integer> maxHeap = new PriorityQueue<>(((o1, o2) -> o2 - o1));

Queue<Data> minHeap = = new PriorityQueue<>(capacity, ((o1, o2) -> o1.field - o2.field));

adaxjin

// @Heap
// time = O(nlogn), space = O(n)
  
class MedianFinder {   
    private Queue<Integer> minHeap;
    private Queue<Integer> maxHeap;

    /** initialize your data structure here. */
    public MedianFinder() {
        minHeap = new PriorityQueue<>(((o1, o2) -> o1 - o2));

adaxjin

// @HashMap

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) return null;
        Map<Integer, Integer> map = new HashMap<>(); // key: number; value: index
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++){
            if (map.containsKey(target - nums[i])){
                res[0] = map.get(target - nums[i]);

adaxjin

// @DFS

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) return res;
        
       // 此处把数字也设置为character。如果设置为Integer的话，line 31 要变成 30
        Map<Character, List<Character>> map = new HashMap<>();
     

adaxjin

/*
@String

1. Brute force: for every possible substring, call out, check palindrome
      时间：n^2个substring，call substring并创建n，check n → n^4
2. 优化：不用创建substring，以left right标边界 → n^3
3. 优化：check palindrome，如果两边往中间走是n^2可能性，如果中间往两边走check相等是线性n种 → n^2
4. 中间往两边走要分奇偶，可能的开始位置是2n-1个
-------------------------------------------------------------------------
中间往两边扫，中间起始位置的string的可能性有2n-1个，左一个右一个去掉中间？

adaxjin

/*
@Tree @BST

Clarify: 
  如果p是最大值，return什么 → null
  p是否存在于treenode里 → 
    always assume contain
    无脑返回下一个比它大的值
    发现不在立刻返回，问面试官返回啥，1. null / special value   2. exception
      返回的值不能有歧义，如果返回null，p有可能是TN最大值，无法判断是数据有问题还是hit到了edge case，所以不行

adaxjin

/* 
@Cache @List @HashMap

case1: check whether the new url is inside the LRU cache or not with O(1), if hits
case2: update the order of the hit url as new one(move to new side), move based on timestamp, return node's value
case3: otherwise not hit O(1)
	case a: if not full, insert the new entry to new side
	case b: if full, deleted the oldest entry & insert the new entry new side

Case 3: 右进左出，知道size                 queue           singly linked list, array