In the last post, We discussed about the basics of Indexing in database. In this post we will discuss about Composite Indexes and how ordering is important in composite indexes. We can have indexes on multiple columns which is also called Composite Index. In Mysql, An index may consist of up to 16 columns. MySQL … Read More →
What is a Database Index?
What is a Database index? A database index is a data structure (most commonly B-tree) that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure. Indexes are used to quickly locate data without having to search every row … Read More →
Check if two rectangles overlap
Given two rectangles ra and rb , check if they overlap. In other words, if they have common area or not. This is most asked interview questions in biggies like FB, Google, Amazon and MS. Structure of the rectangle is : This questions was asked in Amazon written test. Approach : Two rectangles A and … Read More →
Spiral traversal of binary tree
Given a binary tree , print it’s nodes in spiral fashion. Example for Given Tree,Output should be F,B,G,I,D,A,C,E,H This is also called zig zag tree traversal. Algorithm : We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal … Read More →
Reverse every k nodes of a linked list
Given a linked list and a number k. Reverse every k nodes in the list. Example : Input 1->2->3->4->5->6 and k = 2 Output 2->1->4->3->6->5 Solution : We have a pointer q which points to the head of the list initially. Advance this k times in a while loop and keep reversing the list. Now … Read More →
Snapdeal Interview Questions – Set 1
I have appeared for snapdeal some time back. I am sharing my interview experience with crazyforcode. First Round: 1. Lowest Common Ancestor of two nodes in binary tree.I wrote code for this.Then interviewer drew a tree and asked to print stacktrace on it. 2. You are given two ropes.Each rope takes exactly 1 hour to … Read More →
Print Pairs with the given difference in sorted array
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 →
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 →
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 →
Convert Sorted Linked list to balanced BST
In previous problem, we discussed how to create a balanced binary search tree for a sorted array. Now we’ll see how to create the same from a sorted linked list. Method 1: This solution is similar to our previous solution but unlike array accessing middle element of linked list is not O(1). Approach : i. … Read More →
Convert sorted array to balanced binary search tree
Problem : Given a sorted array . Write a program to create balanced BST from the sorted array. We know that the in-order traversal of binary search tree gives the elements in sorted order. This tells us that the middle element of array will be the root. We can create left and right subtree by … Read More →
What’s going on ?