DEV Community: Vadym Pinchuk

Coding Interviews questions: Building Data Structures in Dart

Vadym Pinchuk — Thu, 20 Jul 2023 13:31:25 +0000

In this article, we explore the main data structures such as trees, hash maps, linked lists, queues, stacks, heaps, and undirected graphs. We discuss their functionalities, space and time complexities, and provide code examples in Dart. Whether you're a beginner or an experienced developer, this comprehensive guide will equip you with the knowledge to effectively utilise data structures in your programming endeavors.

Content Overview

Introduction
Queue
Stack
Single Linked List
Double Linked List
Hash Map (Hash Table)
Min/Max Heap
Undirected Graph
Trees
Trees: Binary Search Tree (BST)
Trees: Red-Black Tree
Conclusion

Introduction

Data structures are fundamental building blocks in computer science and play a crucial role in organising and manipulating data efficiently. Whether you're a beginner learning programming or an experienced developer looking to refresh your knowledge, understanding how different data structures work is essential. We will dive into the world of data structures and explore their inner workings, space and time complexities, and best use cases. We will provide code examples in Dart, a versatile programming language, to help you grasp the concepts and see them in action. By the end of this article, you'll have a solid understanding of various data structures and be ready to apply them to solve real-world problems.In the Dart language, there is no specific data type called "array" in the traditional sense. Instead, the List class is used as the fundamental data structure to hold a collection of elements. It serves as a versatile container that provides array-like functionality and operations.

Queue

A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front.

Space Complexity:
O(n), where n is the number of elements in the queue.

Time Complexity:
Enqueue: O(1) - Adding an element to the queue.
Dequeue: O(1) - Removing an element from the queue.

Use case: Used when the First-In-First-Out (FIFO) principle needs to be followed, such as in a task scheduling system or breadth-first search algorithms.

class Queue<T> {
  List<T> _items = [];

  void enqueue(T item) {
    _items.add(item);
  }

  T dequeue() {
    if (isEmpty()) {
      throw StateError("Cannot dequeue from an empty queue.");
    }
    return _items.removeAt(0);
  }

  bool isEmpty() {
    return _items.isEmpty;
  }
}

Stack

A Stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Elements are added and removed from the same end, known as the top.

Space Complexity:
O(n), where n is the number of elements in the stack.

Time Complexity:
Push: O(1) — Adding an element to the stack.
Pop: O(1) — Removing an element from the stack.

Use case: Used when the Last-In-First-Out (LIFO) principle needs to be followed, such as in function call stacks or depth-first search algorithms.

class Stack<T> {
  List<T> _items = [];

  void push(T item) {
    _items.add(item);
  }

  T pop() {
    if (isEmpty()) {
      throw StateError("Cannot pop from an empty stack.");
    }
    return _items.removeLast();
  }

  bool isEmpty() {
    return _items.isEmpty;
  }
}

Single Linked List

Linked Lists are linear data structures where each element (node) contains a value and a reference to the next node.

Space Complexity:
O(n), where n is the number of nodes in the linked list.

Time Complexity:
Insertion at the beginning: O(1) — Adding a new node at the beginning of the linked list.
Insertion at the end: O(1) — Adding a new node at the end of the linked list.
Deletion: O(1) — Removing a node from the linked list.
Searching: O(n) — In the worst case, visiting all nodes in the linked list.

Use case: Used when frequent insertion and deletion of elements at the beginning or end of the list is required

class Node<T> {
  T value;
  Node<T> next;

  Node(this.value);
}

class LinkedList<T> {
  Node<T> head;

  void insertAtBeginning(T value) {
    var newNode = Node<T>(value);
    newNode.next = head;
    head = newNode;
  }

