Algorithm

Search in a row wise and column wise sorted matrix

You are given an 2D array of MxN which is row and column wise sorted. What is the efficient way to search for an element? Steps: 1) Start from top right element 2) for loop compare this element e with x a) if they are equal then return its position b) e < x then Read More →

Generate integer from 1-8 with equal probability

Problem: Write a method to generate a random number between 1 and 8, given a method that generates a random number between 1 and 3. The distribution between each of the numbers must be uniform. Solution: Let’s think of this like a decision tree. Each rand3() will be a decision. If we somehow generate integers Read More →

Check for Children Sum Property in a Binary Tree

You are given a binary tree, you have to check if tree satisfies the property of children sum. This property says that for each node sum of its left and right children should be equal to node value. Solution: 1)Traverse the given binary tree (recursively) 2) For each node check if the node and both Read More →

Inorder Predecessor in Binary Search Tree

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

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

original list

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 →

Rotate linked list by K nodes

You are given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer. i.e. if the given linked list is: 1->2->3->4->5 and k is 3, the list should be modified to: 4->5->1->2->3. Assume that k is smaller than the number of nodes in linked list. Steps: Read More →

Sort an array of 0s,1s,2s

You are given an array of 0s 1s and 2s in random order. Sort the array so the o,1 and 2 are segregated. This problem is similar to Dutch national Flag problem.   Method 1: Use count sort logic. Complexity: O(N) Method 2: 1. Sort the array treating {0} as one group and {1, 2} Read More →

Missing number in an array

You are given an array of n – 1 unique numbers in the range from 0 to n – 1. There is only one number missing in the range from 0 to n – 1 . You need to find the missing number. We know that sum of of numbers from 0 – n-1  is Read More →

Find a pair of elements from an array whose sum equals a given number

Given array of n integers and given a number X, find all the unique pairs of elements (a,b), whose summation is equal to X. Algorithm: (1) Sort the array in ascending order. Use quick sort O(n logn), we mentioned in our previous post. (2) Initialize two index variables to find the candidate elements in the Read More →

Write C code to search for a value in a binary search tree (BST)

There are two ways to solve this problem. Algorithm: 1) Compere the root node if equal to data return 2) else if data < root value go to left sub tree 3) else if  data > root value go to right sub tree Method 1 : Iterative approach Method 2: Recursive approach Complexity O(log N), 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 →