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