Tuesday, June 14, 2016

O(1) Map

Question:
Design a Map so that it supports the following operations:
1. add(int val), O(1) time
2. remove(int val), O(1) time
3. contains(int val), O(1) time
4. clear(), O(1) time
5. iterate(), O(num of elements)

Analysis:
If we just use a randomized array, i.e, a hash map, add(), remove(), and contains() operations take O(1) time. The clear() takes O(size of array) time (NOT SURE), and iterate takes O(size of array) time. Note that iterate() takes O(size of array) time instead of O(num of elements) because of the implementation of a hash map is usually an array or array + list. So it needs to iterate all elements of the array no matter if it is taken or not. 

If we only use a sequential accessed array, i.e, an ArrayList in Java, the add() takes O(1), but remove() and contains() takes O(num of elements) time. clear() takes O(1) ?? not sure. 
iterate() takes O(num of elements) time as well. 

So the idea is to combine the two data structures together. 

Method 1: HashMap + Array
Code (Java):
import java.io.*;
import java.util.*;


class Solution implements Iterable<Integer> {
  private int[] list;
  private Map<Integer, Integer> map;
  private int size;
  private final int INIT_CAPACITY = 4;
  
  public Solution() {
    list = new int[INIT_CAPACITY];
    map = new HashMap<>();
    size = 0;
  }
  
  public void add(int val) {
    if (size == list.length) {
      resize(2 * list.length); 
    }
    
    map.put(val, size);
    list[size] = val;
    size++;
  }
  
  public void remove(int val) {
    if (!map.containsKey(val)) {
      throw new NoSuchElementException();
    }
    
    // step 1: get the index of the val to be removed
    int idxToRemove = map.get(val);
    
    // step 2: move the last element to the index to be removed
    int lastE = list[size - 1];
    list[idxToRemove] = lastE;
    //list[size - 1] = null;
    
    size--;
    map.remove(val);
    map.put(lastE, idxToRemove);
    
    // shrink the array
    if (size > 0 && size == list.length / 4) {
      resize(list.length / 2);
    }
    
  }
  
  public boolean contains(int val) {
    return map.containsKey(val) && 
           map.get(val) < size && 
           val == list[map.get(val)];
  }

  public void clear() {
    size = 0;
  }
  
  @Override
  public Iterator<Integer> iterator() {
    return new MyListIterator();
  }
  
  private class MyListIterator implements Iterator<Integer> {
    private int i = 0;
    
    @Override
    public boolean hasNext() {
      return i < size;
    }
    
   @Override
    public Integer next() {
      Integer result = 0;
      if (hasNext()) {
        result = (Integer) list[i];
        i++;
      }
      
      return result;
    }
    
    @Override
    public void remove() {
      throw new UnsupportedOperationException();
    }
  }
  
  private void resize(int newSize) {
    int[] newList = new int[newSize];
    newList = Arrays.copyOf(list, size);
    list = newList;
  }
  
  public static void main(String[] args) {
    Solution sol = new Solution();
    sol.add(1);
    sol.add(3);

    sol.clear();
    
    sol.add(4);
    sol.add(5);
    
    System.out.println(sol.contains(3));
    
    Iterator<Integer> it = sol.iterator();
    while (it.hasNext()) {
      int val = it.next();
      System.out.println(val);
    }
  }
}



Method 2: Use two arrays
Use two arrays, map[n] and list[n], where for the map[i], the index stores the val of the data, and its value stores the index of the data in the list array. The real value is stored in the list array as well for the convenience of iterator() in O(num of elements) time. 

The basic idea of this solution is very close the method 1, just to use the map[] array to simulate a hash map. Therefore here we assume that the size of the map[] array is unlimited and the value of the data to be stored is never out of boundary. 

Code (Java):
import java.io.*;
import java.util.*;


class Solution implements Iterable<Integer> {
  private Integer[] map;
  private Integer[] list;

  private int size;
  private final int INIT_CAPACITY = 4;
  private final int MAP_CAPACITY = 1000;
  
  public Solution() {
    list = new Integer[INIT_CAPACITY];
    map = new Integer[MAP_CAPACITY];
    this.size = 0;
  }
  
  public void add(int val) {    
    if (size == list.length) {
      resize(2 * list.length); 
    }
    
    map[val] = size;
    list[size] = val;
    size++;
  }
  
  public void remove(int val) {
    if (!contains(val)) {
      throw new NoSuchElementException();
    }
    
    // step 1: get the index of the val to be removed
    int idxToRemove = map[val];
    
    // step 2: move the last element to the index to be removed
    int lastE = list[size - 1];
    list[idxToRemove] = lastE;
    list[size - 1] = null;
    
    size--;
    
    map[lastE] = idxToRemove;
    map[val] = null;
    
    
    
    // shrink the array
    if (size > 0 && size == list.length / 4) {
      resize(list.length / 2);
    }
  }
  
  public boolean contains(int val) {
    return map[val] != null && 
           map[val] < size && 
           val == list[map[val]];
  }

  public void clear() {
    size = 0;
  }
  
  @Override
  public Iterator<Integer> iterator() {
    return new MyListIterator();
  }
  
  private class MyListIterator implements Iterator<Integer> {
    private int i = 0;
    
    @Override
    public boolean hasNext() {
      return i < size;
    }
    
   @Override
    public Integer next() {
      Integer result = 0;
      if (hasNext()) {
        result = list[i];
        i++;
      }
      
      return result;
    }
    
    @Override
    public void remove() {
      throw new UnsupportedOperationException();
    }
  }
  
  private void resize(int newSize) {
    Integer[] newList = new Integer[newSize];
    for (int i = 0; i < size; i++) {
      newList[i] = list[i];
    }
    list = newList;
  }
  
  public static void main(String[] args) {
    Solution sol = new Solution();
    sol.add(1);
    sol.add(3);


    //sol.add(5);
    
    //System.out.println(sol.contains(3));
    
    sol.clear();
    
    sol.add(4);
    sol.add(5);
    
    System.out.println(sol.contains(3));
    
    //sol.remove(3);
    

    
    Iterator<Integer> it = sol.iterator();
    while (it.hasNext()) {
      int val = it.next();
      System.out.println(val);
    }
    
  }
}

No comments:

Post a Comment