Programmer: Lifelong Learning: Data Structure Design - How to Succeed in Algorithms Interview

Data Structure Design - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

Implementation Detail

DoubleLinkedList + Map/TreeMap
Use DoubleLinkedList class to wrap the logic of maintain head tail nodes.
use version to track valid element in map

DoubleLinkedList + Map/TreeMap

LeetCode 716 - Max Stack
- [Two Stacks, O(n) for popMax]
- [DoubleLinkedList + TreeMap<Integer, List>()]
LeetCode 380 - Insert Delete GetRandom O(1)
[LeetCode 381 - Insert Delete GetRandom O(1) - Duplicates allowed]
- ArrayList nums; Map<Integer, Set> locs;
Logger:started, finished, print - Google

Freq Buckets

freq increases from 1 to n continuously

LeetCode 895 - Maximum Frequency Stack: popMax

class FreqStack {
  List<Stack<Integer>> bucket;
  HashMap<Integer, Integer> map;
  public FreqStack() {
      bucket = new ArrayList<>();
      map = new HashMap<>();
  }
  public void push(int x) {
      map.put(x, map.getOrDefault(x, 0) + 1);
      int freq = map.get(x);
      if (freq - 1 >= bucket.size()) {
          bucket.add(new Stack<Integer>());
      }
      bucket.get(freq - 1).add(x);
  }
  public int pop() {
      int freq = bucket.size();
      int x = bucket.get(freq - 1).pop();
      if (bucket.get(freq - 1).isEmpty()) bucket.remove(bucket.size() - 1);
      map.put(x, map.get(x) - 1);
      if (map.get(x) == 0) map.remove(x);
      return x;
  }
}
class FreqStack {
  class Pair{
      int num;
      int count;
      int time;
      Pair(int num, int count, int time){
          this.num = num;
          this.count = count;
          this.time = time;
      }
  }
  private PriorityQueue<Pair> queue;
  private HashMap<Integer,Integer> map;
  private int clock = 0;
  public FreqStack() {
      queue = new PriorityQueue<Pair>((a,b) -> (a.count == b.count?b.time-a.time:b.count-a.count));
      map = new HashMap();
  }
  public void push(int x) {
      Pair pair = new Pair(x,map.getOrDefault(x,0)+1,clock++);
      map.put(x,map.getOrDefault(x,0)+1);
      queue.offer(pair);
  }
  public int pop() {
      Pair cur = queue.poll();
      // update
      map.put(cur.num,map.getOrDefault(cur.num,0)-1);
      return cur.num;
  }   
}

Design a Data Structure with Insert & Delete & GetMostFrequent of O(1) － LRU
- HashMap<Integer, Node> map: Node contains all values with same frequency

LeetCode 432 - All O`one Data Structure

// maintain a doubly linked list of Buckets
private Bucket head;
private Bucket tail;
// for accessing a specific Bucket among the Bucket list in O(1) time
private Map<Integer, Bucket> countBucketMap;
// keep track of count of keys
private Map<String, Integer> keyCountMap;
// each Bucket contains all the keys with the same count
// sorted linked
private class Bucket {
  int count;
  Set<String> keySet;
  Bucket next;
  Bucket pre;
  public Bucket(int cnt) {
      count = cnt;
      keySet = new HashSet<>();
  }
}

Custom LinkedList + HashMap

LeetCode 146 - Least Recently Used (LRU) Cache
- Linkedlist + HashMap

[LeetCode 460 - LFU Cache][keyValueMap, freqMap, Map<Integer, LinkedHashSet> sameFreqMap, minFreq](https://leetcode.com/problems/lfu-cache/discuss/94521/java-o1-very-easy-solution-using-3-hashmaps-and-linkedhashset)

When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
keyValueMap, freqMap, Map<Integer, LinkedHashSet> sameFreqMap, minFreq
- use another map: Map<Integer, LinkedHashSet> sameFreqMap to simulate doubly linked list
keyValueMap, Map<Integer, Node> nodeHash, had, Node{freq, sameFreqKyes}
TreeSet

private Node head = null;
private int cap = 0;
private HashMap<Integer, Integer> valueHash = null;
private HashMap<Integer, Node> nodeHash = null;
public LFUCache(int capacity) {
  this.cap = capacity;
  valueHash = new HashMap<Integer, Integer>();
  nodeHash = new HashMap<Integer, Node>();
}
public int get(int key) {
  if (valueHash.containsKey(key)) {
      increaseCount(key);
      return valueHash.get(key);
  }
  return -1;
}
public void set(int key, int value) {
  if ( cap == 0 ) return;
  if (valueHash.containsKey(key)) {
      valueHash.put(key, value);
  } else {
      if (valueHash.size() < cap) {
          valueHash.put(key, value);
      } else {
          removeOld();
          valueHash.put(key, value);
      }
      addToHead(key);
  }
  increaseCount(key);
}
private void addToHead(int key) {
  if (head == null) {
      head = new Node(0);
      head.keys.add(key);
  } else if (head.count > 0) {
      Node node = new Node(0);
      node.keys.add(key);
      node.next = head;
      head.prev = node;
      head = node;
  } else {
      head.keys.add(key);
  }
  nodeHash.put(key, head);      
}
private void increaseCount(int key) {
  Node node = nodeHash.get(key);
  node.keys.remove(key);
  if (node.next == null) {
      node.next = new Node(node.count+1);
      node.next.prev = node;
      node.next.keys.add(key);
  } else if (node.next.count == node.count+1) {
      node.next.keys.add(key);
  } else {
      Node tmp = new Node(node.count+1);
      tmp.keys.add(key);
      tmp.prev = node;
      tmp.next = node.next;
      node.next.prev = tmp;
      node.next = tmp;
  }
  nodeHash.put(key, node.next);
  if (node.keys.size() == 0) remove(node);
}
private void removeOld() {
  if (head == null) return;
  int old = 0;
  for (int n: head.keys) {
      old = n;
      break;
  }
  head.keys.remove(old);
  if (head.keys.size() == 0) remove(head);
  nodeHash.remove(old);
  valueHash.remove(old);
}
private void remove(Node node) {
  if (node.prev == null) {
      head = node.next;
  } else {
      node.prev.next = node.next;
  }
  if (node.next != null) {
      node.next.prev = node.prev;
  }
}
class Node {
  public int count = 0;
  public LinkedHashSet<Integer> keys = null;
  public Node prev = null, next = null;
}

N Queens

Map<Integer, Integer> row = new HashMap();       // row number to count of lamps
Map<Integer, Integer> col = new HashMap();       // col number to count of lamps
Map<Integer, Integer> diag = new HashMap();       // diagonal x-y to count of lamps
Map<Integer, Integer> diag2 = new HashMap();       // diagonal x+y to count of lamps
Map<Integer, Boolean> lamps = new HashMap();       // whether lamp is  ON|OFF

Examples

[LeetCode 353 - Design Snake Game]
- Set body, Deque snake
LeetCode 155 - Min Stack
Constant Clear Map
History Query on Stack

Binary Tree

[Google – Manager Peer Problem]

setManager(A, B) sets A as a direct manager of B
setPeer(A, B) sets A as a colleague of B. After that, A and B will have the same direct Manager.
query(A, B) returns if A is in the management chain of B.

Map<Integer, TNode> nodeMap
union find: int[] parent