Print unique rows in a boolean matrix

Unique rows in boolean matrix

Given a matrix of 0 and 1, print all unique rows in boolean matrix. For example, if the matrix is show below:
0 1 0 0 1
1 0 1 1 1
0 1 0 0 1
1 0 1 0 0
Output should be
 0 1 0 0 1
 1 0 1 1 1
1 0 1 0 0

The first brute force solution which has a complexity of O(n2 m) where is n is the number of rows and m is the number of columns is as follows:
For each row in the boolean matrix, check all the rows if it matches with any one of them. If yes, skip printing, else print the row.
Another way which is better than the above approach is to convert each row in equivalent decimal and then check for duplicates. Again it has a complexity of O(n * m) where n is the number of rows and m as the number of columns.

Can we do better than this? There is a standard technique to check if a particular pattern is already seen or not. That’s using tries. Each pattern is added to trie, when we try to add a duplicate pattern, we will end up at the leaf node which is already marked as leaf due to an earlier pattern.
With given info, we can say that we will insert each row pattern in the trie. We will modify the insert function of trie to return us whether the row is added newly or it was already present in the trie. As explained above it can be ascertained by the fact that if the last node is marked as leaf node already, then it is duplicate row as we must have traveled the same nodes above. If the last node is not a leaf node already, then there is at least one digit which is different and hence row becomes unique. Mark last node of this pattern as a leaf node, so that same patterns will be detected as duplicates.

Add a row in the trie.
If the last node while entering the pattern is the leaf node, return false. It’s not a unique row.
If the last node is not a leaf node, mark it as a leaf node and return true.
If insert operation returns true, print the row.
Else, skip printing row.

#include<stdio.h>
#include<stdlib.h>

#define MAX_SIZE 2

#define LEAF_NODE  1
#define true 1
#define false 0

typedef struct trie_node_t {
    int value;
    struct trie_node_t * children[MAX_SIZE];
}Node;

typedef struct trie{
    int count ;
    Node *root;
}trie;

void initialize(trie *t){
    t->root = (Node *)malloc(sizeof(Node));
    t->count =0;
}

int insert_1(trie *t, int key[], int col){

    int i;

    if(t->root == NULL){
        printf("\n Trie is not initialized\n");
    }

    Node * current = t->root;
    for(i=0; i<col; i++){
        int index  =  key[i];
        if(current->children[index] == NULL){
            current->children[index] = (Node *)malloc(sizeof(Node));
        }
        current = current->children[key[i]];
    }

    /* To mark it as leaf */
    if(current->value != LEAF_NODE){
        current->value = LEAF_NODE;
        return true;
    }
    else{
        return false;
    }
}

void print_unique_rows(int a[5][5], int col, int row){

    int i,j;
    int key[col];

    trie t;
    initialize(&t);
    for(i=0; i<row; i++){
        for(j=0; j<col; j++){
            key[j] = a[i][j];
        }
        if(insert_1(&t, key, col)){
            for(j=0;j<col; j++){
                printf("%d", key[j]);
            }
            printf("\n");
        }
    }
}
//Driver program
int main(){

    int a[4][5] = {{0, 1, 0, 0, 1},
                    {1, 0, 1, 1, 0},
                    {0, 1, 0, 0, 1},
                    {1, 0, 1, 0, 0}
                  };

    print_unique_rows(a, 5, 4 );

    return 0;
}

The complexity of trie based solution is O(n * m).

Merge overlapping intervals

Given N intervals S = {E1,E2,…..En} with each Ei has start time si and end time ei. Some of these intervals are overlapping. The problem statement is to merge these overlapping intervals.

Ei and Ej overlap when start time of Ej i.e sj is less than end time of Ei i.e ei.

For example:

Input:
[(1,3),(2,4),(5,8), (6,9)] 
Output: 
[(1, 4),(5,9)]
Explantion:
Interval (1,3) and (2,4) and interval (5,8) and (6,9) overlap.

merge overlapping intervals

Merge overlapping intervals solution

As we always do, first try to come up with brute force solution, given enough time and space and money, how would you solve this?
The natural course is to take ith interval and compare start time of all jth intervals with end time of ith, if the start time of jth interval is less than the end time of ith event, then you can merge intervals. What should be end time for merged interval then?  It should be a maximum of end times of two merged intervals.

What will be the time complexity of this approach? We are not using any additional space, however, the worst-case time complexity is O(n2). Can we do better?

What are two times we are comparing in brute force solution? It’s the start time of one interval with the end time of another. If we arrange input in a specific order, can we reduce processing some entries?

If we sort all intervals based on their start time, si < si+1< si+2. Also, interval is always forward looking, ei > si, ei+1 > si+1 and so on.

If si is greater ei-1, then si+1 will be greater than ei-1, so no need to compare si+1 with ei-1, that is no need to go beyond immediate previous interval for any interval Ei.

If si is less than ei-1, update ei-1 with maximum of ei-1 and ei and move to Ei+1.

Notice that we need last interval Ei-1 to decide if to merge new interval into previous one or keep it as standalone. A stack is the best data structure to use. The algorithm will look like:

  1. Consider interval Ei.
  2. If stack is empty, push Ei to stack.
  3. If stack is not empty, then pop interval at top of stack call it Ei-1.
  4. Compare si, start time of Ei with ei-1, end time of Ei-1.
  5. If si less than ei-1, update ei-1 as max(ei-1, ei), as in maximum of end times of two intervals and push back Ei-1on to stack.
  6. Else push Ei on to stack.
  7. Continue till all events are considered.
  8. At the end of processing, stack will contain all merged interval.

Let’s take an example and see how this algorithm works. We have following intervals and we have to merge overlapping intervals.
algorithm to merge overlapping intervals
algorithm to find overlapping intervals java

Find the maximum of end times of two intervals and update the previous interval with that end time and push it back on to stack.

