Data Structures

What is your favorite data structure and why?

My favorite data structure is the Trie. It is a tree-like data structure that is widely used for efficiently storing and retrieving strings. It is especially useful for searching for patterns in a large dataset and is used in a number of applications such as spell checkers, autocomplete systems, and IP routing.

What makes Trie my favorite data structure is its ability to handle large amounts of data with a very low time complexity for both insertion and search operations. It is also very space-efficient, making it a good choice for memory-constrained systems. In addition, the structure of a Trie allows for quick prefix-based searches, which can be very useful in certain applications.

Overall, the Trie is a highly versatile and efficient data structure that is well-suited for a wide range of applications and is one of the most important tools in a computer scientist's toolkit.

Difference between a linked list and an array?

A linked list is a data structure that consists of a series of nodes, where each node stores a value and a reference to the next node in the list. In contrast, an array is a data structure that stores a fixed-size collection of elements, each of which can be accessed using an index.

One key advantage of linked lists over arrays is that inserting or deleting elements in the middle of a linked list is a relatively simple operation. With arrays, on the other hand, inserting or deleting elements requires shifting all the elements after the insertion/deletion point, which can be time-consuming.

Another advantage of linked lists is that they are dynamic in size, meaning that you can add or remove elements as needed without having to specify the size of the list in advance. With arrays, on the other hand, you must specify the size of the array when you create it and you cannot change the size once it has been created.

On the other hand, arrays are much more efficient when it comes to accessing individual elements, as you can access any element in constant time using an index. With linked lists, you must traverse the list from the beginning to access a specific element, which can be slow for large lists.

How would you implement a stack or a queue?

A stack and a queue are two fundamental data structures in computer science. Both structures have specific uses based on the ordering of elements within them.

A stack is a Last-In-First-Out (LIFO) data structure, meaning that the last item pushed onto the stack will be the first item popped off. The stack has two main operations, push and pop. Push adds an element to the top of the stack, and pop removes the element from the top of the stack. In Java, a stack can be implemented using an array or a linked list.

Implementation using an array

class Stack {
  int[] stackArray;
  int top;

  public Stack(int size) {
    stackArray = new int[size];
    top = -1;
  }

  public void push(int value) {
    top++;
    stackArray[top] = value;
  }

  public int pop() {
    int popped = stackArray[top];
    top--;
    return popped;
  }

  public boolean isEmpty() {
    return (top == -1);
  }
}

A queue, on the other hand, is a First-In-First-Out (FIFO) data structure, meaning that the first item added to the queue will be the first item removed. Queues have two main operations, enqueue and dequeue. Enqueue adds an element to the end of the queue, and dequeue removes the element from the front of the queue. In Java, a queue can be implemented using an array, a linked list, or a circular buffer.

Implementation using a linked list

class Queue {
  Node front, rear;

  public Queue() {
    this.front = this.rear = null;
  }

  static class Node {
    int data;
    Node next;

    public Node(int data) {
      this.data = data;
      this.next = null;
    }
  }

  public void enqueue(int data) {
    Node newNode = new Node(data);

    if (this.rear == null) {
      this.front = this.rear = newNode;
      return;
    }

    this.rear.next = newNode;
    this.rear = newNode;
  }

  public int dequeue() {
    if (this.front == null) {
      throw new NoSuchElementException("Queue is Empty");
    }

    int data = this.front.data;
    this.front = this.front.next;

    if (this.front == null) {
      this.rear = null;
    }
    return data;
  }
}

What is a hash table and how does it work?

A hash table is a data structure that allows for constant-time O(1) average-case lookups, insertions, and deletions. A hash table consists of an array of buckets and a hash function that maps each key to a bucket index.

The hash function takes the key as input and converts it into an integer index within the range of the array. When a new key-value pair is inserted into the hash table, the hash function is used to determine the index of the corresponding bucket where the value will be stored. If multiple keys result in the same index, a collision occurs and the hash table must handle this by using a collision resolution strategy, such as chaining or open addressing.

In chaining, each bucket is a linked list and when a collision occurs, the value is added to the end of the linked list for that bucket. In open addressing, the hash function tries to find the next available bucket until it finds an empty one to store the value.

