Flip all zeros to ones
Given a string of bits and a number k. In one flip, you can toggle k consecutive characters, how many flips are required to change the entire string to all ones. For example Input String: 0000110000 k: 3 OUTPUT: 4 Following are the four flips: FLIP-1: 1110110000 FLIP-2: 1110110111 FLIP-3: 1111000111 FLIP-4: 1111111111 If it is not possible […]
Sum of all nodes at a vertical level
Given a binary tree and a number n representing the vertical level. Write code to compute the sum of all nodes which are at vertical level n. For example, if the binary tree given is as below: and n=-1, then the output should be 12. Because Nodes at level =1 are 7 and 5 and […]
Vertical distance of a Node from root
Given a Binary Tree and a Node, Write a function that return the vertical distance of that node from root of the tree. The vertical distance of a node is computed as below: Then the vertical distance of root is 0. The vertical distance of right node is distance of root+1. The vertical distance of […]
Max value node between two elements of BST
Given an array of integers that represent values of nodes in a Binary Search Tree. For example, If the given array is {9, 4, 17, 6, 5, 3, 7, 22, 20} Then BST created from above array will be as below Two numbers are given (along with the array), find largest number in the path […]
Check if a subtree exist with a given sum
Given a binary tree and a Number N, write code to check if there exist a subtree of the Binary tree with sum of all the nodes = N. For example, if the Binary tree is as given on the right: And N = 12, then the output should be ‘true’ because there exist a […]
Reversing a linked list iteratively using only 2 pointers
Given a linked list, write the non-recursive function to reverse the list. If Input list is 1 -> 2 -> 3 -> 4 -> 5 Then output should be 5 -> 4 -> 3 -> 2 -> 1 We have seen the recursive and non-recursive functions to reverse the list. In the non-recursive version, we take three […]
How to prepare for Dynamic Programming Questions
The most difficult problems in Coding competitions and interviews of companies like Google, Microsoft etc. are from Dynamic Programming. DP as an approach to problem solving is discussed in almost all algorithm books. But, in most of the books, DP, as a concept is lost behind the difficult problems. For example, in one of the best […]
Rotten Oranges Problem
Given a Matrix of order M*N, where each cell can have zero or one orange. The orange in the cell (if present) can be either fresh or rotten. A rotten orange will rot the fresh oranges in the nearby cell in unit time. If a rotten orange is in cell (i,j), then it will rot […]
Recursive function to add 5 to alternate nodes of the linked list
Write a recursive function that add 5 to the alternate nodes of the linked list. For example, if the list is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 then the function should change the list to the below one 1 -> 7 -> […]
Print a circular linked list
Write a function that prints all the elements of a circular linked list. (or traverse a circular linked list)