At this point, when there is no more interval remaining, the stack contains all merged overlapping intervals.

Merge intervals Java implementation

package com.company;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;

/**
 * Created by sangar on 8.4.18.
 */
public class OverlappingIntervals {
    public  static ArrayList<Interval>
        mergeOverlappingIntervals(ArrayList<Interval> intervals){

        ArrayList<Interval> mergedIntervals = new ArrayList<>();
        Stack<Interval> s = new Stack();

        //Sort the ArrayList of interval based on start time.
        Collections.sort(intervals, Comparator.comparing(p -> p.getStartTime()));
        for(Interval currentInterval : intervals){
            if(s.empty())s.push(currentInterval);
            else {
                Interval previousInterval = s.pop();
                if(previousInterval.getEndTime() > 
                     currentInterval.getStartTime()){
                    /*
                    If current interval's start time is less than end time of
                    previous interval, find max of end times of two intervals
                    and push new interval on to stack.
                     */
                    int endTime = Integer.max(previousInterval.getEndTime(),
                                              currentInterval.getEndTime());
                    /* Notice that we have created new interval and 
                       did not update the old one
                       This concept is called as immutability of class
                     */
                    s.push(new Interval(previousInterval.getStartTime(),
                                        endTime));
                }
                else{
                    s.push(previousInterval);
                    s.push(currentInterval);
                }
            }
        }
        while(!s.empty()){
            mergedIntervals.add(s.pop());
        }

        return mergedIntervals;
    }

    public static void main(String[] args) {
        ArrayList<Interval> intervals = new ArrayList<>();

        intervals.add(new Interval(1,3));
        intervals.add(new Interval(2,4));
        intervals.add(new Interval(5,8));
        intervals.add(new Interval(6,9));
        ArrayList<Interval> mergedIntervals 
                    = mergeOverlappingIntervals(intervals);
        for (Interval interval : mergedIntervals){
            System.out.print("(" + interval.getStartTime() +"," 
                      + interval.getEndTime() + ")");
        }
    }
}
Complexity of algorithm to merge overlapping intervals will be O(nlogn) due to sorting with O(n) extra space for stack and then copying into the list to return also takes O(n) space.

There is another way to implement the same function without using the stack, here we use the fact that ArrayList in Java is implemented using the array as the base and getting an element at a particular index should be O(1) operation. The code looks more or less the same, however, there is no traversal of the stack at the end to create the list to return.

find overlapping intervals

public List<Interval> mergeOptimized(List<Interval> intervals) {

        if(intervals.size() == 0) return intervals;

        Collections.sort(intervals, 
           (Interval a, Interval b) -> a.getStartTime() - b.getStartTime());

        List<Interval> mergedIntervals = new ArrayList<Interval>();
        for(Interval interval : intervals){

            /*If the merged list is empty add the interval to 
              it or check if the last interval in merged list overlaps

            /*Remember the get function on ArrayList is O(1) operation
              because Arraylists in Java are backed by arrays */
            if(mergedIntervals.isEmpty()
                    || mergedIntervals.get(
                           mergedIntervals.size()-1).getEndTime() < 
                           interval.getStartTime() ){
                mergedIntervals.add(interval);
            }
            else {
                int lastEndTime = Math.max(
                        mergedIntervals.get(mergedIntervals.size()-1)
                                            .getEndTime(),
                        interval.getEndTime()
                );
                mergedIntervals.get(mergedIntervals.size()-1)
                                     .setEndTime(lastEndTime);
            }
        }

        return mergedIntervals;
    }

You can use the above snippet of code to submit for this leetcode problem and it should be accepted.

Please share if there is something missing or wrong. Also, please reach out to us at [email protected] if you want to contribute to the website and help others to learn by sharing your knowledge. If you are preparing for an interview and need some coaching to prepare for it, please sign up for the free session with us.

Largest sum subarray

Largest sum subarray (Kadane’s algorithm)

Given an array of integers (positive and negative), find largest sum subarray, that is contiguous elements in array, which add up to maximum sum. This problem is solved using Kadane’s algorithm. For example, for array {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3}, largest sum subarray will be {4,6,-1,2,-7,13} with sum = 17.

What will be the brute force solution, without considering any time complexity? Well, scan all the subarrays of an array and take the one which has the maximum sum. How many such subarrays can be there? If size of array is n, n * (n -1 ) / 2 subarrays, hence complexity of brute solution will O(n2)

package com.company;

/**
	* Created by sangar on 20.8.18.
	*/
public class KadaneAlgorithm {
	public static int largestSumSubarray (int[] a){
		int maxSum = Integer.MIN_VALUE;

		for(int i=0; i < a.length; i++){
			int currentSum = 0;
			for(int j=i; j < a.length; j++){
				currentSum+= a[j];
				if(maxSum < currentSum){
					maxSum = currentSum;
				}
			}
		}
		return maxSum;
	}
	public static void main(String args[]) {
		int[] a = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
		System.out.println(largestSumSubarray(a));
	}
}

Dynamic programming approach

Dynamic programming builds solutions from the bottom up by breaking each problem down into smaller, problems that you solve first. Recursion also breaks problems down into subproblems but does this from the top down. One advantage of dynamic programming over recursion is that it prevents possible duplicate solutions of the same subproblem, which uses less CPUs and generally makes your code run faster.

Code Chef Wiki

How can we fill create the solution bottom-up? Consider a case where there is only one element in the array. What will be the largest sum subarray? Haha, it the element itself. 
Assume now, that there is one more element in the same array, what will be the condition that you will include the second element into the largest sum subarray? Obviously, if adding the second element increase the previous sum.

Also, there is a possibility that the second element itself is the largest sum subarray or it starts from the second element. If the first number was negative and the second one is positive, the second number itself is bigger than the sum, no matter what. So, the second element becomes the current sum.

