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.
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 →
Write a function to get the intersection point of two Linked Lists (Y Shape)
Method 1 (Brute Force) Using 2 for loops. Outer loop will be for each node of the 1st list and inner loop will be for 2nd list. In the inner loop, check if any of nodes of 2nd list is same as the current node of first linked list. Time complexity of this method will … Read More →
Write a program to detect loop in a Linked List
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 →
Iterative preorder, inorder and postorder tree traversals
Here is a complete C program which prints a BST using both recursion and iteration. The best way to understand these algorithms is to get a pen and a paper and trace out the traversals (with the stack or the queue) alongside. Dont even try to memorize these algorithms! And here is the output… Creating the root.. … Read More →
Determine if two binary trees are identical
Two trees are identical when they have same data and there physical layout is also same. To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees. Time Complexity: Complexity of the problem will be according to the tree … Read More →
Write C code to implement the Binary Search algorithm
Binary search is used to quickly find a value in a sorted sequence.At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually … Read More →
What’s going on ?