Given a sorted array and a number k. print all pairs in the array with difference between them is k. Solution 1: Using Hash Map Create a hashmap and then traverse the array. Use array elements as hash keys and enter them in hashmap. Traverse the array again and look for value k + arr[i] … Read More →
Difference between an interface and an abstract class?
We have seen in previous posts what is abstract class and interface. Here we will compare and see difference between these two. Abstract class is a class which contain one or more abstract methods, which has to be implemented by sub classes. Interface is a Java Object containing method declaration and doesn’t contain implementation. The … Read More →
Microsoft Interview – Set 2
I recently have appeared for Microsoft interview process. I would like to share it with crazyforcode and help others. Following questions were asked during interview. Round 1 Q1. Two numbers are stored in two linked lists, with one digit in each node. Add the numbers and return the resultant sum in a linked list. eg. … Read More →
Find loop in linked list and remove the loop
To remove the loop, we need to find the node at which the loop begins. Detection is easy by using fast and normal pointers (referred to as FP and NP from now on) to traverse such that the fast pointer traverses 2 nodes while normal pointer moves 1 node at a time. If they meet, … Read More →
Merge k sorted arrays
Given k sorted arrays of size n,merge them into an output array which is sorted. Solution (Using Min Heap): This solution is similar to method 4 of this post. Steps: i. Create a min heap of size k of first element of each array. Repeat steps from 2 to 4 n*k times: ii. Take the … Read More →
Length of Longest substring without repeating characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1. Solution: When you have found a repeated character (let’s say at index j), … Read More →
Pythagorean triplets in an array
Given an array of integers . Write an algorithm to find all the Pythagorean triples. Eg : i/p : int arr[ ] = {1,3,4,5,6,7,8,10,11} o/p: Print 3,4,5 and 6,8,10 Solution: Steps: (1) First square each element. (2) Sort the array in ascending order. This takes O(n log n). (3) Now consider each element a[ i … Read More →
Non overlapping maximum subsequence
Given n sequences, and starting and stopping point of every sequence with its score. For eg. no of sequences = 5 start stop score 0 4 4 3 10 11 6 8 8 7 15 10 11 15 4 All scores are positive. You have to find the maximum subset of non overlapping sequences having … Read More →
Flipkart Interview Questions – Set 1
I recently have appeared for flipkart interview process. I would like to share it with crazyforcode and help others. Round 1 Q1. Write a code to check if a tree is BST or not. Q2. Modify this code to find the maximum subtree in tree which is a BST. Maximum subtree means subtree goes upto … Read More →
Microsoft Interview – Set 1
I appeared for MS interview for developer profile recently. I would like to contribute for CrazyforCode by sharing my experience. Round 1 Q1. Two numbers are stored in two linked lists, with one digit in each node. Add the numbers and return the resultant sum in a linked list. eg. if LL1= 2 > 3 … Read More →
What’s going on ?