Rule is that, at each element j, take the maximum of sum of the current element and accumulated sum till previous index and current element.

current_sum  = max ( current_sum + A[j], A[j])

Now, you have the current sum at element A[j], see if it is greater than global maximum till now? If yes, replace global maximum with current sum.

if(maxSum < currentSum )
	maxSum = currentSum;

Let’s see how this algorithm works with an example. we have an array as [-1, 4, 2, -1]

  1. Set a maxSum and currentSum, both equal to first element of array to start
  2. Now, look at the next element which is 4, so subarray under consideration is [-1, 4], the maximum is either current element or is the sum of the current element plus the previous maximum (-1 + 4 = 3)
  3. Since 4 > 3, the currentSum is 4, and since 4 > -1, we can update the maxSum as well
  4. With the value of the next index (2), the maximum is either 2 or is the sum of the current element plus the previous maximum (4 + 2 = 6)
  5. Next element is -1, which is less than currentSum, so currentSum remains as it is, so is maxSum.

Hope this example helps to understand the beauty of this Kadane’s algorithm to find largest sum subarray in an array.

Kadane’s algorithm does not work with an array with all elements being negative. What we can do is that scan all elements of array prior to application of the algorithm and if there is at least one positive number. Also during this phase keep track of the largest number seen. If all elements are negative, just return the largest number.

Largest sum subarray : Kadane’s algorithm implementation

package com.company;

/**
	* Created by sangar on 20.8.18.
*/
public class KadaneAlgorithm {
	public static int kadaneAlgorithm (int[] a){
		int maxSum = a[0];
		int currentSum = a[0];
		
		for(int i=1; i<a.length; i++) {
			currentSum = Integer.max(a[i], currentSum + a[i]);
			if (maxSum < currentSum) {
				maxSum = currentSum;
			}
		}
		return maxSum;
	}
	public static void main(String args[]) {
		int[] a = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
		System.out.println(kadaneAlgorithm(a));
	}
}

Complexity of finding largest sum subarray in an array is O(N) in time and O(1) in space.

Please share if there is something wrong or missing. If you are interested in contributing to the website, please reach out to us at [email protected]

References:

  • https://www.codechef.com/wiki/tutorial-dynamic-programming
  • https://www.hackerrank.com/challenges/maxsubarray/problem

Merge point of two linked lists

Merge point of two linked lists

Given two linked lists, we need to find out that if two linked lists merge, if yes, find the merge point.
For example, in the figure below, node(5) is the merge point of two linked lists.

merge point of two linked list

How can we identify that two linked lists do not merge? Easy, if two linked lists merge at any given node including the last node, the last node should be the same. If the last nodes of two linked lists are different, we can safely say that two linked lists do not merge.

Merge point of two linked lists

How to find the merge point is the next problem. From the above diagram, notice that all the nodes after the merge point are the same if two linked lists are merged at a certain node. So that part of two linked lists is common to both.
We can use this insight to find the merge point. If lengths of two linked lists are equal, then we can just start traversal of those lists from heads and they will meet the merge point.

What if the lengths are different? In this case, there is an equal number of nodes in two linked list after the merge point. The difference has to be before the merge point. If we get the difference between the lengths and move the pointer on the longer list head by the difference, we will reach the merge point at the same time when we traverse lists again.

merge point of two linked lists

If the length of two linked lists is different, the problem reduces to the problem where we need to reach the end of two lists at the same time. There is a simple solution to that.

Implementation

#include<stdlib.h>
#include<stdio.h>

typedef struct node{
    int data;
    struct node *next;
} Node;

void print_list(Node * head){
        while(head){
                 printf("%d->" , head->data );
                 head = head->next;
        }

        printf("NULL");
        printf("\n");

}

int merge_point(Node *L1, Node *L2){

        Node * current1 = L1;
        Node * current2  = L2;

        int count_1 = 0;
        int count_2 = 0;
        //If any one list is null, return false
        if(!current1 || !current2 ) return -1;

        //Count number of nodes in list 1;
        while(current1->next){
                count_1++;
                current1 = current1->next;
        }
        // Count number of nodes in list 2
        while(current2->next){
                count_2++;
                current2 = current2->next;
        }
        /*If last nodes of both linked list are not same,
        linked list don't merge. */
        if(current1 != current2)
                return -1;

        //Calculate the difference in lengths of linked list.
        int diff = abs(count_1 - count_2);

        //Move the longer linked list by diff number of nodes
        if(count_1 < count_2){
                Node * temp = L1;
                L1 = L2;
                L2 = temp;
        }
        current1 = L1;
        current2 = L2;

        while(diff && current1){
                diff--;
                current1 =  current1->next;
        }
        // Now move both linked list till they meet at merge point
        while(current1 != current2){
                current1 =  current1->next;
                current2 =  current2->next;
        }
        return current1->data;
}

void push(Node **head, int value){
    if(*head == NULL){
        (*head) = (Node *)malloc(sizeof(Node));
        (*head)->data = value;
        (*head)->next = NULL;
    }
    else{
        Node * newNode= (Node *)malloc(sizeof(Node));
        if(newNode){
            newNode->data = value;
            newNode->next = (*head);
            *head = newNode;
        }
    }
}

void main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
 		push(&L1,3);
 		Node * temp1 = L1;
        push(&L1,4);
        push(&L1,6);
        push(&L1,7);
        push(&L1,8);
        push(&L1,9);
        print_list(L1);
        printf("\n");
        push(&L2,5);
        Node * temp2 = L2;
        push(&L2,7);
        push(&L2,8);
        push(&L2,2);
        push(&L2,1);
        push(&L2,10);
        printf("\n");

        temp2->next = temp1;

        print_list(L2);
        int result1 = merge_point(L1, L2);
        if(result1 != -1){
                printf("\n Merge Point : %d", result1);
        }
        else{
                printf("\n Lists don't merge");
        }
}

