Re: [algogeeks] BT
@Nishaanth T1 has millions of nodes. Suppose all the nodes of T1 are equal to root of T2. Then u will have to check every where in T1. Putting height as constraint, u will have to check only those nodes whose height is equal to T2. It will reduce time complexity. Well m not able to think of better time complexity, another way would be: Find Height of T2 ... O(k) //k is no. of nodes in T2 Find Height of each node in T1... O(N) //N is no. of nodes in T1 now if p nodes in T1 have height same as T2, then we can find if a subtree rooted at any of those p nodes are identical to T2 in O(pk) time. Thus total time complexity: O(N) + O(k) + O(pk). correct me if I am wrong.. -- 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: post and pre increment operators
@priya...ya thats wat i meant by interleaving of operations(non-atomic operations). you can understand the results if you can trace the register values. On Sat, Jan 8, 2011 at 10:18 PM, Priyanka Chatterjee dona.1...@gmail.comwrote: @harshal, sundi: Use some compiler to check, i checked on gcc , it gives 13,14,14 On 9 January 2011 11:44, Harshal hc4...@gmail.com wrote: hey i am also getting the output as 12,13,13,13.. -- 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. -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] tic tac toe
someone - going by the exact words of the problem description. Just see all the 8 possible winning combinations(row,column, 2 diagonals)...if anyone combination is filled by the same player..then there is a winner. I know it sounds trivial, correct me if i am wrong. On Sat, Jan 8, 2011 at 11:16 AM, divya sweetdivya@gmail.com wrote: Design an algorithm to figure out if someone has won in a game of tic- tac-toe. give O(N) soln -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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
In essence what you say boils down to DFS , isnt it ? On Sat, Jan 8, 2011 at 10:15 PM, Algoose chase harishp...@gmail.com wrote: Will this work ? Find the node x, then the node y within the sub tree rooted at x and then z within the sub tree rooted at y since they must within a unique path If any of those searches fails there are no such nodes On Sun, Jan 9, 2011 at 6:02 AM, Gene gene.ress...@gmail.com wrote: The problem never says that the tree is rooted. So LCA is not very relevant. The path between two nodes in any tree is unique. (Otherwise it has a cycle and is not a tree.) So all that's needed is to search for z starting at x (DFS or BFS will work fine). When you find the unique path, see if it contains y. This is O(n) where n is the number of nodes. The problem is more interesting if you are allowed to pre-process the tree one time in order to build a data structure to support many queries. -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] Linear Recurrences
hi all, Is there a way to find a formula for the nth element of a linear recurrence ? Instead of going linearly one by one c1, c2, c3 are the three constants. a(n+3) = c1*a(n+2) - c2*a(n+1) + c3*a(n) thanks. shady -- 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] Serialization in BT
And what else? List doesn't represent the original tree structure. -- 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: Problem from ACM ICPC 2010
There are 4 kids). So 1, 2, 3 are connected into a circle. There is no place for the remaining 4-th) -- 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] Linear Recurrences
yes,u can use matrix exponentiation On Sun, Jan 9, 2011 at 3:49 PM, shady sinv...@gmail.com wrote: hi all, Is there a way to find a formula for the nth element of a linear recurrence ? Instead of going linearly one by one c1, c2, c3 are the three constants. a(n+3) = c1*a(n+2) - c2*a(n+1) + c3*a(n) thanks. shady -- 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.
[algogeeks] Re: Serialization in BT
You may find this http://en.wikipedia.org/wiki/Binary_tree#Encodings useful. -- 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: Serialization in BT
And this: http://www.cs.usfca.edu/~galles/cs245/lecture/lecture9.pdf -- 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
Your approach is failed! Read my previous post. There is a simple counterexample when doing dfs from x we cannot reach target node cause z can be placeed into another subtree, so x is not its ancestor. -- 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: Linear Recurrences
There is very useful technique for this kind of problem. A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3). Let's introduce matrix B: C1 -C2 C3 100 010. A(n-1) A(n) B x A(n-2) = A(n-1) A(n-3) A(n-2) and so on.. So to find A(n) you should muultiply matrix B^n by initial vector (A2, A1, A0). B^n can be calculated using fast exponention algorithm. Complexity is O(k^3 * log(n)), where k - size of the matrix B, so k=3. -- 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: tic tac toe
What do you mean by N term? Is it a size of the matrix N*N? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.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] post and pre increment operators
You are wrong, this doesn't depend on the order which is used by printf. In C/C++ order of evaluating function's parameters is undefined. So you may receive different results in different compilers. -- 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
@lalit hi its because whenever we talk about multi-threading we need to take care of synchronization as the problem clearly says application made only single threaded means not synchronized otherwise as a programmer its his job to make a app..for multithreaded environment so that such problem can avoided simultaneous access of any segment/part of this application causes curruption od data...let us take a example Let us assume that two threads T1 and T2 each want to increment the value of a global integer by one. Ideally, the following sequence of operations would take place: 1. Integer i = 0; (memory) 2. T1 reads the value of i from memory into register1: 0 3. T1 increments the value of i in register1: (register1 contents) + 1 = 1 4. T1 stores the value of register1 in memory: 1 5. T2 reads the value of i from memory into register2: 1 6. T2 increments the value of i in register2: (register2 contents) + 1 = 2 7. T2 stores the value of register2 in memory: 2 8. Integer i = 2; (memory) In the case shown above, the final value of i is 2, as expected. However, if the two threads run simultaneously without locking or synchronization, the outcome of the operation could be wrong. The alternative sequence of operations below demonstrates this scenario: 1. Integer i = 0; (memory) 2. T1 reads the value of i from memory into register1: 0 3. T2 reads the value of i from memory into register2: 0 4. T1 increments the value of i in register1: (register1 contents) + 1 = 1 5. T2 increments the value of i in register2: (register2 contents) + 1 = 1 6. T1 stores the value of register1 in memory: 1 7. T2 stores the value of register2 in memory: 1 8. Integer i = 1; (memory) The final value of i is 1 instead of the expected result of 2. its the problem of synchronization..future solution of this problem is it is mutual exclusion..its not ended world computer science.. Hope It Will help You Thanks Regards Shashank Mani Narayan Don't Be Evil U Can Earn While U Learn Cell No +91-9740852296 -- 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: Linear Recurrences
I am not familiar with such techniques, can you please refer to some article where such techniques are explained, ... Regards, Shady On Sun, Jan 9, 2011 at 5:44 PM, juver++ avpostni...@gmail.com wrote: There is very useful technique for this kind of problem. A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3). Let's introduce matrix B: C1 -C2 C3 100 010. A(n-1) A(n) B x A(n-2) = A(n-1) A(n-3) A(n-2) and so on.. So to find A(n) you should muultiply matrix B^n by initial vector (A2, A1, A0). B^n can be calculated using fast exponention algorithm. Complexity is O(k^3 * log(n)), where k - size of the matrix B, so k=3. -- 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: Linear Recurrences
You find this so useful http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html On Sun, Jan 9, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: I am not familiar with such techniques, can you please refer to some article where such techniques are explained, ... Regards, Shady On Sun, Jan 9, 2011 at 5:44 PM, juver++ avpostni...@gmail.com wrote: There is very useful technique for this kind of problem. A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3). Let's introduce matrix B: C1 -C2 C3 1 0 0 0 1 0. A(n-1) A(n) B x A(n-2) = A(n-1) A(n-3) A(n-2) and so on.. So to find A(n) you should muultiply matrix B^n by initial vector (A2, A1, A0). B^n can be calculated using fast exponention algorithm. Complexity is O(k^3 * log(n)), where k - size of the matrix B, so k=3. -- 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. -- 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] Adobe - Algorithm
Convert in O(n) time and O(1) space : a1,a2,a3,a4,.aN,b1,b2,b3,b4,.,bN to a1,b2,a2,b2,a3,b3,a4,b4,..aN,bN. -- 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 Question
i think its DP Problemstill thinking on the soultion.. @ankur..ur approach nearly matches to mine..what i thought..but we need actual 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.
Re: [algogeeks] SUMMER INTERNSHIP
somebody might enlighten for 3rd year as well (INDIA) On Sun, Jan 9, 2011 at 6:53 PM, abhishesh srivastava abhishesh.srivast...@gmail.com wrote: Can anyone please tell me about the summer internship programs of various institute. I want to know how to register and about various summer internship program for CSE 2nd year student -- 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: Adobe - Algorithm
No its a single array . You have to convert first array into second in O(n) time and O(1) space . -- 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: SUMMER INTERNSHIP
Post your resume on some Job search website or try LinkedIn(Job search option) . In the search engine (of that website) put trainee or software trainee . You might find some useful result there . Or google search internship . -- 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
so if its in another subtree, whats the problem? If z is not reachable print 'no'. On Sun, Jan 9, 2011 at 5:32 PM, juver++ avpostni...@gmail.com wrote: Your approach is failed! Read my previous post. There is a simple counterexample when doing dfs from x we cannot reach target node cause z can be placeed into another subtree, so x is not its ancestor. -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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 Interview - Algorithms
It doesn't matter how to make transitions: from current position make all necessary moves, or determine all positions from which we can achieve i-th position. So your method is only the one of possible. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe 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
x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1 cannot be reached while DFS from node 2 https://lh3.googleusercontent.com/_qdJSDBXyZKE/TSi5XyCrEzI/ARg/PB7anNiPA2c/graph.png -- 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] c aps
#includestdio.h
int main()
{
int i=2;
for(printf(cat );printf(rat )i--;printf(mat ))
{
printf(bat );
}
}
ouput : cat rat bat mat rat bat mat rat
can anybody plz explain how we get this output??
--
Regards,
$iva
--
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: c aps
This is simple. cat - initilization step of for loop rat - first loops's if passed, so i == 1 now bat - loop's body mat - loop's post operations rat - second loop's if passed, i == 0 now bat - loop's body mat - loop's post operations rat - thirrd calculation of the loop statement, first term always returns 3, so for the operation calculate second term, but i == 0 and the whole result if false, so loop is terminated. -- 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] c aps
the printf function returns 1 when it prints a string..
for (1;1i--;1)
{
printf(bat);
}
note that i=2 has been cunningly initialized before. and the decrement of i
has been done in middle expression of the for loop
hence, actually its like
for(;i--;)
{
}
how many times will this execute? Twice.i=1 and i=2, for i=O, the middle
condition shall become O and hence fails.
therefore the ouput.
On Sun, Jan 9, 2011 at 6:48 PM, siva viknesh sivavikne...@gmail.com wrote:
#includestdio.h
int main()
{
int i=2;
for(printf(cat );printf(rat )i--;printf(mat ))
{
printf(bat );
}
}
ouput : cat rat bat mat rat bat mat rat
can anybody plz explain how we get this output??
--
Regards,
$iva
--
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: tic tac toe
For each row, column and both diagonals keep track amount of equal marks. Update these counts in O(1) when player makes move. To determine winner, iterater over each column, row and diagonals to check whether there is N equal marks. -- 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
please describe the tree...give an elaborate explanation to your input On Sun, Jan 9, 2011 at 8:02 PM, juver++ avpostni...@gmail.com wrote: x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1 cannot be reached while DFS from node 2 https://lh3.googleusercontent.com/_qdJSDBXyZKE/TSi5XyCrEzI/ARg/PB7anNiPA2c/graph.png -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] Problem from ACM ICPC 2010_2
I have solved the last one :)
how can i solve this one:
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4805
using LCA, I used this algorithm:
http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor
but i dont know how to count the weights of the edges.
I have this code that prints the Lowest Common Ancestor:
#include iostream
#include stdio.h
using namespace std;
#define MAXN 12
int P[MAXN][20];//parent 16=log(MAXN)
int T[MAXN];//first parent
int L[MAXN];//level
int C[MAXN];//weight of edges
int query(int p, int q){
int tmp,log,i,c=0;
//if p is situated on a higher level than q then we swap them
if(L[p]L[q])
swap(p,q);
//we compute the value of [log(L[p)]
for(log=1;1log=L[p];++log);
log--;
//we find the ancestor of node p situated on the same level
//with q using the values in P
for(i=log;i=0;--i)
if(L[p]-(1i)=L[q])
p=P[p][i];
if(p==q)
return p;
//we compute LCA(p, q) using the values in P
for(i=log;i=0;--i){
if(P[p][i]!=-1 P[p][i]!=P[q][i]){
p=P[p][i];
q=P[q][i];
}
}
return T[p];
}
int main(){
//freopen(1.txt,r,stdin);
int n,i,j,a,b,q;
T[0]=P[0][0]=0;
while(cinn n){
//preprocess;
for(i=1;in;++i)
for(j=1;1jn;++j)
P[i][j]=-1;
for(i=1;in;++i){
cinab;
T[i]=P[i][0]=a;
L[i]=L[a]+1;//level
C[i]=b;//weight
}
for(j=1;1jn;++j){
for(i=0;in;++i){
if(P[i][j-1]!=-1)
P[i][j]=P[P[i][j-1]][j-1];
}
}
cinq;//queries
for(i=0;iq;i++){
if(i) cout ;
cinab;
coutquery(a,b);
}
coutendl;
}
}
please, Thanks in advance.
--
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
See at the image. It is enough to see tre structure of the tree. -- 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: Problem from ACM ICPC 2010_2
Run dfs/bfs from the root (node 0). Store distance from the root to each node at the node's data. Then the final path's weight between i and j is: dist[i] + dist[j] - dist[lca(i, j)]. -- 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: Linear Recurrences
thanks that was a very nice tutorial. but i am still stuck with S(n,3) = A(n+3) = 6*A(n+2) - 11*A(n+1) + 6*A(n) --- 1 S(n+1,4)=S(n,3)+4*S(n,4) 2nd stirling number 3*S(n+1,4) = 0, 0, 3, 30, 195, 1050, 5103, 23310 what will be the matrix for the second sequence i know how to solve the first recurrence, but how to solve the second one On Sun, Jan 9, 2011 at 6:13 PM, radha krishnan radhakrishnance...@gmail.com wrote: You find this so useful http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html On Sun, Jan 9, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: I am not familiar with such techniques, can you please refer to some article where such techniques are explained, ... Regards, Shady On Sun, Jan 9, 2011 at 5:44 PM, juver++ avpostni...@gmail.com wrote: There is very useful technique for this kind of problem. A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3). Let's introduce matrix B: C1 -C2 C3 100 010. A(n-1) A(n) B x A(n-2) = A(n-1) A(n-3) A(n-2) and so on.. So to find A(n) you should muultiply matrix B^n by initial vector (A2, A1, A0). B^n can be calculated using fast exponention algorithm. Complexity is O(k^3 * log(n)), where k - size of the matrix B, so k=3. -- 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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Use a linked list (maintain both head and tail positions) and treat it as a queue insert/delete front or back... whatever... For each insert, see if it's less than the current min and maintain min... If you're deleting the current min, you may traverse from head to tail and recompute the min... On Jan 1, 9:23 pm, sourav souravs...@gmail.com wrote: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations. -- 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: combinations problem
knapsack typically tries to maximize one attribute while minimizing some other (or optimal max for both or similar such conditions)... for this problem, all we need to do is find one subset that adds up to the given number... there's no second criteria to maximize/minimize... Please correct me if my understanding of knapsack is wrong... On Dec 29 2010, 8:01 am, juver++ avpostni...@gmail.com wrote: Yes, and this subset can be find using DP (which is cimular to 0-1 knapsack problem). -- 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.
All operations should constant at least on average. So your idea is not suitable. -- 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: combinations problem
As I've stated, problem is similar to the 0-1 knapsack. Find subset of elements which sums up to a given value. Possible transitions - to take or not to take particular element. That's why it's 0-1 knspsack. -- 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
Start from the root and do a breadth first traversal until you hit x or Z... Once you have x or Z, treat that node as root and traverse breadth first on that sub-tree till you reach the other node (i.e, if you hit X first, see if you can reach Z from X)... At the same time, if you encounter Y during the sub-tree traversal and you indeed hit Z at some point, return true. On Jan 6, 11:00 am, Decipher ankurseth...@gmail.com wrote: There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x and z. -- 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
Start from the root and do a breadth first traversal until you hit x or Z... Once you have x or Z, treat that node as root and traverse breadth first till you reach the other node (if you hit X first, see if you can reach Z from X)... At the same time, if you encounter Y during the sub-tree traversal and you indeed hit Z, return true. On Jan 9, 10:45 am, juver++ avpostni...@gmail.com wrote: See at the image. It is enough to see tre structure of the tree. -- 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.
why's the linked list option not constant (at least for most cases)? the time's not constant only for delete operation (that too only if you delete the current min)... otherwise, everything is a O(1) operation... get_min() already has the min... push_rear(), pop_front() - you're maintaining the head and tail positions of the linked list... so u can easily do these... On Jan 9, 11:22 am, juver++ avpostni...@gmail.com wrote: All operations should constant at least on average. So your idea is not suitable. -- 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 - Algorithm
Hey guys .. saw this discussion and wanted to add something .. I wrote the
below program in college .. and I kindof have forgotten wat was the logic
(see the problem with badly written code :P ), It works on a pattern which I
found in this problem, I checked it and feel it works in order O(n) as each
element is accessed only twice, if you guys find any problem do post it.
#include stdio.h
int main() {
int n, i, j , k, t1, l;
scanf(%d,n);
int arr[n1 + 1];
for (i=1,j=n1,k=-1,l=0;i = j ; i++ ) {
if ( i = n )
arr[i] = k+=2; // 1 3 5 7
else
arr[i] = l+=2;
}
arr[0]=0;
printf(\n\nBefore Shuffling ..\n);
for (i = 0;i = n1; i++) printf(%d , arr[i]);
printf(\n\nShuffling Now ..\n);
// Shuffleing starts
i = 1;
int chk[j+1]; // To check if each element was visited only once
for (i=0;i=j;i++) chk[i]=0;
i = 1;
while (i = j) {
while (i=j arr[i] == i) {
chk[i]++;
i++;
}
if (i j)
break;
t1 = arr[i]; // swap with temp
k = i; // note the curr. loc in array
l = i;
printf(%d : Value of i entering loop\n,i);
while (1) {
k = k 1 ? (k + 1) / 2 : n + k / 2;
chk[k]++;
if (k == i) break;
arr[l] = arr[k];
l = k;
}
arr[l] = t1;
}
for (i = 0;i = j;i++) printf(%d ,arr[i]);
printf(\n Checking which element was processed how many times.\n);
for (i = 0; i = j; i++)
printf(%d %d\n,i,chk[i]);
return 0;
}
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the scripture of this age.
On Sun, Jan 9, 2011 at 7:11 PM, Decipher ankurseth...@gmail.com wrote:
No its a single array . You have to convert first array into second in
O(n) time and O(1) space .
--
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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
When you remove element from the front of queue, you should update min value for all remaining nodes. So it's linear. -- 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: Linear Recurrences
Sorry for the confusion, Given series : http://oeis.org/A032263/list How to get the nth number of the series in O(log(n)) ? Regards, Shady On Mon, Jan 10, 2011 at 12:36 AM, shady sinv...@gmail.com wrote: thanks that was a very nice tutorial. but i am still stuck with S(n,3) = A(n+3) = 6*A(n+2) - 11*A(n+1) + 6*A(n) --- 1 S(n+1,4)=S(n,3)+4*S(n,4) 2nd stirling number 3*S(n+1,4) = 0, 0, 3, 30, 195, 1050, 5103, 23310 what will be the matrix for the second sequence i know how to solve the first recurrence, but how to solve the second one On Sun, Jan 9, 2011 at 6:13 PM, radha krishnan radhakrishnance...@gmail.com wrote: You find this so useful http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html On Sun, Jan 9, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: I am not familiar with such techniques, can you please refer to some article where such techniques are explained, ... Regards, Shady On Sun, Jan 9, 2011 at 5:44 PM, juver++ avpostni...@gmail.com wrote: There is very useful technique for this kind of problem. A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3). Let's introduce matrix B: C1 -C2 C3 100 010. A(n-1) A(n) B x A(n-2) = A(n-1) A(n-3) A(n-2) and so on.. So to find A(n) you should muultiply matrix B^n by initial vector (A2, A1, A0). B^n can be calculated using fast exponention algorithm. Complexity is O(k^3 * log(n)), where k - size of the matrix B, so k=3. -- 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.
[algogeeks] Re: Adobe - Algorithm
It can be done in O(n) time and O(1) space. Logic: 1. Start at i = 0. 2. Take first half of the array and exchange elements at i=2 to n/2 with n/2+1 3. n = n/2, start = n/2+1 4. Repeat steps 2 and 3 until n becomes 0. On Jan 9, 7:41 am, Decipher ankurseth...@gmail.com wrote: No its a single array . You have to convert first array into second in O(n) time and O(1) space . -- 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] Mathalon
About Me: Currently work as SDE in Microsoft . Constant participant in programming contest around the world Handle : FameofLight. Successfully conducted many programming contest in college , including Alkhwarizm [ First Indian Contest to Publish a Editorial : I should take credit for this , as it called my 4 days of effort in turn I learned a lot from ACRush ] Here is Link http://fameoflight.com/Mathalon/ . Feel to explore the website , you are not required to register until you wish to submit for problem. I don't store any of your password , just a encrypted md5 hash with some private key. So less assure about anything. Your email is not displayed anywhere in website. Hope you guys can contribute some WOW problem to the system. A Very simple interface exist to add problem to the system. Regards, Hemant Verma -- 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
@Juver++ I am not sure if your input represents a path as asked in the problem. We typically think of a path within a binary tree as a downward path(from root to a leaf) thats not spread across different branches. Of course, if you consider that example as a valid case, then DFS wont work ! On Sun, Jan 9, 2011 at 9:57 PM, nishaanth nishaant...@gmail.com wrote: please describe the tree...give an elaborate explanation to your input On Sun, Jan 9, 2011 at 8:02 PM, juver++ avpostni...@gmail.com wrote: x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1 cannot be reached while DFS from node 2 https://lh3.googleusercontent.com/_qdJSDBXyZKE/TSi5XyCrEzI/ARg/PB7anNiPA2c/graph.png -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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: c aps
@juver and prateekthanks a lot for the detailed and nice explanation :) On Jan 9, 8:03 pm, juver++ avpostni...@gmail.com wrote: This is simple. cat - initilization step of for loop rat - first loops's if passed, so i == 1 now bat - loop's body mat - loop's post operations rat - second loop's if passed, i == 0 now bat - loop's body mat - loop's post operations rat - thirrd calculation of the loop statement, first term always returns 3, so for the operation calculate second term, but i == 0 and the whole result if false, so loop is terminated. -- 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: Problem from ACM ICPC 2010_2
Thanks, i finished it. :) it wasdist[i] + dist[j] - 2*dist[lca(i, j)] this problem is difficult :( http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4809 I dont have idea how to solve it. -- 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.
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init stuff...
//all insert/delete methods, front, rear etc,...
//one example set of insert and delete pseudocode
public void Insert(int i)
{
if( currentMin == null || currentMin i )
currentMin = i;
itemsList.Add(i);
}
public int Delete()
{
var itemToReturn = itemsList.First.Value;
itemsList.RemoveFirst();
if(itemToReturn == currentMin)
RecomputeAndStoreMin(); //A private method that'll
find and store min in O(n) time
return itemToReturn;
}
public int GetMinValue()
{
If(currentMin == null)
throw new InvalidOperationException();
return currentMin;
}
}
On Jan 9, 11:42 am, juver++ avpostni...@gmail.com wrote:
When you remove element from the front of queue, you should update min value
for all remaining nodes.
So it's linear.
--
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 only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
that too when the minimum item is deleted. For all other cases, delete
is constant as well... For delete in those special cases, time is
O(n)...
On Jan 9, 10:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote:
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init stuff...
//all insert/delete methods, front, rear etc,...
//one example set of insert and delete pseudocode
public void Insert(int i)
{
if( currentMin == null || currentMin i )
currentMin = i;
itemsList.Add(i);
}
public int Delete()
{
var itemToReturn = itemsList.First.Value;
itemsList.RemoveFirst();
if(itemToReturn == currentMin)
RecomputeAndStoreMin(); //A private method that'll
find and store min in O(n) time
return itemToReturn;
}
public int GetMinValue()
{
If(currentMin == null)
throw new InvalidOperationException();
return currentMin;
}
}
On Jan 9, 11:42 am, juver++ avpostni...@gmail.com wrote:
When you remove element from the front of queue, you should update min value
for all remaining nodes.
So it's linear.
--
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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Then it is O(n) worst case. While juver's algo is amortized constant time in
worst case.
On Jan 9, 2011 10:26 PM, SVIX saivivekh.swaminat...@gmail.com wrote:
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
that too when the minimum item is deleted. For all other cases, delete
is constant as well... For delete in those special cases, time is
O(n)...
On Jan 9, 10:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote:
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init stuff...
//all insert/delete methods, front, rear etc,...
//one example set of insert and delete pseudocode
public void Insert(int i)
{
if( currentMin == null || currentMin i )
currentMin = i;
itemsList.Add(i);
}
public int Delete()
{
var itemToReturn = itemsList.First.Value;
itemsList.RemoveFirst();
if(itemToReturn == currentMin)
RecomputeAndStoreMin(); //A private method that'll
find and store min in O(n) time
return itemToReturn;
}
public int GetMinValue()
{
If(currentMin == null)
throw new InvalidOperationException();
return currentMin;
}
}
On Jan 9, 11:42 am, juver++ avpostni...@gmail.com wrote:
When you remove element from the front of queue, you should update min
value
for all remaining nodes.
So it's linear.
--
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.
