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 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 →
3 Bulbs and 3 Switches
This puzzle is perhaps not as ‘pure’ as the others, it doesn’t reduce to a mathematical model. But it is quite a common question asked in interviews so it’s worth looking at it… Problem: You are in a room with 3 switches which correspond to 3 bulbs in another room and you don’t know which … 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 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 →
100 Doors Puzzle
Puzzle: : You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the … Read More →
What’s going on ?