Design

PreviousKnapsack Problem NextConcurrency

Last updated 4 years ago

Was this helpful?

Design

class MovingAverage {
    Queue<Integer> list;
    int capacity;
    double sum;
    public MovingAverage(int size) {
        this.capacity = size;
        this.list = new LinkedList<>();
        this.sum = 0;
    }
    
    public double next(int val) {
        list.add(val);
        sum += val;
        while (list.size() > this.capacity) {
            sum -= list.poll();
        }
        return sum / (double)list.size();
    }
}

Use a map to store the last time the log is printed.

Map<String, Integer> memo;
/** Initialize your data structure here. */
public Logger() {
    memo = new HashMap<>();
}

/** Returns true if the message should be printed in the given timestamp, otherwise returns false.
    If this method returns false, the message will not be printed.
    The timestamp is in seconds granularity. */
public boolean shouldPrintMessage(int timestamp, String message) {
    if (!memo.containsKey(message)) {
        memo.put(message, timestamp);
        return true;
    } else if (memo.containsKey(message) && memo.get(message) <= timestamp - 10) {
        memo.put(message, timestamp);
        return true;
    } else {
        return false;
    }
}

Use a list to store all numbers, use Hashmap <number, it is position> to find the position of each number.

insert: add val to the list and map
remove: check if the val is the last element of the list. If yes, simply remove the last element from list and map. Otherwise, replace val with the last element in the list, and remove the last element.
getRandom: return list.get(rand.nextInt(list.size()));

    List<Integer> list;
    Random rand;
    Map<Integer, Integer> map;
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int valpos = map.get(val);
        if (valpos != list.size() - 1) {
            int lastval = list.get(list.size() - 1);
            list.set(valpos, lastval);
            map.put(lastval, valpos);
        }
        map.remove(val);
        list.remove(list.size() - 1);
        return true;
    }
    
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }

Use Map<Integer, Set<Integer>> to store val and corresponding positions. When remove, random pick one from the current val set by using iterator, swap with the last position.

    List<Integer> list;
    Random rand;
    Map<Integer, Set<Integer>> map;
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        boolean res = !map.containsKey(val);
        map.putIfAbsent(val, new HashSet<>());
        map.get(val).add(list.size());
        list.add(val);
        return res;
    }
    
   public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int valpos = map.get(val).iterator().next();
        map.get(val).remove(valpos);
        int lastval = list.get(list.size() - 1);
        Set<Integer> lastset = map.get(lastval);
        if (valpos != list.size() - 1) {
            lastset.remove(list.size() - 1);
            lastset.add(valpos);
        }
        list.set(valpos, lastval);
        list.remove(list.size() - 1);
        if (map.get(val).isEmpty()) map.remove(val);
        return true;
    }
    
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.list = []
    self.map = collections.defaultdict(set)

def insert(self, val: int) -> bool:
    """
    Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
    """
    res = val not in self.map
    self.map[val].add(len(self.list))
    self.list.append(val)
    return res

def remove(self, val: int) -> bool:
    """
    Removes a value from the collection. Returns true if the collection contained the specified element.
    """
    if self.map[val]:
        inVal, outIndex = self.list[-1], self.map[val].pop()
        self.list[outIndex] = inVal
        if self.map[inVal]:
            self.map[inVal].add(outIndex)
            self.map[inVal].discard(len(self.list) - 1)
        self.list.pop()
        return True
    return False

def getRandom(self) -> int:
    """
    Get a random element from the collection.
    """
    return random.choice(self.list)

When new value <= min, add min to the stack then add new value. When pop, check if the popped element equals to min, if yes, pop again.

int min;
Stack<Integer> stack;
public MinStack() {
    min = Integer.MAX_VALUE;
    stack = new Stack<>();
}

public void push(int x) {
    if (x <= min) {
        stack.add(min);
        min = x;
    }
    stack.add(x);
}

public void pop() {
    int pop = stack.pop();
    if (pop == min) {
        min = stack.pop();
    }
}

public int top() {
    return stack.peek();
}

public int getMin() {
    return min;
}

/** initialize your data structure here. */
Stack<Integer> stack;
Stack<Integer> mstack;
public MinStack() {
    stack = new Stack<>();
    mstack = new Stack<>();
}

public void push(int x) {
    stack.push(x);
    if (mstack.isEmpty() || x <= mstack.peek()) {
        mstack.push(x);
    }
}

public void pop() {
    int pop = stack.pop();
    if (!mstack.isEmpty() && pop == mstack.peek()) {
        mstack.pop();
    }
}

public int top() {
    return stack.peek();
}

