Re: [algogeeks] Re: Suggest some Data Structure appropriate to the problem
@Gene : Thanx for the reply. Understood your point. On Tue, Mar 6, 2012 at 6:24 AM, Gene gene.ress...@gmail.com wrote: What Don so succinctly said is this: Comparison sort _requires_ O(n log n) comparisons. If you had the data structure you're asking for, you could easily implement a comparison sort: Just insert n items, then then repeat n times: find min and delete that min. With your proposed time bounds, the resulting sort would be O(n). This is how you can immediately tell what you're asking for is impossible. On Mar 5, 5:51 pm, Sehaj Singh Kalra sehaj...@gmail.com wrote: Ok. Got it. I think that without the assumption that you took ( about FIFO implementation i.e. only the recent most element to be added can be deleted or else there would be problem in updating stack 2) the problem can't be done. Thanks for the proposed solution. On Tue, Mar 6, 2012 at 4:13 AM, SAMM somnath.nit...@gmail.com wrote: As I mentioned we have to use hashing using Separate Chaning to find the element in constant time . This is different than than opening addresing which added the element to the next free slot in case of a collision , so we cann't keep track of the element in a constant . In sepate Chaning the elements when collision is found the element will be in the stored in the form of the linked list on the same slot . IN worst case if all the element give collision then the time complexity can be of O(n) . But chossing the proper hash key can give the result in constant time . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Suggest some Data Structure appropriate to the problem
I want insertion , deletion, find (any general element) and min_element - all 4 operations in constant time order. Is there any data structure that can help me do this? - Sehaj -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Suggest some Data Structure appropriate to the problem
@SAMM : Nice way to keep the track of the smallest number. But by your way we won't be able to do search in constant time. @Don : I was asked this question during an interview, so I think there must/might be some possible solution. On Tue, Mar 6, 2012 at 3:55 AM, SAMM somnath.nit...@gmail.com wrote: Use two stack :- One stack is used for inserting and deleting the elements in the stack , supposing the the addition and deletion is done at the end of the stack . So it will be of in constant time . The Second Stack is used keeping track of the smallest number . For finding the element we need to used Separate Channing in hashing . Take the element to be added suppose (N). Now compare the top element of second stack (suppose X) with N . If (N X) Added N to both the Stack . else if (N X) Added N to the first Stack . When the element(N) is removed from the top of the first stack. Then compare it with the second stack (X) . If (N = X) Remove N from both the Stack . The Second stack will ensure that on removing or adding an element in the stack , The second stack will let u know the smallest element . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Suggest some Data Structure appropriate to the problem
Ok. Got it. I think that without the assumption that you took ( about FIFO implementation i.e. only the recent most element to be added can be deleted or else there would be problem in updating stack 2) the problem can't be done. Thanks for the proposed solution. On Tue, Mar 6, 2012 at 4:13 AM, SAMM somnath.nit...@gmail.com wrote: As I mentioned we have to use hashing using Separate Chaning to find the element in constant time . This is different than than opening addresing which added the element to the next free slot in case of a collision , so we cann't keep track of the element in a constant . In sepate Chaning the elements when collision is found the element will be in the stored in the form of the linked list on the same slot . IN worst case if all the element give collision then the time complexity can be of O(n) . But chossing the proper hash key can give the result in constant time . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Sms Api
Does anyone knows any sms api which i can integrate with my own api? Reply asap.. its urgent... Sehaj IIT-Delhi Computer Science, 2nd sem -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Binary Tree Amazon
Claim: any given vertical line will start with a node.(This is obvious)
Divide this problem into 2 subparts.
1st: Finding the starting node of given line.
2nd : finding the required sum.
Let T be the tree and L be the given level.
For 1st part: Find the leftmost node of the given tree,T.This corresponds to
1st level.
Now let temp=L.
Traverse back from the leftmost tree to its parent(if
T.root is reached then start traversing towards right)
For each traverse decrease temp by 1.Keep on doing this
till temp is not equal to 1.
let temp. Call sum_find(temp)
For 2nd part : int sum=0;
int sum_find(node)
{if (node==null) return 0;
else return ( sum + sum_find(node.left.right) +
sum_find(node.right.left) )}
Cheers,
Sehaj Singh Kalra
IIT Delhi
B.Tech,Computer Science Department,
2nd Sem.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Fwd: [algogeeks] Binary Tree Amazon
HAD MISSED OUT SOPME THINGS IN PREVIOUS REPLY.
SORRY GUYS
hereby i rectify the mistakes:
Claim: any given vertical line will start with a node.(This is obvious)
Divide this problem into 2 subparts.
1st: Finding the starting node of given line.
2nd : finding the required sum.
Let T be the tree and L be the given level.
For 1st part: Find the leftmost node of the given tree,T.This corresponds to
1st level.
Now let temp=L.
Traverse back from the leftmost tree to its parent(if
T.root is reached then start traversing towards right)
For each traverse decrease temp by 1.Keep on doing this
till temp is not equal to 1.
Call sum_find(temp)
For 2nd part : int sum=0;
int sum_find(node)
{if (node==null) return 0;
else {sum+= node.data +
sum_find(node.left.right) + sum_find(node.right.left) )
return sum;}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Special Binary Tree Again
What is meant by : preceding P’s node in the in-order traversal of the tree ? On Mon, Feb 14, 2011 at 7:03 PM, bittu shashank7andr...@gmail.com wrote: You have a tree, in which each node has an additional pointer, P. P can either be NULL or point a node preceding P’s node in the in-order traversal of the tree. Write a program to check in a tree if each node’s P is assigned correctly. If not, make P null Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
