Training.md

Basic Data Structures

Lists, Stacks, Queues, Maps

Lists

Definition

• Linear type of data, guarentee random access (depending on the implementation), keeps ordre of the elements entered, Implemented as an array that grows automatically .

Access Time Complexity

• read O(1), add O(1), remove O(N)

Code example

  List<Integer> list = new ArrayList<>();
  list.add(10);
  list.remove(10);
  list.get(0);

• Note: use ArrayList instead of Vector in java, as the first one is not synchronized .

Queues

Definition

• a FIFO implementation, generally represented as an array or a LinkedList

Access Time Complexity

• read O(1), addFirst O(1), removeLast O(1)

Code Example

  Queue<Integer> qa = new ArrayDeque<>();
  Queue<Integer> ql = new LinkedList<>();
  qa.add(10);
  qa.poll();
  qa.peek();

Stacks

Definition

• a LIFO implementation, generally represented as an array or a linkedList

Access Time Complexity

• read O(1), addFirst O(1), removeFirst O(1)

Code Example

  Stack<Integer> stack = new Stack<>();
  stack.add(10);
  stack.peek();
  stack.pop();

Priority Queues

Definition

• just as queues but the ordre of the elements matter, implemented using binary heaps (fibonnacci heaps)

Access Time Complexity

• add O(log(N)), poll O(log(N))

Code Example

  PriorityQueue<Integer> pq = new PriorityQueue<>();
  pq.add(10);
  pq.peek();
  pq.poll();

Maps

Definition

• Non linear Data structures, keeps the elements in Key - Value pairs, implemented using arrays and hash functions, or binary search trees

Access Time Complexity

• get O(Log(N)) or O(1), put O(Log(N)) or O(1), remove O(Log(N)) or O(1)

Code Example

  Map<String, Integer> map = new HashMap<>();
  map.put("age", 12);
  map.get("age");
  map.removeKey("age");

Practice Problems:

• Simple Text Editor
• Monk and Multiplication
• Pair Sums