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/

Linked Lists:

1. 3 sum problem (from 3 diff linked lists): http://www.geeksforgeeks.org/find-a-triplet-from-three-linked-lists-with-sum-equal-to-a-given-number/

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/

Explained: http://stackoverflow.com/questions/5502916/explain-morris-inorder-tree-traversal-without-using-stacks-or-recursion

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:

a. http://www.geeksforgeeks.org/find-the-largest-subtree-in-a-tree-that-is-also-a-bst/

b. http://leetcode.com/2010/11/largest-binary-search-tree-bst-in_22.html [Prefer]

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/

Advertisements

Leave a comment

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.

Answer:

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:

Image

Leave a comment

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’

Answer: 

(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:

Image

Leave a comment

Filed under Algorithms