Implementation of a hash table using chaining

import java.util.LinkedList;

public class HashTable {
  private int size;
  private LinkedList<Entry>[] bucketArray;

  public HashTable(int size) {
    this.size = size;
    bucketArray = new LinkedList[size];
    for (int i = 0; i < size; i++) {
      bucketArray[i] = new LinkedList<>();
    }
  }

  static class Entry {
    int key;
    int value;

    public Entry(int key, int value) {
      this.key = key;
      this.value = value;
    }
  }

  public int hashFunction(int key) {
    return key % size;
  }

  public void put(int key, int value) {
    int index = hashFunction(key);
    LinkedList<Entry> bucket = bucketArray[index];
    for (Entry entry : bucket) {
      if (entry.key == key) {
        entry.value = value;
        return;
      }
    }
    bucket.addLast(new Entry(key, value));
  }

  public int get(int key) {
    int index = hashFunction(key);
    LinkedList<Entry> bucket = bucketArray[index];
    for (Entry entry : bucket) {
      if (entry.key == key) {
        return entry.value;
      }
    }
    return -1;
  }

  public void remove(int key) {
    int index = hashFunction(key);
    LinkedList<Entry> bucket = bucketArray[index];
    for (Entry entry : bucket) {
      if (entry.key == key) {
        bucket.remove(entry);
        return;
      }
    }
  }
}

Difference between a heap and a priority queue?

A priority queue is an abstract data type that represents a queue where each element has a priority assigned to it, and the element with the highest priority is removed first.

A heap is a specific implementation of a priority queue, where the elements are stored in a binary tree structure such that the parent node is always of higher priority than its child nodes. There are two types of heaps: a max heap where the largest element is the root, and a min heap where the smallest element is the root.

The main difference between a priority queue and a heap is that a priority queue is an abstract data type, while a heap is a specific implementation of that abstract data type. Other implementations of priority queues include binary search trees and sorted arrays.

How would you implement a binary search tree?

A binary search tree (BST) is a data structure that stores elements in a tree structure where each node has a value, and the

left child node has a value that is less than its parent node and the right child node has a value that is greater than its parent node.

Implementation of a binary search tree

class BST {
  class Node {
    int key;
    Node left, right;

    public Node(int item) {
      key = item;
      left = right = null;
    }
  }

  Node root;

  BST() {
    root = null;
  }

  void insert(int key) {
    root = insertRec(root, key);
  }

  Node insertRec(Node root, int key) {
    if (root == null) {
      root = new Node(key);
      return root;
    }
    if (key < root.key)
      root.left = insertRec(root.left, key);
    else if (key > root.key)
      root.right = insertRec(root.right, key);
    return root;
  }

  void inorder() {
    inorderRec(root);
  }

  void inorderRec(Node root) {
    if (root != null) {
      inorderRec(root.left);
      System.out.println(root.key);
      inorderRec(root.right);
    }
  }
}

Implement a LRU (Least Recently Used) Cache and explain its time complexity?

A LRU (Least Recently Used) cache is a cache management system that discards the least recently used items first. It can be implemented using a doubly linked list and a hash table. The hash table stores the keys and their corresponding addresses in the linked list, and the linked list stores the values in the order of their usage, with the most recently used item at the front and the least recently used item at the end.

The time complexity for adding an element to the cache is O(1), as it only requires a hash table lookup and a linked list update. The time complexity for accessing an element in the cache is also O(1) on average, as it only requires a hash table lookup.

Implementation of a LRU cache

import java.util.HashMap;

public class LRUCache {
  static class Node {
    int key;
    int value;
    Node prev;
    Node next;

    public Node(int key, int value) {
      this.key = key;
      this.value = value;
      prev = null;
      next = null;
    }
  }

  HashMap<Integer, Node> map = new HashMap<>();
  int capacity;
  Node head = null;
  Node end = null;

  public LRUCache(int capacity) {
    this.capacity = capacity;
  }

  public int get(int key) {
    if (map.containsKey(key)) {
      Node n = map.get(key);
      remove(n);
      setHead(n);
      return n.value;
    }
    return -1;
  }

