Re: [algogeeks] ThreeListSum
does any better solution exists than O(N^2logN)?? On Tue, Jan 11, 2011 at 2:56 AM, juver++ avpostni...@gmail.com wrote: There is no need to sort first two arrays. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anoop Chaurasiya CSE (2008-2012) NIT DGP -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] ThreeListSum
I think for unsorted lists, it will be O(n^3). On Tue, Jan 11, 2011 at 1:26 PM, juver++ avpostni...@gmail.com wrote: There is no need to sort first two arrays. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] ThreeListSum
can't u presort one of them in O(nlogn)...??? On Tue, Jan 11, 2011 at 5:05 AM, dinesh bansal bansal...@gmail.com wrote: I think for unsorted lists, it will be O(n^3). On Tue, Jan 11, 2011 at 1:26 PM, juver++ avpostni...@gmail.com wrote: There is no need to sort first two arrays. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anoop Chaurasiya CSE (2008-2012) NIT DGP -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] ThreeListSum
How big is the data set? In case the three arrays are quite large, probably they can be divided into smaller sets and then possible combinations can be given to separate threads like {A1,B1,C1}, {A1,B1,C2}...{A1,B2, C1}...where we make BST (one of AVL or RB Tree ) for set C1, C2 etc... and each set is handled in parallel maybe on different processors..may be use mapReduce.. Having said that, i am not sure if the question means such big sets..if no, then probably another optimization is to avoid the same sums like 2+3=5, 3+2=5 or 1+4=5...etc thereby if the search of the third number is once done should not be done again. Again, the question is do we need to do preprocessing to find out various possible non duplicate sums of first two arrays and then search for third in tree/hash table or a plain vanilla N2logN solution is expected. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jan 11, 2011 at 12:04 PM, Decipher ankurseth...@gmail.com wrote: Given three lists: A, B and C of length n each. Write a function which returns true if any 3 three numbers (1 from each list), sum up to zero. Else return false, if there is no such combination. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] ThreeListSum
sort two of the list and pick one number in C(unsorted) to find if there exists a pair with the sum. This can be done in linear time by maintaining two pointers. Hence O(n^2). -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Interview Question
Given a dictionary find out if given word can be made by two words in dictionary. For eg. given newspaper you have to find if it can be made by two words. (news and paper in this case). I cant think of anything but brute force. Thanks, Vikas -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
No, there is no B on the path A-C -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview Question
you can optimize BF newspaper first word you will search n then ne then new then news..and so onif at any point of time first word exist in dictionary then only see whether the word with the remaining characters exist in the dictionary or not. On Tue, Jan 11, 2011 at 5:57 PM, Vikas Singh vikas.sing...@gmail.comwrote: Given a dictionary find out if given word can be made by two words in dictionary. For eg. given newspaper you have to find if it can be made by two words. (news and paper in this case). I cant think of anything but brute force. Thanks, Vikas -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview Question
Use trie (or similar DS). For each word, try to find second part of the target in a linear time O(length). -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] ThreeListSum
This cannot be done in a linear time. Cause you have two Separate arrays. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] ThreeListSum
@above This cannot be done in a linear time. Cause you have two Separate arrays. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview Question
lalla..bruteforce na bako.. :P On Tue, Jan 11, 2011 at 6:07 PM, manoj lalavat manoj.lala...@gmail.comwrote: you can optimize BF newspaper first word you will search n then ne then new then news..and so onif at any point of time first word exist in dictionary then only see whether the word with the remaining characters exist in the dictionary or not. On Tue, Jan 11, 2011 at 5:57 PM, Vikas Singh vikas.sing...@gmail.comwrote: Given a dictionary find out if given word can be made by two words in dictionary. For eg. given newspaper you have to find if it can be made by two words. (news and paper in this case). I cant think of anything but brute force. Thanks, Vikas -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Interview Question
please ignore earlier message...it was supposed to be a private message.. On Tue, Jan 11, 2011 at 6:52 PM, Vikas Singh vikas.sing...@gmail.comwrote: lalla..bruteforce na bako.. :P On Tue, Jan 11, 2011 at 6:07 PM, manoj lalavat manoj.lala...@gmail.comwrote: you can optimize BF newspaper first word you will search n then ne then new then news..and so onif at any point of time first word exist in dictionary then only see whether the word with the remaining characters exist in the dictionary or not. On Tue, Jan 11, 2011 at 5:57 PM, Vikas Singh vikas.sing...@gmail.comwrote: Given a dictionary find out if given word can be made by two words in dictionary. For eg. given newspaper you have to find if it can be made by two words. (news and paper in this case). I cant think of anything but brute force. Thanks, Vikas -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Interview Question
Wouldn't that be O(n2) . what if n, ne, new, news, newsp etc all are valid words ? Cant it be optimized? On Tue, Jan 11, 2011 at 6:27 PM, juver++ avpostni...@gmail.com wrote: Use trie (or similar DS). For each word, try to find second part of the target in a linear time O(length). -- 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...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Amazon Question
1.Given two Sorted Array 1ts is size of X and 2nd is size of X+Y we have to merge 1st into 2nd array ..No Additional Memory ,Data Structure Allowed to Use...Write a Program to solve this problem explain time space complexity Regards Shashank -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: ThreeListSum
@Anoop: It can be done in O(n^2): Sort arrays B and C For i = 1 to n Do j = 1 k = n While( j = n and k = 1) If( A(i) + B(j) + C(k) 0 ) Then j = j + 1 Else if( A(i) + B(j) + C(k) 0 ) Then k = k - 1 Else Return TRUE End While Return FALSE The While loop is iterated at most 2N times for each i. Dave On Jan 11, 4:02 am, anoop chaurasiya anoopchaurasi...@gmail.com wrote: does any better solution exists than O(N^2logN)?? On Tue, Jan 11, 2011 at 2:56 AM, juver++ avpostni...@gmail.com wrote: There is no need to sort first two arrays. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anoop Chaurasiya CSE (2008-2012) NIT DGP -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question
2nd array contains elements upto first Y positions ?? On Tue, Jan 11, 2011 at 6:59 PM, bittu shashank7andr...@gmail.com wrote: 1.Given two Sorted Array 1ts is size of X and 2nd is size of X+Y we have to merge 1st into 2nd array ..No Additional Memory ,Data Structure Allowed to Use...Write a Program to solve this problem explain time space complexity Regards Shashank -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview Question
how abt this.. Pass1 = look whether words like n,ne,new,news.exist or not...store information in some array like n is not found so is ne but new is found and news is found so array will be like 0,0,1,1. Pass2 = do d same from from the end... r,er,per,aper,paper 0,0,1,0,1 Pass3 on first array whenever you find 1see index [len(newspaper) - (index of one in first array)] in second array...if its one we have words n so on On Tue, Jan 11, 2011 at 6:58 PM, Vikas Singh vikas.sing...@gmail.comwrote: Wouldn't that be O(n2) . what if n, ne, new, news, newsp etc all are valid words ? Cant it be optimized? On Tue, Jan 11, 2011 at 6:27 PM, juver++ avpostni...@gmail.com wrote: Use trie (or similar DS). For each word, try to find second part of the target in a linear time O(length). -- 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...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@juver, thanks for the explanation... but a few more queries... In my implementation, when I delete first element, why should we access all other elements? I should do that if the element i'm deleting is the current minimum... or is my understanding of get_min() totally wrong? I assumed get_min() should return the smallest item in the queue... On Jan 10, 11:20 pm, juver++ avpostni...@gmail.com wrote: About 2 stack implementation. Yes some operations can be O(n) as a separate estimation. But all other will be constant, cause we access elements at most twice. So for the sequence of M operations (pop,push,min) total complexity will be O(M), so the average cost of each operations is O(1). There are no two consecutive operations which are linear. But in your implementation, when you delete first element, you will access all remaining elements. So, it is O(n) for every operation of delete! Insert M numbers, then remove all elements with accessing to the min item - this will cost you O(M*M) for all, and O(M) in average! -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Question
There was the same question some days ago. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Intrerview
Does a path even exist from A to C if its a regular old binary tree? in a binary tree, you can only go from a parent to the children right? On Jan 11, 4:31 am, juver++ avpostni...@gmail.com wrote: No, there is no B on the path A-C -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
You are right about purpose of get_min(). Please post detailed pseudocode for each operation. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Queue: 1 2 3 4 1 5 6 7 1. After deleting from the head, you always should update minimum element for O(n). However, there is another way for queue modification, so the current min is accessed for O(1). This can be done using queue and initial elements (may be in a separate queue). -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Intrerview
The tree can be unrooted. Although, in any tree there is unique path from one node to another. Not only from the parent to childs. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview Question
What do you mean by N? If N - size of the dictionary. And L- maximum length of the words then above algo is O(N*L) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Question
@sunny...yes..it should occupy atleast position because Y is nothing but the no_of_elements that we wants to store into 2nd array..so rest(e.g.( ((x+y)-x) in this case ) of the elements initializes to their default value in case of it is 0 ..i think its okk Regrads Shashank -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Question
@juver++ so post your approach...i will also do the same..i posted the question here so that we can learn new way to solve or you can say best way to solve problem... One Problem Can be Solved My Many Ways But There is Only One Best Way to Solve It Regards Shashank -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question
best method i know is. start comparing elements from ends and put the larger at end and so on TC: O(X+Y) SC: O(1) On Tue, Jan 11, 2011 at 8:11 PM, bittu shashank7andr...@gmail.com wrote: @juver++ so post your approach...i will also do the same..i posted the question here so that we can learn new way to solve or you can say best way to solve problem... One Problem Can be Solved My Many Ways But There is Only One Best Way to Solve It Regards Shashank -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Question
Do merging of the array's tails, and place the result at the array's back. So its right side grows to the left. It's linear solution. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Interview Question
@Arpit Please explain your solution to me. As far as I understand, every alternate of two person should sum up equally. Which means every pair of (john, mary) has the same sum for john and mary. On Jan 11, 2:55 am, Arpit Sood soodfi...@gmail.com wrote: @jammy your code isnt working for the mentioned test case. One simple approach is to go greedy on the test data, but that wont always give the optimum answer. On Tue, Jan 11, 2011 at 1:11 PM, Arpit Sood soodfi...@gmail.com wrote: the output for first test case is wrong it should be (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 1 7 8 -- (Mary) 8 1 7 minimum cuts made are 2 On Tue, Jan 11, 2011 at 10:04 AM, Jammy xujiayiy...@gmail.com wrote: (a) it is intuitive to see we need to make a recursive function which takes the following arguments: 1) array, 2) start index, 3) length of the array, 4) a sentinel indicating if it is the first half or second half 5) a sum if it is the second half 6) number of cuts so far 7) a global minimal cuts So my recursive function looks something like this, void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum, int cut, int minV, vectorint res); and its wrapper just takes two arguments void cutMin(int *arr, int len); The idea is to differentiate the first half and second half. If it's the first half, you need make all possible cuts, and recursive call itself to get the second done. If it's the second half, you need calculate sums all the way to the end. Break out of the loop if it equals to the sum of the first part. And then recursively call itself to get the first half done. I hope my code explains the idea...Please report any bugs you find :) vectorint minVector; //storing the cuts void cutMin(int *arr, int len){ int cut=0, minV = INT_MAX; vectorint res; cutMinHelper(arr, 0, len, true, 0, cut, minV, res); if(minVINT_MAX){ coutminimal cut isminVendl; } } void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum, int cut, int minV, vectorint res){ if(isFirst startlen){ if(start==0) cut = 0; int sum = arr[start]; cut++; for(int i = start+1; i len; i++){ vectorint addOne = res; addOne.push_back(i-1); cutMinHelper(arr, i , len, !isFirst, sum, cut, minV, addOne); sum += arr[i]; } } if(!isFirst startlen){ int i, sum2 = 0; for(i = start; i len; i++){ sum2 += arr[i]; if(sum2 == sum){ break; } } if( i==len-1 sum2==sum) { if(cutminV){ minV = cut; minVector = res; } } if(ilen-1){ cut++; vectorint addOne = res; addOne.push_back(i); cutMinHelper(arr, i+1, len, !isFirst, 0, cut, minV, addOne); } } } (b) I didn't write the code, but I think the code would look like the first one with few modifications. On Jan 10, 1:08 pm, shady sinv...@gmail.com wrote: Given an array of numbers : a1, a2, a3. an (a) divide them in such a way that every alternate segment is given to two persons john and mary, equally the number of segments made should be minimum... eg for input 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7 segments : (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 --- (john) 1 7 8 -- (Mary) 8 1 7 minimum cuts made are 3 (b) Divide the numbers in such a way that both recieve same sum of numbers. If input 3 4 5 7 2 5 2 segments (john) 3 4 5 - (mary) 7 2 5 - (john) 2 minimum cuts are 2 -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Arpit Sood Some day you will see things my way. http://arpit-sood.blogspot.com -- Arpit Sood Some day you will see things my way.http://arpit-sood.blogspot.com -- 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...@googlegroups.com. For more
Re: [algogeeks] Interview Question
words and...so on... on dictionaries lookup is O(1) now think abt complexity... pass1 for (1 to N) example here N=strlen(newspaper) other passes are also same... On Tue, Jan 11, 2011 at 8:07 PM, juver++ avpostni...@gmail.com wrote: What do you mean by N? If N - size of the dictionary. And L- maximum length of the words then above algo is O(N*L) -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Manoj Lalavat -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Adobe Interview Question
oh, i considered that the sum of the total numbers for both john and mary to be equal after the whole division process. I am not considering pair wise sum. That's why for input 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7 segments should be: (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 1 7 8 -- (John) 8 1 7 minimum cuts made are 2 but if we consider pair wise cuts as done by you, output will be : (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 --- (john) 1 7 8 -- (Mary) 8 1 7 minimum cuts = 3 On Tue, Jan 11, 2011 at 8:38 PM, Jammy xujiayiy...@gmail.com wrote: @Arpit Please explain your solution to me. As far as I understand, every alternate of two person should sum up equally. Which means every pair of (john, mary) has the same sum for john and mary. On Jan 11, 2:55 am, Arpit Sood soodfi...@gmail.com wrote: @jammy your code isnt working for the mentioned test case. One simple approach is to go greedy on the test data, but that wont always give the optimum answer. On Tue, Jan 11, 2011 at 1:11 PM, Arpit Sood soodfi...@gmail.com wrote: the output for first test case is wrong it should be (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 1 7 8 -- (Mary) 8 1 7 minimum cuts made are 2 On Tue, Jan 11, 2011 at 10:04 AM, Jammy xujiayiy...@gmail.com wrote: (a) it is intuitive to see we need to make a recursive function which takes the following arguments: 1) array, 2) start index, 3) length of the array, 4) a sentinel indicating if it is the first half or second half 5) a sum if it is the second half 6) number of cuts so far 7) a global minimal cuts So my recursive function looks something like this, void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum, int cut, int minV, vectorint res); and its wrapper just takes two arguments void cutMin(int *arr, int len); The idea is to differentiate the first half and second half. If it's the first half, you need make all possible cuts, and recursive call itself to get the second done. If it's the second half, you need calculate sums all the way to the end. Break out of the loop if it equals to the sum of the first part. And then recursively call itself to get the first half done. I hope my code explains the idea...Please report any bugs you find :) vectorint minVector; //storing the cuts void cutMin(int *arr, int len){ int cut=0, minV = INT_MAX; vectorint res; cutMinHelper(arr, 0, len, true, 0, cut, minV, res); if(minVINT_MAX){ coutminimal cut isminVendl; } } void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum, int cut, int minV, vectorint res){ if(isFirst startlen){ if(start==0) cut = 0; int sum = arr[start]; cut++; for(int i = start+1; i len; i++){ vectorint addOne = res; addOne.push_back(i-1); cutMinHelper(arr, i , len, !isFirst, sum, cut, minV, addOne); sum += arr[i]; } } if(!isFirst startlen){ int i, sum2 = 0; for(i = start; i len; i++){ sum2 += arr[i]; if(sum2 == sum){ break; } } if( i==len-1 sum2==sum) { if(cutminV){ minV = cut; minVector = res; } } if(ilen-1){ cut++; vectorint addOne = res; addOne.push_back(i); cutMinHelper(arr, i+1, len, !isFirst, 0, cut, minV, addOne); } } } (b) I didn't write the code, but I think the code would look like the first one with few modifications. On Jan 10, 1:08 pm, shady sinv...@gmail.com wrote: Given an array of numbers : a1, a2, a3. an (a)divide them in such a way that every alternate segment is given to two persons john and mary, equally the number of segments made should be minimum... eg for input 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7 segments : (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 --- (john) 1 7 8 -- (Mary) 8 1 7 minimum cuts made are 3 (b)Divide the numbers in such a way that both recieve same sum of numbers. If input 3 4 5 7 2 5 2 segments (john) 3 4 5 - (mary) 7 2 5 - (john) 2 minimum cuts are 2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to
[algogeeks] twin pair
you will be given an input no. n u have to output nth twin pair.. for eg input 1 output(3,5) input 5 output (29,31) twin pair is a pair in which prime no. differ by 2.. (3,5) , (5,7) (11,13), (17,19) (29,31) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] amazon c questn
what is the wrong in the program? main() { char *p,*q; p=(char *)malloc(25); q=(char *)malloc(25); strcpy(p,amazon); strcpy(q,hyd); strcat(p,q); printf(%sp); } -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] amazon c questn
its correct, only a comma is missing in printf line: printf(%s,p); On Tue, Jan 11, 2011 at 10:14 PM, snehal jain learner@gmail.com wrote: what is the wrong in the program? main() { char *p,*q; p=(char *)malloc(25); q=(char *)malloc(25); strcpy(p,amazon); strcpy(q,hyd); strcat(p,q); printf(%sp); } -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Arpit Sood Some day you will see things my way. http://arpit-sood.blogspot.com -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] kth largest in tree
how to find kth largest in bst. u cnt use static/global variable and u cnt pass value of k to any function. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Interview Question
There are apparently more than one way to make the cuts(totally it'll still be three). The code only outputs first possible. On Jan 11, 10:42 am, Arpit Sood soodfi...@gmail.com wrote: oh, i considered that the sum of the total numbers for both john and mary to be equal after the whole division process. I am not considering pair wise sum. That's why for input 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7 segments should be: (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 1 7 8 -- (John) 8 1 7 minimum cuts made are 2 but if we consider pair wise cuts as done by you, output will be : (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 --- (john) 1 7 8 -- (Mary) 8 1 7 minimum cuts = 3 On Tue, Jan 11, 2011 at 8:38 PM, Jammy xujiayiy...@gmail.com wrote: @Arpit Please explain your solution to me. As far as I understand, every alternate of two person should sum up equally. Which means every pair of (john, mary) has the same sum for john and mary. On Jan 11, 2:55 am, Arpit Sood soodfi...@gmail.com wrote: @jammy your code isnt working for the mentioned test case. One simple approach is to go greedy on the test data, but that wont always give the optimum answer. On Tue, Jan 11, 2011 at 1:11 PM, Arpit Sood soodfi...@gmail.com wrote: the output for first test case is wrong it should be (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 1 7 8 -- (Mary) 8 1 7 minimum cuts made are 2 On Tue, Jan 11, 2011 at 10:04 AM, Jammy xujiayiy...@gmail.com wrote: (a) it is intuitive to see we need to make a recursive function which takes the following arguments: 1) array, 2) start index, 3) length of the array, 4) a sentinel indicating if it is the first half or second half 5) a sum if it is the second half 6) number of cuts so far 7) a global minimal cuts So my recursive function looks something like this, void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum, int cut, int minV, vectorint res); and its wrapper just takes two arguments void cutMin(int *arr, int len); The idea is to differentiate the first half and second half. If it's the first half, you need make all possible cuts, and recursive call itself to get the second done. If it's the second half, you need calculate sums all the way to the end. Break out of the loop if it equals to the sum of the first part. And then recursively call itself to get the first half done. I hope my code explains the idea...Please report any bugs you find :) vectorint minVector; //storing the cuts void cutMin(int *arr, int len){ int cut=0, minV = INT_MAX; vectorint res; cutMinHelper(arr, 0, len, true, 0, cut, minV, res); if(minVINT_MAX){ coutminimal cut isminVendl; } } void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum, int cut, int minV, vectorint res){ if(isFirst startlen){ if(start==0) cut = 0; int sum = arr[start]; cut++; for(int i = start+1; i len; i++){ vectorint addOne = res; addOne.push_back(i-1); cutMinHelper(arr, i , len, !isFirst, sum, cut, minV, addOne); sum += arr[i]; } } if(!isFirst startlen){ int i, sum2 = 0; for(i = start; i len; i++){ sum2 += arr[i]; if(sum2 == sum){ break; } } if( i==len-1 sum2==sum) { if(cutminV){ minV = cut; minVector = res; } } if(ilen-1){ cut++; vectorint addOne = res; addOne.push_back(i); cutMinHelper(arr, i+1, len, !isFirst, 0, cut, minV, addOne); } } } (b) I didn't write the code, but I think the code would look like the first one with few modifications. On Jan 10, 1:08 pm, shady sinv...@gmail.com wrote: Given an array of numbers : a1, a2, a3. an (a) divide them in such a way that every alternate segment is given to two persons john and mary, equally the number of segments made should be minimum... eg for input 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7 segments : (John)1 4 5 6 2 2 - (Mary)2 2 4 5 6 1 --- (john) 1 7 8 -- (Mary) 8 1 7 minimum cuts made are 3 (b) Divide the numbers in such a way that both recieve same sum of numbers.
Re: [algogeeks] amazon c questn
sorry that was typing error.. anything else wrong except that? as it seems correct to me... On Tue, Jan 11, 2011 at 10:31 PM, Arpit Sood soodfi...@gmail.com wrote: its correct, only a comma is missing in printf line: printf(%s,p); On Tue, Jan 11, 2011 at 10:14 PM, snehal jain learner@gmail.comwrote: what is the wrong in the program? main() { char *p,*q; p=(char *)malloc(25); q=(char *)malloc(25); strcpy(p,amazon); strcpy(q,hyd); strcat(p,q); printf(%sp); } -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Arpit Sood Some day you will see things my way. http://arpit-sood.blogspot.com -- 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...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] amazon c questn
amazom needs 7*4=28 bytes -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: twin pair
as all prime no. greater than 3 are of the form 6n+1 or 6n-1 so start checking for all these numbers and if they both are prime then they will make pair count the pair no. as well as u move on Ankit On Jan 11, 9:23 pm, snehal jain learner@gmail.com wrote: you will be given an input no. n u have to output nth twin pair.. for eg input 1 output(3,5) input 5 output (29,31) twin pair is a pair in which prime no. differ by 2.. (3,5) , (5,7) (11,13), (17,19) (29,31) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] amazon c questn
no nothing is wrong i have run it on my computer On Tue, Jan 11, 2011 at 9:09 AM, snehal jain learner@gmail.com wrote: sorry that was typing error.. anything else wrong except that? as it seems correct to me... On Tue, Jan 11, 2011 at 10:31 PM, Arpit Sood soodfi...@gmail.com wrote: its correct, only a comma is missing in printf line: printf(%s,p); On Tue, Jan 11, 2011 at 10:14 PM, snehal jain learner@gmail.comwrote: what is the wrong in the program? main() { char *p,*q; p=(char *)malloc(25); q=(char *)malloc(25); strcpy(p,amazon); strcpy(q,hyd); strcat(p,q); printf(%sp); } -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Arpit Sood Some day you will see things my way. http://arpit-sood.blogspot.com -- 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...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- UTKARSH SRIVATAV CSE-3 B-TECH 2nd YEAR -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] amazon c questn
technically, malloc(25*sizeof(char)) or so would have been right ... here malloc(25) assigns just 25 bytes as against the requirement... On Tue, Jan 11, 2011 at 11:10 PM, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: no nothing is wrong i have run it on my computer On Tue, Jan 11, 2011 at 9:09 AM, snehal jain learner@gmail.comwrote: sorry that was typing error.. anything else wrong except that? as it seems correct to me... On Tue, Jan 11, 2011 at 10:31 PM, Arpit Sood soodfi...@gmail.com wrote: its correct, only a comma is missing in printf line: printf(%s,p); On Tue, Jan 11, 2011 at 10:14 PM, snehal jain learner@gmail.comwrote: what is the wrong in the program? main() { char *p,*q; p=(char *)malloc(25); q=(char *)malloc(25); strcpy(p,amazon); strcpy(q,hyd); strcat(p,q); printf(%sp); } -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Arpit Sood Some day you will see things my way. http://arpit-sood.blogspot.com -- 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...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- UTKARSH SRIVATAV CSE-3 B-TECH 2nd YEAR -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Best, T Anand Karthik, Contact number: +91-9571552652 -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Ok so here's the pseudocode... class MyQueue { int? currentMinVal; //nullable LinkedListint contents; public void MyQueue() { contents = new LinkedListint(); currentMinVal = null; } //the regular implementations of insert and delete are below... insert_rear, delete_front can be just as easily implemented as my contents are in a linked list public void Insert(int item) { contents.AddLastint(item); //add item to the linked list //set the current min... O(1) operation if(currentMinVal == null || currentMinVal.Value item) currentMinVal = item; } public int Delete() { if(!contents.IsEmpty) { int itemToreturn = contents.First.Value; contents.RemoveFirst(); //some method of linked list that removes specified element from the linked list and adjusts head and tail pointers if(itemToRetun == currentMinVal) // check if the item you remove is the current minimum... RecomputeMinValue(); //O(n) operation to set the new minimum return itemToReturn; } else throw new InvalidOperationException(); } public int? get_min() { return currentMinVal; } } For this, it's not true that for all deletes, I need to do a O(n) operation O(n) operation on delete is needed only if the currently deleted item is the current min... for Queue: 1 2 3 4 1 5 6 7 1, the linked list will have 1 -7-6-5- 1-4-3-2-1 currentMinVal = 1. on first delete, since 1 is going to be deleted, currentMin will be once again computed O(n)... its once again 1 on second delete, the item to be deleted is 2... this is not the current min... so we don't do a O(n) traversal of the list to get the new currentMin... On Jan 11, 6:35 am, juver++ avpostni...@gmail.com wrote: Queue: 1 2 3 4 1 5 6 7 1. After deleting from the head, you always should update minimum element for O(n). However, there is another way for queue modification, so the current min is accessed for O(1). This can be done using queue and initial elements (may be in a separate queue). -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
traverse inorder for k steps.. Regards Aviral http://coders-stop.blogspot.com/ On Jan 11, 10:03 pm, snehal jain learner@gmail.com wrote: how to find kth largest in bst. u cnt use static/global variable and u cnt pass value of k to any function. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: twin pair
Use sieve algorithm for generating the primes and then check for the condition of twin numbers... Regards Aviral http://coders-stop.blogspot.com/ On Jan 11, 10:20 pm, ankit agarwal ankit.agarwal.n...@gmail.com wrote: as all prime no. greater than 3 are of the form 6n+1 or 6n-1 so start checking for all these numbers and if they both are prime then they will make pair count the pair no. as well as u move on Ankit On Jan 11, 9:23 pm, snehal jain learner@gmail.com wrote: you will be given an input no. n u have to output nth twin pair.. for eg input 1 output(3,5) input 5 output (29,31) twin pair is a pair in which prime no. differ by 2.. (3,5) , (5,7) (11,13), (17,19) (29,31) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
And what about the 1 2 3 1 1 1 1 1 1 1 3 5 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1. Your algo is inefficient in all cases. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview Question
If you represent dictionary as a hash table, lookup costs you O(L) at least! Cause you need to calculate hash for the string. But for the trie it is O(L) in a worst 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...@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] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
The best way to check your algo on practice, generate a very big test case with many operations. Check the time and amount of accesses for each element. In your case you have O(n) for the operation on average. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] amazon c questn
You are partially wrong. There is a right way to define the memeory allocation - malloc(25*sizeof(char)). But size of char is always 1 on all platforms. So malloc(25*sizeof(char)) == malloc(25). The last is not the convenient way to work with. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
juver++, If we do inorder traversal (right_child -- parent -- left_child) and output kth element then we are done. I didn't understand the 2nd point, why we need to modify the bst (store clind count at each node). Am I missing anything here? Please advise. On Jan 12, 12:04 am, juver++ avpostni...@gmail.com wrote: 1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
juver++, If we do inorder traversal (right_child -- parent -- left_child) and output kth element then we are done. I didn't understand the 2nd point, why we need to modify the bst (store clind count at each node). Am I missing anything here? Please advise. On Jan 12, 12:04 am, juver++ avpostni...@gmail.com wrote: 1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
juver++, If we do inorder traversal (right_child -- parent -- left_child) and output kth element then we are done. I didn't understand the 2nd point, why we need to modify the bst (store child count at each node). Am I missing anything here? Please advise. On Jan 12, 12:04 am, juver++ avpostni...@gmail.com wrote: 1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
juver++, If we do inorder traversal (right_child -- parent -- left_child) and output kth element then we are done. I didn't understand the 2nd point, why we need to modify the bst (store child count at each node). Am I missing anything here? Please advise. On Jan 12, 12:04 am, juver++ avpostni...@gmail.com wrote: 1. Make inorder traversal and output k-th element. 2. Store in each node additional variable - amount of nodes in the subtree rooted at node. Process the query in O(height) -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon questions
For 2nd question (probability): Looks like one data is missing for C. If I assume C can shoot 8 out of 10. times then: P(A) = 4/5 P(B)=6/7 P(C)=8/10 Required Probability should be = P(A) * P(B) + P(B) * P(C) + P(A) * P(C) On Jan 11, 9:58 pm, snehal jain learner@gmail.com wrote: 1. what is valid in cpp char *cp; const char* cpp; 1. cpp=cp 2. cp=cpp 2 there r 3 ppl A B C A can shoot the target 4 out of 5 times B can shoot 6 out of 7 times and C can shoot 8 out of times. 2 people r selected at random. then wat is the probability of hitting the target? -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
If modification of the tree is allowed then each query can be solved in O(height). find(node, k) { if (count(node-left) + 1 == k) result = node; else if (count(node-left) k) result = find(node-right, k - count(node-left) - 1); return find(node-left, k); } -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
That's right. Tks. But looks like above algorithm is for kth smallest. Not kth largest. That's why I mentioned inorder traversal as right_child -- parent -- left_child. Not usual way: left_child -- parent -- right_child On Jan 12, 1:08 am, juver++ avpostni...@gmail.com wrote: If modification of the tree is allowed then each query can be solved in O(height). find(node, k) { if (count(node-left) + 1 == k) result = node; else if (count(node-left) k) result = find(node-right, k - count(node-left) - 1); return find(node-left, k); } -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: kth largest in tree
It doesn't matter. Algo can be adopted for both versions. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon questions
anuragh assume each can shoot the target everytime... P(A) = 1 P(B) = 1 P(C) = 1 per your logic, the probability that the target will be hit is 3 actually, it should have only been 2 as we're going to pick only 2 people out of 3 to shoot... I think you should factor in the probability that A or B or C will be picked... There are 3C2 ways to pick 2 cards out of 3... Since its purely random, each card has 2/3rd chance that it's picked... so if you factor in the probability, the answer is required probablilty = P(A) * 2/3 + P(B) * 2/3 + P(C) * 2/3 On Jan 11, 12:06 pm, anurag.singh anurag.x.si...@gmail.com wrote: For 2nd question (probability): Looks like one data is missing for C. If I assume C can shoot 8 out of 10. times then: P(A) = 4/5 P(B)=6/7 P(C)=8/10 Required Probability should be = P(A) * P(B) + P(B) * P(C) + P(A) * P(C) On Jan 11, 9:58 pm, snehal jain learner@gmail.com wrote: 1. what is valid in cpp char *cp; const char* cpp; 1. cpp=cp 2. cp=cpp 2 there r 3 ppl A B C A can shoot the target 4 out of 5 times B can shoot 6 out of 7 times and C can shoot 8 out of times. 2 people r selected at random. then wat is the probability of hitting the target? -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] MICROSOFT IDC
Find the intersection of two unsorted singly linked list in O(1) space and less than O(n^2) complexity. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MICROSOFT IDC
sort both linked lists using non-recursive merge sort: Time: O(nlogn), Space: O(1) Then while both lists are not null loop if list1-data == list2-data then print/store list1-data move list1 pointer one node further move list2 pointer pne node further else if list1-data list2-data then move list1 pointer one node further else move list2 pointer one node further done On Jan 12, 2:23 am, Aniket aniket...@gmail.com wrote: Find the intersection of two unsorted singly linked list in O(1) space and less than O(n^2) complexity. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MICROSOFT IDC
sort in-place and check. O(nlogn) time and O(1) space. On Wed, Jan 12, 2011 at 2:53 AM, Aniket aniket...@gmail.com wrote: Find the intersection of two unsorted singly linked list in O(1) space and less than O(n^2) complexity. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
Based on various comments I think folks do not consider B in the path from A to C which leads to the LCA solution. @SVIX, one can implement the tree with a parent pointer in each node but that doesn't matter in the general case. What you are essentially saying is: consider the tree to be a directed graph with parent - child link to be one way, if that were the case we cannot even reach from A to C so that is out of question that's why we consider it to be a both way link. Now given this one can always argue that B lies in the path from A to C! i.e. A-D-M-B-M-C so here we can, perhaps, define a shortest path from A to C and it has to go through LCA. @all guys, one request please use @XYZ in case you are referring to a particular post by the person XYZ unless it is a general comment. just to avoid confusion. On Tue, Jan 11, 2011 at 8:06 PM, juver++ avpostni...@gmail.com wrote: The tree can be unrooted. Although, in any tree there is unique path from one node to another. Not only from the parent to childs. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] SPOJ PROBLEM-pour1
i tried solving this prob... http://www.spoj.pl/problems/POUR1/ i tried using BFS...getting TLE in judge.. pl suggest some optimisation or better solution.. Thanks in advance.. Code: http://ideone.com/qIgcU -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Modular Arithmetic
Somehelp with (a/b)modm expression. http://en.wikipedia.org/wiki/Modular_arithmetic i visited this link but found only for addition,subtraction and multiplication. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon questions
it is (p(a)p(b)+p(b)p(c)+p(c)p(a))/3 On Jan 12, 1:51 am, SVIX saivivekh.swaminat...@gmail.com wrote: anuragh assume each can shoot the target everytime... P(A) = 1 P(B) = 1 P(C) = 1 per your logic, the probability that the target will be hit is 3 actually, it should have only been 2 as we're going to pick only 2 people out of 3 to shoot... I think you should factor in the probability that A or B or C will be picked... There are 3C2 ways to pick 2 cards out of 3... Since its purely random, each card has 2/3rd chance that it's picked... so if you factor in the probability, the answer is required probablilty = P(A) * 2/3 + P(B) * 2/3 + P(C) * 2/3 On Jan 11, 12:06 pm, anurag.singh anurag.x.si...@gmail.com wrote: For 2nd question (probability): Looks like one data is missing for C. If I assume C can shoot 8 out of 10. times then: P(A) = 4/5 P(B)=6/7 P(C)=8/10 Required Probability should be = P(A) * P(B) + P(B) * P(C) + P(A) * P(C) On Jan 11, 9:58 pm, snehal jain learner@gmail.com wrote: 1. what is valid in cpp char *cp; const char* cpp; 1. cpp=cp 2. cp=cpp 2 there r 3 ppl A B C A can shoot the target 4 out of 5 times B can shoot 6 out of 7 times and C can shoot 8 out of times. 2 people r selected at random. then wat is the probability of hitting the target? -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: amazon c questn
p= (char*)malloc(25); KK: p should be checked for null after this statment q = (char*)malloc(25); KK: q should be checked for null after this statement -Kiran On Jan 11, 9:44 pm, snehal jain learner@gmail.com wrote: what is the wrong in the program? main() { char *p,*q; p=(char *)malloc(25); q=(char *)malloc(25); strcpy(p,amazon); strcpy(q,hyd); strcat(p,q); printf(%sp); } -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview Question
I agree with the trie solution. But now how do you generalise it for K. I mean a word can be made from k other words. On Wed, Jan 12, 2011 at 12:53 AM, juver++ avpostni...@gmail.com wrote: If you represent dictionary as a hash table, lookup costs you O(L) at least! Cause you need to calculate hash for the string. But for the trie it is O(L) in a worst 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...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: amazon questions
(1-(1-p(a))(1-p(b)) + 1-(1-p(b))(1-p(c)) + 1- (1-p(a))(1-p(c)))/3 On 1月12日, 上午9时36分, ankit agarwal ankit.agarwal.n...@gmail.com wrote: it is (p(a)p(b)+p(b)p(c)+p(c)p(a))/3 On Jan 12, 1:51 am, SVIX saivivekh.swaminat...@gmail.com wrote: anuragh assume each can shoot the target everytime... P(A) = 1 P(B) = 1 P(C) = 1 per your logic, the probability that the target will be hit is 3 actually, it should have only been 2 as we're going to pick only 2 people out of 3 to shoot... I think you should factor in the probability that A or B or C will be picked... There are 3C2 ways to pick 2 cards out of 3... Since its purely random, each card has 2/3rd chance that it's picked... so if you factor in the probability, the answer is required probablilty = P(A) * 2/3 + P(B) * 2/3 + P(C) * 2/3 On Jan 11, 12:06 pm, anurag.singh anurag.x.si...@gmail.com wrote: For 2nd question (probability): Looks like one data is missing for C. If I assume C can shoot 8 out of 10. times then: P(A) = 4/5 P(B)=6/7 P(C)=8/10 Required Probability should be = P(A) * P(B) + P(B) * P(C) + P(A) * P(C) On Jan 11, 9:58 pm, snehal jain learner@gmail.com wrote: 1. what is valid in cpp char *cp; const char* cpp; 1. cpp=cp 2. cp=cpp 2 there r 3 ppl A B C A can shoot the target 4 out of 5 times B can shoot 6 out of 7 times and C can shoot 8 out of times. 2 people r selected at random. then wat is the probability of hitting the target?- 隐藏被引用文字 - - 显示引用的文字 - -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Symmetric matrix
I have a symmetric matrix. I am wondering what would be the best data structure to store such a matrix? How many elements do I need to store for a nxn matrix? Thanks in advance for the help. - Azhar. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Symmetric matrix
i can tell 1 thing tht only (((n*n)-n)/2) +n elements are unique and the (((n*n)-n)/2) term is the one shoes the no of repeated elements and n represents the diagonal elements hope this gives some usefull info (i havent gone through any book nor do i guarantee optimal or best memory usage) On Wed, Jan 12, 2011 at 9:50 AM, Azhar Hussain azhar...@gmail.com wrote: I have a symmetric matrix. I am wondering what would be the best data structure to store such a matrix? How many elements do I need to store for a nxn matrix? Thanks in advance for the help. - Azhar. -- 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...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ehab Abdul Rahman Shariff -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview Question
This problem has DP solution in O(n^2) I think. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] lock and unlock procedures in a N-ary Trees
Hi Write a procedure for LOCK(pointer to x) in a N-ary Tree , satisfying the following: 1. nx(x is a descendant of n) and n is locked, then LOCK(x) should return false else true. 2. ny(n is a descendant of y) and n is locked, then LOCK(y) should return false else true. Similarly for UNLOCK, one solution is: to traverse through the subtree of the pointer to which lock is to be applied to chk condition 2, but is there any solution better then (O(n)), check 1 can be easily tracked by using parent pointer -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: lock and unlock procedures in a N-ary Trees
Thanks I got the solution. Sorry for repeat..:) If anyone is interested in the solution, please read the above carefully !!! :) Regards Sundi On Jan 12, 12:33 pm, Sundi sundi...@gmail.com wrote: Hi Write a procedure for LOCK(pointer to x) in a N-ary Tree , satisfying the following: 1. nx(x is a descendant of n) and n is locked, then LOCK(x) should return false else true. 2. ny(n is a descendant of y) and n is locked, then LOCK(y) should return false else true. Similarly for UNLOCK, one solution is: to traverse through the subtree of the pointer to which lock is to be applied to chk condition 2, but is there any solution better then (O(n)), check 1 can be easily tracked by using parent pointer -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.