public int getMin() {
    return mstack.peek();
}

Use an array of size k to store the elements, a start and end to set the boundary and size to maintain the queue size.

    int[] arr;
    int start, end, size;
    public MyCircularQueue(int k) {
        arr = new int[k];
        start = 0;
        end = -1;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull()) return false;
        end = (end + 1) % arr.length;
        arr[end] = value;
        size++;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty()) return false;
        start = (start + 1) % arr.length;
        size--;
        return true;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        return isEmpty() ? -1 : arr[start];
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        return isEmpty() ? -1 : arr[end];
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return size == arr.length;
    }

Clarifications:

For simplicity, are the keys integers only?
For collision resolution, can we use chaining?
Do we have to worry about load factors?
Can we assume inputs are valid or do we have to validate them?
Can we assume this fits memory?

Method: Use a list of buckets to store the node. Each bucket is a linked-list:

int getIndex(int key): get index in the list based on the provide key
ListNode getPrev(int index, int key): get the last node with the right key for insertion or deletion.

Follow-up:

What if there are too many nodes in one bucket? Load factor + rehashing or use Red-Black tree on each node
What if there key is a String? Multiply ASCII value of each character and MOD by 31 to get the index.

class MyHashMap {
    ListNode[] list;
    int SIZE = 10000;
    public MyHashMap() {
        list = new ListNode[SIZE];
    }
    
    private int getIndex(int key) {
        return Integer.hashCode(key) % SIZE;
    }
    
    private ListNode getPrev(int index, int key) {
        if (list[index] == null) {
            list[index] = new ListNode(-1, -1);
            return list[index];
        }
        ListNode prev = list[index];
        while (prev.next != null && prev.next.key != key) {
            prev = prev.next;
        }
        return prev;
    }
    
    public void put(int key, int value) {
        int index = getIndex(key);
        ListNode prev = getPrev(index, key);
        if (prev.next == null) {
            prev.next = new ListNode(key, value);
        } else {
            prev.next.val = value;
        }
    }
    
    public int get(int key) {
        int index = getIndex(key);
        ListNode prev = getPrev(index, key);
        if (prev.next == null) {
            return -1;
        }
        return prev.next.val;
    }
    
    public void remove(int key) {
        int index = getIndex(key);
        ListNode prev = getPrev(index, key);
        if (prev.next == null) {
            return;
        }
        prev.next = prev.next.next;
    }
    
    class ListNode {
        int val, key;
        ListNode next;
        ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}

class LRUCache {
    Node head, tail;
    int size, capacity;
    Map<Integer, Node> map;
    public LRUCache(int capacity) {
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
        this.capacity = capacity;
        map = new HashMap<>();
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node curt = map.get(key);
            removeNode(curt);
            addToFirst(curt);
            return curt.value;
        } 
        return -1;
    }
    
    public void put(int key, int value) {
        Node curt = null;
        if (map.containsKey(key)) {
            curt = map.get(key);
            curt.value = value;
            removeNode(curt);
        } else {
            curt = new Node(key, value);
            if (++size > capacity) {
                Node temp = tail.prev;
                removeNode(temp);
                map.remove(temp.key);
            }
        }
        addToFirst(curt);
        map.put(key, curt);
    }
    
    private void removeNode(Node curt) {
        Node nxt = curt.next;
        Node pre = curt.prev;
        pre.next = nxt;
        nxt.prev = pre;
        curt.prev = null;
        curt.next = null;
    }
    
    private void addToFirst(Node curt) {
        Node sec = head.next;
        head.next = curt;
        curt.prev = head;
        curt.next = sec;
        sec.prev = curt;
    }
    
    class Node {
        int key, value;
        Node prev, next;
        Node(int key, int val) {
            this.key = key;
            this.value = val;
        }
    }
}

class LFUCache {
  Map<Integer, DoublyLinkedList> freqListMap;
  Map<Integer, ListNode> keyNodeMap;
  int size, capacity, minFrequency;
  public LFUCache(int capacity) {
    this.freqListMap = new HashMap<>();
    this.keyNodeMap = new HashMap<>();
    this.size = 0;
    this.capacity = capacity;
    this.minFrequency = 0;
  }

  public int get(int key) {
    ListNode curt = keyNodeMap.get(key);
    if (curt == null) {
      return -1;
    }
    updateNode(curt);
    return curt.val;
  }

