Velut arbor aevo.
When we are scheduling jobs or tasks, they may have dependencies, i.e., before we finish task a, we have to finish b first. In this case, given a set of tasks and their dependencies, how shall we arrange our schedules? There comes another graph algorithm: Topological Sort.
Continue reading “Graph Algorithm: Topological Sort”
Backtracking is a general algorithm … that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
https://en.wikipedia.org/wiki/Backtracking
Note: This is the second part for BFS, DFS and Backtracking. The first part is here: [Leetcode for Interview]DFS, BFS, and Backtracking I.
After Intro to Graph Algorithms – BFS & DFS, let’s take a look at some popular and most common interview questions. Questions that fall under this category are quite typical and static, so it’s not difficult to master them if you go through the following lists, and then you will find patterns in their solutions.
Continue reading “[Leetcode for Interviews]DFS, BFS, and Backtracking I”Graphs are a pervasive data structure in computer science, and algorithms for working with them are fundamental to the field.
Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.
Given a graph defined as G=(V,E) which is a set of vertices and edges, we’d be curious about how to represent it and how to search it systematically so as to visit the vertices following the edges. This blog will briefly introduce two ways of representations of a graph, and then will dive deep into two graph search algorithms: Breadth-First-Search (BFS) and Depth-First-Search (DFS).
Continue reading “Intro to Graph Algorithms – BFS & DFS”
Question: Given a preorder traversal, reconstruct the binary search tree and return the root. Input:Continue reading “[Leetcode]1008. Construct Binary Search Tree from Preorder Traversal”[8,5,1,7,10,12]Output:[8,5,10,1,7,null,12]Visiualization of the output:
After introducing traversing trees using BFS and DFS in Tree Traversal – Recursively & Iteratively – Preorder, Inorder, Postorder, it’s time to get some practices! Here are Leetcode questions that appear frequently during tech interviews.
Continue reading “[Leetcode for Interviews] BinaryTree Traversal – DFS & BFS”Tree traversal refers to the process of visiting each node in a tree data structure (Wikipedia). The two general strategies are Depth-First-Search (DFS) and Breadth-First-Search (BFS). For BFS, it iterates through the tree level by level with Queue, from top to bottom. When using DFS, there are three different ways: Preorder, Inorder, and Postorder.
Continue reading “Tree Traversal – Recursively & Iteratively”