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 →
Reverse a singly linked list
How to reverse a singly linked list ? This problem demonstrates the ability to work with pointers and visualize a data structure. Here we are using two pointers to reverse a list. Time complexity will be O(n) as you have to visit every node to change the pointers.
Singly Linked List – Delete Node
You are given a pointer to a node in a singly linked list. Delete that node from the linked list. Pointer to previous node is not available. Solution: The algorithm is as the following: We have a list looking like: … -> Node(i-1) -> Node(i) -> Node(i+1) -> … and we need to delete Node(i). … 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 →
Write a function to check if a binary tree is a binary search tree
Binary search tree’s Properties : 1. root value is greater than or equal to maximum value in left sub tree. 2. root value is less than minimum value in right sub tree. 3. In Order traversal of BST produces a sorted array. Based on above properties we can check if a binary tree is a … Read More →
C program to reverse a string
For example if a user enters a string “crazyforcode” then on reversing the string will be “edocrofyzarc “. We show you two different methods to reverse string the first one we make our own function to reverse string using pointers and in second, reverse string using recursion. Method 2 : Using recursion In recursion method … Read More →
Maximum sum in contiguous subarray
This is very famous interview question. Given an array A of integers (both positive and negative) and you need to find the maximum sum found in any contiguous subarray of A. Example A = [11, -12, 15, -3, 8, -9, 1, 8, 10, -2] Answer is 30. There are many solutions to this problem. Method … Read More →
Quick Sort
QuickSort is based on divide-and-conquer approach. QuickSort is inplace sorting algorithm.A sorting algorithm is said to be in-place if it requires very little additional space besides the initial array holding the elements that are to be sorted. The key to the Algorithm is the Partition Procedure, which rearranges the subarray a[p..r] in place. Partition selects … Read More →
Write a program to count nodes in a tree
Approach: Traverse all the nodes in a tree. You can do any traversal and just start counting. But there is a concept called tail recursion which is handy and very easily readable. If you have a tree, if you know the number of nodes in the left and number of nodes in right +1, then, … Read More →
What’s going on ?