  public void put(int key, int value) {
    if (capacity == 0) return;
    if (keyNodeMap.containsKey(key)) {
      ListNode curt = keyNodeMap.get(key);
      curt.val = value;
      updateNode(curt);
    } else {
      size++;
      if (size > capacity) {
        DoublyLinkedList minList = freqListMap.get(minFrequency);
        ListNode deleteNode = minList.popLast();
        keyNodeMap.remove(deleteNode.key);
        size--;
      }
      minFrequency = 1;
      ListNode curt = new ListNode(value);
      curt.key = key;
      DoublyLinkedList ddl = freqListMap.getOrDefault(
          curt.freq, new DoublyLinkedList());
      ddl.addToFirst(curt);
      keyNodeMap.put(key, curt);
      freqListMap.put(curt.freq, ddl);
    }
  }

  private void updateNode(ListNode curt) {
    int curtFeq = curt.freq;
    DoublyLinkedList ddl = freqListMap.get(curtFeq);
    ddl.popNode(curt);

    if (curtFeq == minFrequency && ddl.emptyList()) {
      minFrequency++;
    }
    curt.freq += 1;

    DoublyLinkedList nextDDL = freqListMap.getOrDefault(
        curtFeq + 1, new DoublyLinkedList());
    nextDDL.addToFirst(curt);
    freqListMap.put(curtFeq + 1, nextDDL);
  }

  class DoublyLinkedList {
    ListNode head, tail;
    DoublyLinkedList() {
      this.head = new ListNode(-1);
      this.tail = new ListNode(-1);
      head.next = tail;
      tail.prev = head;
    }
    public void addToFirst(ListNode curtNode) {
      ListNode next = head.next;
      curtNode.next = next;
      next.prev = curtNode;
      head.next = curtNode;
      curtNode.prev = head;
    }

    public ListNode popNode(ListNode node) {
      ListNode next = node.next;
      node.prev.next = next;
      next.prev = node.prev;
      node.prev = null;
      node.next = null;
      return node;
    }

    public ListNode popLast() {
      ListNode last = tail.prev;
      return popNode(last);
    }

    private boolean emptyList() {
      return head.next == tail && tail.prev == head;
    }
  }

  class ListNode {
    ListNode prev, next;
    int freq;
    int val;
    int key;
    ListNode(int val) {
      this.val = val;
      this.freq = 1;
    }
  }
}

Solution1: two stacks

Solution2: Use a LinkedList and TreeMap to store value.

class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> maxStack;

    public MaxStack() {
        stack = new Stack();
        maxStack = new Stack();
    }

    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        stack.push(x);
    }

    public int pop() {
        maxStack.pop();
        return stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return maxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}

    TreeMap<Integer, LinkedList<ListNode>> map;
    ListNode head, tail;
    /** initialize your data structure here. */
    public MaxStack() {
        map = new TreeMap<>();
        head = new ListNode(-1);
        tail = new ListNode(-1);
        head.next = tail;
        tail.prev = head;
    }
    
    private void addToFirst(ListNode node) {
        map.putIfAbsent(node.val, new LinkedList<>());
        map.get(node.val).add(node);
        ListNode next = head.next;
        head.next = node;
        node.prev = head;
        node.next = next;
        next.prev = node;
    }
    
    private void removeNode(ListNode node) {
        map.get(node.val).removeLast();
        if (map.get(node.val).size() == 0) map.remove(node.val);
        ListNode prev = node.prev;
        ListNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }
    
    public void push(int x) {
        ListNode curt = new ListNode(x);
        addToFirst(curt);
    }
    
    public int pop() {
        if (head.next == tail) return -1;
        ListNode pop = map.get(head.next.val).peekLast();
        removeNode(pop);
        return pop.val;
    }
    
    public int top() {
        return head.next == tail ? -1 : head.next.val;
    }
    
    public int peekMax() {
        return map.isEmpty() ? -1 : map.lastKey();
    }
    
    public int popMax() {
        int maxKey = map.lastKey();
        removeNode(map.get(maxKey).peekLast());
        return maxKey;
    }
    
    class ListNode {
        int val;
        ListNode prev, next;
        ListNode(int val) {
            this.val = val;
        }
    }

This is similar to LFU. Each bucket is has a pre bucket and a next buck, also has a keySet to store all keys in the frequency, and the frequency itself. Build two maps:

