Print Permutation And Combination

Nearest Neighbhour on a 2-D Plane Using KD-Tree

Nearest Neighbour (NN) is an intuitive method for finding a similar item.
In the recent past I kept stumbling on NN at work, quora and at coursera course. So here us an implementation in c++ to find nearest neighbour using a data structure called KD Tree on a 2-D Plane.

Here is the github gist:


References: 
http://en.wikipedia.org/wiki/K-d_tree 

 I had actually implemented the above for a K-Nearest Neighbour, using a priority queue. you can all see that it only takes a minor tweak to achieve that.

Amazon Interview Question #2 - Maximum Sum Sub Matrix

This is a slightly more involved problem, We would be very happy if someone could code this within the stipulated interview time. I was going to vote "Strongly Inclined" for that candidate:).

Amazon Interview Question #2: 

Problem: Maximum Sum Sub Matrix.
Description: given an integer matrix find the sub matrix that has maximum sum.

This is a logical extension of Amazon Interview Question #1: Maximum Sum Sub Array. This is essentially the same problem in 2D space.

My Solution:


Have Feedback?Is my solution buggy?
please leave a comment

Amazon Interview Question #1 - Maximum Sum Sub Array

I have been taking data-structures and algorithm interviews for Amazon. But I have been repeating from a small set of questions and I want to break this habit. So I am planning to post the interview questions and my code.

We expect the candidate to solve these question within an interview of 1 hr duration.

Amazon Interview Question #1: 

Problem: Maximum Sum Sub Array.
Description: given an integer array find the sub array that has maximum sum.

for e.g.
Sample Array = {2,-1,2,-1,4,-5}
Answer: 2,-1,4
Answer: 2,-1,2,-1,4

My Solution:

Have Feedback?Is my solution buggy?
please leave a comment

I am really impressed by www.algorithmist.com it is a great way to explore the programming problems on www.spoj.pl. I am going to do the same for www.codechef.com. I am planning to break down the programming problems.

So here is the first problem


problem-link: http://www.codechef.com/submit/HS08TEST

crux of problem:
The problem needs you to compare floating point numbers and print the output with a fixed decimal precision. The problem states that the range is from 0 to 2000 and precision is 2 decimal places.
Note: In languages like C++, C the floating point comparison can be tricky.

solution:
I converted all the float values into int. then processed and later converted back to float.

source code:
https://github.com/ramprasadg/AlgosForOnlineJudges/blob/master/CodeChef/HS08TEST.cpp

Puzzle Algorithms

topcoder's algorithm tutorials have been a great place to learn from.
esp the one based on geometry are good. here is the link
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index


apart from this, http://www.techinterview.org/index.html
claims to have some puzzles and algorithms frequently asked in tech interviews.

SPOJ

good place to start ones habit of SPOJing.
http://ajayfromiiit.wordpress.com/2006/06/04/spoj-method-to-solve-for-beginners-part-1/