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 →
Maximum size square sub-matrix with all 1s
Problem: Given a binary matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s. Example: Consider the below matrix. 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 The … Read More →
The Coin Problem – Dynamic Programming
Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way … Read More →
Rotate an array by d elements
Problem: Write a program that will rotate a given array of size n by d elements. eg: 1 2 3 4 5 6 7 and d = 3 Output : 4 5 6 7 1 2 3 Method 1: For rotating the array by d elements, first rotate it by 1. Move a[1] to a[0], … 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 →
Kth largest or smallest element in an array
Write an C program to find kth largest element in an array. Elements in array are not sorted. example, if given array is [1, 3, 12, 19, 13, 2, 15] and you are asked for the 3rd largest element i.e., k = 3 then your program should print 13. Method 1 Use sorting. Return first … Read More →
Longest Increasing Subsequence
Problem: Find length of the subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Example : {10, 25, 9, 30, 21, 55, 40, 60, 75} Here Length of LIS … Read More →
Level of a given node in binary tree
Given a Binary Tree and a pointer to the Node in that tree. Write a function to find level of Node in the Tree. For Example, in the below tree 0 / \ 1 4 / \ / \ 2 3 5 6 If the input key … Read More →
Heap Data Structure
Heap data structure is an array object that can be viewed as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest , which is filled from the left up to a point. There are two … Read More →
Find local minima in an array
You are given an array Arr[1 .. n] with the special property that Arr[1] ≥ Arr[2] and Arr[n − 1] ≤ Arr[n]. We say that an element Arr[x] is a local minimum if it is less than or equal to both its neighbors. Derive an algorithm in O(log n) For example in the array 9,6,2,14,5,7,4 … Read More →
Binary Tree diff of sum of nodes at odd and sum of nodes at even
Given a Binary Tree, write a function which calculates the difference between the sum of node values at odd levels and sum of node values at even levels. Consider the root node is at height 1. The solution is short and uses recursion. The idea is that you negate all levels under the current one … Read More →
What’s going on ?