Minimum No. of Jumps

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example :
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
If it is not possible to reach the end index, return -1.

 Follow this link to read a O(n^2) solution GeeksforGeeks: Minimum number of jumps

Read my O(n) solution below

Maximum Product Subarray

One of the standard dp problems, the approach given below is similar to kadane algorithm for maximum subarray sum problem. The code given below fails when negative output is the max possible. For example the input

Input : -4

Comments are welcome.

Preparing for the Coding Interview

Here are a few things that I did while preparing for my placements and a few things that I think I should have done.

This post is written with the plan that you have max of 6 months left before the D-Day, for people in the their 2nd or 3rd years there is a variety of things that would further enhance their chances of being placed.

<-------------------------- 6 Months -------------------------------->
www.geeksforgeeks.org    This is a very big repository of coding interview questions and preparations material. Usually one would require about 6 months to go through the whole material.

<--------------------------- 4 - 5 Months --------------------->

After having read the standard algorithms and Data Structures, its time to gain some coding experience

www.interviewbit.com This site is very good for coders with not much experience, you will have revision of concepts and get practice at the same time. It provides a gaming level sort of UI to make it interesting, which a growing community.

www.leetcode.com This is another site is popular among coders for interview preparation, but many questions between interviewbit and this overlaps so do one of them. InterviewBit has more structure and organization for preparation.

<------------------------------1-2 Months ---------------------------->

Hopefully above level of preparation would be sufficient for clearing hte coding rounds and you are now shortlisted your dream companies. So brush up the topics on your resume and prepare for the specific domains like Networks, OS .

Some important topics to prepare for :
1. Linked List
2. Stacks and Queues
3. Dynamic Programming ( geeksforgeeks has an extensive collection)
4. Greedy
5. Backtracking 
6. Graph Theory ( dfs and bfs will do for most except google,fb ) 


Comments and suggestions are welcome . 

Getting started with Python API for Facebook

Install the repository with

sudo pip install facebook-sdk

Here is a sample program to print the name of your friends 

To get the oauth_access_token follow this link Graph API Explorer

See the following the snippet for printing posts with some specific substring in them. This way we can complete the hack of posting multiple comments on similar posts

I found another python libray, which seems more easier to use than this one. visit that Facepy

SPOJ PRATA

The problem : www.spoj.com/problems/PRATA/

Solution: There are many solutions one can use binary search which is straight forward if you understand the concept of binary search . Use the link to find a binary search based implementation

http://spoj-solutions.blogspot.in/2014/10/prata-roti-prata.html

I used a min-heap based solution. The algorithm is to find the the cook who will next become free and assign him a prata, as simple as that.

My solution is O(p*L) which got accepted. You can find the code through following link
https://github.com/kanirudh/spoj/blob/master/prata.cpp

Comment below in case of queries.

A list of algorithms for Competitive Programming

Solving problems on SPOJ, I realised I used to forget the algorithms which I had previously used. For this fallacy of mine I am listing the algorithms and the corresponding SPOJ problems. There may be better resources on net similar to this but this is my effort. You can also find solutions to these problems on my github page http://www.github.com/kanirudh/SPOJ/

1. Sorting:
     Using the library function for sorting usually does the trick. You need to know how to define a comparator function for sorting user-defined structure arrays.
   
     http://www.spoj.com/problems/DOTAA/

2. String Algorithms
 
     Patten Matching
     a) KMP Algorithm
     http://www.spoj.com/problems/NHAY/
     b) Rabin Karp 

3. Dynamic Programming Algorithms
   
     a) 0/1 Knapsack
     http://www.spoj.com/problems/LKS/
   
     b) Longest Increasing Subsequence
     http://www.spoj.com/problems/XMEN/

     c) Longest Common Subsequence
     http://www.spoj.com/problems/LCS/
     http://www.spoj.com/problems/TRIP/

4. Divide And Conquer
     a) Closest Pair of Points
     http://www.spoj.com/problems/CLOPPAIR/

     b) Binary Search
     http://www.spoj.com/problems/PIE/
     http://www.spoj.com/problems/EKO/
     http://www.spoj.com/problems/OPCPIZZA/
 

5. Graph Algorithms
    ( DFS, BFS, Djisktra, Floyd-Warshall, Bellman-Ford, kruskal)
    http://www.spoj.com/problems/PARADOX/

6. Maths
    Gaussian Elimination
    http://www.spoj.com/problems/XMAX/






 

HTKBook Tutorial and Solutions

While re-creating the chapter 3 of the HTK I encountered the following problems and the solutions to the those problems when I found them

1. The 'gram' file copy the text shown the book into a file 'gram.txt' and run the following command
HParse gram.txt wdnet

2. HSlab does not work showing the following error " MakeXGraf: Not compiled with X11 support" 

Step1. Open htk/HTKLib/htik_htklib_nt.mkf

          Change HGraf.null.obj -> HGraf_WIN32.obj
          Change HGraf.null.olv -> HGraf_WIN32.olv
          Run "nmake /f htk_htklib_nt.mkf all" under HTKLib directary
Step2. Open htk/HTKTools/Makefile.in
           Delete -lXll (lower case of "L")
           Run "nmake /f htk_htktools_nt.mkf all" under HTKTools directory

Found a awesome site which lists all the common error noticed when using HTK. Here is the link for your benefit: HTK Problems and Solutions

Note: The tutorial given in the HTKBook it misses one thing which training dataset. It suggests using TIMIT Database for training. But TIMIT is not free.

I decided to skip a step and search for pre-trained models available online. First I found this one
http://www.keithv.com/software/htk/us/
But then again this did not work as given, many errors occured in the pronounciation dictonary.

Next I found this one http://www.repository.voxforge1.org/downloads/Nightly_Builds/ which has a nicely trained hmm models along with the respective dictionary which is very helpful. Now note you cannot run the live recogniser with these models because they use the following feature extraction scheme which is "MFCC_0_D_N_Z" , but you can sucessfully use the HVite decoding example given in the tutorial. The accuracy for decoding module is very low using these models since they use features described above but which is only possile using HCompV used for training.

I couldn't find a way to emulate the features using HCopy

The next database I tries was the part of TIMIT database available freely( thanks to MIT) , the link is following MIT TIMIT Corpora . The problem with this I am facing is that the pronounciation dictionary is and label files are not matching and some phoneme are not there.

Hacking my way through HTK, I was told that TIMIT label format needs to be modified quite a bit for use with HTK.

Incase of any queries you can contact me.