Write a program to Implement a queue using the stack. The implemented queue should support standard operations like enqueue, dequeue, and front. This is an excellent problem to learn problem-solving and visualize the use case of stack and queue operations.
The code structure of a well-designed algorithm using data structure is just like a good house design. So learning algorithms require a good understanding of data structures properties, implementation techniques, and efficiency of critical operations. The fact is: Data Structures are the core building blocks of algorithms and real-life applications.
Level order traversal accesses nodes in level by level order. This is also called breadth-first search traversal or BFS traversal. Here we start from the root node and process it, then process all the nodes at the first level, then process all the nodes at the second level, and so on. In other words, we explore all nodes at the current level before moving on to the nodes at the next level.
We know that a binary tree is a rooted tree in which each node has no more than two children. We can extend this definition to an n-ary tree. If a tree is rooted in which each node has no more than N children, it is called an n-ary tree. In other words, n-ary trees are tree data structures with up to n children nodes for each node.
Suffix trees are a compressed version of the trie that includes all of a string's suffixes. Suffix trees can be used to solve many string problems that occur in text-editing, free-text search, etc. The ability to search efficiently with mismatches might be considered their greatest strength.
AVL Trees named after its inventors Adelson-Velsky and Landis, is a unique variation of the Binary Search Tree, which is a self-balancing BST. The property of AVL Trees is that they automatically attain the tree's minimum possible height after executing any operation.
Trie is a famous data structure used to store and process data, especially strings. It is a tree where each node represents a prefix or end of a word (the path traced from the root to that node). The word trie comes from retrieval as a trie can retrieve all the words with a given prefix.
In this blog, we will learn how to use segment trees for efficient point and range updates. For the point update query, update(idx, val), we need to increment the element at the index idx from the original array by val, i.e. arr[idx] = arr[idx] + val. For the range update query, update(l, r, val), we must increment all the elements from index l to r from the original array by val.
Hashing is a technique to map (key, value) pairs into the hash table using a hash function. It uses an array of size proportional to the number of keys and calculates an array index from the key using a hash function. Explore this blog to learn how hash tables work in programming?
A heap is a complete binary tree structure where each element satisfies a heap property. We learn two types of the heap in programming: 1) max-heap, which satisfies the max heap property, and 2) min-heap, which satisfies the min-heap property. We use the heap to implement the priority queue efficiently.
A Segment Tree is a data structure used to answer multiple range queries on an array efficiently. Also, it allows us to modify the array by replacing an element or an entire range of elements in logarithmic time. This blog will focus on the build and query operations on segment trees.
To process data stored in a binary tree, we need to traverse each tree node, and the process to visit all nodes is called binary tree traversal. In this blog, we will be discussing three popular recursive tree traversals: preorder, inorder and postorder traversals. These traversals are also called depth-first search traversal or dfs traversal in data structures.
We cannot adjust the size of regular arrays in the middle of the code execution. We solve this problem using the dynamic array, where we can increase the array size dynamically as we need them. The Vector class in C++ and ArrayList in Java class use a dynamic array for storing the elements.
Bloom filter is a space-efficient data structure that tells whether an element may be in a set (either a false positive or true positive) or definitely not present in a set (True negative). It will take O(1) space, regardless of the number of items inserted. However, their accuracy decreases as more elements are added.
The least frequently used (LFU) is a cache algorithm used to manage memory within a computer. In this method, the system keeps track of the number of times a block is referenced in memory, and when the cache is full, our system removes the item with the lowest reference frequency.
A Fenwick tree is a data structure that efficiently updates elements and calculates prefix sums in an array. It takes O(logn) time for both updates and range sum queries. It is also called Binary Indexed Tree (BIT), which was first described in the paper titled “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).
The Least Recently Used (LRU) is one of the popular caching strategies, which defines the policy to discard the least recently used items first from the cache and make room for new elements when the cache is full. It is used to organize items in order of their use, which allows identifying items that have not been used for a long time.
Write a program to implement a stack using the queues. The implemented stack should support standard operations like push(x), pop(), and top(). This is an excellent problem to learn problem-solving and visualize the use case of stack and queue operations.
An array is a contiguous block of memory of the same type of elements where the size is equal to the number of elements in that array, which must be fixed. It is a structure of data such that each element can be efficiently located by its index or memory address.
Write a program to detect the loop in a linked list. A linked list with a cycle causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list has no cycle before trying an iteration. So, we are going to discuss various algorithms to detect a loop in a singly linked list. This is also one of the best-linked list interview problems.
Write a program to reverse a linked list. A head pointer of a linked list is given and our task to reverse the entire list so that when the resulted list is traversed it looks like we are traversing the original list from tail to head.
In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.