# Category Archives: Algorithms

## GsFGs important questions

Recursion:

1. Reverse stack using only push(), pop() and isempty(): http://www.geeksforgeeks.org/reverse-a-stack-using-recursion/

2. Backtracking: Tug of war: http://www.geeksforgeeks.org/tug-of-war/

3. Permutations of a string: http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Trees:

1. Find a pair with given sum in BST: http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/

2. Morris Traversal: http://www.geeksforgeeks.org/morris-traversal-for-preorder/

3. BST from preorder: http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversal-set-2/

4. Boundary traversal Binary Tree: http://www.geeksforgeeks.org/boundary-traversal-of-binary-tree/

5. Parallel inorder search: http://www.geeksforgeeks.org/merge-two-bsts-with-limited-extra-space/

6. Find largest BST in a tree:

7.Check if a binary tree is sum tree: http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/

8. Print BST keys in a given range: http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/

9. Get the level of a node: http://www.geeksforgeeks.org/get-level-of-a-node-in-a-binary-tree/ (Important, also used in printing all nodes at a distance k from root)

10. Sorted order printing of an array: http://www.geeksforgeeks.org/sorted-order-printing-of-an-array-that-represents-a-bst/

11. Root to leaf path sum equal to a given number: http://www.geeksforgeeks.org/root-to-leaf-path-sum-equal-to-a-given-number/ (important to know how to return bool)

12. Level order in spiral (using recursion, complexity is O(n^2)) http://www.geeksforgeeks.org/level-order-traversal-in-spiral-form/

Filed under Algorithms

## Dynamic Programming – Kadane’s Algorithm

Question: Write a program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

We need to focus on the fact that whenever sum of digits of array goes less than zero it is better to keep the sum as 0. Anywhere we’ll encounter a positive integer we’ll again start the sum.

Example:

array : -2 -3 4 -1 -2 1 5 -3

sum  :  0 0 4 3 1 2 7 4

So 7 is the result.

Code:

Filed under Algorithms

## Dynamic Programming – Famous coin sum question

Question: Out of given ‘N’ coins, give the minimum number of coins required to sum upto ‘S’

(Assumption: list of coins is sorted)

Loop from 1 to S and check solution for each denomination keeping solution for 0 as 0. DYNAMIC PROGRAMMING !!

For example, if you have N coins as {1, 3, 5} and you have to sum upto 10 then loop from 1 to 10 and for each number check if the number is more than maximum value of denomination present. If yes, than your answer will be (number – maximum denomination)’s answer + 1.

Number — COINS REQUIRED

0 — 0

1 — 1

2 — 2  (i.e. [2-1]’s answer + 1 i.e. [1]’s answer + 1 i.e. 1 + 1 == 2)

3 — 3  (i.e. [3-3]’s answer + 1 i.e. [0]’s answer + 1 i.e. 0 + 1 == 1)

4 — 2

5 — 1

and so on…

10 — 2  (you know why !)

Code: