My software development journey
In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time. Here is the strategy for linked list insertion…
Given two binary tress, how do we check if they are identical in structure, and contents? For example the following two binary trees are identical. We can solve this problem using recursion effectively. The function checks if the root element is equal and use the same function to check if it’s left and right sub-trees…
Depth First Search (DFS) is graph traversal algorithm. Using this algorithm, given a source vertex (s), we can answer queries such as What are the all the vertices connected to s? Is there any path from s to v? What is the path from s to v? For example consider the following undirected graph. 0…
Given an array of N values and a value K, Write a program to print the maximum of all the sliding windows (sub-array) of size K. For example let us consider the following array as input [4, 5, 3, 2, 6, 1, 2, 3, 8, 4] Let as take the sliding window of size 3.…
Given a sorted linked list write a program to insert data into it’s correct position. For example consider the following linked list 1 -> 3 -> 4 -> 5 Inserting 2 should change the list to 1 -> 2 -> 3 -> 4 -> 5 Inserting 0 should change it to 0 -> 1 ->…
Given a singly linked list, we have to swap the adjacent nodes in it. For example some input/output samples are given below Input output ————————————————- 1->2->3->4->X 2->1->4->3->X 1->2->3->4->5->X …
Given a singly linked list, how do we reverse it by re-arranging the links? For example if the given linked list is 1 -> 2 -> 3 -> NULL. The output of reverse method should be 3 -> 2 -> 1 -> NULL. The following diagram shows the simple steps to perform the reversal. And…
Given a doubly linked list, how do we reverse it by just re-arranging the pointers? Here is an example of input/output. The following picture depicts how we re-arrange the pointers. Here is the Java implementation.
Given two sorted linked lists, how do we merge them without using any extra space. That means we have to re-arrange the links to form a single sorted linked list. For example let us consider the following two sorted lists as input. 1 -> 3 -> 5 -> 7 2 -> 4 -> 6 ->…
Given K sorted lists, how to merge them into a single sorted list? Let total number of elements in K sorted lists is N. We have to form a single sorted list of length N. For example let us consider the following input lists{4, 19, 27}{1, 6, 50, 73}{9, 45, 59, 67} The output should…