Given n sequences, and starting and stopping point of every sequence with its score. For eg. no of sequences = 5 start stop score 0 4 4 3 10 11 6 8 8 7 15 10 11 15 4 All scores are positive. You have to find the maximum subset of non overlapping sequences having … Read More →
Convert Sorted Linked list to balanced BST
In previous problem, we discussed how to create a balanced binary search tree for a sorted array. Now we’ll see how to create the same from a sorted linked list. Method 1: This solution is similar to our previous solution but unlike array accessing middle element of linked list is not O(1). Approach : i. … Read More →
Convert sorted array to balanced binary search tree
Problem : Given a sorted array . Write a program to create balanced BST from the sorted array. We know that the in-order traversal of binary search tree gives the elements in sorted order. This tells us that the middle element of array will be the root. We can create left and right subtree by … Read More →
Merge a linked list into another linked list at alternate positions
Given two linked lists, insert nodes of second list into first list at alternate positions of first list. eg. 1->5->7->3->9 6->10->2->4, the first list should become 1->6->5->10->7->2->3->4->9 and second list should become empty. The nodes of second list should only be inserted when there are positions available. If the first list is 1->2->3 and second … Read More →
Kth largest or smallest element in an array
Write an C program to find kth largest element in an array. Elements in array are not sorted. example, if given array is [1, 3, 12, 19, 13, 2, 15] and you are asked for the 3rd largest element i.e., k = 3 then your program should print 13. Method 1 Use sorting. Return first … Read More →
Longest Increasing Subsequence
Problem: Find length of the subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Example : {10, 25, 9, 30, 21, 55, 40, 60, 75} Here Length of LIS … Read More →
Find sub-array whose sum equal to a given number
Given an array of non negative ints, is it possible to choose a sub array, such that the sum is equal to the given target? Example: Input : arr[] = {2, 4, 8}, target = 12 Output : true.(because 4+ 8 = 12(target sum)) Input : arr[] = {2, 4, 8}, target = 10 Output … Read More →
Move last node to front in linked list
Write a C function that moves last element to front in a given Singly Linked List. For example, if the given Linked List is 1->2->3->4->5, then the function should change the list to 5->1->2->3->4. 1) Traverse the linked list till last node. 2) Use two pointers – one points to last node and other to … Read More →
Root to leaf path with sum equal to given sum
Given a binary tree and a number,Write a function to find out whether there is a path from root to leaf with sum equal to given Number. In above tree, root to leaf paths exists for following sum. 7=> 1->2->4 9=> 1->3->5 10=>1->3->6 Implementation :
Mirror image of a binary tree
Write a program to create a mirror copy of a binary tree i.e. left nodes become right and right nodes become left. Solution 1 : Following program will create a new mirror tree. Solution 2: This program will convert tree into it’s mirror tree.
Remove characters from input string that are present in mask string
Write a C program that takes two strings as arguments and removes the characters from first string which are present in second string called mask string. ex: str1 “crazy for code” str2 “cod” Result: “razy e” Steps: 1) Get count array from mask string which stores count of chars from mask string. 2) Check for … Read More →
Level of a given node in binary tree
Given a Binary Tree and a pointer to the Node in that tree. Write a function to find level of Node in the Tree. For Example, in the below tree 0 / \ 1 4 / \ / \ 2 3 5 6 If the input key … Read More →
What’s going on ?