How to find square root of a number in Java - Algorithm Interview question

Write a program to calculate the square root of a number in Java or C++ is one of the popular coding interview questions from Programming job interviews both on tech companies like Facebook, Amazon, and investment banks like Citibank and Bank Of America etc. The problem may look easy because you might know how to find the square root of a number but it's not. In fact, it's one of the tricky questions you would encounter in programming job interviews. The first hurdle is do you really remember how to calculate square root by hand? Many programmers don't. I know they have learned it past but when you ask them to calculate square root by hand, many won't remember the algorithm they have learned in school or college.

Read more »

Post Order binary tree traversal in Java - Recursion and Iteration

This is the third article on tree traversal. In the last couple of articles, I have shown you how to implement preorder and inorder traversal in Java, both recursively and iteratively and today, you will learn about the post order traversal. Out of these three main tree traversal algorithms, the post-order traversal is most difficult to implement, especially the iterative version. In post order traversal, you first visit left subtree, then right subtree and at last you print the value of root or not. So, the value of root is always printed at last in the post-order traversal. As I told you before, all three preOrder, inOrder, and postOrder are depth-first algorithms so they go down in the binary tree first before visiting nodes of the same level. The implementation of the recursive algorithm is very simple, you just need to adjust the order of recursive call according to the algorithm and you are done, but iterative algorithm requires some effort to get it right, which you will see in this article.

Read more »

How to check if two Rectangle Overlap in Java - Algorithm

Can you write a Java program to check if two rectangles are overlapping with each other or not? is one of the frequently asked coding questions on tech giants like Facebook, Amazon, Microsoft and others. This is also a kind of problem where it's easy to find opposite or negative conditions e.g. when rectangles are not overlapping and then inverting the result to prove that rectangles are colliding with each other. I first heard about this problem from one of my friend who was on Android game development space. He was asked to write an algorithm to find if given rectangles are intersecting or not. He was given the choice to implement the algorithm in any programming language e.g. Java, C, C++ or even pseudo code was fine, so don't worry about language here, it's more about algorithm and logic. He is a genius so he came successful from that interview, impressing the interviewer, talking about efficiency and accuracy of the algorithm as well.

Read more »

Iterative QuickSort Example in Java - without Recursion

The quicksort algorithm is one of the important sorting algorithms. Similar to merge sort, quicksort also uses divide-and-conquer hence it's easy to implement quicksort algorithm using recursion in Java, but it's slightly more difficult to write an iterative version of quicksort. That's why Interviewers are now asking to implement QuickSort without using recursion. The interview will start with something like writing a program to sort an array using quicksort algorithm in Java and most likely you will come up with a recursive implementation of quicksort as shown here. As a  follow-up, Interviewer will now ask you to code the same algorithm using Iteration.

Read more »

How to Print all Leaf Nodes of Binary tree in Java - Recursion and Stack

Binary tree based questions are very common in Java or any other Programming job interviews. One of the frequently asked binary tree questions is "write a program to print all leaf nodes of a binary tree". In order to solve this problem, you must know what is a leaf node? A leaf node in a binary tree is a node whose left and right child is null. They are actually the last nodes of any binary tree. In a typical programming interview, you would be given a binary tree and asked to write a program to print all leaf nodes. Usually, all binary tree related questions can be solved easily using recursion because a tree is a recursive data structure, but you should also know how to solve them without recursion.

Read more »

InOrder traversal of Binary tree in Java using Recursion and Iteration

This is the second article about tree traversal algorithms using Java. In the first part, we have seen the pre-order algorithm for visiting all nodes of the binary tree and today we'll learn about the InOrder traversal. As I told you before, unlike array and linked list, binary tree has several ways of traversal. The traversal algorithms are broadly divided into depth first and breadth first traversal algorithms depending upon how algorithm actually works. As the name suggest, depth first explores binary tree towards depth before visiting sibling, while breath first visits all nodes in the same level before going to next level, hence it is also known as level order traversal. Both PreOrder and InOrder tree traversal algorithms are depth first and the only difference between pre-order and in-order algorithm is the order on which root, left node, and right node of the binary tree is visited.

Read more »

How to find the 3rd element from end in linked list in Java

The problem to find the 3rd element from the end in a singly linked list or nth node from the tail is one of the tricky but frequently asked linked list problems in programming job interviews. The challenge here is to solve the problem in just one pass, i.e. you can not traverse the linked list again and you cannot traverse backward because it's a singly linked list. If you have practiced some linked list problems e.g. finding length, inserting elements, or deleting elements then you should be familiar with traversal. Here, we'll use the same algorithm which we have used to find the middle element of linked list in one pass. The algorithm is also known as tortoise and hare algorithm because of the speed of two pointers used by the algorithm to traverse the singly linked list.

Read more »

Binary Tree PreOrder Traversal in Java - Recursion and Iteration Example

Unlike linked list and array which can only be traversed linearly, there are several ways to traverse a binary tree. The tree traversal algorithms are mainly divided into two parts, depth first and breadth first. As their name suggests, in depth first, the tree is traversed downwards (towards the depth) before the next sibling is visited, the PreOrder, InOrder and PostOrder traversal of a binary tree are actually depth-first traversals. On the breadth first, the entire breadth of the tree is traversed before moving to next level, hence it is also known as level order traversal. There are other algorithms to traverse a binary tree as well e.g. Monte Carlo tree search, which concentrates on analyzing the most promising moves, but the pre-order, post-order, and in-order traversal are the most popular ways to traverse a binary tree in Java. They are also the most popular data structure and algorithm questions at beginner and intermediate level.

Read more »

How do you find length of a Singly Linked list using Loop and Recursion

Hi Guys,
Here is one of the classical programming questions asked to me first time on an interview with multinational Investment bank. After that, this question has been asked to me on several occasions in other programming job interviews as well. What makes this question interesting is that Java developers are not that great with the data structure as compared to C++ developer which is obvious because of the fundamental difference between these two languages. The C++ is more of system programming language while Java is more on application programming , also a rich set of Java API allows the programmer to skip this kind of basic programming techniques.

Read more »

How to declare and initialize a List (ArrayList and LinkedList) with values in Java

Initializing a list while declaring is very convenient for quick use, but unfortunately, Java doesn't provide any programming constructs e.g. collection literals, but there is a trick which allows you to declare and initialize a List at the same time. This trick is also known as initializing List with values. If you have been using Java programming language for quite some time then you must be familiar with syntax of array in Java and how to initialize an array in the same line while declaring it as shown below:

String[] oldValues = new String[] {"list" , "set" , "map"};

or even shorter :

String[] values = {"abc","bcd", "def"};

Similarly, we can also create List  and initialize it at the same line, popularly known as initializing List in one line example. Arrays.asList() is used for that purpose which returns a fixed size List backed by Array. By the way don’t confuse between Immutable or read only List which doesn’t allow any modification operation including set(index) which is permitted in fixed length List.Here is an example of creating and initializing List in one line:

Read more »