View Code? Open in Web Editor
NEW
Problems related to Algorithms and DataStructures
dsalgo's Introduction
01sumswap
02mergesort
03linkedlist
linked list data structure
04quicksort
tbd
tbd
07maxcontiguoussubsequence
save state to avoid recomputation
pre-process information into data structures
divide and conquer
scanning algorithms (esp. for problems on arrarys)
cumulatives
08graphtraversal
09queue
10onlinepoker
11countinversions
divide and conquer
extension to mergesort with sorting
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?")
13stackelementlargest
think data structures + algorithms
greedy using state information
14heapsort
heap data structure
fencepost problems.
15bst
binary search tree
Some nice BST properties.
16encodedecodestrings/
Google Interviews Q
Python lists, .append, .join
Python None v/s False
Think before Code
17maxequality
foobar
find pattern through trials.
18stdinstdout
raw_input() for Python 2.7 v/s input() Python3.0
19nthnodefromend
Think multiple pointers to pre-process state.
Using Dummy Node at beginning may be helpful.
20coinchange
Dynamic Programming. Think Scanning..
Implementation of Multi-Dimensional Lists (without numpy)
21superbalanced
DFS on Trees
Dont hesitate in maintaining state to solve problems.
Iterative v/s Recursive. Stacks and Queues are cheap for iterative versions.
22arrayrotation
Bentley's Programming Pearls
Array Indexing and FencePost issues
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.
24friendcircles
(Two Sigma Pb)
Connected Components Problem
Converted adjacency matrix to a proper graph classes.
25stringchains
(Two Sigma Pb)
Dynamic Programming. Nice Problem.
Was hitting 1 error on a hidden test case.
26catalannumbers
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 ?
28lca