Coding Interview Questions

Coding is one of the most important and popular topic in today's era as huge no. of students are focused in this domain. They are using different different platforms like Geeks for Geeks, HackerRank, HackerEarth to solve the questions and crack Interview.

So here I introduce some of the "Coding Interview Questions" necessary for all of us..

What to prepare for Coding Interviews?

Now that I have cleared the confusion that Coding Interview is important and you should not distract, let’s get into real work. The big question is what to prepare for Coding interviews?

Well, the most important thing to prepare is Data Structure-based coding problems like array-based coding problems, string problems, linked list problems, binary tree problems, etc

Service Based Company Question

How a merge sort algorithm implemented?

The merge sort algorithm is a divide and conquer algorithm. In the divide and conquer paradigm, a problem is broken into smaller problems where each small problem still retains all the properties of the larger problem -- except its size. To solve the original problem, each piece is solved individually; then the pieces are merged back together.

For example, imagine you have to sort an array of 200 elements using the bubble sort algorithm. Since selection sort takes O(n^2) time, it would take about 40,000-time units to sort the array. Now imagine splitting the array into ten equal pieces and sorting each piece individually still using selection sort. Now it would take 400-time units to sort each piece; for a grand total of 10*400 = 4000.

Once each piece is sorted, merging them back together would take about 200-time units; for a grand total of 200+4000 = 4,200. Clearly, 4,200 is an impressive improvement over 40,000.

Now think bigger. Imagine splitting the original array into groups of two and then sorting them. In the end, it would take about 1,000-time units to sort the array.

That's how merge sort works. It makes sorting a big array easy and hence it's suitable for large integer and string arrays. Time Complexity of the mergesort algorithm is the same in the best, average and worst-case and it's equal to O(n*log(n))

How do you check if two rectangles overlap with each other?

The algorithm to check if two rectangles are overlapping or not is very straight forward but before that, you need to know how you can represent a rectangle in Java programs? Well, a rectangle can be represented by two coordinates, top left, and bottom right.

As part of the problem, you will be given four coordinates L1, R1 and L2, R2, top left and bottom right coordinate of two rectangles and you need to write a function isOverlapping() which should return true if rectangles are overlapping or false if they are not.

Btw, if you are interested in learning algorithms, I

Algorithm to check if rectangles are overlapping
Two rectangles A and B will not overlap or intersect with each other if one of the following four conditions is true.

1. The left edge of A is to the right of the right edge of B. In this case first rectangle A is completely on the right side of second rectangle B as shown in the following diagram

2. right edge of A is to the left of left edge of B. In this case first rectangle A is completely on the left side of second rectangle B, as shown below

3. Top edge of A is below bottom edge of B. In this case, first rectangle A is completely under second rectangle B as shown in the following diagram

4. Bottom edge of A is above top edge of B. In this case, first rectangle A is completely above second rectangle B as shown in the following diagram

If any of above four conditions is not true then two rectangles are overlapping with each other, as in following diagram first condition is violated, hence rectangle A intersects rectangle B.

How is an integer array sorted in place using the quicksort algorithm?

Quicksort algorithm is one of the most used sorting algorithms, especially to sort the large lists, and most of the programming languages, libraries have implemented it in one or another way. In Java, Arrays.sort() method sorts primitive data types using a double-pivot Quicksort algorithm, authored by Joshua Bloch and others. This implementation provides better performance for a lot of data sets, where traditional quicksort algorithms reduced into quadratic performance. This method also uses MergeSort, another good sorting algorithm, to sort objects. QuickSort implementations are also available in the C++ STL library.

Have you ever thought why quicksort is so popular? because on average it is one of the fastest sorting algorithms we have. On average quicksort is an O(n log n) algorithm, while it's the worst case is O(n^2), which is much better comparing with Bubble Sort or Insertion Sort

One of the most important thing interviewer look in your quicksort implementation is the choice of the pivot and whether you are sorting in place or not. In "in-place" sorting, actual sorting takes place in the same array and no additional space is needed.

Due to this reason, quicksort is very efficient in sorting a large list of numbers, as no additional memory is required, a very space-efficient sorting algorithm..

How do you check if a given string is a palindrome?

A String is said to be a palindrome if the reverse of String is equal to itself like "aba" is a palindrome because the opposite of "aba" is also "aba", but "abc" is not a palindrome because the reverse of "abc" is "cba" which is not equal. Recursion means solving a problem by writing a function which calls itself. In order to check if String is a palindrome in Java, we need a function that can reverse the String.

Once you have original and reversed String, all you need to do is check if they are equal to each other or not. If they are equal then String is palindrome or not. You can write this reverse() function by using either for loop or by using Recursion.

If you remember, I already shared the logic of reversing String in my earlier post, how to reverse String in Java using Iteration and Recursion. Here we will use the same logic to check if String is palindrome or not.

ere is our Java program, which checks if a given String is palindrome or not. Program is simple, and here are steps to find palindrome String :

1) Reverse the given String
2) Check if the reverse of String is equal to itself; if yes, then given String is a palindrome.

In our solution, we have a static method isPalindromeString(String text), which accepts a String. It then calls the reverse(String text) method to reverse this String. This method uses Recursion to reverse String. This function first checks if given String is null or empty, if yes then it returns the same String because they don't require to be reversed.

After this validation, it extracts the last character of String and passes rest or String using substring() method to this method itself, hence the recursive solution. The validation also servers as base case because, after every step, String keeps getting reduced, and eventually it will become empty, there your function will stop Recursion and will use String concatenation to concatenate all character in reverse order. Finally, this method returns the reverse of String.

When the call to reverse() returns back, isPalindromeString(String text) uses equals() method to check if the reverse of String is equal to original String or not, if yes then it returns true, which also means String is a palindrome.

How to remove Nth Node from the end of a linked list?

The above algorithm could be optimized to one pass. Instead of one pointer, we could use two pointers. The first pointer advances the list by n+1n+1 steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by nn nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the nnth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node's next next node.

So in this blog i tried hard to cover important topics so give your best. ..

Instead, talk about how you use rejection as a motivator and an opportunity to learn..

Blog written by: Shruti Agarwal

Contact us: