GeeksSpot

Set of points, the points closest to each other Given a set of points in a x and y coordinates, find the pairs of points (x1, y1) (x2, y2) that are closest . Algorithm will be used plane sweep and data structure will be 2-4 tree. d - minimum distance between the so-far found closest points. p is current point. D is the ordered set of points present in strip. Remove the points further than d to the left of p from the ordered set D that is storing the points in the strip. Determine the point on the left of p that is closest to it If the distance between this point and p is less than d (the current minimum distance), then update the closest current pair and d . Algorithm given http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html 2-4 tree link is http://www.cs.mcgill.ca/~cs251/ClosestPair/2-4trees.html.

You have given "k" dice. How many way you can get a sum "S" and yes you have to throw all the dice. Write program for this. Its same permutations program...but we have to try with all the six S(1,2,3,4,5,6) possibilities for a dice. Exit condition will be If all the dice run out. SumP(dice,sum) = SumP(dice-1,sum-i)+i (from S).

print all balanced parenthesis of size "n". [ex:- for 1: (), for 2: ()(), (()); like this] Printing balance paranthesis, need dynamically updating your options. Such as initially only openeing brace can be choosen and closing braces are not present. You choose one opening brace and add into your result, this will decrease the number of opening brace but increase the closing brace count by one. In normal permuations program, we try with every element in set with every other element. So, here are only two choices given one opening brance and closing brace with n numbers. So, everytime we try to choose, we check for the opening brace count available and closing brance count available. I am posting my program here, #include using namespace std; static int permcnt; void print( char out[], int cnt) { //Print all the index from 0 to cnt-1 of out permcnt++; } void generate ( char in[], int i, int opara,int cpara) { int j; if ( opara == 0 && cpara == 0) {

Yor are given occurrences of 3 words (say, "bangalore", "hyderabad", "google") in a file. bangalore: 100, 130, 157, ... hyderabad: 80, 145, 180, .... google: 60, 139, 197, ... [Note: occurrences are given in sorted order.] Now, you need to find the "smallest snip" containing all these three words. [In this case: 130("hyderabad"), 139("google"), 145("bangalore") - 15 is snippet size]. Can you generalize this for m words and length of occurrences is n. Algorithm: Take first element from all list and put in a array. minsnip = INT_MAX; while any of list have element. do currentsnip = max in array - min in array; if currentsnip < minsnip minsnip = currentsnip; delete the min element from array. Get second element fron deleted list. done

Given a dictionary containing four letter words print out all the words which can be formed by changing only character from the word each time.

There are billions of points find the 10 points which are closest to the origin.

Find the two numbers whose difference is minimum among the set of numbers. For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19 The algorithm should return min diff = 20-19 = 1. Make an efficient algorithm, yeah best could be O(n). Not sure if i could use DP here, will post a solution tommorow. Let me know if you find a answer. Algorithm:MiniMumDiffN Get the size of array , say n. Get the range of array, range. Bucket Sort the above array. Search the above sorted array for minimum difference. This will be the minimum difference numbers. Now question comes where the range of above given array is very big. Algorithm:DivideArray Take an random element. Search for its position in array. Return the index of element. Algorithm:MiniMumDiff if array_range > MAXRANGE int mid = divideArray (arr,start,end); d1,max1 = MiniMumDiff( arr,start,mid-1); d2,max2 = MiniMumDIff(arr,mid+1,end); d3 = difference max1 and arr[mid] d4 = difference max2 and arr[mid] return minimum( d1,d2

you are given a M x N matrix with 0's and 1's find the matrix- 1. find the largest square matrix with all elements 1's 2. Find the largest rectangular matrix with all elements 1's Its simple DP problem guys ..just think of extending the solution to sub-problem. Will post answer soon..till then give it a try. Okie so recursive expression is SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))*ARR(i,j)+ARR(i,j); Idea is that SQ(i,j) will be a 1+ min of its precedents square size. I am multiplying and adding to avoid if else condition if ( ARR[i][j] == 1 ) SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))+1; else SQ(i,j) = 0; is same as this SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))*ARR(i,j)+ARR(i,j); Will post code soon.

