1. Minimum Multiplications to reach End [program link]
Given start, end and an array arr of n numbers. At each step, start is multiplied with any number in the array and then mod operation with 100000 is done to get the new start. Your task is to find the minimum steps in which end can be achieved starting from start. If it is not possible to reach end, then return -1.
2. Binary Tree to BST [program link]
Given a Binary Tree, convert it to Binary Search Tree in such a way that keeps the original structure of Binary Tree intact.
3. Kth largest element in BST [program link]
Given a Binary Search Tree. Your task is to complete the function which will return the Kth largest element without doing any modification in Binary Search Tree.
4. Insert a node in a BST [program link]
Given a BST and a key K. If K is not present in the BST, Insert a new Node with a value equal to K into the BST. If K is already present in the BST, don't modify the BST.
5. Lucky Numbers [program link]
Lucky numbers are subset of integers. Rather than going into much theory, let us see the process of arriving at lucky numbers,
Take the set of integers
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,……
First, delete every second number, we get following reduced set.
1, 3, 5, 7, 9, 11, 13, 15, 17, 19,…………
Now, delete every third number, we get
1, 3, 7, 9, 13, 15, 19,….….
Continue this process indefinitely……
Any number that does NOT get deleted due to above process is called “lucky”.
You are given a number N, you need to tell whether the number is lucky or not. If the number is lucky return 1 otherwise 0.
6. Perfect Numbers [program link]
Given a number N, check if a number is perfect or not. A number is said to be perfect if sum of all its factors excluding the number itself is equal to the number. Return 1 if the number is Perfect otherwise return 0.
7. Largest number possible [program link]
Given two numbers 'N' and 'S' , find the largest number that can be formed with 'N' digits and whose sum of digits should be equals to 'S'. Return -1 if it is not possible.
8. Perfect Sum Problem [program link]
Given an array arr[] of non-negative integers and an integer sum, the task is to count all subsets of the given array with a sum equal to a given sum.
9. Partition Equal Subset Sum [program link]
Given an array arr[] of size N, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.
10. Count number of hops [program link]
A frog jumps either 1, 2, or 3 steps to go to the top. In how many ways can it reach the top of Nth step. As the answer will be large find the answer modulo 1000000007.
11. Print first n Fibonacci Numbers [program link]
Given a number N, find the first N Fibonacci numbers. The first two number of the series are 1 and 1.
12. Power of 2 [program link]
Given a non-negative integer N. The task is to check if N is a power of 2. More formally, check if N can be expressed as 2^x for some integer x.
13. Find first set bit [program link]
Given an integer N. The task is to return the position of first set bit found from the right side in the binary representation of the number.
14. Rotate Bits [program link]
Given an integer N and an integer D, rotate the binary representation of the integer N by D digits to the left as well as right and return the results in their decimal representation after each of the rotation.
15. Stickler Thief [program link]
Stickler the thief wants to loot money from a society having n houses in a single line. He is a weird person and follows a certain rule when looting the houses. According to the rule, he will never loot two consecutive houses. At the same time, he wants to maximize the amount he loots. The thief knows which house has what amount of money but is unable to come up with an optimal looting strategy. He asks for your help to find the maximum money he can get if he strictly follows the rule. ith house has a[i] amount of money present in it.
16. First and last occurrences of x [program link]
Given a sorted array arr containing n elements with possibly duplicate is to find indexes of first elements, the task is to find the first and last occurrences of an element x in the given array.
17. Equilibrium Point [program link]
Given an array A of n positive numbers. The task is to find the first equilibrium point in an array. Equilibrium point in an array is a position such that the sum of elements before it is equal to the sum of elements after it.
18. Find duplicates in an array [program link]
Given an array a of size N which contains elements from 0 to N-1, you need to find all the elements occurring more than once in the given array. Return the answer in ascending order. If no such element is found, return list containing [-1].
19. Maximum Sum Combination [program link]
Given two integer array A and B of size N each. A sum combination is made by adding one element from array A and another element of array B. Return the maximum K valid sum combinations from all the possible sum combinations.
20. Find All Four Sum Numbers [program link]
Given an array A of integers and another number K. Find all the unique quadruple from the given array that sums up to K. Also note that all the quadruples which you return should be internally sorted, ie for any quadruple [q1, q2, q3, q4] the following should follow: q1 <= q2 <= q3 <= q4.
21. Find the closest pair from two arrays [program link]
Given two sorted arrays arr and brr and a number x, find the pair whose sum is closest to x and the pair has an element from each array. In the case of multiple closest pairs return any one of them.
22. Wave Array [program link]
Given a sorted array arr[] of distinct integers. Sort the array into a wave-like array(In Place). In other words, arrange the elements into a sequence such that arr[1] >= arr[2] <= arr[3] >= arr[4] <= arr[5].....
If there are multiple solutions, find the lexicographically smallest one.
23. Number Of Enclaves [program link]
You are given an n x m binary matrix grid, where 0 represents a sea cell and 1 represents a land cell. A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid. Find the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.
24. Boolean Matrix [program link]
Given a boolean matrix of size RxC where each cell contains either 0 or 1, modify it such that if a matrix cell matrix[i][j] is 1 then all the cells in its ith row and jth column will become 1.
25. Boundary traversal of matrix [program link]
You are given a matrix of dimensions n x m. The task is to perform boundary traversal on the matrix in a clockwise manner.
26. Number of distinct subsequences [program link]
Given a string consisting of lower case English alphabets, the task is to find the number of distinct subsequences of the string.
27. Column name from a given column number [program link]
Given a positive integer, return its corresponding column title as appear in an Excel sheet. Excel columns has a pattern like A, B, C, … ,Z, AA, AB, AC,…. ,AZ, BA, BB, … ZZ, AAA, AAB ….. etc. In other words, column 1 is named as “A”, column 2 as “B”, column 27 as “AA” and so on.
28. Roman Number to Integer [program link]
Given a string in roman no format, your task is to convert it to an integer.
29. Count number of substrings [program link]
Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters.
30. Reverse alternate nodes in Link List [program link]
Given a linked list, you have to perform the following task:
- 1. Extract the alternative nodes starting from second node.
- 2. Reverse the extracted list.
- 3. Append the extracted list at the end of the original list.
31. Pairwise swap elements of a linked list [program link]
Given a singly linked list of size N. The task is to swap elements in the linked list pairwise. For example, if the input list is 1 2 3 4, the resulting list after swaps will be 2 1 4 3.
32. Insert in a Sorted list [program link]
Given a linked list sorted in ascending order and an integer called data, insert data in the linked list such that the list remains sorted.
33. Height of Binary Tree [program link]
Given a binary tree, find its height.
34. Nodes at given distance in binary tree [program link]
Given a binary tree, a target node in the binary tree, and an integer value k, find all the nodes that are at distance k from the given target node. No parent pointers are available.
35. Check for Balanced Tree [program link]
Given a binary tree, find if it is height balanced or not. A tree is height balanced if difference between heights of left and right subtrees is not more than one for all nodes of tree.
36. Duplicate subtree in Binary Tree [program link]
Given a binary tree, find out whether it contains a duplicate sub-tree of size two or more, or not.
37. Floor in BST [program link]
You are given a BST(Binary Search Tree) with n number of nodes and value x. your task is to find the greatest value node of the BST which is smaller than or equal to x.
38. Find Common Nodes in two BSTs [program link]
Given two Binary Search Trees. Find the nodes that are common in both of them, i.e- find the intersection of the two BSTs.
39. Normal BST to Balanced BST [program link]
Given a Binary Search Tree, modify the given BST such that it is balanced and has minimum possible height. Return the balanced BST.
40. Making A Large Island [program link]
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1. A group of connected 1s forms an island. Two 1s are connected if they share one of their sides with each other. Return the size of the largest island in the grid after applying this operation.
41. Transitive closure of a Graph [program link]
Given a directed graph, determine whether a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here, vertex j is reachable from another vertex i means that there is a path from vertex i to j. The reachability matrix is called the transitive closure of a graph. The directed graph is represented by an adjacency matrix where there are N vertices.
42. Eventual Safe States [program link]
A directed graph of V vertices and E edges is given in the form of an adjacency list adj. Each node of the graph is labelled with a distinct integer in the range 0 to V - 1. A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node. You have to return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
43. Level of Nodes [program link]
Given an integer X and an undirected acyclic graph with V nodes, labeled from 0 to V-1, and E edges, find the level of node labeled as X. Level is the minimum number of edges you must travel from the node 0 to some target. If there doesn't exists such a node that is labeled as X, return -1.
44. Form a number divisible by 3 using array digits [program link]
You will be given an array arr of integers of length N. You can construct an integer from two integers by treating the integers as strings, and then concatenating them. For example, 19 and 4 can be used to construct 194 and 419.
The task is to find whether it’s possible to construct an integer using all the digits of these numbers such that it would be divisible by 3.
If it is possible then print 1 and if not print 0.
45. Sum of all divisors from 1 to n [program link]
Given a positive integer N, The task is to find the value of Σi from 1 to N F(i) where function F(i) for the number i is defined as the sum of all divisors of i.
46. Number of paths [program link]
The problem is to count all the possible paths from top left to bottom right of an MxN matrix with the constraints that from each cell you can either move to right or down.
47. Maximum sum increasing subsequence [program link]
Given an array of n positive integers. Find the sum of the maximum sum subsequence of the given array such that the integers in the subsequence are sorted in strictly increasing order i.e. a strictly increasing subsequence.
48. Palindromic Partitioning [program link]
Given a string str, a partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome. Determine the fewest cuts needed for palindrome partitioning of the given string.
49. Knapsack with Duplicate Items [program link]
Given a set of N items, each with a weight and a value, represented by the array w and val respectively. Also, a knapsack with weight limit W. The task is to fill the knapsack in such a way that we can get the maximum profit. Return the maximum profit.
50. Minimum Operations [program link]
Given a number N. Find the minimum number of operations required to reach N starting from 0. You have 2 operations available:
1.Double the number
2.Add one to the number
51. Minimum Deletions [program link]
Given a string of S as input. Your task is to write a program to delete the minimum number of characters from the string so that the resultant string is a palindrome.
52. Bleak Numbers [program link]
Given an integer, check whether it is Bleak or not. A number n is called Bleak if it cannot be represented as sum of a positive number x and set bit count in x, i.e., x + countSetBits(x) is not equal to n for any non-negative number x.
This prgram takes a natural number as input and returns the sum of the prime multiples (2,3,5,7,11,13 ...) of the number.
If the input is a prime number, the program returns the number itself.
Example :
num = 60
Output = 12
Solution:
60 = 2 * 2 * 3 * 5
2 + 2 + 3 + 5 = 12