kanglicheng / dsalgo

Problems related to Algorithms and DataStructures

1. 01sumswap

• hashmap

2. 02mergesort

• divide and conquer

3. 03linkedlist
   • linked list data structure
4. 04quicksort
   • sorting
5. tbd
6. tbd
7. 07maxcontiguoussubsequence
   • save state to avoid recomputation
   • pre-process information into data structures
   • divide and conquer
   • scanning algorithms (esp. for problems on arrarys)
   • cumulatives
8. 08graphtraversal

• stack, queue

9. 09queue

• stack, queue

10. 10onlinepoker

• recursive to iterative

11. 11countinversions
    • divide and conquer
    • extension to mergesort with sorting
12. 12applestockprice
    • save state
    • pre-process
    • using itertools
    • greedy ("Suppose we could come up with the answer in one pass through the input, by simply updating the 'best answer so far' as we went. What additional values would we need to keep updated as we looked at each item in our set, in order to be able to update the 'best answer so far' in constant time?")
13. 13stackelementlargest

• think data structures + algorithms
• greedy using state information

14. 14heapsort

• heap data structure
• fencepost problems.

15. 15bst
    • binary search tree
    • Some nice BST properties.
16. 16encodedecodestrings/
    • Google Interviews Q
    • Python lists, .append, .join
    • Python None v/s False
    • Think before Code
17. 17maxequality
    • foobar
    • find pattern through trials.
18. 18stdinstdout
    • raw_input() for Python 2.7 v/s input() Python3.0
19. 19nthnodefromend
    • Think multiple pointers to pre-process state.
    • Using Dummy Node at beginning may be helpful.
20. 20coinchange
    • Dynamic Programming. Think Scanning..
    • Implementation of Multi-Dimensional Lists (without numpy)
21. 21superbalanced
    • DFS on Trees
    • Dont hesitate in maintaining state to solve problems.
    • Iterative v/s Recursive. Stacks and Queues are cheap for iterative versions.
22. 22arrayrotation
    • Bentley's Programming Pearls
    • Array Indexing and FencePost issues
23. 23stockmaximize
    • To simplify, start with brute force. Think how to apply patterns : sort,scan,cumulative,hashing,greedy,divideconquer
    • Think before code. Slow down urge to code rightaway. Think of alternate strategies.
24. 24friendcircles
    • (Two Sigma Pb)
    • Connected Components Problem
    • Converted adjacency matrix to a proper graph classes.
25. 25stringchains
    • (Two Sigma Pb)
    • Dynamic Programming. Nice Problem.
    • Was hitting 1 error on a hidden test case.
26. 26catalannumbers
    • Catalan numbers
27. 27orderstatistics
    • (Rocket Fuel Pb)
    • Divide and Conquer. Is there a way to exploit some property of the problem so we have to solve a smaller problem ?
28. 28lca