Top 5 MUST know algorithms for coding interviews

As a final year undergrad who is preparing for on-campus and off-campus opportunities and doing some intensive research, I have came across some of the commonly asked algorithms in coding interviews. Please note that these algos are not the end of your interview preparation, you have to solve a lot of patters questions to stand out in an interview but knowing these algos, you will have an upper hand.

Photo by Андрей Сизов on Unsplash

In this article, you will find the following algorithms :-

1. Sliding Window
2. BFS
3. DFS
4. Topological Sorting
5. Dijkstra algorithm

Sliding Window

The Sliding window is a problem-solving technique for problems that involve arrays/lists. These problems are easy to solve using a brute force approach in O(n²) or O(n³). Using the sliding window technique, we can reduce the time complexity to O(n).

So, how to identify that a problem can be solved using sliding window, luckily there are some common patterns involved in a problem :

• The problem will involve a data structure that is ordered and iterable like an array or a string.
• We are looking for some subrange in the array/string like longest, shortest or target value.
• There is an apparent naive or brute force solution that runs in O(n²) or O(2 ^n) or some other large complexity, i.e. we are doing repetitive work which we can avoid.

e.g. Suppose we have an array like [1, 2, 3, 4, 5, 6] , and we have to calculate a subarray of size 3 having maximum sum.

so, our repetitive work would look like this :

1 + 2 + 3
  2 + 3 + 4
    3 + 4 + 5
      4 + 5 + 6      

Here, we are adding previous last two values, in each iteration.

Some basic steps to solve sliding window problem :

• Take HashMap or dictionary to count specific array input and uphold on increasing the window towards right using an outer loop.
• Take one inside a loop to reduce the window side by sliding towards the right. This loop will be very short.
• Store the current maximum or minimum window size or count based on the problem statement.

Example : Finding maximum sum of k consecutive elements of an array

int maxSumKConsecutive(int arr[], int n, int k) {

    // Compute the sum of the first k elements to initialize maxSum
    int maxSum = 0;
    for (int i = 0; i < k; i++) {
        maxSum += arr[i];
    }

    // Initialize the current window sum as maxSum
    int windowSum = maxSum;

    // Slide the window through the array
    for (int i = k; i < n; i++) {
        // Add the next element to the current window sum
        windowSum += arr[i];

        // Subtract the element that is no longer in the window
        windowSum -= arr[i - k];

        // Update maxSum if the current window sum is greater
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }

    return maxSum;
}

Breadth-Fist Search(BFS)

Breadth-First Search (BFS) is a fundamental graph traversal algorithm used to explore graphs or trees. It operates by visiting all the nodes of a graph in a breadthward motion, meaning it explores all the neighbors of a vertex/node before moving on to their neighbors.

The breadthwise motion involves :

• First move horizontally and visit all nodes of the current level and then after traversing all nodes of current level, move to the next level.

Some basic steps to solve BFS problem:

• Take a queue
• Add root node in the queue
• Run loop for all elements in queue. Pop that element and push its child nodes in the queue.

Example : Level order traversal of binary tree

void LevelOrder(Node * root) {
    
  if (root == NULL) return;
  
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
      Node * node = q.front();
      cout << node -> data << " ";
      q.pop();
      if (node -> left != NULL)
        q.push(node -> left);
      if (node -> right != NULL)
        q.push(node -> right);
   }
}

Here we are printing nodes of binary tree level wise . So we take queue push root element and run loop for elements in queue and add both child of that root in queue and pop the root node.

Depth-First Search(DFS)

Depth-First Search (DFS) is an algorithm that is mainly used to traverse the graph data structure. The algorithm starts from an arbitrary node (root node in case of trees) and explore as far as possible in the graph before backtracking.

DFS algorithm works as follow :

• Start by putting any one of the graph’s vertices on top of a stack.
• Take the top item of the stack and add it to the visited list.
• Create a list of that vertex’s adjacent notes. Add the ones which aren’t in the visited list to the top of the stack.
• Keep repeating steps 2 and 3 until the stack is empty.

Example : General DFS for graph

void dfs(int i, vector<int>& vis, vector<int> adj[], vector<int>& res){
        res.push_back(i);
        vis[i] = 1;
        for(auto it : adj[i]){
            if(!vis[it]){
               dfs(it,vis,adj,res);
            }
        }
        return;
    }
    
    vector<int> dfsOfGraph(int V, vector<int> adj[]) {
         vector<int>res;
         vector<int>vis(V,0);
         for(int i=0;i<V;i++)
         {
             if(!vis[i])
             dfs(i,vis,adj,res);
         }
         return res;
    }

Topological Sorting

Topological sorting for DAG(Directed acyclic graph) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.

Steps involved in topological sorting :

• Use a temporary stack.
• Don’t print the vertex immediately
• First recursively call topological sorting for all its adjacent vertices, then push it to a stack.
• Print all elements of stack.

Example : Topological sort in a graph

void dfs(int node , vector<int> adj[] , vector<int> &vis , stack<int> &st){
     
     
     vis[node] =1;
     for(auto x : adj[node]){
         if(!vis[x]){
             dfs(x , adj , vis , st);
         }
     }
     
     st.push(node);
     
     
 }
 
 vector<int> topoSort(int V, vector<int> adj[]) 
 {
     vector<int> vis(V);
     stack<int> st;
     vector<int> ans;
     
     for(int i=0;i<V;i++){
         if(!vis[i]){
             dfs(i,adj,vis,st);
         }
     }
 
 
     while(!st.empty()){
         ans.push_back(st.top());
         st.pop();
     }
     
     return ans;
 }

Dijkstra Algorithm

This algorithm allows us to find the shortest path between any two vertices of a graph.

Steps involved in Dijkstra algorithm :

• Initialize priority queue and distance vector.
• Set distance vector to a large value except for the source vertex, which is set to 0.
• Continuously selects the vertex with the smallest tentative distance.
• Updates distances to neighboring vertices if shorter paths are found.
• Ensures vertices are explored in order of increasing distance from the source.

Example : Implementing Dijkstra Algorithm.

vector <int> dijkstra(int V, vector<vector<int>> adj[], int S)
    {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        vector<int> dist(V);
        for(int i = 0; i < V; i++) dist[i] = 1e9;
        
        dist[S] = 0;
        pq.push({0,S});
        while(!pq.empty()) {
            int dis = pq.top().first;
            int node = pq.top().second;
            pq.pop();
            for(auto it : adj[node]) {
                int edgeWeight = it[1];
                int adjNode = it[0];
                
                if(dis + edgeWeight < dist[adjNode]) {
                    dist[adjNode] = dis + edgeWeight;
                    pq.push({dist[adjNode], adjNode});
                }
            }
        }
        return dist;
    }

Given a weighted, undirected and connected graph of V vertices and an adjacency list adj where adj[i] is a list containing two integers where the first integer of each list j denotes there is edge between i and j, second integers corresponds to the weight of that edge.