  public void remove(Node n) {
    if (n.prev != null) {
      n.prev.next = n.next;
    } else {
      head = n.next;
    }
    if (n.next != null) {
      n.next.prev = n.prev;
    } else {
      end = n.prev;
    }
  }

  public void setHead(Node n) {
    n.next = head;
    n.prev = null;
    if (head != null)
      head.prev = n;
    head = n;
    if (end == null)
      end = head;
  }

  public void set(int key, int value) {
    if (map.containsKey(key)) {
      Node old = map.get(key);
      old.value = value;
      remove(old);
      setHead(old);
    } else {
      Node created = new Node(key, value);
      if (map.size() >= capacity) {
        map.remove(end.key);
        remove(end);
        setHead(created);
      } else {
        setHead(created);
      }
      map.put(key, created);
    }
  }
}

Concept of a Trie and how it's different from other tree structures?

A Trie, also known as a prefix tree, is a tree-based data structure that is used for efficient search and retrieval of strings. It is different from other tree structures, such as binary search trees, in that each node in a Trie represents a single character in a string rather than a whole string.

The Trie stores the strings by breaking them down into individual characters and adding each character as a child node to the parent node. The root node of the Trie represents an empty string and the final leaf node represents a complete string. This allows for efficient searching of strings that start with a specific prefix, as the Trie only needs to traverse the nodes that represent the prefix characters.

The time complexity for searching for a string in a Trie is O(m), where m is the length of the string. This is because the Trie only needs to traverse the nodes that represent the characters in the string.

Implementation of a Trie

class TrieNode {
  TrieNode[] children = new TrieNode[26];
  boolean isEndOfWord;

  TrieNode() {
    isEndOfWord = false;
    for (int i = 0; i < 26; i++)
      children[i] = null;
  }
};

class Trie {
  TrieNode root;

  Trie() {
    root = new TrieNode();
  }

  void insert(String key) {
    int level;
    int length = key.length();
    int index;

    TrieNode pCrawl = root;

    for (level = 0; level < length; level++) {
      index = key.charAt(level) - 'a';
      if (pCrawl.children[index] == null)
        pCrawl.children[index] = new TrieNode();
      pCrawl = pCrawl.children[index];
    }
    pCrawl.isEndOfWord = true;
  }

  boolean search(String key) {
    int level;
    int length = key.length();
    int index;
    TrieNode pCrawl = root;

    for (level = 0; level < length; level++) {
      index = key.charAt(level) - 'a';
      if (pCrawl.children[index] == null)
        return false;
      pCrawl = pCrawl.children[index];
    }

    return (pCrawl != null && pCrawl.isEndOfWord);
  }
};

Can you implement an AVL tree?

An AVL tree is a self-balancing binary search tree, where the difference in height between the left and right subtrees of any node is at most 1. When the tree becomes unbalanced, AVL trees perform rotations to restore the balance, making insertion and deletion operations in an AVL tree more efficient than in a binary search tree.

Implementation of an AVL tree

class AVLNode {
  int key, height;
  AVLNode left, right;

  AVLNode(int d) {
    key = d;
    height = 1;
  }
};

class AVLTree {
  AVLNode root;

  int height(AVLNode N) {
    if (N == null)
      return 0;
    return N.height;
  }

  int max(int a, int b) {
    return (a > b) ? a : b;
  }

  AVLNode rightRotate(AVLNode y) {
    AVLNode x = y.left;
    AVLNode T2 = x.right;

    x.right = y;
    y.left = T2;

    y.height = max(height(y.left), height(y.right)) + 1;
    x.height = max(height(x.left), height(x.right)) + 1;

    return x;
  }

  AVLNode leftRotate(AVLNode x) {
    AVLNode y = x.right;
    AVLNode T2 = y.left;

    y.left = x;
    x.right = T2;

    x.height = max(height(x.left), height(x.right)) + 1;
    y.height = max(height(y.left), height(y.right)) + 1;

    return y;
  }

  int getBalance(AVLNode N) {
    if (N == null)
      return 0;
    return height(N.left) - height(N.right);
  }

