Re: [algogeeks] Re: O(n)

We can sort the array in O(n) time using counting sort. And then take the difference of consecutive elements in O(n) time to get the minimum one. -Abhirup On Mon, Jun 28, 2010 at 10:36 AM, Jagadish M wrote: > In the general case, we can reduce Element-Distinctness(ED) problem to > this problem

[algogeeks] Re: O(n)

In the general case, we can reduce Element-Distinctness(ED) problem to this problem. Since ED has a lower bound of Omega(n log n), we cannot get an O(n) algorithm for this problem. http://en.wikipedia.org/wiki/Element_distinctness_problem -Jagadish http://www.cse.iitb.ac.in/~jagadish On Jun 2

[algogeeks] crazy

Problem :- A line of 100 airline passengers is waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. (For convenience, let's say that the nth passenger in line has a ticket for the seat number n.) Unfortunately, the first person in line is crazy, and will ignore

Re: [algogeeks] Re: common

it is not always true.. like you have to store all distinct strings somewhere to be compared.. so you can go for hashing also... but in that case different strings will take more space to store and it is tough to find a good hash function.. however in trie you are using a character only once at lev

Re: [algogeeks] Re: microsoft

#include #include #include using namespace std; int main () { int arr[] = {1,0,2,0,3,0,0,4,5,6,7,0,0,0}; int i=0,j=0; int len = sizeof(arr)/sizeof(int); while(1) { while(jhttp://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: longest chain

On Jun 20, 6:20 am, sharad wrote: > Given a dictionary of words, find out the longest chain of 'ancestors' > in it. Ancestors are defined in the following way: A word is said to > be the parent of another word if >      1) It is a valid word in the dictionary >      2) It can be obtained by dele

Re: [algogeeks] Matrix Problem

if the matrix is m*n for each item A[i][j] search for X-A[i][j] (this can be done in O(m+n) ) so the overall time is O( m*n*(m+n) ) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups

Re: [algogeeks] Re: String Problem

@amit: does the order of characters in Ssmall have to be the same in Sbig? On 6/27/10, amit wrote: > @ above can u plzz explain how to do it using LCS... > > I think u r finding the LCS and then backtracking to keep into account > the first and the last characters of the LCS in the Longer > strin

[algogeeks] second shortest path

How to find the second shortest path in a graph? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegrou

[algogeeks] graph

How many vertices are required to obtain 1024 unique undirected graphs. Find out the no. of vertices in a graph given the graph is: a) Undirected cyclic b) Directed Cyclic c) Undirected non cyclic d) Directed non cyclic. The graph can be disconnected. -- You received this message because you are

[algogeeks] sort in o(n)

Given a complete binary search tree in form of array. Write a sort function to sort the given array in O(n)time complexity and constant memory. say the tree is 100 _50___150 ___25___75__125___200 then array is {100 50 150 25 75 125 200} you need to sort the array. -- You receiv

[algogeeks] Project on finding an optimal route given a map.