  void insertAtEnd(T value) {
    var newNode = Node<T>(value);
    if (head == null) {
      head = newNode;
    } else {
      var current = head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  void delete(T value) {
    if (head == null) {
      return;
    }
    if (head.value == value) {
      head = head.next;
      return;
    }
    var current = head;
    while (current.next != null) {
      if (current.next.value == value) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }
}

Double Linked List

Double Linked Lists are similar to single-linked lists, but each node has references to both the next and previous nodes.

Space Complexity:
O(n), where n is the number of nodes in the linked list.

Use case: Used when frequent insertion and deletion of elements at the beginning or end of the list is required

class Node<T> {
  T value;
  Node<T> next;
  Node<T> previous;

  Node(this.value);
}

class DoublyLinkedList<T> {
  Node<T> head;

  void insertAtBeginning(T value) {
    var newNode = Node<T>(value);
    if (head != null) {
      head.previous = newNode;
    }
    newNode.next = head;
    head = newNode;
  }

  void insertAtEnd(T value) {
    var newNode = Node<T>(value);
    if (head == null) {
      head = newNode;
    } else {
      var current = head;
      while (current.next != null) {
        current = current.next;
      }
      newNode.previous = current;
      current.next = newNode;
    }
  }

  void delete(T value) {
    if (head == null) {
      return;
    }
    if (head.value == value) {
      head = head.next;
      if (head != null) {
        head.previous = null;
      }
      return;
    }
    var current = head;
    while (current != null) {
      if (current.value == value) {
        current.previous.next = current.next;
        if (current.next != null) {
          current.next.previous = current.previous;
        }
        return;
      }
      current = current.next;
    }
  }
}

Hash Map (Hash Table)

Hash Maps store key-value pairs in an array, using a hash function to determine the index where each key-value pair should be stored.

Space Complexity:
O(n), where n is the number of key-value pairs stored.

Time Complexity:
Insertion: O(1) — Adding a key-value pair to the hash map.
Deletion: O(1) — Removing a key-value pair from the hash map.
Searching: O(1) — Retrieving the value associated with a given key.

Use case: Used for fast lookup of values based on keys when the relationship between keys and values is not necessarily ordered.

class HashMap<K, V> {
  int _capacity;
  List<List<Entry<K, V>>> _buckets;

  HashMap({int capacity = 16}) {
    _capacity = capacity;
    _buckets = List<List<Entry<K, V>>>.filled(_capacity, []);
  }

  int _hashCode(K key) {
    return key.hashCode % _capacity;
  }

  void put(K key, V value) {
    int index = _hashCode(key);
    List<Entry<K, V>> bucket = _buckets[index];
    for (Entry<K, V> entry in bucket) {
      if (entry.key == key) {
        entry.value = value;
        return;
      }
    }
    bucket.add(Entry<K, V>(key, value));
  }

  V get(K key) {
    int index = _hashCode(key);
    List<Entry<K, V>> bucket = _buckets[index];
    for (Entry<K, V> entry in bucket) {
      if (entry.key == key) {
        return entry.value;
      }
    }
    return null;
  }

  void remove(K key) {
    int index = _hashCode(key);
    List<Entry<K, V>> bucket = _buckets[index];
    for (Entry<K, V> entry in bucket) {
      if (entry.key == key) {
        bucket.remove(entry);
        return;
      }
    }
  }

  bool containsKey(K key) {
    int index = _hashCode(key);
    List<Entry<K, V>> bucket = _buckets[index];
    for (Entry<K, V> entry in bucket) {
      if (entry.key == key) {
        return true;
      }
    }
    return false;
  }
}

class Entry<K, V> {
  final K key;
  V value;
  Entry(this.key, this.value);
}

Min/Max Heap

A Heap is a binary tree-based data structure in which the parent nodes have a specific ordering (e.g., minimum or maximum value) with respect to their children.

Space Complexity:
O(n), where n is the number of elements in the heap.

Time Complexity:
Insertion: O(log n) — Adding an element to the heap.
Removal: O(log n) — Removing the root element from the heap.
Peek (accessing the minimum/maximum element): O(1).

Use case: Used to efficiently retrieve the minimum or maximum element in constant time or perform efficient sorting of elements.

class MinHeap {
  List<int> _heap;

  MinHeap() {
    _heap = [];
  }

  // Insert an element into the min heap
  void insert(int value) {
    // Add the new value to the end of the heap
    _heap.add(value); 
    // Restore the min heap property 
    // by moving the value up if necessary
    _moveUp(_heap.length - 1); 
  }

  // Extract the minimum element from the heap
  int extractMin() {
    if (isEmpty()) {
      throw Exception("Heap is empty");
    }
    // The minimum value is always at the root (index 0)
    final minValue = _heap[0]; 
    // Remove the last element from the heap
    final lastValue = _heap.removeLast();

    if (!isEmpty()) {
      // Move the last value to the root
      _heap[0] = lastValue; 
      // Restore the min heap property 
      // by moving the value down if necessary
      _moveDown(0); 
    }
    return minValue;
  }

  bool isEmpty() {
    return _heap.isEmpty;
  }

  // Get the index of the parent node of a given index
  int _parentIndex(int index) {
    return (index - 1) ~/ 2;
  }

  // Get the index of the left child node of a given index
  int _leftChildIndex(int index) {
    return 2 * index + 1;
  }

  // Get the index of the right child node of a given index
  int _rightChildIndex(int index) {
    return 2 * index + 2;
  }

  // Move a value up the heap 
  // to restore the min heap property
  void _moveUp(int index) {
    while (index > 0 && _heap[index] < _heap[_parentIndex(index)]) {
      final parentIndex = _parentIndex(index);
      _swap(index, parentIndex);
      index = parentIndex;
    }
  }

  // Move a value down the heap to restore the min heap property
  void _moveDown(int index) {
    while (true) {
      var smallest = index;
      final lChildIdx = _leftChildIndex(index);
      final rChildIdx = _rightChildIndex(index);
      if (lChildIdx < _heap.length 
          && _heap[lChildIdx] < _heap[smallest]) {
        // Update the smallest index if the left child is smaller
        smallest = lChildIdx;
      }
      if (rChildIdx < _heap.length 
          && _heap[rChildIdx] < _heap[smallest]) {
        // Update the smallest index if the right child is smaller
        smallest = rChildIdx;
      }
      if (smallest == index) {
        break;
      }
      // Swap the value with the smallest child
      _swap(index, smallest);
      // Move down to the smallest child index
      index = smallest;
    }
  }

  void _swap(int i, int j) {
    final temp = _heap[i];
    _heap[i] = _heap[j];
    _heap[j] = temp;
  }
}

To convert a max heap into a min-heap, the following changes need to be done:

Change the comparison operator: In a max heap, the comparison operator used for comparing elements is typically “greater than” (>). To convert it into a min heap, you need to change the comparison operator to “less than” (<) or “less than or equal to” (<=).
Adjust the heapify operation: The heapify operation is responsible for maintaining the heap property. In a max heap, it ensures that the maximum element is at the root. In a min heap, it needs to be modified to ensure that the minimum element is at the root.
Update any relevant code that relies on the assumption of a max heap: If there are any other parts of your code that assume a max heap, such as extraction of maximum element or operations based on the max heap property, you may need to modify them accordingly to work with a min heap.

Undirected Graph

An Undirected Graph consists of a set of vertices connected by edges, where the edges have no direction. Check this for different types of Graph data structure

Space Complexity:
O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Time Complexity:
Add Vertex: O(1) — Adding a vertex to the graph.
Add Edge: O(1) — Adding an edge between two vertices.
Remove Vertex: O(V + E) — Removing a vertex and all associated edges.
Remove Edge: O(1) — Removing an edge between two vertices.

Use case: Used to represent relationships between entities or to solve problems related to graph theory, such as pathfinding algorithms.

class Graph {
  Map<String, List<String>> _adjacencyList = {};

  void addVertex(String vertex) {
    if (!_adjacencyList.containsKey(vertex)) {
      _adjacencyList[vertex] = [];
    }
  }

  void addEdge(String vertex1, String vertex2) {
    _adjacencyList[vertex1]?.add(vertex2);
    _adjacencyList[vertex2]?.add(vertex1);
  }

  void removeVertex(String vertex) {
    _adjacencyList.remove(vertex);
    _adjacencyList.forEach((key, value) => value.remove(vertex));
  }

  void removeEdge(String vertex1, String vertex2) {
    _adjacencyList[vertex1]?.remove(vertex2);
    _adjacencyList[vertex2]?.remove(vertex1);
  }
}

Trees

In computer science, a tree is a widely used data structure that represents a hierarchical structure. Just like a real-life tree, it consists of nodes connected by edges. Each node in a tree can have zero or more child nodes, except for the root node, which has no parent. The nodes in a tree are organised in a specific way to allow efficient data manipulation and retrieval.

Types of Trees:

Binary Tree: A binary tree is a tree structure in which each node has at most two child nodes, referred to as the left child and the right child. Binary trees are commonly used as the basis for more complex tree structures.
Binary Search Tree (BST): A binary search tree is a binary tree where the values in the left subtree of a node are less than the node’s value, and the values in the right subtree are greater than or equal to the node’s value. BSTs are commonly used for efficient searching, insertion, and deletion operations.
AVL Tree: An AVL (Adelson-Velskii and Landis) tree is a self-balancing binary search tree. It maintains a balance factor for each node, ensuring that the heights of the left and right subtrees differ by at most one. AVL trees guarantee efficient logarithmic time complexity for various operations.
Red-Black Tree: A red-black tree is another self-balancing binary search tree. It ensures balanced properties by assigning colors (red or black) to nodes and performing rotations and color adjustments during insertion and deletion operations. Red-black trees provide efficient logarithmic time complexity for operations and are widely used in various applications.
B-Tree: A B-tree is a self-balancing tree structure designed for efficient disk access. It allows for multiple keys and child pointers per node, enabling efficient data storage and retrieval in external storage systems.
Trie: A trie, also known as a prefix tree, is a tree structure commonly used for efficient retrieval of strings or sequences. It stores characters of a string in a tree-like structure, making it efficient for prefix-based searches.

Common Tree Applications:

File systems: Directory structures in operating systems are often represented using trees.
Database systems: Indexing structures like B-trees are used for efficient data retrieval.
Compiler design: Syntax trees are used to represent the structure of programs.
Artificial Intelligence: Decision trees and search trees are used in various AI algorithms.
Networking: Routing algorithms use tree-based data structures for efficient packet routing.
Hierarchical data representation: Trees are used to represent hierarchical relationships in data, such as organisation charts or family trees.

Balanced Trees
A balanced tree is a type of tree data structure where the heights of the subtrees of any node differ by at most a constant factor. This balance ensures that the tree remains relatively symmetrical and avoids the creation of long paths that can lead to inefficient operations. Balanced trees are designed to provide optimal performance for various operations, such as searching, insertion, and deletion.

Some examples of balanced trees include AVL trees, red-black trees, and B-trees. These trees employ specific balancing mechanisms, such as rotations and color adjustments, to maintain their balanced properties.

Benefits of Balanced Trees:

Efficient Operations: Balanced trees offer efficient time complexities for operations like searching, insertion, and deletion. These operations typically have logarithmic time complexity, ensuring fast access to elements even as the size of the tree increases.
Stable Performance: By maintaining balance, these trees prevent worst-case scenarios where the tree becomes highly skewed and performance degrades significantly. Balanced trees provide stable and predictable performance across a wide range of inputs.
Optimal Space Utilisation: Balanced trees optimise space utilisation by minimising the height of the tree. This ensures that the tree structure occupies a reasonable amount of memory, regardless of the number of elements it contains.

Unbalanced Trees
Unbalanced trees, on the other hand, do not maintain the balance property. As a result, the heights of the subtrees of a node can differ significantly, leading to a skewed or elongated tree structure.

In an unbalanced tree, certain operations can become inefficient. For example, searching for an element may require traversing a long path, resulting in a time complexity closer to linear rather than logarithmic. Similarly, inserting or deleting nodes may disrupt the tree’s structure, making subsequent operations less efficient.

Unbalanced trees can occur due to various reasons, such as improper insertion and deletion operations or a specific pattern of data that causes the tree to become lopsided.

Impact of Unbalanced Trees:

Reduced Performance: Unbalanced trees can lead to poor performance for operations such as searching, insertion, and deletion. The time complexity may no longer be logarithmic, and the efficiency of the tree decreases as the number of elements grows.
Increased Memory Consumption: In some cases, unbalanced trees may require more memory than balanced trees to store the same number of elements. This is because unbalanced trees may have longer paths and higher heights.

It is important to note that unbalanced trees are not inherently bad or inappropriate in all scenarios. There are specific situations where unbalanced trees can still offer acceptable performance, especially if the tree remains relatively shallow or the number of elements is small.

Binary Search Tree (BST)

A Binary Search Tree is a binary tree-based data structure in which the left child node has a value smaller than its parent node, and the right child node has a value greater than or equal to its parent node.

Space Complexity:
O(n), where n is the number of nodes in the BST.

Time Complexity:
Search: O(log n) — Searching for a value in the BST.
Insertion: O(log n) — Inserting a value into the BST.
Deletion: O(log n) — Deleting a value from the BST.
In-order Traversal: O(n) — Visiting all nodes in ascending order.

Use case:
Searching for an element in a sorted collection efficiently.
Maintaining a collection of elements in sorted order.
Efficiently performing range queries (finding elements within a given range).
Implementing associative arrays with efficient key-value lookup.

class Node<T> {
  T value;
  Node<T> left;
  Node<T> right;

  Node(this.value);
}

class BinarySearchTree<T extends Comparable<T>> {
  Node<T> _root;

  void insert(T value) {
    _root = _insertRecursive(_root, value);
  }

  Node<T> _insertRecursive(Node<T> node, T value) {
    if (node == null) {
      return Node<T>(value);
    }
    if (value.compareTo(node.value) < 0) {
      node.left = _insertRecursive(node.left, value);
    } else {
      node.right = _insertRecursive(node.right, value);
    }
    return node;
  }

  bool search(T value) {
    return _searchRecursive(_root, value);
  }

  bool _searchRecursive(Node<T> node, T value) {
    if (node == null) {
      return false;
    }
    if (value.compareTo(node.value) == 0) {
      return true;
    }
    if (value.compareTo(node.value) < 0) {
      return _searchRecursive(node.left, value);
    } else {
      return _searchRecursive(node.right, value);
    }
  }

  void delete(T value) {
    _root = _deleteRecursive(_root, value);
  }

  Node<T> _deleteRecursive(Node<T> node, T value) {
    if (node == null) {
      return node;
    }
    if (value.compareTo(node.value) < 0) {
      node.left = _deleteRecursive(node.left, value);
    } else if (value.compareTo(node.value) > 0) {
      node.right = _deleteRecursive(node.right, value);
    } else {
      if (node.left == null && node.right == null) {
        node = null;
      } else if (node.left == null) {
        node = node.right;
      } else if (node.right == null) {
        node = node.left;
      } else {
        var minValue = _findMinValue(node.right);
        node.value = minValue;
        node.right = _deleteRecursive(node.right, minValue);
      }
    }
    return node;
  }

  T _findMinValue(Node<T> node) {
    while (node.left != null) {
      node = node.left;
    }
    return node.value;
  }

  void inOrderTraversal() {
    _inOrderTraversalRecursive(_root);
  }

  void _inOrderTraversalRecursive(Node<T> node) {
    if (node != null) {
      _inOrderTraversalRecursive(node.left);
      print(node.value);
      _inOrderTraversalRecursive(node.right);
    }
  }
}

Red-Black Tree

A Red-Black Tree is a self-balancing binary search tree that ensures the tree remains balanced by enforcing certain properties (such as colorings) on the nodes.

Space Complexity:
O(n), where n is the number of nodes in the Red-Black Tree.

Time Complexity:
Search: O(log n) — Searching for a value in the Red-Black Tree.
Insertion: O(log n) — Inserting a value into the Red-Black Tree.
Deletion: O(log n) — Deleting a value from the Red-Black Tree.
In-order Traversal: O(n) — Visiting all nodes in ascending order.

Use case:
Maintaining a sorted collection efficiently while supporting efficient insertion and deletion operations.
Implementing ordered data structures such as interval trees or augmented search trees.
Database indexing and storage systems where efficient searching, insertion, and deletion are essential.
enum NodeColor { red, black }

class RBNode<T extends Comparable<T>> {
  T value;
  RBNode<T> left;
  RBNode<T> right;
  RBNode<T> parent;
  NodeColor color;
  RBNode(this.value) {
    color = NodeColor.red;
  }
}

class RedBlackTree<T extends Comparable<T>> {
  RBNode<T> _root;

  void insert(T value) {
    var newNode = RBNode<T>(value);
    _insertNode(newNode);
    _fixViolation(newNode);
  }

  void _insertNode(RBNode<T> newNode) {
    if (_root == null) {
      _root = newNode;
      _root.color = NodeColor.black;
      return;
    }
    var current = _root;
    RBNode<T> parent;
    while (current != null) {
      parent = current;
      if (newNode.value.compareTo(current.value) < 0) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    newNode.parent = parent;
    if (newNode.value.compareTo(parent.value) < 0) {
      parent.left = newNode;
    } else {
      parent.right = newNode;
    }
  }

  void _fixViolation(RBNode<T> node) {
    RBNode<T> parent;
    RBNode<T> grandparent;
    while (node != _root && node.color == NodeColor.red 
            && node.parent.color == NodeColor.red) {
      parent = node.parent;
      grandparent = parent.parent;
      if (parent == grandparent.left) {
        var uncle = grandparent.right;
        if (uncle != null && uncle.color == NodeColor.red) {
          parent.color = NodeColor.black;
          uncle.color = NodeColor.black;
          grandparent.color = NodeColor.red;
          node = grandparent;
        } else {
          if (node == parent.right) {
            _rotateLeft(parent);
            node = parent;
            parent = node.parent;
          }
          _rotateRight(grandparent);
          var temp = parent.color;
          parent.color = grandparent.color;
          grandparent.color = temp;
          node = parent;
        }
      } else {
        var uncle = grandparent.left;
        if (uncle != null && uncle.color == NodeColor.red) {
          parent.color = NodeColor.black;
          uncle.color = NodeColor.black;
          grandparent.color = NodeColor.red;
          node = grandparent;
        } else {
          if (node == parent.left) {
            _rotateRight(parent);
            node = parent;
            parent = node.parent;
          }
          _rotateLeft(grandparent);
          var temp = parent.color;
          parent.color = grandparent.color;
          grandparent.color = temp;
          node = parent;
        }
      }
    }
    _root.color = NodeColor.black;
  }

  void _rotateLeft(RBNode<T> node) {
    var rightChild = node.right;
    node.right = rightChild.left;
    if (rightChild.left != null) {
      rightChild.left.parent = node;
    }
    rightChild.parent = node.parent;
    if (node.parent == null) {
      _root = rightChild;
    } else if (node == node.parent.left) {
      node.parent.left = rightChild;
    } else {
      node.parent.right = rightChild;
    }
    rightChild.left = node;
    node.parent = rightChild;
  }

  void _rotateRight(RBNode<T> node) {
    var leftChild = node.left;
    node.left = leftChild.right;
    if (leftChild.right != null) {
      leftChild.right.parent = node;
    }
    leftChild.parent = node.parent;
    if (node.parent == null) {
      _root = leftChild;
    } else if (node == node.parent.right) {
      node.parent.right = leftChild;
    } else {
      node.parent.left = leftChild;
    }
    leftChild.right = node;
    node.parent = leftChild;
  }

  bool search(T value) {
    var current = _root;
    while (current != null) {
      if (value.compareTo(current.value) == 0) {
        return true;
      } else if (value.compareTo(current.value) < 0) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }
}

Conclusion

In this article, we explored a wide range of data structures and their implementations in Dart. We covered various fundamental data structures, including sets, queues, linked lists, doubly-linked lists (deques), hash maps, undirected graphs, heaps, binary search trees (BST), and red-black trees.

Sets allow for storing unique elements efficiently and performing set operations such as union, intersection, and difference. Queues and deques are used for managing elements in a first-in-first-out (FIFO) manner, with deques also allowing efficient insertion and deletion at both ends.

Linked lists provide flexibility for dynamic element insertion and deletion, while hash maps enable fast key-value lookups based on a hash function. Undirected graphs were introduced as a way to represent relationships between entities, and we explored different graph traversal algorithms. Heaps, specifically the min heap and max heap variants, were discussed as tree-like structures useful for maintaining the minimum or maximum element at the root.

Finally, we delved into binary search trees (BST) and red-black trees, which are self-balancing binary search trees. We examined their properties, operations such as insertion, deletion, and searching, and their advantages in maintaining ordered collections efficiently.

By covering these diverse data structures, readers gained a comprehensive understanding of their functionalities, performance characteristics, and best use cases. Armed with this knowledge, developers are equipped to select and implement the most appropriate data structure for their specific problem domains, optimising efficiency and achieving scalable solutions.

From chaos to order: achieving understanding of algorithms through visualisation

Vadym Pinchuk — Thu, 06 Apr 2023 17:26:25 +0000

TL;DR

As a developer preparing for interviews with FAANG companies, I found myself struggling with simple algorithms like string traversal and palindrome checks. However, I persevered and, after nine months of hard work, was able to master even more specific algorithms like KMP. During this time, I relied on a notebook and pen to visualise how sorting algorithms work and how numbers are compared.

Where it started from

When I began preparing for interviews with FAANG companies, I struggled with simple algorithms such as String traversal and palindrome checks. There were times when I almost gave up, but I have always been one to finish what I start. The same approach was applied here, and after nine months of hard work, I went from struggling with simple algorithms to understanding more specific ones like KMP (which I like a lot).

On my journey to master these algorithms, I used a notebook and pen to visualise how sorting works, how numbers are compared, and where it all goes. This helped me to better understand the algorithms and improved my ability to work with them.

We are all developers

So why not create a project that visualises sorting algorithms in a more user-friendly way? Additionally, writing algorithmic solutions in a different language provides an extra opportunity to better understand and learn them.

I took advantage of this opportunity to improve my knowledge and develop a stronger understanding of the sorting pathway. By creating a mobile application using Flutter, I was able to utilise my experience with cross-platform development to build an effective tool for visualising complex algorithms, particularly sorting. This allowed me to further improve my knowledge and understanding of these algorithms while also creating a user-friendly platform for others to do the same.

Flutter is a handy tool

With solid experience in developing cross-platform applications using the Flutter framework, I chose to utilise it to create a mobile application for both Android and iOS operating systems. Currently, the same code can run on web and desktop platforms if I add support.

During the process I achieved:

I was able to write the same algorithms with Dart on top of Java implementations that I had done previously on Leetcode and AlgoExpert (both great resources for interview preparation).
I learned about the Provider (recommended to use Riverpod) state management pattern, which was not previously in my development stack. Provider allows for a great separation of logic and UI and reactively updates UI with consumed data, making updates process very smooth.
I also pushed my imagination beyond the norm and transformed a simple set of numbers into visually-pleasing widgets. To simplify the understanding of the algorithms, users can turn the numbers on and off.

My implementation

Each sorting algorithm is a descendant of BaseSort, which, in turn, is a ChangeNotifier. The details of each algorithm’s implementation are covered under its specific implementation: BubbleSort, HeapSort, InsertionSort, MergeSort, and SelectionSort. BaseSort only covers the basic parts of each algorithm, such as the references of left and right pointers, as well as the index of the sorted part. This class is responsible for generating random data and notifying each subscriber of a new dataset.

class BaseSort with ChangeNotifier {
  BaseSort() {
    generateData();
  }

  List<int> array = List.empty(growable: true);

  int left = -1;
  int right = -1;
  int sorted = -1;

  bool isSorting = false;

  @mustCallSuper
  void generateData() {
    array.clear();
    isSorting = false;
    int counter = 0;
    final rand = Random();
    left = -1;
    right = -1;
    sorted = -1;

    while (counter < 50) {
      // to show anything in case of 0 -> shifting it to 1
      array.add(rand.nextInt(99) + 1);
      counter++;
      notifyListeners();
    }
  }

  Future startSorting() async {}

  Future sleep() async {
    await Future.delayed(const Duration(milliseconds: 150), () {});
  }
}

BaseSortWidget is an abstract class that represents a collection of common widget parts, with several abstract methods to be implemented in each specific algorithm widget.

abstract class BaseSortWidget extends StatelessWidget {
  @override
  Widget build(BuildContext context) => Card(
        margin: const EdgeInsets.all(8.0),
        elevation: 2.0,
        shape: const RoundedRectangleBorder(
          borderRadius: BorderRadius.all(Radius.circular(12.0)),
        ),
        child: Padding(
          padding: const EdgeInsets.all(12.0),
          child: Column(
            mainAxisAlignment: MainAxisAlignment.center,
            children: <Widget>[
              Text(
                algorithmName(),
                style: const TextStyle(fontWeight: FontWeight.bold),
                textAlign: TextAlign.center,
              ),
              const SizedBox(height: 10),
              consumerWidget(),
              const SizedBox(height: 10),
              Text(
                algorithmComplexity(),
                style: const TextStyle(fontWeight: FontWeight.bold),
                textAlign: TextAlign.center,
              ),
            ],
          ),
        ),
      );
}

Each algorithm widget implementation, with the exception of SelectionSort, is simplified to a state of:

class HeapSortWidget extends BaseSortWidget {
  @override
  String algorithmName() => HEAP_SORT;

  @override
  String algorithmComplexity() => 'Time: O(n*log(n))  Space: O(1)';

  @override
  Widget consumerWidget() => Consumer<HeapSort>(
        builder: (context, state, _) => Row(
          mainAxisAlignment: MainAxisAlignment.center,
          crossAxisAlignment: CrossAxisAlignment.end,
          children: buildItemsArray(
            state.array,
            state.left,
            state.right,
            state.sorted,
            Colors.cyan,
          ),
        ),
      );
}

All the other parts are merely for aesthetic purposes, to create a cleaner and more elegant code. The main screen is a list of sorting widgets.

Consumer<SortHolder>(
  builder: (context, types, _) {
    final List<Widget> widgets = types.generateWidgets(context);
    return widgets.isEmpty
        ? Center(
            child: Text(
              '$DRAWER_TITLE\n\n$EMPTY_MESSAGE',
              textAlign: TextAlign.center,
              style: Theme.of(context)
                  .textTheme
                  .bodyLarge
                  .copyWith(fontSize: 18.0),
            ),
          )
        : ListView(
            padding: const EdgeInsets.all(8),
            children: widgets,
          );
  },
)

Whenever we add or remove widgets, the screen updates with more or fewer items. To hold data about widgets and to shuffle data/start sorting, we used SortHolder.

The view

The resulting view of my work looks very neat and is easily understandable.

Sorting process

Observing the sorting process is a true pleasure. Additionally, it is an easier way to understand the sorting algorithm by seeing which data is being compared. The left pointer is represented by yellow, while the right pointer is represented by red. Enjoy!

Summary

While preparing to algorithmic and data-structure interviews it might be tricky to master these complex topics. People are using different approaches to make is simpler, and easier to understand. Having no whiteboard, which could help me to visualise data, I have found simple notebook and pen quite useful, but for automatisation of the process and to repeat algorithms again, I have used coding, one instrument I am good at. Now we can observe how these algorithms are working. But I would love to extend this knowledge base with other more complex algorithms, which might be even harder to visualise. But still possible.

I am calling everyone, who want to participate in this project, to contribute to my gitHub via pull requests. I am happy to dedicate time for short catch-ups and collaboration.

VadymPinchuk / visualizer

Flutter project for sorting algorithms visualization

visualiser

As I geared up for a potential interview with a FAANG (MANGA) company, I acquired a wealth of new knowledge. While algorithms can be tedious, why not utilize Flutter for visualization? Creating visually appealing depictions of sorting algorithms could greatly enhance their comprehension and aesthetic appeal.

Getting Started

For playing around, adding new algorithms to the project, feel free to copy this repository, or make a pull request with any updates

Reach me out at LinkedIn: https://www.linkedin.com/in/vpinchuk/

Articles

Medium: https://medium.com/@vad.pinchuk/from-chaos-to-order-achieving-understanding-of-algorithms-through-visualisation-713e06baa7fd Dev.to: https://dev.to/vadympinchuk/from-chaos-to-order-achieving-understanding-of-algorithms-through-visualisation-81b HackerNoon: https://hackernoon.com/from-chaos-to-order-achieving-understanding-of-algorithms-through-visualization

View on GitHub

Exploring the Latest State of Flutter’s Experimental Feature for Developing Multiple-Entry Android Applications

Vadym Pinchuk — Sun, 02 Apr 2023 22:10:45 +0000

In the rapidly evolving world of mobile application development, developers need to keep themselves updated with the latest tools and frameworks. Flutter is one such framework that has gained immense popularity among developers due to its ease of use and flexibility. In a previous article and its updated version, I shared a sample application that I created to showcase the “Experimental feature on Flutter,” which enables the creation of multi-entry Android application using the Flutter framework. However, with the continuous evolution of Flutter, the framework has undergone significant changes since the initial version. In the current stable version 3.7.9, my sample app’s code looks significantly different. In this article, we will revisit the sample app, incorporating the fresher look and updated codebase, and provide an overview of the changes in the latest version of Flutter.

Problem statement

During my work on another Flutter project, I encountered an intriguing and somewhat unusual task. The project was required to function as a POS terminal on Android OS and other mobile devices but with a simplified version of the app that served as a regular application with a single-entry point on standard iOS and Android devices, without payments and bill printing. On the other hand, the extended fully functional POS-terminal version required a custom launcher, and the application was built and installed in such a way that it had multiple entry points leading to separated chunks of functionality, with no access from one point to another (for example, from catalogs to reports).

While this is a specific case that currently only applies to Android, I found the Flutter GitHub Repository’s wiki to be helpful at the beginning of my work. However, for some reason, it did not work correctly and caused problems with my project.

Although it is an experimental feature and an edge case in development, I decided to create a test application to make any future attempts easier. In the following pages, I will explain this test application and how it can be used to simplify the process of building multi-entry Android applications with Flutter.

Test application

The test application that I created to simplify building multi-entry Android applications with Flutter consists of three pages, each with its own unique colour and title, and buttons for navigation. These pages are named Amber, Blue, and Purple, and can be found on the AppBar. The application has three separate entry points while maintaining the same package name.

The “1 Amber” entry point leads to the limited functionality with the Amber page only.
The “1 Blue” entry point leads to the limited functionality with the Blue page only.
The “1 Purple” entry point leads to the Purple page only.
The “All 3 colors” is a fully functional application with 3 screens and interaction in between

The View

Single entry app (on the left) and multiple entry app (on the right)

Steps to reproduce

Creating a simple Flutter application with multiple entries is a straightforward process that can be accomplished by following a few simple steps. To get started, you can follow the guide provided in this article. Alternatively, you can clone my sample application, which is referenced in the footer of this article, to see an example of how it can be done.

Lets dive into Android code a bit, to define flavours we build:

To implement multi-entry functionality in our Flutter application, we need to define two or more build flavours in the app/build.gradle file. For the purposes of this article, I have created two build flavours: “single” and “multiple”:

productFlavors {

    multiple {
        dimension "app"
        versionCode 1
        versionName "1.0.0"
    }

    single {
        dimension "app"
        versionCode 1
        versionName "1.0.0"
    }
}

For each build flavour we need to create a dedicated directory within the project structure. The directory structure will look something like this:

The “main” directory in Android codebase will contain general resources and a simple entry point, but it will not be used for the build process.
On the other hand, the “multiple” directory will contain multiple implementations of the BaseActivity, which is responsible for defining the entry point name for the Flutter application:

abstract class BaseActivity : FlutterActivity() {

    abstract var entryPoint: String

    override fun getDartEntrypointFunctionName() = entryPoint

    override fun configureFlutterEngine(@NonNull flutterEngine: FlutterEngine) =
            GeneratedPluginRegistrant.registerWith(flutterEngine)
}

In the “single” directory there is only one AllColorsActivity, which is a fairly generic implementation:

class AllColorsActivity : FlutterActivity() {}

The final step on the Android side of our multi-entry Flutter application is to declare the activities in the AndroidManifest.xml file, with a separate title for each entry point:

<activity
    android:name=".AllColorsActivity"
    android:configChanges="orientation|keyboardHidden|keyboard|screenSize|locale|layoutDirection|fontScale|screenLayout|density|uiMode"
    android:exported="true"
    android:hardwareAccelerated="true"
    android:label="All 3 colors"
    android:launchMode="singleTop"
    android:theme="@style/LaunchTheme"
    android:windowSoftInputMode="adjustResize">
    <meta-data
        android:name="io.flutter.app.android.SplashScreenUntilFirstFrame"
        android:resource="@drawable/launch_background" />

    <meta-data
        android:name="io.flutter.embedding.android.NormalTheme"
        android:resource="@style/NormalTheme" />
    <intent-filter>
        <action android:name="android.intent.action.MAIN" />
        <category android:name="android.intent.category.LAUNCHER" />
    </intent-filter>
</activity>

As you develop your application in Android Studio, it’s crucial to create distinct build configurations for situations involving single and multiple entries. Remember, the last step in this process is just as vital as the first:

Flutter part is simple and very intuitive, while some code is just created for better feature showcasing.

In the main.dart file, create the main entry point along with a few alternative entry points, as demonstrated in the code. To prevent TreeShaking in release mode, make sure to mark the alternative entry points with the @pragma(‘vm:entry-point’) annotation.

void main() => runApp(
      MultiEntryApp(
        initialRoute: defaultRoute,
        primaryColor: Colors.blueGrey,
      ),
    );

@pragma('vm:entry-point')
void amber() => runApp(
  MultiEntryApp(
    initialRoute: amberRoute,
    primaryColor: Colors.pink,
  ),
);

In our multi-entry Flutter application, each entry point starts with its own route name, making route generation much simpler. The key to this functionality lies in the routes generation, which limits accessibility to some screens for each specific entry point. By defining routes in this way, we can ensure that users are only able to access the screens that are relevant to their entry point, providing a clear and intuitive user experience:

const String defaultRoute = "/";
const String amberRoute = "/amber";
const String blueRoute = "/blue";
const String purpleRoute = "/purple";

The code for route generation may not be the most elegant or sophisticated, but it is simple and easy to understand:

Route<dynamic> generateRoute(RouteSettings settings, String initial) {
  switch (initial) {
    case blueRoute:
      return CupertinoPageRoute(builder: (context) => BluePage(false));
    case purpleRoute:
      return CupertinoPageRoute(builder: (context) => PurplePage(false));
    case amberRoute:
      return CupertinoPageRoute(builder: (context) => AmberPage(false));
    default:
      return _allRoutes(settings);
  }
}

And with that, we have covered all of the key components of building a multi-entry Flutter application.

Important notes

To prevent entry points in our Flutter application from being removed during the tree-shaking process, it is important to annotate them with the @pragma(‘vm:entry-point’) annotation. This tells the compiler to keep the entry points in the final executable, ensuring that they are available for use by the application.
To ensure that our multi-entry Flutter application routes correctly and avoid any confusion, it is recommended to use initialRoute: “/”’ in the MaterialApp.
In earlier versions of Flutter, using Experimental feature could potentially cause issues with the SplashScreen. However, starting from Flutter v1.12 and future versions, this is no longer a problem, as the Splash screen is now defined in the activity meta-data by using ‘io.flutter.app.android.SplashScreenUntilFirstFrame’.

Summary

In summary, while the techniques and approaches discussed in this article may not work for every situation or project, they provide valuable insights into the process of building a multi-entry Flutter application. It is important for developers to remain flexible and adapt to the needs of the project and the users. By sharing our experiences and insights, we can encourage others to explore the possibilities of Flutter and push the boundaries of mobile application development.

GitHub - VadymPinchuk/multiple_entry