Re: [algogeeks] random function
read modeling and simulation book it has a great discussion on random number generartion and testing On Mon, Dec 27, 2010 at 11:52 AM, 王大东 dadongk...@gmail.com wrote: Linear congruential sequence maybe a simple approach. A[n]=(a*A[n-1]+b)%c, But it's another problem how to chose a,b,c. On Sat, Dec 25, 2010 at 1:05 PM, Puneet Ginoria punnu.gino...@gmail.comwrote: volume 2 , chapter 3 On Fri, Dec 24, 2010 at 11:13 AM, Puneet Ginoria punnu.gino...@gmail.com wrote: There is a book called The art of computer programming by donald knuth. He had discussed the random function in great detail. On Tue, Dec 21, 2010 at 8:06 PM, snehal jain learner@gmail.comwrote: How do you write your own random 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.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. -- What are we to be? -- 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. -- DIPANKAR DUTTA M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in email%3adipan...@iitr.ernet.in -- 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: 1s and 0s
your first approach is totally correct. On Dec 22, 12:36 pm, juver++ avpostni...@gmail.com wrote: Use bits manipulation tricks. 1. There is a way to remove a group of consecutive 1's from the right: A = n (n + 1). Then check if A==0 then OK. 2. Second approach: B=n+1, check if B (B-1) (this checks if B is a power of 2, so it contains only 1 set bit) is zero then OK. -- 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: Interview question
Program is incorrect. Why does it output the following answer: point at (3,5 )size is 8??? -- 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
interested ppl can read ths link for stream algorithms...
http://www.americanscientist.org/issues/pub/the-britney-spears-problem/1
Mohit
On Sun, Dec 26, 2010 at 7:49 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
may be we can assume that klog(n)
else i dont see a way out than hashing , because that is the only
thing less that log(n).
On Sun, Dec 26, 2010 at 6:37 PM, mohit ranjan shoonya.mo...@gmail.com
wrote:
hmm..
ok let me try to explain my point...
suppose in stream, the rate is 1 integer/k time, so within k time we need
to
process that number and be ready for next number.
Now when stream has just started, n is small so log(n) is OK, but a time
will come when log(n)k and then numbers will start accumulating
Mohit
On Sun, Dec 26, 2010 at 6:25 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
with BST we can query the occurence in lg (n)
On Sun, Dec 26, 2010 at 5:19 PM, mohit ranjan shoonya.mo...@gmail.com
wrote:
@Radha
With BST, the time taken to search a node depends on size (n), which
will
keep on increasing as stream grows long, whereas we need to calculate
freq
within the fixed time interval for all numbers...
any better solution ?
Mohit
On Sun, Dec 26, 2010 at 4:48 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
An Augmented and self Balancin Binary Search Tree Will suffice
Tree {
int element;
int occurence;
}
when u have the element in the BST increment the occurence
Else create a New node
Total Complexity is O(n lgn )
Correct me if am wrong
lg n -- for finding the previous occurence of the number
On Sun, Dec 26, 2010 at 4:39 PM, bittu shashank7andr...@gmail.com
wrote:
You are provided with a stream of numbers, design a data structure
to
store the numbers in the stream along with their no. of
occurrences.
Regards
Shashank Mani
--
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.
--
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.
--
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.
--
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: convert binary matrix to zero matrix
when you are talking abt starting from 1 that means that array is 1 based , right ? Right. 111 000 000 Up-left element: 1 Choice 3: 0 (number of 0's on the first row) + 1 (number of 1's on the first column) = 1 Choice 4: 3 (number of 1's on the first row) + 2 (number of 0's on the first column) = 5 Best choice: 3, with 1 toggle. (toggle the first row) 011 100 100 Up-left element: 0 Choice 1: 1 (number of 0's on the first row) + 1 (number of 0's on the first column) = 2 Choice 2: 2 (number of 1's on the first row) + 2 (number of 1's on the first column) = 4 Best choice: 1, with 2 toggles. (toggle the first row and first column) Clarification: In choice 1 and 2, the up-left element is counted twice, ie. 1. number of 0's on the first row and (number of 0's on the) first column 2. number of 1's on the first row and (number of 1's on the) first column The idea is simple: 1) toggle the first row or not? When 1) is decided and applied, 2) toggle columns to make first row all 0. -- the number of 1's in the first row (original or inverted) 3) toggle rows to make first column 0.-- the number of 1's in the first column (after step 2) On 2010-12-25 17:31, Ankur wrote: when you are talking abt starting from 1 that means that array is 1 based , right ? and how did you get the steps calculated. please can you explain, once more take this example, a trivial but albeit will help me explain. 111 000 000 and 011 100 100 if it is feasible for you to reply . On Dec 8, 1:45 pm, Terencetechnic@gmail.com wrote: As Amir pointed out: convert the first row and first column to all zeros In details: 1. choose operations on first row and first column to make up-left element 0. * There are 2 cases, 2 choices for each case: 1. If the up-left element is 0, then 1. toggle both first row and first column, or 2. leave both untouched. 2. If the up-left element is 1, then 3. toggle first row, or 4. toggle first column 2. for each 1 on the first row, toggle the corresponding column, to change first row to all 0s. 3. for each 1 on the first column, toggle the corresponding row, to change first column to all 0s. After above 3 steps, if there are still some 1's, no solution is possible. Otherwise, compare the 2 choice, and choose the minimum steps. --- In fact, we can directly calculate the number of steps in choice a)-d): 1. number of 0's on the first row and first column 2. number of 1's on the first row and first column 3. number of 0's on the first row + number of 1's on the first column 4. number of 1's on the first row + number of 0's on the first column And if we denote the j'th element on i'th row as M[i,j] (start from 1), then the problem have valid solution if and only if: for each element M[i,j], M[1,1]+M[1,j]+M[i,1]+M[i,j] is even. On 2010-12-7 22:59, Prims wrote: Hello Rajan Suppose we have the following matrix 1 1 0 0 If a toggle operation performed on first row, it will change all 1s to 0s and 0s to 1s which result in the followig matrix 0 0 0 0 It is zero matrix and the result. Similarly if a toggle operation is performed on column, it will change all 1s to 0s and 0s to 1s in that particular column. Say you have a function toggle(int , Type) which does the toggle operation. where number is the number of row or column Type can be of Type.Row or Type.Column. Hope it is clear -Prims On Dec 7, 5:33 pm, rajan goswamirajan.goswam...@gmail.comwrote: @Prims Can you please elaborate the problem in detail... What do you mean by toggling row and column... 1 Interchanging a row with some column ? 2 Changing 0s to 1s and 1s to 0s of that row ? or Some thing else ? In both options mentioned above .. no of 1s present in a matrix can not be changed to 0s in any ways ... Please explain the step that can be performed on given matrix. regards, Rajan. On Mon, Dec 6, 2010 at 11:55 PM, Primstopcode...@gmail.comwrote: Amir Could you please explain with an example in detail? On Dec 6, 7:02 pm, Amir hossein Shahriari amir.hossein.shahri...@gmail.comwrote: actually a greedy approach for this problem exists: just convert the first row and first column to all zeros if after this step matrix is not a complete zero matrix then it's impossible to make it On Sun, Dec 5, 2010 at 9:10 AM, Primstopcode...@gmail.comwrote: How do i convert a binary matrix(containing only 0s and 1s) to a complete zero matrix? Only operations allowed are u can toggle a whole row or a whole column. The conversion has to be done in minimum number of steps (a step is defined as toggling a
Re: [algogeeks] 10 Most Frequent Search Text
hey... what's about the storage managment ? the search text may not be a fixed length string.. is implementation of a node is fessible? one alternative solution may be associate a hash table along with this. but again the problem with collision ,, to avoid collision u can use perfect hashing with universal hash function. you can also use an alternative solution hash function and priority queue using MAX heap... On Mon, Dec 27, 2010 at 2:20 AM, Chi i...@chihoang.de wrote: A trie is a binary tree with it nodes has as many leafs as is suitable. A binary tree has only 2 leafs per nodes. In a trie it happens that a node doesn't contain any leafs. This happens over many nodes. This is considerable a waste of space. A radix-trie tries to eliminate this empty nodes by compressing them into 1 node. The difference between a radix-trie and suffix-trie is that a suffix-trie can solve text-based problems. A radix-trie is good to store a dictionnary and search for words. Or associative arrays. Or ip addresses. Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). This doesn't seem like an advantage, since normally k ≥ log n, but in a balanced tree every comparison is a string comparison requiring O(k) worst-case time, many of which are slow in practice due to long common prefixes. In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons and require many fewer nodes. K=key n=string I have a written a kart-trie in php: https://sourceforge.net/projects/kart-trie The only difference to a radix-trie is that the decision to branch either left or right is used with a key of 32-bit. - Ursprüngliche Mitteilung - @Chi: Would you please explain the process in a little bit more details? It will be helpful. Is Trie and Radix-Trie same? -- 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. -- 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. -- DIPANKAR DUTTA M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in email%3adipan...@iitr.ernet.in -- 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: Simulation algo
Hello , Sorry :( Chi i can not help you , i don't know that algorithm . All the best . On 26 déc, 20:10, Chi i...@chihoang.de wrote: Hi, I'm looking for the fleury or the hierholzer algorithm in php, c or fleury. Do u can help? Perhaps u can take a look at bin-packing algorithm and monte-carlo simulation. If u want optimize the throughput of a referent u have to calculate the costs first. Or what about dynamic-programming? Can u calculate the lower bounds of a tsp? That I need also to know. Best regards, Chi - Ursprüngliche Mitteilung - Hello , discret event simulation is description of the behavior of a referent (real or virtual) as a digital model . On 25 déc, 22:20, Chi i...@chihoang.de wrote: Aco is for optimization of tsp or chinese postman. It is related to find a minimum spanning tree in an undirected weighted graph. What do u mean by discret event simulation? - Ursprüngliche Mitteilung - Hello , any one have a documentation or code source related to simulation send to me , please . All the best . On 25 déc, 19:12, Glauben glauben...@gmail.com wrote: Hello , Thank you very much Chi and pschaus for your answers , i know that The Ant-Colony-Optimization is related to computer science simulation but to Discrete Event Simulation i don't know any way i will study it . All the best . On 24 déc, 11:44, pschaus psch...@gmail.com wrote: I don't think Ant-Colony-Optimization is related to Discrete Event Simulation. If you are looking for a framework to model DES, you may have look at SimPyhttp://simpy.sourceforge.net/ Cheers, Pierre On 24 déc, 04:29, Chi i...@chihoang.de wrote: Ant-Colony-Optimization - Ursprüngliche Mitteilung - Hello, I'm looking for an algorithm of computer science simulation and specifically the discrete simulation of any model. Please All the best. -- 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 athttp://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 athttp://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 athttp://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] 10 Most Frequent Search Text
Thank u for reading. My kart-trie is between a radix-trie and suffix-trie because a radix-trie can also have as many leafs as suitable and a suffix-trie also. A kart-trie has exactly 2 leafs per node. Correct me if I'm wrong! - Ursprüngliche Mitteilung - hey... what's about the storage managment ? the search text may not be a fixed length string.. is implementation of a node is fessible? one alternative solution may be associate a hash table along with this. but again the problem with collision ,, to avoid collision u can use perfect hashing with universal hash function. you can also use an alternative solution hash function and priority queue using MAX heap... On Mon, Dec 27, 2010 at 2:20 AM, Chi i...@chihoang.de wrote: A trie is a binary tree with it nodes has as many leafs as is suitable. A binary tree has only 2 leafs per nodes. In a trie it happens that a node doesn't contain any leafs. This happens over many nodes. This is considerable a waste of space. A radix-trie tries to eliminate this empty nodes by compressing them into 1 node. The difference between a radix-trie and suffix-trie is that a suffix-trie can solve text-based problems. A radix-trie is good to store a dictionnary and search for words. Or associative arrays. Or ip addresses. Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). This doesn't seem like an advantage, since normally k ≥ log n, but in a balanced tree every comparison is a string comparison requiring O(k) worst-case time, many of which are slow in practice due to long common prefixes. In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons and require many fewer nodes. K=key n=string I have a written a kart-trie in php: https://sourceforge.net/projects/kart-trie The only difference to a radix-trie is that the decision to branch either left or right is used with a key of 32-bit. - Ursprüngliche Mitteilung - @Chi: Would you please explain the process in a little bit more details? It will be helpful. Is Trie and Radix-Trie same? -- 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. -- 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. -- DIPANKAR DUTTA M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in email%3adipan...@iitr.ernet.in -- 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. -- 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] 10 Most Frequent Search Text
This can be done in O(n ) with O(1) space compexity . This problem can be reduced to finding the kth smallest number in an unordered collection . There exists an O(n) algo for this . For finding the 10th most frequent number we should find (n-10)th smallest number . Once found by doing an linear scan we can finf max 10 elements . If we want to preserve the order of 10 max elements we can sort it constant time . -Thanks Regards K.Abhinav Raghunandan Department of Computer Science Engg, IIT Madras On Mon, Dec 27, 2010 at 10:01 PM, DIPANKAR DUTTA dutta.dipanka...@gmail.com wrote: hey... what's about the storage managment ? the search text may not be a fixed length string.. is implementation of a node is fessible? one alternative solution may be associate a hash table along with this. but again the problem with collision ,, to avoid collision u can use perfect hashing with universal hash function. you can also use an alternative solution hash function and priority queue using MAX heap... On Mon, Dec 27, 2010 at 2:20 AM, Chi i...@chihoang.de wrote: A trie is a binary tree with it nodes has as many leafs as is suitable. A binary tree has only 2 leafs per nodes. In a trie it happens that a node doesn't contain any leafs. This happens over many nodes. This is considerable a waste of space. A radix-trie tries to eliminate this empty nodes by compressing them into 1 node. The difference between a radix-trie and suffix-trie is that a suffix-trie can solve text-based problems. A radix-trie is good to store a dictionnary and search for words. Or associative arrays. Or ip addresses. Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). This doesn't seem like an advantage, since normally k ≥ log n, but in a balanced tree every comparison is a string comparison requiring O(k) worst-case time, many of which are slow in practice due to long common prefixes. In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons and require many fewer nodes. K=key n=string I have a written a kart-trie in php: https://sourceforge.net/projects/kart-trie The only difference to a radix-trie is that the decision to branch either left or right is used with a key of 32-bit. - Ursprüngliche Mitteilung - @Chi: Would you please explain the process in a little bit more details? It will be helpful. Is Trie and Radix-Trie same? -- 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. -- 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. -- DIPANKAR DUTTA M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in email%3adipan...@iitr.ernet.in -- 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] Re: Pythagorean triples
http://tech-queries.blogspot.com/2010/12/find-pythagorean-triples-in-unsorted.html Regards, Akash Agrawal http://tech-queries.blogspot.com/ On Mon, Dec 20, 2010 at 8:12 PM, Dave dave_and_da...@juno.com wrote: Unless sorting the array is forbidden, sort it and then use the obvious O(n^2) algorithm. This can be done with only O(1) extra space. If O(n) extra space is available, either use it to copy and sort the original array, or use it as a hash table, again achieving O(n^2) in either case. If sorting is forbidden and using extra space is forbidden, then I doubt that any algorithm less than O(n^3) exists. Dave On Dec 20, 4:41 am, bittu shashank7andr...@gmail.com wrote: can we find Pythagorean triples in an unsorted array in write program so that have minimum time 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. -- 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] Google Interview Question
@Terence. Could please elaborate your answer. Bottom up level order traversal helps to get the final root value but how to use it to find minimum flips needed to Obtain the desired root value. On Fri, Dec 24, 2010 at 1:56 AM, Terence technic@gmail.com wrote: Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. Regards Shashank Mani Narayan BIT Mesra -- 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] arrays
I have a two arrays One is 2 5 1 6 4 3 other is 1 2 3 4 5 6. I want to make an array X which gives the index of its element on other arrays. Meaning X[1] = 3 1 is element of the second array and 3 is the index of element 1 in first array. How shall we get array X in O(nlogn). -- 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] Google Interview Question
here is my approach : Starting from the root node , if root node need to have a 1 ... if root is an and gate : flips = minflips for left child to have value 1 + minflips for the right child to have value 1 else flips = minimum of ( minflips for left child to have value 1 , minflips for right child to have value 1) For a leaf node , return 0 if the leaf has the value needed else return INFINITY.Also if at any internal node if it is not possible return INFINITY. On Tue, Dec 28, 2010 at 10:06 AM, Anand anandut2...@gmail.com wrote: @Terence. Could please elaborate your answer. Bottom up level order traversal helps to get the final root value but how to use it to find minimum flips needed to Obtain the desired root value. On Fri, Dec 24, 2010 at 1:56 AM, Terence technic@gmail.com wrote: Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. Regards Shashank Mani Narayan BIT Mesra -- 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. -- 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: Google Interview Question
This problem can be solved using dp in O(n), where 'n' is the number of nodes in the tree. Definitions: Let gate[i] be a boolean denoting whether the gate at node 'i' is 'AND' or 'OR'. (0-'AND' 1-'OR') Let dp[i][j] store the minimum no. of swaps required to get a value of 'j' (0 or 1), for the subtree rooted at 'i'. Let ok[i] be a boolean which denotes whether a flip operation can be performed at the i'th node or not. Let i1,i2,i3.ik be the children of node 'i' Now we have 2 cases: case 1: ok[i] = 0 (means no flipping possible at node 'i') In this, we have many cases: case 1.1: gate[i]=0 (there is an AND gate at node 'i'), and j=1 this means all children should have a value 1. hence dp[i][j]=dp[i1][j]+dp[i2][j] +.dp[ik][j] case 1.2: gate[i]=0 (there is an AND gate at node 'i'), and j=0 i will discuss this case in the end. case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and j=1 this one too, for the end case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and j=0 this means all children should have a value 0. hence dp[i][j]=dp[i1][j]+dp[i2][j] +.dp[ik][j] case 2: ok[i] = 1 (means flipping is possible at node 'i') We have 2 cases in this: case 2.1: we choose not to flip gate at node 'i'. This reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4) case 2.2: we choose to flip gate 'i'. Again it is similar to cases discussed above, except replacing 'AND' by 'OR' and vice versa and dp[i][j]=1 + dp[i1][j]+dp[i2][j] +.dp[ik][j] Note: 1)Boundary cases for leaf nodes. 2)Top down is easier. 3)If it is impossible to get a value 'j' for subtree rooted at 'i', then dp[i][j]=INF(some large value) 4)Answer is dp[root][required_value(o or 1)]. If this quantity is INF, then it is impossible to achieve this. Now, lets discuss case 1.2: We have an 'AND' gate and we want a result of 0. So, atleast one of the children of node 'i' should be 0. Now create 2 arrays x,y each of size 'k' x[1]=dp[i1][0], y[1]=dp[i1][1] x[2]=dp[i2][0], y[2]=dp[i2][1] . . . x[k]=dp[ik][0], y[k]=dp[ik][1] Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the minimum element(x[h] is minimum) Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])] The other cases are similar to this! I can write a code and send if you have doubts. On Dec 28, 9:36 am, Anand anandut2...@gmail.com wrote: @Terence. Could please elaborate your answer. Bottom up level order traversal helps to get the final root value but how to use it to find minimum flips needed to Obtain the desired root value. On Fri, Dec 24, 2010 at 1:56 AM, Terence technic@gmail.com wrote: Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. Regards Shashank Mani Narayan BIT Mesra -- 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: Google Interview Question
Your approach is for a binary tree, but the problem statement does not say anything about it. On Dec 28, 10:27 am, pacific pacific pacific4...@gmail.com wrote: here is my approach : Starting from the root node , if root node need to have a 1 ... if root is an and gate : flips = minflips for left child to have value 1 + minflips for the right child to have value 1 else flips = minimum of ( minflips for left child to have value 1 , minflips for right child to have value 1) For a leaf node , return 0 if the leaf has the value needed else return INFINITY.Also if at any internal node if it is not possible return INFINITY. On Tue, Dec 28, 2010 at 10:06 AM, Anand anandut2...@gmail.com wrote: @Terence. Could please elaborate your answer. Bottom up level order traversal helps to get the final root value but how to use it to find minimum flips needed to Obtain the desired root value. On Fri, Dec 24, 2010 at 1:56 AM, Terence technic@gmail.com wrote: Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. Regards Shashank Mani Narayan BIT Mesra -- 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. -- 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: SUN Microsystem Question
It would be interesting to do some tests. Asymptotic performance isn't always important. It's possible that since we are looking for only the top 10 elements, we'll get better run times using a simple linear scan to find the insertion point (as in insertion sort) rather than the more complex heapify operation. Log base 2 of ten is 3+, but on average we'd scan only 5 elements for a simple insertion. These are so close that constant factors will make a difference. It's likely that the interviewer was looking for people to notice this. -- 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.
