Algorithms

What is a Trie? A Trie is a data structure usually called a “prefix tree,” often represented as a nested tree of dictionaries where each key is a character that maps to the next character in a word. Let’s look at some examples of a Trie. The Trie consists of two main classes: the TrieNode class and the Trie class. TrieNode The TrieNode class has two properties: children - a property that represents all characters in a given word and points to the next character. isEndSymbol - a property that indicates the end of the word in a given sequence of characters. final class TrieNode { var children: [Character: TrieNode?] var isEndSymbol: Bool init() { self.children = [:] self.isEndSymbol = false } } Trie The Trie class has two main operations, insert and exists, and a root property that stores all possible combinations of words. ...

What is a Tree? A Tree is a data structure that has a root and subtrees of children, representing a set of linked nodes. Trees behave similarly to a LinkedList in that they have a collection of nodes starting with a head (root). The main difference is that Trees can have multiple children, whereas a LinkedList, on the other hand, can have only one next child. I’m going to focus on a commonly used type of tree, the Binary Search Tree. ...

What is the sliding window technique? The sliding window technique is a common algorithmic approach used to create a fixed-sized window that moves through the data one step at a time, typically from left to right, to perform specific operations or computations on the elements within the window. What is the sliding window algorithm? The sliding window algorithm is a method for finding a subset of elements that satisfy certain conditions in a given problem. ...

What is a Linked List? A linked list is a common data structure that is similar to an array, but its order is based on pointers to the next element in memory instead of using physical placement (indices). A linked list has two main components: ListNode class: This class has a val property that represents the value and a next property that represents a pointer to the next element in memory. LinkedList class: This class stores a collection of ListNode elements and provides operations like add to tail and add to head. The add to tail operation takes O(n) time because it needs to iterate through the list to find the last element. The add to head operation takes O(1) time because it only needs to set the next pointer of the new node to the current head and update the head with the new node. Where can it be used? A linked list can be used in stacks, queues, and lists. ...

What is binary search? Binary search is an algorithm that helps find an element in a sorted array in O(log n) time. Why should the input be sorted before performing binary search? The input array for binary search needs to be sorted because the algorithm eliminates half of the choices at each step. If the guessed value is greater than the target value, it knows that the right part can’t contain the target value. ...