In Previous Post We learned about In-Order Successor.In this post ,We’ll learn what is In-Order Predecessor. The predecessor of a node x in a search tree is the node with largest key that belongs to the tree and that is strictly less than x’s key. In above binary search tree, in-order predecessor of 17 is … Read More →
Inorder Successor in Binary Search Tree
Given a node in binary search tree say x,the in-order successor of node x is the node with the smallest value greater than node x’s value. In above binary search tree, in-order successor of 18 is 20, successor of 6 is 7 and successor of 13 is 15. Algorithm : In in-order traversal of binary … Read More →
Copy a linked list with next and arbit pointer
Problem: Given a doubly linked list with one pointer of each node pointing to the next node just like in a singly linked list. The second pointer(arbit pointer) however can point to any node in the list and not just the previous node. Write a program in to create a copy of this list. Algorithm: … Read More →
Print all ancestors of a node in binary tree
Problem: Given a Binary tree and a node’s value, Write a function to print all the ancestors of the node. Thinking of solution??Think Recursively.This problem can be easily solved using recursion. We start from the root of the tree and keep going down the tree. When we reach the node with given value we return … Read More →
Find missing number and duplicate number
Given an array of size N containing number from 1 to n,except one number is missing and one number is duplicated.Find Both numbers in linear time. This problem is an extension of our post of finding missing number in an array. Solution : Let missing number be x and duplicate number be y. We know … Read More →
Adobe Interview – Set 1
I am Aman gupta. I passed out in 2010. I recently appeared for the adobe interview. I had one written test. It consisted questions of C/C++,English and logical reasoning. I cleared the written test and then got call for face to face interview. Round 1: 1. Given a router which takes a ip as input … Read More →
Lowest common ancestor in a Binary Tree.
Problem : Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Lowest Common Ancestor: The lowest common ancestor (LCA) of two nodes v and w is defined as the lowest node in tree that has both v and w as descendants (where we allow a node to be … Read More →
Print a Square Matrix in Spiral Form
Given a N*N square matrix. Write a code to print it in spiral order. Time Complexity : O(N^2)
How many possible ways the child can run up the ladder
A child is running up a ladder with n steps, and can hop either 1 step or 2 steps at a time. Calculate how many possible ways the child can run up the ladder. This problem is similar to Fibonacci Problem. Each step n can be reached from either two steps below (n-2) or one … Read More →
Find the Nth Highest Salary in a table.
In previous database posts we have seen how to retrieve 2nd highest salary (in whole table and for each department). But, what if we want to find the Nth highest salary, where N can be any number whether it’s the 3rd highest, 4th highest, 5th highest, 10th highest, etc?. EmpName Salary Steve 150 Mark 100 … Read More →
Write a function to check whether two strings are anagram of each other.
Input: s – “abcde”, t – “abced” Output = true Input s – “abcde”, t – “abcfed” Output – false Below are two solutions to this problem. Method 1: Sort both the strings and then compare the strings. Time Complexity is O(nlogn). Method 2: Check if the two strings have same count for each character. … Read More →
Check if a binary tree is a binary search tree in O(n)
Method 1 of previous post runs slowly since it traverses over some parts of the tree many times.As we stated in previous post that all left nodes must be less than or equal to current node, which must be less than all the right nodes. Keeping this in mind, we can approach the problem by … Read More →
What’s going on ?