Problem: Given two binary trees, write a function to check if they are equal or not. Solution: Two binary trees are considered equal if they are structurally identical andthe nodes have the same value. Time Complexity: O(N), Where N is number of nodes in a tree. This article is contributed by Vishwas Garg. You can … Read More →
Replace all spaces in a string with “%20″
Problem: Write a C program that will replace all spaces with ‘%20′ Solution: The algorithm is as follows: 1. Count the number of spaces during the first scan of the string. 2. Parse the string again from the end and for each character: If a space is encountered, store “%20”. Else, store the character as … 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 the Minimum Distance Between Two Numbers
Problem: You are given an array and two elements, find the minimum distance between the elements in the array. The array may have duplicates. For example, if the array is (1, 5, 3, 7, 2, 8, 3, 4, 5, 9, 9, 3, 1, 3, 2, 9) Min Distance (4, 7): 4 Min Distance (9, 3): … Read More →
Deleting all Leaves from a Binary Tree
Problem: Given a binary tree, how do you remove leaves of it? Solution: By using post-order traversal we can solve this problem (other traversals would also work). Time Complexity: O(n). Where is numbe of nodes in tree. Write or Comment if you find anything incorrect or better approach.
Move the Spaces to Front of the String
Problem: Given a string that has set of words and spaces, write a program to move the spaces to front of string, you need to traverse the array only once and need to adjust the string in place. string = “move these spaces to beginning” output =” movethesepacestobeginning” Solution: 1) Maintain two indices i and … Read More →
Find a Pair Whose Sum is Closest to Zero in Array
Problem: This problem is also called minimum absolute sum pair. You are given an array of integers, containing both +ve and -ve numbers. You need to find the two elements such that their sum is closest to zero. eg. Array [15, 5, -20, 30, -45] O/P should be 15, -20 Solution: Searching for two numbers … 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 →
Eliminate the pairs (two same chars adjacent to each other) in string
Problem: You are given a string. You have to eliminate the pairs (two same chars adjacent to each other). eg. input string RGBBGBGR –> RGGBGR–> RBGR (output) Solution: We should check if we have character pair then cancel it. and then check for next character and previous character. Keep canceling the character until we either … Read More →
Print nodes at K distance from root in binary tree
In a binary tree, given a root and a number K. You have to find the all nodes at distance K from given root node. For example in a given tree, if K =2 then Output should be 4,5,6 if k = 1 then Output should be 2,3 Time complexity: O(N) as we have to … 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 →
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 →
What’s going on ?