The complexity of the algorithm to find merge point of two linked list is O(n), however, we scan the lists multiple times.

Please share if there is something wrong or missing. If you are preparing for an interview and want to have personalized coaching, please signup for a free demo session.

Right view of a binary tree

Right view of a binary tree

We learned different traversals of a binary tree like inorder, preorder, postorder, level order etc in previous posts. Today’s problem includes traversal of a binary tree too but in a different manner. The problem statement is to write a program to print the right view of a binary tree. The first question would be what is the right view of a binary tree?

Right view of a binary tree would be all the nodes of the binary tree which are visible when the tree is looked at from the right-hand side of the binary tree. For example, we would see nodes: 10, 15, and 19 when we look at the binary tree below from the right side as node 7 will be hidden by node 15 and node 8,9 and 18 will be hidden by node 19.

right view of a binary tree
Right view of a binary tree

Right view of a binary tree: thoughts

What do we see when we look at the tree from the right-hand side? What is the observation? It is that once we see a node, we can not see any node which is on the same level behind the visible node. The visible node obstructs all other nodes.
Which node will be the first one to be visible? It would be the rightmost node on that level. So we have to visit the right child of a node first before we visit the left child. If there was a right child of a node, the left child will not be visible. How can we make sure even the cousins of the rightmost node are not visible?

The idea is simple, we will do a preorder traversal of a binary tree with the right child visited first. Why? Because if we see the right child, the left child will not be visible as explained above.

To make sure none of the cousins are visible of a rightmost node are visible, we have to keep track of the levels. When we reach a node, we see if the level of the node is deeper than already seen maximum level? If yes, this node is the rightmost node (Why? because we are visited right child first) on that level and should be visible. Now, the maximum visited level is this new level, all the nodes which are this new level will not be visible.

Right view of a binary tree: example

Let’s take an example and see how this method works.

right view of a binary tree

We have current max level traversed as -1. At node(10), we visit the level 0 which is greater than the current maximum. So node(10) should be visible in the right view of the binary tree.

right view of binary search tree

At node(15), we are moving down a level, so the current level would be 1, whereas current max visited level is 0. node(15)will be visible from the right-hand side of the tree. The max level visited is 1.

right side view of binary tree

As we are doing preorder traversal, we will visit node(19) next, which is at level 2 which is greater than max level, so, node(19) will be visible in the right view of the binary tree.

right view of binary tree

Next, we visit the node(18), which is at the level 2, which is equal to max level, hence node(18) will not be visible.

node(7) is at the level 1, which is less than current max level 2, so it will not be visible. Same is the case for the node(8) and node(9).

Right view of a binary tree: implementation

#include<stdio.h>
#include<stdlib.h>

struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

void printRightView(Node * node, int currLevel, int *maxLevel){

	if(node == NULL) return;

	if(currLevel >  *maxLevel){
		printf("%d  ", node->value);
		*maxLevel = currLevel;
	}
	printRightView(node->right, currLevel+1, maxLevel);
	printRightView(node->left, currLevel+1, maxLevel);
}
/* driver program */
Node * createNode(int value){
	Node *temp =  (Node *)malloc(sizeof(Node));
	temp->value = value;
	temp->right= NULL;
	temp->left = NULL;
	return temp;
}

Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

int main(){

    Node *root = NULL;
    //Creating a binary tree
    root = addNode(root,6);
    root = addNode(root,3);
    root = addNode(root,2);
    root = addNode(root,1);
    root = addNode(root,7);
    root = addNode(root,5);
    root = addNode(root,9);
    
    int max = -1;
    printRightView(root, 0, &max);

    return 0;
}

We visit each node only once, complexity of above code is O(n).

Please share if there is something wrong or missing. If you are willing to contribute and share your learning with thousands of learners across the world, please reach out to us at [email protected]

Please signup for free interview material.

Subarrays with sum zero

Given an array of positive and negative integers, find number of subarrays with sum zero in that array. For example, in the array given below, there are two subarrays whose elements sum to zero.

Input:
A = [1,3,2,-1,5,4,-8,4,3,-7]
Output:
4
Explanation:
Sybarrays [-1,5,4,-8], [4,-8,4], [-1,5,4,-8,4,3,-7] and [4,3,-7] are subarrays with zero sum.

Brute force method solve this problem will be to find all subarrays of the given array and then add them individually to see if any subarray adds up to zero. There can be n * (n-1) subarrays for a given array of size n, so the complexity of brute force solution is O(n2).

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSumBrute(int[] a){
        int len = a.length;
        int count = 0;
        for(int i=0; i<len; i++){
            int  sum  = 0;
            for(int j=i; j<len; j++){
                sum += a[j];
                if(sum == 0){
                    count++;
                }
            }
        }
        return count;
    }
}

Thought proces

A subarray is a contiguous part of an array. Let’s say we find the sum of subarray starting at 0 and ending at any index i. So, T[i] represents the sum of subarray A[0..i].

What if we have two indices i and j; such that i< j and T[i] = T[j]. In this case, all the elements which are from index i+1 and index j add up to zero and that is our subarray with sum zero. Length of subarray with sum zero will be j-i+1.

Show me implementation

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSum(int[] a){

        int len = a.length;
        int [] T = new int[len];

        T[0] = a[0];
        for(int i=1; i<len; i++){
            T[i] = T[i-1] + a[i];
        }

        //Complexity of below code is O(n^2)
        int count = 0;
        for(int i=0; i<len; i++){
            for(int j=i+1; j<len; j++){
                if(T[i]== T[j]){
                    count++;
                }
            }
        }
        return count;
    }
}

The complexity of the implementation is O(n2) with an additional space complexity of O(n) to store sum till index i.

