My strategy to solve an algorithmic challenge in 60 mins
Refresher and also a guide for newbies. The time compartments below are not hard and fast. They are an after thought.
Time to solve a problem: 60 mins.
0–10 mins: Mathematics
Use pen and paper extensively to solve the problem for some datasets.
- Read the problem carefully and try solving it manually on paper.
- Identify the patterns in the data doing so.
- Formulate rules for the patterns found, such as — if I see XYZ pattern in data, I would next see ABC.
10–20 mins: Algorithm
Write some pseudo-code. See APPENDIX 1 (cheet sheet).
- Think of algorithms you can use to solve the problems.
- Think of the data structures you need to create to solve the problem.
- At this point, you might have two candidates for data structures that you can use.
20–30 mins: Code
Start writing some code and create a dirty solution.
- Figure out how you would read data from file into those structures.
- If you had two data structure candidates in the earlier step, choose one that seems to work better.
- Apply the algorithms and make it work on simple datasets.
30–40 mins: Fix
Do bug fixes and make it work on all datasets.
40–60 mins: Optimise
We can use the last 20 mins to optimise our solution.
- Expect to see timeouts with some datasets or runs out of memory.
- Add pre-processing steps to the existing data structures, where the computation is lesser or where the space used is lesser (ex. remove recursion and use queues).
- See if you are cracking more datasets.
Hope that leaves you better prepared to solve algorithmic challenges.
Very Useful links:
Hi all,I need your help to make a list of most used data structures and algorithms along with their tutorials…discuss.codechef.com
Memorise or go over the string functions in java. They come in handy quite often. — http://docs.oracle.com/javase/7/docs/api/java/lang/String.html
Choosing the right data structure, given our algorithm (used in the solution). (Work in Progress!!!)
Requirement: Algorithms where we traverse in some order inside the graph, such as DFS, BFS, Topological Sort.
Data structure: Graph
A graph consists of two lists — Nodes and Edges (usually ArrayLists)
private List<Vertex<T>> verticies = new ArrayList<Vertex<T>>();
private List<Edge<T>> edges = new ArrayList<Edge<T>>();
Vertex will have a value (indicative of node number) and edge (Edge class) will have two vertices (Vertex class) ‘from’ and ‘to’.
You can add below to a vertex to create a faster access to adjacent edges.
or Weak reference it.. ( Reminder: to access a WeakReference object, we use weakref.get() )
If the graph is a tree (or unidirected graph), each vertex can have — parent(/s) and children.
We can HashMap to find Vertex object, given their key/index value and different edges related to the Vertex.
So the Vertex stores some value and also (optionally) various edges associated with it.
Another way to store a Graph is to use a Matrix. Its not often used for large data sets (say, 1024 vertices … is 1MB x (bytes used per Edge)). So maybe we can run it till we are limited to (50K vertices)…