Given a binary tree,write an algorithm to find if the tree is a binary search tree or not. Simple Recursive call is good.. int check_tree(bst *node) { if(!node) return TRUE; if(node->left!=NULL && node->info left)) return(false); if(node->right!=NULL && node->info right)) return(false); if(!check_tree(node->left) || !check_tree(node->right)) return(false); return(true); } I have already posted better algorithm in my tree sections earlier. Set Min and Max to INT_MIN and INT_MAX bool IsBst( node *root, int min, int max) { if (!root) return true; if ( !isBst( root->left,min,root->info) return false; if ( !isBst(root->right,root->info,max) return false; return true; }

For a binary matrix of size n x m of 0's and 1's. eg 1 0 0 1 0 0 1 0 0 0 0 0 If a location has 1; make all the elements of that row and column = 1. eg 1 1 1 1 1 1 1 1 1 0 1 1 Solution should be with Time complexity = O(n*m) and space complexity = O(1) Will post answer in comments. Try till then.

Problem: Design a data structure which can perform most efficiently insert and median. My Solution: struct node { int number; node *left; node *right; int leftTreeNode; }; struct header { int totalNodes; Int valid; int median; node *root; } myhead ; //myhead ......thats where it will start. void initialize() { valid = 0, median = 0, root =NULL, totalNodes =0; } void AddNode ( int n ) { myhead.totalNodes++; myhead.valid = 0; node *prev = NULL; node *temp = myhead->root; while ( temp != NULL ) { if ( n <>number ) { prev = temp; temp->leftTreeNodes +=1; temp = temp->left; } else { prev = temp; temp = temp->right; } } if ( prev != NULL ) { if ( n <>number ) prev->left = createNode(n) else prev->right = createNode(n); } else myhead->

There are N persons in a country. N is very big in millions. Design a efficient data structure and algorithm to find out whether there is blood relations between given two person or say they have a common ancestor . My solution: Used a map //UID by Nandan Nilekani :) struct person { struct person *father; struct person *mother; list child; //However may not be needed for this problem string name ...i.e. //Add more } struct person * findAncestor ( struct person *a, struct person *b) { Take first node in stack. While ( stack is not null ) { Mark Node. Push Its ancestor in stack; } Take second node in stack. while ( stack is not null ) { If marked return Node, push ancestor in stack. } return NULL; } It has a drawback, i need to clear the flagged node before i apply the search algorithm again. But till now the best i know.

Given an array which have samples of stock price at different timestamps. You have to find best timings when we can buy and sell and make maximum benifit by it. No need to say u can sell only after you buy. Its simple DP problem, just need to form a equation MaxGain(i) = Max(MaxGain(i-1), DIff(i,min)) Min is the index of element having min value till now. Diff will return the value(i)-value(min). Hope its clear.

Given an array of size n and value from 1-n. Find the number of times each value occured in array inplace. and O(n). Easy one: Lets say array is a[]. size is N while ( i < n) a[a[i]%N] += N

In a city there are n number of gas stations. A gas pipleline from government has to pass right through (vertically only) the city. You have to create an algorithm which tells you the best place the pipe line should pass and cost to government is minimum. Cost is always propotional to the distance from gas station to pipeline. Silly me, it took so much time to answer this one. Okie i am posting my answer.... Sort the points for X axis...take a median of them. That will be the line x=c. Lets say there are n points. case 1: n is odd. So there will be a single point for median. say i. Distance between a point from pipeline is abs(x1-xi). As there are odd points so except the median, all the points will form a pair. Between a pair of points if we move the pipeline between them, effective distance from pipeline will remain constant. So if median of x-axis value our pipeline is passing then effective distance will be same till for all the pair

There is n parking slots and n-1 car already parked. Lets say car parked with initial arrangement and we want to make the car to be parked to some other arrangement. Lets say n = 5, inital = free, 3, 4, 1, 2 desired = 1, free, 2, 4 ,3 Give an algorithm with minimum steps needed to get desired arrangement. Told by one of my friend and after a lot of search i really got a nice solution. I will post solution in comment part

A great site for math and physics puzzles http://www.blogcatalog.com/blog/physically-incorrect/f5ae796cc31d8af0b3ea6df7945e569b

what next? 1 11 21 1211 111221 See pronunciation? You will get the answer.

U have 5 NOs , X1,X2,X3,X4,X5 With minimum no. of comparisons we have to find a median. SWAP(X,Y) function is available to u . I have a answer of six comparisons and eight swaps....wait for people to find out by themselves.

Given n distinct points prove that for all k,0 divide points into n-k and k points by drawing a line segment.... Proof given on a site There are n points, so max n(n-1)/2 different directions of the line segments joining two points among these n points. Now draw any line which has direction different than above at most n(n-1)/2 values. By choosing a different direction you are making sure that no two points can lie on the line. Now you can 'drag' the line as much as you want and get as many points on it's one of the sides as you want.