We can optimize it further by creating a hash of all the sums which we see while adding. When we add the index i to already calculated sum till index i-1, we check if the new sum is zero? If yes, then subarray from 0 to index i add up to zero. If there is already a sum present which is equal to the current sum then there is subarray with sum zero between index when we saw the sum last and current index.

Implementation with hashmap

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {

    public int [] findSubarrayWithZeroSumOptimized(int[] a){

        int len = a.length;
        HashMap<Integer, Integer> T = new HashMap<Integer, Integer>();
        T.put(0, 1);

        int sum  = 0 ;
        int count = 0;
        for(int i=0; i<len; i++){
            sum  += a[i];
            if(T.containsKey(sum)){
                count += T.get(sum);
                T.put(sum, count);
            }else{
                T.put(sum, 1);
            }
        }
        return count;
    }
}

The complexity of this method is O(n) with additional space of O(n) in worst case.

If you want to solve an advance version of the problem, read it here: subarrays with sum k.

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free interview kit.

Constant time max operation on stack

Constant time max operation on stack

We understood stack data structure, operations on it and some examples problems which can be solved using stack. Let’s take problem which is actually based on stack and with the help of other data structures, how can make it more efficient for certain function. Today’s problem is to implement constant time max operation on stack.

To elaborate, you have been given a stack, where elements are pushed and popped randomly. At any given point of time, you have to tell max of all the elements present in stack.
For example : we have stack, we push 5,3,1, current max in stack is 5; we push 6 next, current max is 6 now. How about we pop 6 back. Current max goes back to 5 again.

Constant time max operation: Line of thoughts

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation.
If always just pushed on to stack, it would have been easy to just keep track of ma of all the elements we pushed on to stack. However if we are popping out from stack, this may not be as easy. Max will change if the element just popped from stack was current max. What can we do? We keep track of previous max just before the current max. What if next operation is again pop and it pops out the new current max. Again, we have to keep track of previous to previous max.
Are you getting some hint here? We have to keep track of all the max we ever saw while operating on stack in reverse order. That means the max we saw the last, goes out first. LIFO pattern and what better data structure than stack to implement that.

Idea is to have an auxiliary stack which stores all the max seen till a given point of time. Top of this auxiliary stack would be current max. What happens when pop happens on original array? We check if popped element is equal to top element of auxiliary array, that means popped element was current max. So we pop that from auxiliary stack too.

Let’s take an example and see if it works? To start with, both stacks are empty. Now, you add 2 as first element on to stack. Since auxiliary stack is empty, we add 2 on to that stack too.

Push 3 on to stack. Push operation so check if current top of aux stack is less than new element pushed. If yes, push new element to aux stack too.

Push 5 on to stack. Again, push operation and new push element is greater than top of aux stack, we push 5 there too.

Now, push 1. Tricky case. Push 1 on to original stack, but since new element is less than current top of aux stack, nothing gets pushed on aux stack.

Pop from stack now. 1 is popped, it is not equal to current top on aux stack, nothing happens.

Pop from stack again, this time popped element is equal to current max, so we have pop from aux stack too. If we are asked max at this point of time, answer would be 3.

Constant time max operation on stack : Implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> auxStack;

    public MaxStack() {
        stack = new Stack();
        auxStack = new Stack();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek();
        //Push on max stack only if max value is being changed.
        if (max <= x) auxStack.push(x);
        stack.push(x);
    }

    public int pop() {
        int returnValue = stack.pop();
        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return auxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}

Complexity of implementation of constant time max operation stack is O(n) in terms of space, with O(1) time complexity for push, pop and max operation.

Wait, interviewer is not satisfied with this only. What we solve is just reporting the max element in stack at a given point of time. What if we were asked to implement pop max element from stack? Well, first of all finding the max element works as it is. However, popping max element requires popping out all element before max, popping out max and then pushing back all other elements again. Quite a lot of work, even when max operation is O(1).

Which data structure allows us to remove an element in constant time? It’s doubly link list. Once you know which node is to be removed, all we have to do is link previous node to next node. If we implement our original stack as doubly linked list, popping max from stack is O(1) operation without moving any other element on stack.

However finding the node in doubly linked list itself is O(n) operation. Back to square one. What would be helpful is that instead of just storing the max element, we store node address of max in doubly linked list. So in our aux stack, we do not store primitive data type, but a pointer to node which is current max.

Let’s see how it works? We follow the same process of finding the max as explained in earlier solution. It starts with pushing element 2 on to stack. This creates the first node on DLL and stores the pointer on stack.

Now, we push 3 on to stack. Since this is greater than current max being pointed to by top of aux stack, we push that to DLL and store the pointer as max pointer on aux stack.

As for 3, same thing happens when 5 is pushed on to stack.

Since new element pushed is less than current max, it’s pointer is not pushed on to aux stack.
constant time max operation on stack

After pushing 1, we want to pop max. Step 1 would be to fetch the node pointer for current max. Go to that node in doubly linked list. Remove that node from DLL and then remove the pointer from top of stack.

Make a note that whenever, new pushed element is equal to current max, push that on aux stack too. Why?

Let’s see the implementation of this method using doubly linked list.

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackDLL {
    private DoubleLinkedList dll;
    private Stack<ListNode<Integer>> auxStack;

    public MaxStackDLL() {
        auxStack = new Stack();
        dll = new DoubleLinkedList();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek().getData();
        //Push on max stack only if max value is being changed.
        ListNode<Integer> newNode = dll.insertAtHead(x);
        if (max <= x) auxStack.push(newNode);
    }

    public int pop() {
        ListNode<Integer> returnValue = dll.deleteAtHead();

        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue.getData();
    }

    public int peekMax() {
        return !auxStack.isEmpty() ? auxStack.peek().getData() : -1;
    }

    public int popMax() {
        return auxStack.isEmpty() ? -1 : dll.deleteNode(auxStack.pop()).getData();
    }
}

