My software development journey
A binary search tree is a hierarchical data structure which stores data in a non-linear fashion. It supports the insertion, search and deletion operations in O( log n ) time. Take a look at the below picture. This is an example of binary search tree. The node at the top containing 5 is the root…
Given a sorted linked list, We have to delete all the duplicates in that list. For example, If we get the following list 1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4 -> 5 The output should be 1 -> 2 -> 3 -> 4 ->5 To solve this…
How do we sort a linked list? In this post, we see one such method using bubble sort algorithm. We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.We first find the length of the linked list (len). The outer loop…
Given a row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently? Example of the array can be int[][] matrix = { {1,3,5,7,9}, {10,12,14,16,18}, {19,21,23,25,27}, {28,30,32,34,36}, {37,39,41,43,45} }; This can be done using the following algorithm. We start our search with the top right element. If it…
Given array of elements we have to write a program to print the biggest element to it’s right for each of the elements in the given array. For example let us consider the array {3, 9, 2, 4, 6, 1}. The output for this array should be {9, 6, 6, 6, 1, -1}. As a…
Given an array of 2n numbers of the following format {a1, a2, a3,…an, b1, b2, b3, …bn} We have to write a program to transform this into the following format. {a1, b1, a2, b2, a3, b3, …, an, bn} This can be done using the following algorithm. We iterate over the array for (n-1) times. In…
Given a linked list, how do efficiently find the nth node from the end? For example in the following linked list, 3rd node from the end is ‘6’. 2 -> 1 -> 6 -> 5 -> 9 One obvious method is to find the length of the linked list (len) by going through the list.…
Given a sorted array and a value, we have to find the closest value (with least difference). For example let the input array be {-2, 4, 7, 11, 17} and the input number is 10, the output should be 11. This problem is actually a variation of binary search where in we have to find…
Given an array of elements which contains some zeros in between, we have to write a program to move all zeros to the end without disturbing the original order of the elements.For example if the input is {0, 6, 2, 0, 0, 3, 1, 0, 4, 5, 0}, the output should be {6, 2, 3,…
Given a large file containing many lines of text, How do we write an efficient program to print last k lines from that file. One obvious approach is to read the entire file first to find the number of lines (n). In the second iteration skip first (n-k) lines, and print the remaining k lines. …