# 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.

**APPENDIX 1**

*Very* Useful links:

**Data Structures and Algorithms**

*Hi all,I need your help to make a list of most used data structures and algorithms along with their tutorials…*discuss.codechef.com

Useful tips

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

Useful links

**APPENDIX 2**

**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.

ArrayList<Vertex<T>> neighbours;

or Weak reference it.. ( Reminder: to access a WeakReference object, we use weakref.get() )

ArrayList<WeakReference<Vertex<T>>> neighbours;

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)…