Doubly linked list class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class DoubleLinkedList {

    ListNode<Integer> head;

    public DoubleLinkedList(){
        head = null;
    }

    public boolean isEmpty(){
        return this.head == null;
    }

    public ListNode<Integer> insertAtHead(int data){
        if(this.isEmpty()) {
            this.head = new ListNode<Integer>(data);
            return this.head;
        }
        /*
            We are inserting node at head. So following things happen
            1. Create a new node.
            2. Set next of new pointer to current head.
            3. Set prev of head to new node
            4. Make new node as head of linked list
          */
        //First two steps are done here
        ListNode<Integer> newNode = new ListNode<Integer>(data,this.head, null);
        //Step 3.
        this.head.setPrev(newNode);
        //Step 4.
        this.head = newNode;

        return this.head;
    }

    public ListNode<Integer> deleteAtHead(){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node at head. So following things happen
            1. Set temporary node point to head.
            2. Move head to next of node.
            3. Set prev of new head to NULL.
            4. Free the temp node.
          */
        ListNode<Integer> tempNode = this.head;
        this.head = this.head.getNext();
        this.head.setPrev(null);

        return tempNode;
    }

    public ListNode<Integer> deleteNode(ListNode<Integer> node){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node in between. So following things happen
            1. If node has prev, set node.prev.next = node.next.
            2. If node has next, set node.next.prev = node.prev
        */
        if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
        if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

        return node;
    }
}

