Problem: Given an binary array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s. Examples: Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1} Output: 1 to 8 (Starting and Ending indexes of output sub array) Implementation: In this method,use two nested loops. The outer loop … Read More →
Recursive Spiral Order Traversal of Tree
This is also called zig-zag order traversal of a binary tree. Approach: To print the nodes in spiral order, nodes at different levels should be printed in alternating order. To change the order of printing alt variable is used. If alt is 1 then printSpiralLevel() prints nodes from left to right else from right to … Read More →
Recursive Level Order Traversal of a tree
Level order traversal is also called breadth first traversal for the tree. Non-Recursive solution of the problem is – Non-recursive Level Order Traversal Approach: There are basically two functions in this method. One is to print all nodes at a given level (printLevel), and other is to get height of tree and print level wise nodes. … Read More →
Find a Number that Appears Only once in array of Duplicates
Problem: Given an array of integers, every element appears twice except for one. Find that single one. Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory. Solution: Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory. Solution: XORing x with itself gives … Read More →
Group all Words in Set of Anagrams of Each Other in Dictionary
Problem: Given a dictionary with set of words in it. Write a program to group all words which are anagrams of each other in to sets. For example – Input: “bat”, “tar”, “xyz” , “tab”, “tar” Output:[["bat", tab"], ["tar", rat"],”xyz” ] Thi sproblem was asked in amazon interview. Steps: 1)Use some sort of a hash … Read More →
Find Anagrams in array of Strings
Problem: You are given an array of strings and you have to print all the anagrams within the array. What is anagram – For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Solution: Let’s use this … Read More →
Find the Rotation Count in Rotated Sorted array
Problem : Find the count k by which array has been rotated in the rotated sorted array. So for example we have sorted array as 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 We have to find K? Solution : This … Read More →
Find the Minimum Element in the Rotated Sorted array
Problem : Find the minimum element in the rotated sorted array. For example we have array as – 1,3,6,9,12,15. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 12,15,1,3,6,9 Solution – The answer to this lies on the fact that if we can find the point on … Read More →
Next Greater Element in array
Problem: You are given an array, print the next greater element for each element. Elements for which no greater element exist, print next greater element as -1. You have to reduce the number of comparisons. For any array, rightmost element always has next greater element as -1. eg. For array [4, 15, 2, 9, 20, … 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 →
Leaders in an array
Problem: You are given an array. You have to write a program that will print all the leaders in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example array {6, 7, 4, 3, 5, 2}, leaders … Read More →
Boolean Matrix Question
Given a matrix of size n x m filled with 0′s and 1′s e.g.: 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 if the matrix has 1 at (i,j), fill the column j and row i with 1′s i.e., we get: 1 1 … Read More →
What’s going on ?