Hi friends, I am doing a project on finding an optimal route between two points given on a map (well just started with it...). The map can be in OSM/ kml format or it can be an image as well (for now i have ruled out this option..since this will involve image processing and i doubt the accuracy..O

Re: [algogeeks] Maximum subset of cuboid boxes

@Senthilnathan: topological sort can be done in O(n) and we can solve LIS in O(n^2) (i'm not sure if the nlogn approach for LIS can be applied here) On 6/26/10, Senthilnathan Maadasamy wrote: > @Amir : What is the complexity of your approach? > > -- > You received this message because you are su

Re: [algogeeks] Diameter of a set of points

it's obvious that these 2 points must be on the convex hull so first find the convex hull O(n) then for each point on the hull find the farthest point by binary search (since if you turn on the hull the distance to the base point increases until the farthest point then it starts to decrease) if the

[algogeeks] Re: microsoft

On Jun 26, 8:59 pm, sharad kumar wrote: > #include > > using namespace std; > int main() > { > int arry[5]={0,1,3,0,4}; > int i=0,j=0,k=0; > for(;k<5;++k) > { > if((i==j)&&(arry[i]!=0)) > { > ++i; > ++j; > > } > > else if(i==j){ > j++;} > > else if(arry[j]==0){ > j++;} > > else if((arry[i] == 0) &

Re: [algogeeks] String Problem

Yes exactly... On Sat, Jun 26, 2010 at 9:57 PM, Anand wrote: > http://codepad.org/NDAeIpxR > Here is code for it > > > On Sat, Jun 26, 2010 at 9:54 PM, Anand wrote: > >> you can use Longest common subsequence algorithm to solve it. >> >> >> >> On Sat, Jun 26, 2010

Re: [algogeeks] rand 7

@Sharad Can u explain the logic behind this? On Sun, Jun 27, 2010 at 9:11 PM, sharad kumar wrote: > > Rand7 => Rand5%2*4+Rand5%2*2+Rand5%2*1; > > On Sun, Jun 27, 2010 at 4:57 PM, sharad kumar wrote: > >> You have a random 5 function. Generate a random 7 function using this >> random 5 function wi

Re: [algogeeks] rand 7

Rand7 => Rand5%2*4+Rand5%2*2+Rand5%2*1; On Sun, Jun 27, 2010 at 4:57 PM, sharad kumar wrote: > You have a random 5 function. Generate a random 7 function using this > random 5 function with equal probability > > -- > You received this message because you are subscribed to the Google Groups > "Algo

[algogeeks] single source problem

in single source shortest path ,having neg cost edges is good but: 1)it may lead us goto into a loop of arbitrary time in the meanwhile we can have another path with minimum positive cost but with less time. now by taking time fact

Re: [algogeeks] rand 7

Random 5 function will ensure equal probability for all number starting from 0 to 5. Now consider an event that you will run that random 5 function twice. This will create 25 elements in your sample space. Now make seven groups of three elements. This means that each group will be having three elem

Re: [algogeeks] Re: common

@harit tries are not space efficient and not a good soln if memory is main not time -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to

Re: [algogeeks] a bst

@Anand: Agreed. But according to this problem only the leaves form the doubly linked list On Sun, Jun 27, 2010 at 10:41 AM, Anand wrote: > @ Raj: I have one doubt. The condition you gave for finding the height of > the tree satisfies on every node if tree is a doubly linked list. Correct me > if

[algogeeks] n ary tree symmetry

Algorithm to find if a tree is symmetric? (The tree is a generalized tree with as many child nodes as possible) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe fr

[algogeeks] Radix Sort.

Can somebody explain why we have to shift the base of numbers while doing Radix Sort. I have read that if we have to sort N numbers we should convert all of them to base N... wats the use of it and while converting them wont it effect the time complexity -- You received this message because y

Re: [algogeeks] Re: Next higher element

@souravsain: Thanks man for a nice explaination On Sun, Jun 27, 2010 at 12:02 AM, souravsain wrote: > @Raj > > You need to examine the nature of the array from end. If form end you > move forward and you find elements are decreasing [10,12,14,16] then > for each element, the previous is next hig

[algogeeks] O(n)

How to find the two numbers whose difference is minimum among the set of numbers -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to a

[algogeeks] rand 7

You have a random 5 function. Generate a random 7 function using this random 5 function with equal probability -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe fro

[algogeeks] Re: arrays

You can count such pairs using the merge sort algorithm. While in merge sort if at any place you need swapping then increase the count. here is the code long long merge(long long *a,long long l,long long m,long long r) { long long i=l,j,k,t,c=0; long long ml[MAX_SIZE]; long long n1=m-l+1; j=l,k=m+

Re: [algogeeks] Re: common

@sharad i don't think there is better solution then trie.. it is space as well as time efficient... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this gro

Re: [algogeeks] Re: microsoft

i think the question is not just about sorting non-zero values... it is asking for a stable sort...so just swapping will not work in this case -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@

Re: [algogeeks] arrays

This is the famous Inversion Problem Hint: you can do it in O(nlogn) using a tweek in merge sort On Sun, Jun 27, 2010 at 11:26 AM, Anil C R wrote: > this is just brute force: > > count = 0 > for i in range(0, len(A)): > for j in range(i+1, len(A)): > if A[i] > A[j]: >

[algogeeks] Re: String Problem

@ above can u plzz explain how to do it using LCS... I think u r finding the LCS and then backtracking to keep into account the first and the last characters of the LCS in the Longer stringCorrect me if I am wrong... On Jun 27, 9:57 am, Anand wrote: > http://codepad.org/NDAeIpxR >

Re: [algogeeks] arrays

#include #define SIZE 5 int main() { int a[SIZE]; int i,j; int count=0; printf("\nEnter the numbers in the array:\n"); for(i=0;ia[j]) count++; printf("\n Count increment in progressCurrent Count=%d",count); } } printf("\nThe Value of count is:%d",c

Re: [algogeeks] c

it means that it can be changed by external processes...like whenever we read from port...it can be changed every time...it has nothing to do with external linkage -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, sen