GeeksforGeeks

Check whether a given string is an interleaving of two other given strings

GeeksforGeeks — Fri, 10 Feb 2012 03:58:15 +0000

Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B. C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved. See previous post for examples. Solution: [...]

Print all interleavings of given two strings

GeeksforGeeks — Thu, 09 Feb 2012 09:40:55 +0000

Given two strings str1 and str2, write a function that prints all interleavings of the given two strings. You may assume that all characters in both strings are different Example: Input: str1 = "AB", str2 = "CD" Output: ABCD ACBD ACDB CABD CADB CDAB Input: str1 = "AB", str2 = "C" Output: ABC ACB CAB [...]

Print all permutations with repetition of characters

GeeksforGeeks — Wed, 08 Feb 2012 04:52:35 +0000

Given a string of length n, print all permutation of the given string. Repetition of characters is allowed. Print these permutations in lexicographically sorted order Examples: Input: AB Ouput: All permutations of AB with repetition are: AA AB BA BB Input: ABC Output: All permutations of ABC with repetition are: AAA AAB AAC ABA ... [...]

In-place conversion of Sorted DLL to Balanced BST

GeeksforGeeks — Fri, 03 Feb 2012 06:55:58 +0000

Given a Doubly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Doubly Linked List. The tree must be constructed in-place (No new node should be allocated for tree conversion) Examples: Input: Doubly Linked List 1 2 3 Output: A [...]

Dynamic Programming | Set 8 (Matrix Chain Multiplication)

GeeksforGeeks — Thu, 02 Feb 2012 09:45:31 +0000

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications. We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter [...]

Dynamic Programming | Set 7 (Coin Change)

GeeksforGeeks — Sun, 29 Jan 2012 17:09:18 +0000

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, [...]

Populate Inorder Successor for all nodes

GeeksforGeeks — Thu, 26 Jan 2012 15:00:20 +0000

Given a Binary Tree where each node has following structure, write a function to populate next pointer for all nodes. The next pointer for every node should be set to point to inorder successor. Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor. [...]

Minimum number of jumps to reach end

GeeksforGeeks — Tue, 24 Jan 2012 15:58:16 +0000

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element. [...]

Count smaller elements on right side

GeeksforGeeks — Mon, 23 Jan 2012 06:07:18 +0000

Write a function to count number of smaller elements on right of each element in an array. Given an unsorted array arr[] of distinct integers, construct another array countSmaller[] such that countSmaller[i] contains count of smaller elements on right side of each element arr[i] in array. Examples: Input: arr[] = {12, 1, 2, 3, 0, [...]

Average of a stream of numbers

GeeksforGeeks — Sat, 21 Jan 2012 05:44:20 +0000

Difficulty Level: Rookie Given a stream of numbers, print average (or mean) of the stream at every point. For example, let us consider the stream as 10, 20, 30, 40, 50, 60, … Average of 1 numbers is 10.00 Average of 2 numbers is 15.00 Average of 3 numbers is 20.00 Average of 4 numbers [...]

Sorted Array to Balanced BST

GeeksforGeeks — Wed, 18 Jan 2012 13:18:01 +0000

Given a sorted array. Write a function that creates a Balanced Binary Search Tree using array elements. Examples: Input: Array {1, 2, 3} Output: A Balanced BST 2 / \ 1 3 Input: Array {1, 2, 3, 4} Output: A Balanced BST 3 / \ 2 4 / 1 Algorithm In the previous post, we [...]

Sorted Linked List to Balanced BST

GeeksforGeeks — Tue, 17 Jan 2012 10:31:45 +0000

Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List. Examples: Input: Linked List 1->2->3 Output: A Balanced BST 2 / \ 1 3 Input: Linked List 1->2->3->4->5->6->7 Output: A Balanced BST 4 / \ 2 [...]

Find the maximum element in an array which is first increasing and then decreasing

GeeksforGeeks — Sat, 14 Jan 2012 13:36:26 +0000

Given an array of integers which is initially increasing and then decreasing, find the maximum value in the array. Input: arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1} Output: 500 Input: arr[] = {1, 3, 50, 10, 9, 7, 6} Output: 50 Corner case (No decreasing part) Input: arr[] = [...]