My software development journey
How do we write a program to find the prime factorization of a given number? For example prime factorization for 18 can written as 2 * 3 * 3 or 2 * 3 ^ 2. For any number there is only one possible prime factorization. An efficient algorithm can be given as follows. we run…
Given a number, how do we write a program to find all of it’s factors or divisors. For example, for the number 18, the factors are {1, 2, 3, 6, 9, 18}. An immediate algorithm that comes to our mind is to run a loop from 1 to n. In each iteration check if the…
Given a two dimensional array or a matrix, how do we write a program to print the elements in a spiral order. For example the spiral order for the following matrix is 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 1 2 3 4…
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 a string, how do we check if any anagram of it can be a palindrome? For example let us consider the string “AAC”. An anagram of it is “ACA” which is a palindrome. We have to write a method which takes a string and outputs true if we can form a palindrome from any…
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…
Given a binary tree, we have to print the data level wise. For example level order traversal of the following tree produces the sequence 5,3,8,2,4,6,1,7. The hint to solve this problem is to use a Queue data structure. We start by inserting the root node into the queue. Until the queue is empty, we remove…
Given a binary search tree, how do we find the maximum and minimum elements in it? For example in the given tree, the maximum element is 8 and the minimum element is 1. This algorithm is based on the following simple observation. In a Binary search tree, the minimum element always lies on the left…
Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure. There are three main traversals of the binary tree. Namely In-order traversal Post-order traversal Pre-order traversal In addition to these, there are inverses of the above algorithms, and there is a level order traversal. In this post…
Given a binary tree how to find the height of the tree. It is defined as the number of nodes in the longest path from root to any leaf. We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the…