Author Archives: Crazyadmin

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 →

Remove duplicate characters in a string

Given a string, Write a program to remove duplcate characters from the string. Input String : crazyforcode Output String : crazyfode Algorithm : 1. For each character, check if it is duplicate of already found characters. 2. Skip duplicate characters and update the non duplicate characters. Method 1 Using Extra Space. Time Complexity : O(N) 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 →

Print letters followed by their frequency (Run Length Encoding)

Given a string ,Write a program to print letter followed by it’s frequency.This is also knows as Run Length Encoding. Example: Input aaabcc Output a3b1c2 Algorithm: 1.Pick the first character from the string and print it. 2.Count the number of subsequent occurrences of the picked character and then print the count. 3.Pick the next character Read More →

Write a program to detect loop in a Linked List

linkedlistLoop

Floyd’s Algorithm: This problem can be solved by using two pointers, slow pointer and fast pointer.Both these pointers will point to head of the linked list initially. Increment slow pointer by 1 node and the fast pointer by 2 nodes. If there’s a loop, the fast pointer will meet the slow pointer somewhere.We’ll discuss in Read More →

Print Level Order Traversal of a tree

levelordertraversal

Level Order Traversal of this tree would be 1 2 3 4 5 6 Approach: Starting from the root, first the node is visited and printed then it’s child nodes are put in a queue. Time Complexity: As we are visiting each node once.So the time complexity would be O(n) where n is the number Read More →

Find second Highest Salary for each department.

In previous mysql post, we found the second highest salary in employee table. In this problem we would like to find second highest salary for each department. EMPLOYEE TABLE EmpName Salary Department Steve 150$ Finance James 120$ IT Andrew 120$ Finance Mark 100$ Back-Office Adam 110$ IT Lewis 130$ Finance Smith 125$ Back-Office Solution : Read More →

Write a C function to find the height or depth of a tree.

Write a C function to find the height or depth of a tree. Solution : The height can be found out recursively by calculating height of left sub tree tree and right sub tree.Height of tree would be the maximum  of height of left subtree and height of right subtree + 1.  

Find the angle between hour handle and minute handle

Given the time in 24 hour format.Find the angle between hour handle and minute handle in a clock at any given time. Solution : Visualize the clock as a 360 degree circle.As we know that Hour handle completes 360 degree in 12 hours.In 1 hour or 60 minutes it complete 360/12 i.e. 30 degree.Minute handle Read More →