  AVLNode insert(AVLNode node, int key) {
    if (node == null)
      return (new AVLNode(key));

    if (key < node.key)
      node.left = insert(node.left, key);
    else if (key > node.key)
      node.right = insert(node.right, key);
    else
      return node;

    node.height = 1 + max(height(node.left), height(node.right));

    int balance = getBalance(node);

    if (balance > 1 && key < node.left.key)
      return rightRotate(node);

    if (balance < -1 && key > node.right.key)
      return leftRotate(node);

    if (balance > 1 && key > node.left.key) {
      node.left = leftRotate(node.left);
      return rightRotate(node);
    }

    if (balance < -1 && key < node.right.key) {
      node.right = rightRotate(node.right);
      return leftRotate(node);
    }

    return node;
  }

  void preOrder(AVLNode node) {
    if (node != null) {
      System.out.print(node.key + " ");
      preOrder(node.left);
      preOrder(node.right);
    }
  }
};

Difference between a balanced and an unbalanced tree?

A balanced tree is a tree where the difference in height between the left and right subtrees of any node is at most 1. This balance ensures that the tree has efficient operations, with a time complexity of O(log n) for search, insert, and delete operations.

An unbalanced tree is a tree where the height difference between the left and right subtrees is greater than 1, making the operations less efficient with a time complexity of O(n) in the worst case. Unbalanced trees can arise when nodes are inserted in such a way that they form a linear structure, leading to longer search times.

Difference between a B-tree and a B+ tree?

B-trees and B+ trees are both balanced trees used for storing large amounts of data in an ordered manner.

A B-tree is a multi-level index, where each node can have multiple children, allowing it to store large amounts of data while keeping the height of the tree small. A B-tree has the property that all nodes except the root and the leaves have a minimum number of children, making it possible to store more keys in each node, reducing the height of the tree and making search operations more efficient.

A B+ tree is an extended form of the B-tree, where all keys and values are stored in the leaves of the tree, and only the keys are stored in the internal nodes. This makes B+ trees more efficient for range searches and disk storage, since all values can be accessed by following the pointers from the leaves, without the need to access the internal nodes.

Write code to implement a segment tree for range queries and updates?

A segment tree is a data structure used for efficient range queries and updates in an array. It is a binary tree where each node represents a range of values in the original array.

Here is an example implementation of a segment tree in Java:

[INSERT CODE EXAMPLE HERE]

How a disjoint-set data structure can be used to solve the Kruskal's algorithm for finding the minimum spanning tree?

The disjoint-set data structure, also known as the union-find data structure, is used to solve the Kruskal's algorithm for finding the minimum spanning tree of a graph. The disjoint-set data structure keeps track of a partition of the nodes in the graph into disjoint sets.

In Kruskal's algorithm, the edges of the graph are sorted in increasing order of their weights. The algorithm then iteratively adds the smallest edge that connects two disjoint sets, until all nodes are part of the same connected component.

The disjoint-set data structure is used to keep track of which nodes are in the same set and which nodes are in different sets. When adding an edge to the minimum spanning tree, the disjoint-set data structure is used to determine if the two nodes connected by the edge are in the same set. If they are in different sets, the edge is added to the minimum spanning tree and the two sets are combined into a single set.

Implement a graph data structure using an adjacency list or an adjacency matrix?

A graph can be implemented in Java using either an adjacency list or an adjacency matrix.

Graph implemented using an adjacency list

import java.util.ArrayList;
import java.util.List;

class AdjacencyListGraph {
  int V;
  List<Integer>[] adj;

  AdjacencyListGraph(int V) {
    this.V = V;
    adj = new ArrayList[V];
    for (int i = 0; i < V; i++) {
      adj[i] = new ArrayList<>();
    }
  }

  void addEdge(int u, int v) {
    adj[u].add(v);
  }
};

Graph implemented using an adjacency matrix

class AdjacencyMatrixGraph {
  int V;
  int[][] adj;

  AdjacencyMatrixGraph(int V) {
      this.V = V;
    adj = new int[V][V];
  }

  void addEdge(int u, int v) {
    adj[u][v] = 1;
  }
};