Key: Count Value: Bucket
Key: String Key Value: Count

    // 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
    private class Bucket {
        int count;
        Set<String> keySet;
        Bucket next;
        Bucket pre;
        public Bucket(int cnt) {
            count = cnt;
            keySet = new HashSet<>();
        }
    }

    /** Initialize your data structure here. */
    public AllOne() {
        head = new Bucket(Integer.MIN_VALUE);
        tail = new Bucket(Integer.MAX_VALUE);
        head.next = tail;
        tail.pre = head;
        countBucketMap = new HashMap<>();
        keyCountMap = new HashMap<>();
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (keyCountMap.containsKey(key)) {
            changeKey(key, 1);
            return;
        } 
        keyCountMap.put(key, 1);
        if (head.next.count != 1) {
            addBucketAfter(new Bucket(1), head);
        }
        head.next.keySet.add(key);
        countBucketMap.put(1, head.next);
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (keyCountMap.containsKey(key)) {
            int count = keyCountMap.get(key);
            if (count == 1) {
                removeKeyFromBucket(countBucketMap.get(1), key);   
                keyCountMap.remove(key);
            } else {
                changeKey(key, -1);
            }
        }
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return tail.pre == head ? "" : (String) tail.pre.keySet.iterator().next();
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        return head.next == tail ? "" : (String) head.next.keySet.iterator().next();        
    }
    
  // helper function to make change on given key according to offset
    private void changeKey(String key, int offset) {
        int count = keyCountMap.get(key);
        keyCountMap.put(key, count + offset);
        Bucket curBucket = countBucketMap.get(count);
        Bucket newBucket;
        if (countBucketMap.containsKey(count + offset)) {
            // target Bucket already exists
            newBucket = countBucketMap.get(count + offset);
        } else {
            // add new Bucket
            newBucket = new Bucket(count + offset);
            countBucketMap.put(count + offset, newBucket);
            addBucketAfter(newBucket, offset == 1 ? curBucket : curBucket.pre);
        }
        newBucket.keySet.add(key);
        removeKeyFromBucket(curBucket, key);
    }
    
    private void removeKeyFromBucket(Bucket bucket, String key) {
        bucket.keySet.remove(key);
        if (bucket.keySet.size() == 0) {
            removeBucketFromList(bucket);
            countBucketMap.remove(bucket.count);
        }
    }
    
    private void removeBucketFromList(Bucket bucket) {
        bucket.pre.next = bucket.next;
        bucket.next.pre = bucket.pre;
        bucket.next = null;
        bucket.pre = null;
    }
    
    // add newBucket after preBucket
    private void addBucketAfter(Bucket newBucket, Bucket preBucket) {
        newBucket.pre = preBucket;
        newBucket.next = preBucket.next;
        preBucket.next.pre = newBucket;
        preBucket.next = newBucket;
    }

BinarySearch version

    Map<String, List<Pair>> map;
    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(new Pair(timestamp, value));
    }
    
    public String get(String key, int timestamp) {
        List<Pair> list = map.get(key);
        if (list == null || list.get(0).timestamp > timestamp) return "";
        if (list.get(list.size() - 1).timestamp < timestamp) return list.get(list.size() - 1).value;
        return binarySearch(list, timestamp);
    }
    
       public String binarySearch(List<Pair> list, int timestamp) {
        int left=0, right = list.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int ts = list.get(mid).timestamp;
            if (timestamp == ts) {
                return list.get(mid).value;
            } else if (timestamp > ts) {
                if (mid + 1 < list.size() && timestamp < list.get(mid+1).timestamp) {
                    return list.get(mid).value;
                } else {
                    left = mid + 1;
                }
            } else {
                right = mid -1;
            }
        }
        return  "";
    }
    
    class Pair {
        int timestamp;
        String value;
        Pair(int t, String v) {
            this.timestamp = t;
            this.value = v;
        }
    }

TreeMap version

Map<String,TreeMap<Integer, String>> map;
    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
        
    }
    
    public String get(String key, int timestamp) {
        if(map.containsKey(key)){
            TreeMap<Integer, String> m = map.get(key);
            Integer val = m.floorKey(timestamp);
            if(val!=null)
              return  m.get(val);
        }
        return "";
    }

Store all seats in a TreeMap, loop over it to detect the largest gap.

class ExamRoom {
    TreeSet<Integer> set;
    int N;
    public ExamRoom(int N) {
        set = new TreeSet<>();
        this.N = N;
    }
    
    public int seat() {
        if (set.isEmpty()) {
            set.add(0);
            return 0;
        }
        int maxInterval = set.first();
        int pre = set.first(), seat = 0;
        for (int curt : set) {
            if ((curt - pre) / 2 > maxInterval) {
                maxInterval = (curt - pre) / 2;
                seat = (curt + pre) / 2;
            }
            pre = curt;
        }
        if (N - pre - 1 > maxInterval) {
            seat = N - 1;
        }
        set.add(seat);
        return seat;
    }
    
    public void leave(int p) {
        set.remove(p);
    }
}

PreviousKnapsack Problem NextConcurrency

Last updated 4 years ago

Was this helpful?