IT FundamentalsAlgorithms & Data StructuresAlgorithms

Algorithms

Algorithms explained here:

Binary Search

A search algorithm used to find the position of a specific element in a sorted list. This is done by continously guessing the middle number until we find it. This algorithm is in contrast with Linear Search algorithm (which is inefficient - O(n)).

The runtime of Binary Search is O(log(n)). Binary Search only works when the list is sorted.

💡

A Linear Search is a simple algorithm that finds an item in a list by checking each item in order until a match is found. Also known as Sequential Search.

Depth-First Search (DFS)

2 most important algorithms (the most commonly asked questions in interviews after arrays):

  • Depth-First Search (DFS) - O(V + E)
  • Breadth-First Search (BFS)

Note: V — Vertices / Nodes, E — Edges / Branches

The idea of DFS is to start from the root node and go as far down one branch as possible all the way to the end. Once we hit the deepest point (why it’s called Depth First Search), we come back to an unvisited branch and go down that one (backtracking). Example usage of DFS is solving a Maze (originally created for).

Steps of DFS:

  1. Before doing any DFSs, create a visited array visited = [] that keeps track of the nodes we’ve visited.
  2. Add the visited nodes to the array.
  3. Once we’re at the bottom-most (depth) of the graph, check (backtrack) the previous nodes if there are any unvisited nodes.
  4. If there are any, add to the visited array.
  5. Repeat number 3 and 4 until all nodes in the graph are visited.

Sources

Data Structures