ListNode class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class ListNode<T> {
    private T data;

    private ListNode<T> next;
    private ListNode<T> prev;

    public ListNode(T data){
        this.data = data;
        next = null;
        prev = null;
    }

    public ListNode(T data, ListNode<T> next, ListNode<T> prev){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    public ListNode<T> getNext(){
        return this.next;
    }

    public ListNode<T> getPrev(){
        return this.prev;
    }

    public void setPrev(ListNode<T> newNode){
        this.prev = newNode;
    }

    public void setNext(ListNode<T> newNode){
        this.next = newNode;
    }

    public T getData(){
        return this.data;
    }
}

Tester class is given below. Can you add more test cases to this?

package test;

import com.company.MaxStackDLL;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackTest {


    MaxStackDLL tester = new MaxStackDLL();
    @Test
    public void popMaxTest() {

        tester.push(2);
        tester.push(3);
        tester.push(5);
        tester.push(1);

        assertEquals(5, tester.popMax());
        assertEquals(3, tester.popMax());
    }
}

Time complexity of push, pop and popMax is O(1). There is additional space requirement which is O(n).

Please share if there is something wrong or missing. If you are interested in taking personalized coaching by our experienced coaches, please reach out to us at [email protected]

Stack data structure and applications

Stacks data structure

What is stack data structure? Stack is a dynamic data structure, where information is stack over one another. In common terminology, we use the stack with same meaning like stack of trays or stack of pancakes. Extend the concept of stack in real life, you remove the tray at the top before moving tray below it. So the tray which goes last on to stack, come off the stack first. This pattern is called as Last In First Out or LIFO.

For any data structure, three operations should be considered : How data can be added to it, how data can be removed from it and how data can be read from it? Let’s discuss these operations on stack one by one.

Operations on stack

Write operation on stack is commonly known as push. Push operation writes information on to top of the stack.Complexity of push operation is O(1) as no iteration is required.

Read operation is known as pop, where element at the top of stack is removed. Complexity of pop is also O(1).
stack data structure

Another operation which is commonly used is isEmpty(), this checks if there are any elements in stack at present.

What if you just want to check the top element of stack but do not want to remove it from stack? Then operation called peek() is for you. It reads the top element, however does not remove it from stack.

Since stack can dynamically increase and decrease in size based on push and pop operation, we need to keep track of the top of the stack.

Stack can be represented as recursive structure i.e if we remove the top of the stack, remaining N-1 element is again a stack.

Let’s take an example to see how push and pop operations on stack actually follow Last In First Out pattern.

stack data structure

Implementation of stack data structure

Stacks can be implemented in two ways, first where underlying data storage is an array and second where underlying storage is linked list. Refer difference between array and linkedlist to understand more that impacts stack implementation.

1. In Array based implementation of stack implementation, underlying data structure used is an array. We keep an extra variable (top) to keep track of number of elements present in stack at given time. When we push an element on to stack, increase the top. When we pop an element from stack, we decrease the top.

In this implementation, top being -1 represents empty stack and top equal to N-1, N being the size of array, represents stack full. Push and pop operations are of O(1) complexity.

Drawback of this implementation is that we need to define stack size statically at the compile time and changing it at runtime dynamically would be overhead.

#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 100

typedef struct stack{
        int top;
        int items[STACK_SIZE];
}stack;
 
void push(stack *ms, int item){
   if(ms->top < STACK_SIZE-1){
       ms->items[++(ms->top)] = item;
   }
   else {
       printf("Stack is full\n");
   }
}

//Get the element at the top of stack and remove it from stack
int pop (stack *ms){
   if(ms->top > -1 ){
       return ms->items[(ms->top)--];
   } 
   else{
       printf("Stack is empty\n");
   }
}

//Get the element at the top of stack without removing it.
int peek(stack ms){
  if(ms.top < 0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}

//Function to check if stack is empty or not?
int isEmpty(stack ms){
   if(ms.top < 0) return 1;
   else return 0;
}

2. In Linked List based implementation of stack implementation, underlying data structure used is linked list. Every node in the linked list represents an element in stack. Every push operation adds a node at the head of linked list and every pop operation removes a node from head of the linked list.

In this implementation too, push and pop operations are of O(1) complexity. Also stack can grow as much as required. Head being NULL represents empty stack.

Drawback is we need to store 4 bytes extra as next pointer for each element.

#include <stdio.h>

#include<stdlib.h>
#include<stdio.h>

typedef struct node{
    int data;
    struct node *next;
} Node;

/* Create a node of linked list */
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
 
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
    Node *newNode  = createNode(data);
    newNode->next = *headRef;
    *headRef  = newNode;
}

/* This function removes node from the head of linked list */
Node * pop(Node **headRef, int data){
    if(!(*headRef)) return NULL;
	
    Node * poppedNode = *headRef;
    *headRef = (*headRef)->next;
    return poppedNode;
}

/* This function return node at the head of linked list */
Node * peek(Node **headRef, int data){
    if(!(*headRef)) return NULL;
	
    return (*headRef);
} 

int isEmpty(Node **headRef){
    return (*headRef == NULL);
}

Stack Overflow

You must have heard the term stack overflow. Why does it occur and how does it relates to stack data structure?
Stack supports function call paradigm in programming languages. When a function in your program calls another function (which can be the same function in case of recursion), program management module in operating system stores quite a few things to have safe return. This includes : parameters passed to function, return values, return pointers. As you go deep into function calls, one function calling second, then second calling third and so on, each of this successive call takes a frame of system stack as explained above. Depending on the size of information you are putting on stack frame in each call, sooner or later, stack will be full, as it has limited memory allocated in kernel.

Now when you try to add one more frame because you are calling another function, there is no space. That’s when stack overflow happens.

Why do you think function call information is store on stack and not on any other data structure? Let’s say your program calls function A from function B, which in turn was called from function C. When you are returning from function A, you want to return to calling address in function B and not function C. So, you want to return back in reverse order of calling sequence, LIFO, that why stack is best data structure.

It is recommended to implement production code in iterative way rather than recursive using application level stacks. As application stack is allocated from heap, it can grow much bigger than kernel stack. Also, you can select what to put on stack. If you look at iterative preorder traversal, iterative postorder traversal interview problems, they are nothing but to test your knowledge of stack data structure. To read more on stack overflow, please refer : stack overflow

Application of stack : browser back button

Let’s solve a problem and see how stack data structure can be used to solve problems. Problem statement is : Implement back button on browser. When you click on back button, you go to previous site you visited. You press it again, than you go to site prior to it and so on.

Do you see application stack here? When you go back, you want to land on the last site you visited. What pattern is this? Of course, it last in first out which can be implemented using stack.
So idea is to whenever you move to new site or page, current page is added to stack. If you press back button, top of the stack is popped and return to you as current page. If you press again, top of the stack contains now the page you visited before current page, so land there.

browser back button using stack

There can one more complexity added to this problem, which is you want to implement forward button too. In that case, whenever you pop out a page from back stack, put it into a new stack called forward stack. Can you run through some examples and see if that actually works?

Please share if there is something wrong or missing. If you are interested in taking personal coaching by our experienced teachers, please reach out to us at [email protected]

Merge k sorted arrays

Given k sorted arrays of varying lengths, merge these k sorted arrays into one sorted array.

For example, given 3 arrays:
merge k sorted arrays

The resulting array should be like

merge k sorted array

Companies this problem is asked in

Microsoft, Amazon, Facebook, Salesforce, Indeed

Merge k sorted arrays divide and conquer

Since all the input arrays are sorted, the first element in the output sorted array will be one of these first elements of input arrays. How can we find the minimum among all the elements plucked from the first index of each array? Easy, take those k elements (there are k arrays, so k first elements) and build a min-heap. The root of the min-heap will be the least element among each of the first elements of the given k sorted arrays, i.e.

result[0] = min(arr1[0], arr2[0], arr3[0]…arrK[0])

merging k sorted arrays

The initial root above will be the first element in the result array. Now the second element for the result array can be found from the set of first elements of all input arrays except the array from which the first element of result array was taken. For example, if arr1 had the least of all first elements while finding the initial root, then:

result[1] = min(arr1[1], arr2[0], arr3[0] … arrK[0])

merge k sorted arrays java

Next iteration, 5 will be picked and put into the result array and index of arr 3 will be increased.
merging k sorted arrays

After putting 5 in the result array, we will move the next element in array 3 to the min-heap.
merge n sorted arrays

In order to know which array gave the minimum element at a particular time, we will store additional information of about array and index at which minimum element was.

If i represents the array number, and j represents the index of the minimum number currently in the heap from the ith array, then we add (j+1)th element to the min-heap next and re-heapify.
If we have put all the element from the ith array in the heap then we need to reduce the size of min-heap to k-1.

Follow the procedure for (n-1)*k times. When all array elements are processed the result array will be the sorted array for all nk element.

Algorithm

  • Build min heap with the first element of all k arrays.
  • Pick the root of min element and put it in the result array.
  • If there are remaining elements in the array,  put next element at the root of min heap and heapify again
  • If all elements are already of an array are processed, reduce the size of min heap by 1.
  • Repeat step 2, 3 and 4 till min heap is empty.

Show me the implementation

package com.company;
import java.util.PriorityQueue;

/**
 * Created by sangar on 2.12.18.
 */
public class MergeKSortedArrays {
    private class HeapNode {
        public int arrayNum;
        public int index;
        public int value;

        public HeapNode(int arrayNum, int index, int value) {
            this.arrayNum = arrayNum;
            this.index = index;
            this.value = value;
        }
    }

    public int[] mergeKSortedArrays(int[][] arrays) {

        if (arrays == null) return null;

        PriorityQueue<HeapNode> minHeap =
                new PriorityQueue<>(arrays.length,
                        (HeapNode a, HeapNode b) -> a.value - b.value);

        int size = 0;
        for (int i = 0; i < arrays.length; i++) {
            size += arrays[i].length;
        }
        int[] result = new int[size]; // k * n

        //add first elements in the array to this heap
        for (int i = 0; i < arrays.length; i++) {
            minHeap.add(new HeapNode(i, 0, arrays[i][0]));
        }

        //Complexity O(n * k * log k)
        for (int i = 0; i < size; i++) {
            //Take the minimum value and put into result
            HeapNode node = minHeap.poll();

            if (node != null) {
                result[i] = node.value;
                if (node.index + 1 < arrays[node.arrayNum].length) {
                    //Complexity of O(log k)
                    minHeap.add(new HeapNode(node.arrayNum,
                            node.index + 1,
                            arrays[node.arrayNum][node.index + 1]));
                }
            }
        }
        return result;
    }
}

The complexity of the code to merge k sorted arrays is O(nklogk) along with space complexity of O(k).

Please share if there is something wrong or missing. If you are preparing for an interview, please sign up to receive interview preparation kit for free.

Loop in linked list

Loop in linked list

Detect loop in linked list is very common linked list question which is asked in telephonic interview rounds. Problem statement is :

Given singly linked list, check if there is loop in linked list and if yes, find start node or point of the loop.

For example, if for linked list shown below, there is a loop in linked list and it start at node 8.

loop in linked list
Loop in linked list, starting node is 8

Loop in linked list : thoughts

What is difference between a normal singly linked list and a linked list with loop? If we traverse normal linked list, we are destined to encounter a node which is null, which in effect is the last node of normal linked list. However, in a linked list with a loop, we will never reach null and circle around in the loop.

Can we use this property to find if there is a loop or not in a linked list? If we move two pointers with different speeds,, the fast pointer, which moves two nodes at a time will reach to end of linked list before slow pointer, which moves one node at a time, in a normal list (without a loop). However, in list with loop, fast pointer will go around in circles and eventually, slow pointer will catch up with it. So, if ever, before fast pointer reaches null, slow pointer catches up with it, there is definitely a loop in linked list. This method of using fast and slow pointers to traverse linked list at different speeds is commonly known as hare and tortoise method and used in solving many problems on linked list like find middle of linked list, palindrome linked list etc.

Let’s take an example and see what we are thinking is correct. Below is a linked list with a loop, let’s see if slow and faster pointer ever meet.

We initialize slow as head(4) and fast as next of head(3).  fast moves two steps and hence reaches node 8, where as slow reaches at 3.

Since, fast is not null yet, we jump again, this time fast points to 7 and slow points to 5.

Again, fast is still not null, so we move again, fast now is at 8 and so is slow.

This is where we can safely say that there is a loop linked list.

    public boolean isLoop(){
        /* 
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return false;
        }
        
        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here
        
        while(fast != null && fast != slow){
            /*
            Move faster ponter two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return false;
            
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }
        
        return fast == slow;
    }

There is common mistake which happens is to check content of fast and slow pointers to see if there are at the same node. This will fail when there are duplicate values in different nodes. To avoid wrongly predicting nodes being equal when actually content is equal, compare node addresses and not content.

Start of loop in linked list

This problem is interesting and require a bit of thinking. Can we find number of nodes in loop?
Starting from node fast and slow met at, move fast two nodes at a time and slow one node at a time, they will again meet at the same node. Keep count of how many nodes slow pointer moved, it will give length of loop. You can try with different length loops and see that it is actually true.

private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

Now, we have number of nodes in loop, let’s say k. How can we find starting node of loop. We take two pointers again, fast and slow, fast is k nodes ahead of slow which is at head of list. Why? Hypothesis is that if we move them with same speed, when slow reaches start of loop, fast would have finished traversing k loop nodes and will also be at the start of loop. So, with fast ahead of slow by k nodes, when both meet, that node should be start of loop in linked list.

Start of loop in linked list implementation

package com.company;

/**
 * Created by sangar on 14.10.18.
 */
public class LinkedList<T> {
    private Node<T> head;

    public LinkedList(){
        head = null;
    }

    public void insert(T data){
        //If this is the first node to insert
        if(this.head == null){
            this.head = new Node<>(data);
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier,
			it should not be null in this while loop ever though
            * */
            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            //We are at the last node.
            current.setNext(new Node(data));
        }
    }

    public Node getLastNode(){

        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;

            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            return current;
        }
    }

    public Node<T> get(T data){
        /*
            Base condition if there is no nodes,
            return null
         */
        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier, it
			should not be null in this while loop ever though
            * */
            while(current != null && current.getData() != data){
                current = current.getNext();
            }

            return current;
        }
    }

    /* As we need slow pointer to get number
    of nodes again, we will return slow pointer
    rather than boolean
     */
    private Node isLoop(){
        /*
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return null;
        }

        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here

        while(fast != null && fast != slow){
            /*
            Move faster pointer two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return null;

            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }

        return fast == slow ? slow : null;
    }

    private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

    public Node getStartNodeLoop(){

        Node slow = isLoop();

        /* If slow is not null, it means there is a loop */
        if(slow != null){
            int k = getNumNodesInLoop(slow);

            slow = this.head;

            //Give fast head start of k nodes.
            Node fast = slow;
            while(k-- > 0 && fast != null){
                fast = fast.getNext();
            }

            while(fast != slow){
                slow = slow.getNext();
                fast = fast.getNext();
            }
        }
        return slow;
    }
}

Test cases for finding loop in linked list implementation

package test;

import com.company.LinkedList;
import com.company.Node;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class LoopInLinkedListTest {

    LinkedList<Integer> tester = new LinkedList<>();
    @Test
    public void loopPresentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        //Created a loop
        Node loopNode = tester.get(8);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopAbsentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void EmptyLinkedListTest() {
        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void OneNodeLoopTest() {
        tester.insert(4);

        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopBackToHeadTest() {
        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(5);
        tester.insert(7);


        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }
}

Complexity to find a loop in linked list is O(n) as we have to scan all node of linked list at least once.

Please share if there is something wrong or missing.

Reference : cslibrary.stanford.edu/103/LinkedListBasics.pdf