[algogeeks] Job Openings in Hyderabad/Bangalore
Folks, I am looking for job switch in Hyderabad/Bangalore, if any one has references/pointers regarding openings please let me know. -- Regards Kumar Raja -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Minimal number of swaps
Adding time and space complexities. Time complexity: O(n) Space complexity: O(1) On 29 March 2016 at 23:44, kumar raja <rajkumar.cs...@gmail.com> wrote: > I think it is straight forward. Correct me if i am wrong or if there is > better solution. > > 1) Do one pass over the list of elements and count the number of 1's. let > us say it is K > 2) count = 0 > from index 0 to K-1 do > if array[index] != 1 > count ++ > end > end > > The variable "count" indicates the minimum number of steps required to > obtain a sorted list. > > > On 29 March 2016 at 19:30, Régis Bacra <fredericdesmoul...@gmail.com> > wrote: > >> This puzzle comes from a contribution on codingame.com (link to the >> puzzle <https://www.codingame.com/games/community/?puzzleId=103>). Any >> idea to solve it efficiently? >> >> Given a list of 1 and 0, you must regroup all the 1 at the begin of the >> list in a minimum number of steps. A step is the interchange of two >> elements located at different positions. >> The expected result is the minimum number of steps required to obtain a >> sorted list. >> >> Examples: >> 1 0 1 0 1 -> 1 >> 0 1 0 1 1 1 0 -> 2 >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> > > > > -- > Regards > Kumar Raja > > > -- Regards Kumar Raja -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Minimal number of swaps
I think it is straight forward. Correct me if i am wrong or if there is better solution. 1) Do one pass over the list of elements and count the number of 1's. let us say it is K 2) count = 0 from index 0 to K-1 do if array[index] != 1 count ++ end end The variable "count" indicates the minimum number of steps required to obtain a sorted list. On 29 March 2016 at 19:30, Régis Bacra <fredericdesmoul...@gmail.com> wrote: > This puzzle comes from a contribution on codingame.com (link to the puzzle > <https://www.codingame.com/games/community/?puzzleId=103>). Any idea to > solve it efficiently? > > Given a list of 1 and 0, you must regroup all the 1 at the begin of the > list in a minimum number of steps. A step is the interchange of two > elements located at different positions. > The expected result is the minimum number of steps required to obtain a > sorted list. > > Examples: > 1 0 1 0 1 -> 1 > 0 1 0 1 1 1 0 -> 2 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- Regards Kumar Raja -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Programming questions
1) string a1b2c3d4. rearrange it as abcd1234. order should be preserved. with time complexity O(n) and space complexity O(1) 2) given a file.txt. replace every occurence of abc by xyz 3) Write a program to check the elements of an array with even number of elements can be grouped into pairs whose sum is divisible by an integer k. Example:{0,4,6,10} with k=4, so the pairing can be {(0,4),(6,10)} 4) Given an array representing insertion order in a BST, find the root-to-node path for any given node. Please share your views on these questions. I am trying to solve them. But i want to know the optimized answers for these questions. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Better data structure/Algorithm to handle the following porblem
which is like a table in database, and produces results for user queries. Data is: in txt file. ID, FIRSTNAME, LASTNAME, AGE, SALARY, TITLE 1, venkatesh, kumar, 21, 3, reporter 2, kiran, kannan, 45, 9000, chairman 3, pradeep, mishra, 35, 15000, manager 4, suman, raj, 35, 12000, manager user query will be like select firstName, lastName where age25 orderby salary dsc dsc - for descending you have to produce appropriate records. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Largest Rectangle
If anyone have answer to this question, please share it. I need the solution for this prolem. On 2 August 2011 at 19:42, payel roy smithpa...@gmail.com wrote: Given a Binary Matrix of 0's and 1's. Print the largest Sub-matrix with all boundary elements 0. Explain your whole algorithm with an example. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
Got it. Any idea on how to solve the problem 2(e) ? On 6 June 2014 00:52, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: T[i][j] = 0 (i 0 || j =n || i = j || s[i] != s[j]) T[i][j] = 1 + T[i-1][j+1] On Fri, Jun 6, 2014 at 12:19 AM, kumar raja rajkumar.cs...@gmail.com wrote: If i get u correctly, this is the recurrence relation ( i feel this makes many people to understand the solution rather than looking at the code) T[i..j] indicates the length of longest even length palin string ( not exactly palin but i think u know what i am saying) with i as begin and j as ending point. T[i,j] = 0 if i=j T[i+1,j-1]+1 if s[i]==s[j] 0else And u find max value in the table which is the answer So time complexity = space complexity = O(n^2). Correct me if i am wrong On 5 June 2014 23:44, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: And now I get what you meant when you said palindrome. You should have explained that if that was not exact palindrome So yes, your solution seems correct but that is the brute force approach. It runs in O(n*n*n) as there are n*n substrings and every check is linear. DP solution helps save time by memoization. On Thu, Jun 5, 2014 at 11:37 PM, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Ok! So I guess now we are talkng my solution. What i do is maintain two pointers i and j, i is the end of the first string and j is the beginning of the second. If both the character match, I calculate the answer for pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I simply mark 0 as the answer for i,j. So my table if filled top-down like this. Finally, I return the maximum entry in the table. Need I explain further? If so, feel free. Should I explain what those methods do? -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
U have two dimensions for the table ( has O(n^2) entries.) and to check whether string is palindrome or not it will take O(n) . So it is O(n^3) solution. I have checked it manually for some inputs, and it works. On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote: I am not too sure about your O (N^3) solution even. Can you link the working code ? On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com wrote: This is a very good collection of DP problems. I want the answers for problem 2(e) and problem 14. for problem 14 the recurrence relation that i have is T[i,j] = 0 if i=j 1 if j=i+1 and s[i]=s[j] 0 if j=i+1 and s[i]!=s[j] j-i+1/2 if s[i..j] is even length palindrome j-i/2 if s[i..j] is odd length palindrome max{T[i+1,j],T[i,j-1]} else But this is O(n^3) solution. Could not find out solution of order O(n^2). If someone knows please share the answers for them. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
Yes i agree that my recurrence relation is wrong. I have checked it some inputs, it did not work. But i think the brute force solution is possible in O(n^3) solution. We have O(n^2) combination of end points. we can check for the maximum possible even length palin string in O(n). So that will give O(n^3). Anyone has solution about O(n^2)? On 5 June 2014 22:25, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Hi all! Well, I agree with Shashwat in that Kumar is wrong with his solution. For example a string kumarxyzramuk will tell you why. I have a solution which runs in O(n*n) time. It is top-down dynamic programming approach. Let me know if you don't understand something or if there is some glitch in the solution. I think it is correct. Link to the C++ code - http://ideone.com/Qzs990 On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand m...@shashwat.me wrote: Code ? On Thu, Jun 5, 2014 at 7:08 PM, kumar raja rajkumar.cs...@gmail.com wrote: U have two dimensions for the table ( has O(n^2) entries.) and to check whether string is palindrome or not it will take O(n) . So it is O(n^3) solution. I have checked it manually for some inputs, and it works. On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote: I am not too sure about your O (N^3) solution even. Can you link the working code ? On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com wrote: This is a very good collection of DP problems. I want the answers for problem 2(e) and problem 14. for problem 14 the recurrence relation that i have is T[i,j] = 0 if i=j 1 if j=i+1 and s[i]=s[j] 0 if j=i+1 and s[i]!=s[j] j-i+1/2 if s[i..j] is even length palindrome j-i/2 if s[i..j] is odd length palindrome max{T[i+1,j],T[i,j-1]} else But this is O(n^3) solution. Could not find out solution of order O(n^2). If someone knows please share the answers for them. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
U need not get an exact palindrome. u will start comparing from both the end points till they are equal and does not cross each other. So that should be possible in linear time right. I did not get ur code exactly and u have written O(n*n) so i have got the doubt. On 5 June 2014 23:22, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Dude! That is what I just posted. Also your logic is wrong, Palindrome thing is just not working. Think for a while on this problem. On Thu, Jun 5, 2014 at 11:18 PM, kumar raja rajkumar.cs...@gmail.com wrote: Yes i agree that my recurrence relation is wrong. I have checked it some inputs, it did not work. But i think the brute force solution is possible in O(n^3) solution. We have O(n^2) combination of end points. we can check for the maximum possible even length palin string in O(n). So that will give O(n^3). Anyone has solution about O(n^2)? On 5 June 2014 22:25, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Hi all! Well, I agree with Shashwat in that Kumar is wrong with his solution. For example a string kumarxyzramuk will tell you why. I have a solution which runs in O(n*n) time. It is top-down dynamic programming approach. Let me know if you don't understand something or if there is some glitch in the solution. I think it is correct. Link to the C++ code - http://ideone.com/Qzs990 On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand m...@shashwat.me wrote: Code ? On Thu, Jun 5, 2014 at 7:08 PM, kumar raja rajkumar.cs...@gmail.com wrote: U have two dimensions for the table ( has O(n^2) entries.) and to check whether string is palindrome or not it will take O(n) . So it is O(n^3) solution. I have checked it manually for some inputs, and it works. On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote: I am not too sure about your O (N^3) solution even. Can you link the working code ? On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com wrote: This is a very good collection of DP problems. I want the answers for problem 2(e) and problem 14. for problem 14 the recurrence relation that i have is T[i,j] = 0 if i=j 1 if j=i+1 and s[i]=s[j] 0 if j=i+1 and s[i]!=s[j] j-i+1/2 if s[i..j] is even length palindrome j-i/2 if s[i..j] is odd length palindrome max{T[i+1,j],T[i,j-1]} else But this is O(n^3) solution. Could not find out solution of order O(n^2). If someone knows please share the answers for them. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DP problems
If i get u correctly, this is the recurrence relation ( i feel this makes many people to understand the solution rather than looking at the code) T[i..j] indicates the length of longest even length palin string ( not exactly palin but i think u know what i am saying) with i as begin and j as ending point. T[i,j] = 0 if i=j T[i+1,j-1]+1 if s[i]==s[j] 0else And u find max value in the table which is the answer So time complexity = space complexity = O(n^2). Correct me if i am wrong On 5 June 2014 23:44, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: And now I get what you meant when you said palindrome. You should have explained that if that was not exact palindrome So yes, your solution seems correct but that is the brute force approach. It runs in O(n*n*n) as there are n*n substrings and every check is linear. DP solution helps save time by memoization. On Thu, Jun 5, 2014 at 11:37 PM, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Ok! So I guess now we are talkng my solution. What i do is maintain two pointers i and j, i is the end of the first string and j is the beginning of the second. If both the character match, I calculate the answer for pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I simply mark 0 as the answer for i,j. So my table if filled top-down like this. Finally, I return the maximum entry in the table. Need I explain further? If so, feel free. Should I explain what those methods do? -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Calculating C(n.r)
Thanks for the idea. On 9 April 2014 10:25, Dave dave_and_da...@juno.com wrote: What you want to do is automate the process of cancelling common factors that you would do if you were calculating nCr by hand. Fill an array a[] with the numerator terms, n, n-1, n-2, ..., n-r+1, and a second array b[] with the denominator terms, 1, 2, 3, ..., r. Inside a double loop with j and i going from 0 to r-1, compute the gcd of a[i] and b[j]. Divide both a[i] and b[j] by the gcd. When the loops finish, you will have cancelled the common factors from all of the terms, and in fact, all of the denominator terms will be 1. In a final loop, compute the product of the numerator terms. There are some obvious optimizations. Dave On Tuesday, April 8, 2014 1:06:47 PM UTC-5, kumar raja wrote: Hi all, I know the way to calculate value of C(n,r) using pascals identity. But i have a different requirement. C(n,r) = n (n-1) (n-2) ... (n-r+1) / r! Suppose the numerator is such that it cant fit into existing data type. So i remember there is a way to strike off the common factors in numerator and denominator then calculate the result of it. But the logic is not striking to me. Googled but could not find much. So please share the clever way to calculate the above value w/o actually computing the factorials and then making division. My actual requirement is to calculate the value of (n1+n2++nk)! / (n1!.n2!.n3!.nk!) . Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Integer partition problem - DP
Given an integer how many number of ways u can partition the number? e.g. 3 can be written as 3,1+2,1+1+1 and 4 can be written as 4, 1+1+1+1,2+2,1+3,1+1+2 So for 3 -- 3 for 4 --5. The order of the elements in the partition does not matter. So how to calculate the number of ways to partition the given number? Can someone give idea on how to write the recurrence relation for the problem? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Permuations with stack constraints
Hi all, Here is a permuatation related question. Suppose the set is {a,b,c}; At a given point of time either u can push an elemnt on to the stack or pop of the element. While pushing the elements u have to follow the order a,b,c as given in the set. When u pop the element u will print it to the output array. one possible sequence of operations is push(a),push(b),pop(),push(c),pop(),pop() The permuation obtained by above combination is {b,c,a}. But out of 6! permuations possible one invalid permutation is {c,a,b} (guess how?) So how to print all valid permuations with the above constaraints? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Permuations with stack constraints
Thanks for the solution. The idea worked for me. On 21 February 2014 01:58, Shashwat Anand m...@shashwat.me wrote: Think in binaries. '1' = push, '0' = pop. So a sequence of operations will consist of 0's and 1s. Say N = length of set. Property 1: count of 0 = count of 1 = N. There will be N push and N pop. Property 2: At any point count of 1s = count of 0s. 1100 is valid. [2 push, 2 pop.] 1001 is invalid. [1 push, 2 pop] At index 3, number of 0s increased that of 1s. Hence invalid. Now just simulate the process by generating valid binaries. Time complexity: O (N * (2 ^ N)), Space complexity: O (N) Code follows, int main () { string s = abc; int N = s.size (); for (int mask = 0; mask (1 (2 * N)); mask++) { bool ok = true; if (__builtin_popcount (mask) != N) continue; for (int i = 0, x = mask, c0 = 0, c1 = 0; i 2 * N; i++, x /= 2) { (x 1) ? c1++ : c0++; ok = (c0 = c1); } if (! ok) continue; // Invalid mask. stack char st; string t = ; for (int i = 0, x = mask, idx = 0; i 2 * N; i++, x /= 2) if (x 1) st.push (s [idx++]); else t += st.top (), st.pop (); printf (%s\n, t.c_str ()); } return 0; } For s = ab, ba ab For s = abc, cba bca acb bac abc For s = abcd, dcba cdba bdca adcb cbda bcda acdb badc abdc cbad bcad acbd bacd abcd Alternatively, you can simply simulate the whole process and do a validity check after generation of string. The check being, stack should be empty and at any point during simulation, you should not try to pop from empty stack. On Thu, Feb 20, 2014 at 11:57 PM, kumar raja rajkumar.cs...@gmail.comwrote: Hi all, Here is a permuatation related question. Suppose the set is {a,b,c}; At a given point of time either u can push an elemnt on to the stack or pop of the element. While pushing the elements u have to follow the order a,b,c as given in the set. When u pop the element u will print it to the output array. one possible sequence of operations is push(a),push(b),pop(),push(c),pop(),pop() The permuation obtained by above combination is {b,c,a}. But out of 6! permuations possible one invalid permutation is {c,a,b} (guess how?) So how to print all valid permuations with the above constaraints? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Accelerating subsequence
Call a sequence X [1 .. n] of numbers accelerating if 2 · X [i] X [i - 1] + X [i + 1] for all i. Describe an efficient algorithm to compute the length of the longest accelerating subsequence of an arbitrary array A of integers. Any idea how to solve it? Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DISTINCT Permutations ( Not Easy)
This u can do it using the backtracking method. To know how to use backtracking refer algorithm design manual by steve skiena. On 7 January 2014 03:35, bujji jajala jajalabu...@gmail.com wrote: generate all possible DISTINCT permutations of a given string with some possible repeated characters. Use as minimal memory as possible. if given string contains n characters in total with m n distinct characters each occuring n_1, n_2, n_m times where n_1 + n_2 + ...+ n_m = n program should generate n! / ( n_1! * n_2! * * n_m! ) strings. Ex: aba is given string Output: aab aba baa -Thanks, Bujji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
Good solution buddy, thanks for the answer. On 26 December 2013 17:25, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: @atul anand :- no, we need not use all the colors. @kumar raja :- sorry dude for replying this late. Continuing with the previous idea, I extend the solution for the modified problem as 1. let answer[i][j][0] represent minimum cost of coloring i houses when ith house is colored with jth color and so is the (i-1)th house. 2. let answer[i][j][1] represent minimum cost of coloring i houses when ith house is colored with jth color and (i-1)th is not. The recurrence will be 3. *answer[i][j][0] = answer[i-1][j][1] + colorvalue[j]* 4. *answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) + colorvalue[j]* for all t from 1 to k except j. // In the first problem, I mistakenly wrote colorvalue[t] here. It will be colorvalue[j] there. ( sorry for the confusion ) 5. finally solution will be min(answer[n][j][0], answer[n][j][1]) for all j from 1 to k. 6. initial settings -: answer[1][j][0] = answer[1][j][1] = colorvalue[j]. Also now that I read the problem, I guess colorvalue is not fixed for every color, so that will be a 2-D matrix as well. *replace every colorvalue[j] with colorvalue[i][j] in the above recurrences*. ( i is the house number, j is the color number ) On Wed, Dec 18, 2013 at 10:16 PM, atul anand atul.87fri...@gmail.comwrote: @kumar : i have one doubt regarding this question.Do we have to use all K colors[K] to color all building. for example :- color[3]={1,2,10}; now if we have to color 6 building then i can use only 1st 2 color to color all building and never 10 ...is this allowed ??? building[N]={1,2,1,2,1,2} On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
Please elaborate the explanation, i want to understand it in detail. On 17 December 2013 11:36, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: I think that can be done by having 2 different values at every position in the answer matrix. One when the previous house is of same color and one when it does not. Answer[n][k][2] will be the new dimensions. I can explain in detail if you don't get this. ☺ On Dec 15, 2013 4:43 PM, kumar raja rajkumar.cs...@gmail.com wrote: What can be the recurrence relation if the condition is changed to No 3 adjacent houses should get same color? On 15 December 2013 16:26, kumar raja rajkumar.cs...@gmail.com wrote: No need for the explanation ,got it man thanks. On 15 December 2013 16:20, kumar raja rajkumar.cs...@gmail.com wrote: Saurabh your solutions seems right , but can u explain me how did u arrive at the time and space complexity with some proof /pseudocode/ explanation? On 15 December 2013 09:47, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.com wrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
Saurabh your solutions seems right , but can u explain me how did u arrive at the time and space complexity with some proof /pseudocode/ explanation? On 15 December 2013 09:47, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
No need for the explanation ,got it man thanks. On 15 December 2013 16:20, kumar raja rajkumar.cs...@gmail.com wrote: Saurabh your solutions seems right , but can u explain me how did u arrive at the time and space complexity with some proof /pseudocode/ explanation? On 15 December 2013 09:47, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
What can be the recurrence relation if the condition is changed to No 3 adjacent houses should get same color? On 15 December 2013 16:26, kumar raja rajkumar.cs...@gmail.com wrote: No need for the explanation ,got it man thanks. On 15 December 2013 16:20, kumar raja rajkumar.cs...@gmail.com wrote: Saurabh your solutions seems right , but can u explain me how did u arrive at the time and space complexity with some proof /pseudocode/ explanation? On 15 December 2013 09:47, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] coloring problem Dynamic programming
You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Saving and restoring Binary trees in files
What is the effective way to save and restore the binary trees to files effectively? Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Pattern matching with regular expressions
Hi, I want to know some direction towards the problem of pattern matching with regular expressions. Suppose we are given two strings say S and T. Where S is pattern that can contain regular expression and T is some large string . Then how to say that S is substring of T. Eg. S= ab.bc* T=adkksdk*abdb*sdfklsfd I want to know approaches apart from Finite automata construction. Is it possible to implement all the wild-chard characters in regex? What is the best data structure for this probem? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Message distribution through rooted tree dynamic programming
I forgot to mention that the tree is n-ary tree, it need not be a binary tree. So what is the approach ? On 7 November 2013 01:04, Don dondod...@gmail.com wrote: Atul, the depth is the important factor, not the number of nodes. If you always pass the message to the deeper subtree first, followed by the other subtree, you get the minimum number of rounds. The problem is to compute the required number of rounds. This can be done in a way similar to computing the depth of a tree. However, be careful to handle the case where the subtrees take an equal number of rounds. int numRounds(TreePtr t) { int result = 0; if (t) { int L = numRounds(t-left); int R = numRounds(t-right); if (L == R) result = R + 2; else result = 1 + max(L,R); } return result; } On Friday, November 1, 2013 1:49:33 AM UTC-4, atul007 wrote: we can first count number of nodes in a subtree below each node.Now transfer message to max(count(root-left),count-root-right); On 11/1/13, kumar raja rajkuma...@gmail.com wrote: Suppose we need to distribute a message to all the nodes in a rooted tree. Initially, only the root node knows the message. In a single round, any node that knows the message can forward it to at most one of its children. Design an algorithm to compute the minimum number of rounds required for the message to be delivered to all nodes. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Message distribution through rooted tree dynamic programming
Suppose we need to distribute a message to all the nodes in a rooted tree. Initially, only the root node knows the message. In a single round, any node that knows the message can forward it to at most one of its children. Design an algorithm to compute the minimum number of rounds required for the message to be delivered to all nodes. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] variation of LIS problem
I think O(nlogn) solution is possible for this problem. First find the largest increasing subsequence in O(nlogn) time. http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms From this one u have LIS array M and parent array P. Now traverse through the array M and for all the length values = k , u can print the k elements using Parent array P. I guess the step of printing the array elements wont be greater than O(n logn). So it is bounded by O(nlogn) . In the worst case it might go up to O(n^2). But i am not sure of this. On 25 October 2013 00:17, atul anand atul.87fri...@gmail.com wrote: OK, i got now why you were using min-heap. now consider this example :- 200,12,33,1,55,100 K=3 insert 200 12 200...cannot insert 33 200...cannot insert . . . 100200 cannot insert output : 200 (not lenght of k) output should be : 33,55,100 On 10/24/13, pankaj joshi joshi10...@gmail.com wrote: Max-heap should not used in this case, why min heap? -- this is because program has to decide the smallest element in k-group. in your example if i consider k =3 than insert 1 insert 2 insert 5 insert 10 size of heap ==4 so delete root of min- heap (which is 1), insert 100 30 cant insert because temp = 100 and 30temp insert 8 cant insert temp = 100 and 8temp (500temp)size of heap ==4 so delete root of min-heap(which is 2) insert 555 now if i check the heap elements {5, 10, 100 , 555} On Thu, Oct 24, 2013 at 11:25 PM, atul anand atul.87fri...@gmail.comwrote: in your updated algo , you should be using max-heap not min-heap. check your algo for :- 1,2,5,10,100,30,8,555 let me know if it work fine.If it is working fine then i need more clarity of your algo On 10/24/13, pankaj joshi joshi10...@gmail.com wrote: @Saurabh: As per the question the elements of sub-sequence should be increasing, so the solution will be {5} and as per the program. * but as written longest sub-sequence of k =2, so it should be {2,3} for this case. (there should be backtrack in this case.) @atul: increasing sub sequence is checked by condition, not by Min-heap, but min heap is used for storing the largest elements. So it is preferable DS, On Thu, Oct 24, 2013 at 8:35 PM, atul anand atul.87fri...@gmail.com wrote: @pankaj : how can you maintain increasing sub-sequence using heapyour soln is for finding finding K largest element in the array...so it wont work. On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: check for {5,2,3} and K = 2. On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi joshi10...@gmail.com wrote: @ Saurabh, I have done a correction on algo temp =0 loop n to a[] if a[i]temp if min-heap(root) a[i] if min-heap(count)==k delete root in min- heap inseart a[i] in min - heap As i have made the condition: min-heap, (condition size should be always k) for this particular case. And in the example {5,2,1,10,9,30,8,55} if K =3 insert 5 2 is less so do nothing 1 is less so do nothing insert 10 9 is less so do nothing insert 30 8 is less so do nothing insert 55 (before inserting 50 delete the root of heap as count of heap == 3), deleted root was - 5 so the output will be {10,30,55} and if k is 4 than {5, 10, 30 , 55) On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: You must be mistaken in the definition of heaps, or maybe the question, look at the updated question I put up there. On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi joshi10...@gmail.comwrote: hi all, nlog(k) is the solution i think. can anyone suggest more optimal? solution: create a min-heap, (condition size should be always k) temp =0 loop n to a[] if a[i]temp if min-heap(root) a[i] delete root in min- heap inseart a[i] in min - heap at the end of main loop the min-heap will contain the final sequence. On Thu, Oct 24, 2013 at 8:50 AM, atul anand atul.87fri...@gmail.comwrote: @Saurabh Paliwal : yes On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: Do you mean *of all the increasing subsequences of length k in this array, find the one with maximum sum ?* On Wed, Oct 23, 2013 at 10:52 PM, atul anand atul.87fri...@gmail.comwrote: Given an array with N elements and integer K . Find sum of longest increasing sub-sequence of length K elements such that sub-sequence found is maximum among all K max su-sequence. Eg arr[]={5,2,1,10,9,30,8,55} K = 3 output : 10,30,55sum = 10+30+55 = 95
[algogeeks] Word breaking problem
I came across the word breaking problem in geeks for geeks. http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/ If the problem statement is to count and print all the possible ways to segment/partitaion a string based on dictionary of words. how to solve this problem? The recurrence relation i have thought is table[i,j] = 0 if ij = contains(dict,str[i]) if i==j = contains(dict,str[i..j])+ sum(table[i[k]*table[k+1][j]) for i=kj if ij But this only gives the number of ways to partition the string, but how to construct the solution? I am thinking of storing the breaking point 'k' for string str[i..j] but there are many break points possible, So what kind of data structure need to be used to print all possible partitions of string ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Breaking a string problem (Dynamic programming)
I have find out the minimum cost using the recurrence relation S[i,j] = |j-i+1| + min ( s[i,k]+s[k+1,j]) for all i=kj. But i could not find a way to print optimal cut sequence.Any pointers? On 16 October 2013 23:13, atul anand atul.87fri...@gmail.com wrote: Question seems similar to matrix chain multiplication problemhere you need to find min cost.. Recurrence for this could be the following , please validate it. DP(i,j) = j + (j - i) * min( DP(i , k) , DP(k, j) ) for all i k j i j On Sat, Oct 12, 2013 at 12:54 PM, kumar raja rajkumar.cs...@gmail.comwrote: I was not able to figure out the solution to the problem in CLRS book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10 (say size of this set is k), then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30. So the task is to find out which sequence gives the minimum cost and what is that sequence out of k! possible sequences. I have seen the solutions in stack overflow using divide and conquer, but i would like to know how to solve this problem using DP. Someother solutions in the web shows it can be solved in O(n^3) or O(n^2) but no where i have seen the sub problem(Optimal substructure) defined. I was not able to identify sub problems and make a recurrence relation out of it.Can someone please throw light on this? I just want to develop approach to solve the DP problems. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Breaking a string problem (Dynamic programming)
I was not able to figure out the solution to the problem in CLRS book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10 (say size of this set is k), then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30. So the task is to find out which sequence gives the minimum cost and what is that sequence out of k! possible sequences. I have seen the solutions in stack overflow using divide and conquer, but i would like to know how to solve this problem using DP. Someother solutions in the web shows it can be solved in O(n^3) or O(n^2) but no where i have seen the sub problem(Optimal substructure) defined. I was not able to identify sub problems and make a recurrence relation out of it.Can someone please throw light on this? I just want to develop approach to solve the DP problems. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Find the max element of sets of size K
I heard there exists a O(n) algorithm in DP? Does anyone has the idea about it? On 11 September 2013 03:21, Aaquib Javed aaquib8...@gmail.com wrote: http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/ On Tue, Sep 10, 2013 at 11:46 PM, kumar raja rajkumar.cs...@gmail.comwrote: suppose we have n numbers and k =n. Then a1,a2... ak is one set. then a2,a3 ak+1 is other set. ... so totally we can have n-k+1 sets. how to figure out the maximum elements of all these k size sets with least possible time complexity and space complexity? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- Aaquib Javed B.Tech. Final Year Electronics Comm Engineering MNNIT Allahabad. +91-8953519834 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Find the max element of sets of size K
suppose we have n numbers and k =n. Then a1,a2... ak is one set. then a2,a3 ak+1 is other set. ... so totally we can have n-k+1 sets. how to figure out the maximum elements of all these k size sets with least possible time complexity and space complexity? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Forums on android
This is an off topic , but because still i am in very need of it i am asking. i have joined in stackoverflow forum, but now it is not letting me to ask questions as i have posted some inferior quality questions in it. But i have asked a lot of questions because i am new to android coding. now i am really in a need of some forum/ good group which is interactive and let me post my queries to get answers from geeks like this group. please suggest me some of them. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Forums on android
Reply me soon On 14 February 2012 12:32, kumar raja rajkumar.cs...@gmail.com wrote: This is an off topic , but because still i am in very need of it i am asking. i have joined in stackoverflow forum, but now it is not letting me to ask questions as i have posted some inferior quality questions in it. But i have asked a lot of questions because i am new to android coding. now i am really in a need of some forum/ good group which is interactive and let me post my queries to get answers from geeks like this group. please suggest me some of them. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Thanks to Algogeeks
I am selected in Oracle Server Technologies today The questions are not much from algorithms But i have learned a lot of things from this group on algorithms Especially Dave sir Thanks once again -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Thanks to Algogeeks
Thank u sir On 5 December 2011 09:27, Dave dave_and_da...@juno.com wrote: @Kumar. Congratulations. Happy to be of help. Dave On Dec 4, 12:49 pm, kumar raja rajkumar.cs...@gmail.com wrote: I am selected in Oracle Server Technologies today The questions are not much from algorithms But i have learned a lot of things from this group on algorithms Especially Dave sir Thanks once again -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Removing Duplicates In array and Linked list
@Karthikeyan: I want linear time solution not nlogn On 1 December 2011 23:42, Karthikeyan V.B kartmu...@gmail.com wrote: Hi, Create a binary search tree with elements , while inserting check for equal elements and delete it. But for insertion of n elements in a BST takes 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Removing Duplicates In array and Linked list
1) In there any way to remove duplicates in Integer array in linear time using constant space?? i dont want the Hash based solution 2) Is there anyway to remove the duplicates elements from an unsorted linked list in * Single Pass*??? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Removing Duplicates In array and Linked list
Please help me in solving above quesitons On 1 December 2011 08:33, kumar raja rajkumar.cs...@gmail.com wrote: 1) In there any way to remove duplicates in Integer array in linear time using constant space?? i dont want the Hash based solution 2) Is there anyway to remove the duplicates elements from an unsorted linked list in * Single Pass*??? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Pattern matching
string pattern matching with reg exp. ex: str : abccdefpattern : bc*dk* should return true; because bccd is subset of str. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Pattern matching
@harry It is not about using existing regexp matching techniques You have to design ur own technique using existing Pattern matching algorithms to handle this stuff... On 29 November 2011 06:35, hary rathor harry.rat...@gmail.com wrote: specify language . if in c then first write code in lex then compile it after that you will got your c code. if in java then you can use regex class for such code . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] What is the difference between Reentrant and Thread Safe code ,please explain with example funcitons..
-- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Pattern matching
Can it be solved using Finite automata?? On 29 November 2011 06:46, kumar raja rajkumar.cs...@gmail.com wrote: @harry It is not about using existing regexp matching techniques You have to design ur own technique using existing Pattern matching algorithms to handle this stuff... On 29 November 2011 06:35, hary rathor harry.rat...@gmail.com wrote: specify language . if in c then first write code in lex then compile it after that you will got your c code. if in java then you can use regex class for such code . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Finding frequent words
You get a stream of words, find top m frequent words. What are all the possible approaches for this problem ?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Finding Minimum Triplet
Given three arrays, find the triplet (containing one element from each array) with the minimum distance. The distance of a triplet (a,b,c) is defined is max(|a-b|, |b-c|, |c-a|) -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding Minimum Triplet
Thanku sir... On 29 November 2011 10:20, Dave dave_and_da...@juno.com wrote: @Kumar: Let the three arrays be a, b, and c, of lengths na, nb, and nc, respectively. Sort each array. Set ia = 0, ib = 0, ic = 0. Record the triplet (a[0], b[0], c[0]) as the best so far. Loop Increment the index corresponding to the smaller of a[ia], b[ib], and c[ic]. If the incremented index reaches its corresponding length, break the loop. If the new (a[ia], b[ib], c[ic]) is better than the best so far, update the best so far. End loop O(n log n), where n = max(na,nb,nc). Dave On Nov 29, 11:42 am, kumar raja rajkumar.cs...@gmail.com wrote: Given three arrays, find the triplet (containing one element from each array) with the minimum distance. The distance of a triplet (a,b,c) is defined is max(|a-b|, |b-c|, |c-a|) -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding frequent words
@Anup: How splay trees come into picture here?? I think TRIE or Hashtable will work out. But it is difficult to conceive the TRIE solutions and explain it to the Interviewer .so i am looking for something else better and concrete one. On 29 November 2011 08:50, Anup Ghatage ghat...@gmail.com wrote: Splay trees On Tue, Nov 29, 2011 at 10:07 PM, kumar raja rajkumar.cs...@gmail.comwrote: You get a stream of words, find top m frequent words. What are all the possible approaches for this problem ?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding Minimum Triplet
he distance of a triplet (a,b,c) is defined is *max*(|a-b|, |b-c|, |c-a|) is the correct one... On 29 November 2011 11:09, atul anand atul.87fri...@gmail.com wrote: @Raja : distance is defined as The distance of a triplet (a,b,c) is defined is *max*(|a-b|, |b-c|, |c-a|) OR The distance of a triplet (a,b,c) is defined is *min*(|a-b|, |b-c|, |c-a|) On Tue, Nov 29, 2011 at 11:50 PM, Dave dave_and_da...@juno.com wrote: @Kumar: Let the three arrays be a, b, and c, of lengths na, nb, and nc, respectively. Sort each array. Set ia = 0, ib = 0, ic = 0. Record the triplet (a[0], b[0], c[0]) as the best so far. Loop Increment the index corresponding to the smaller of a[ia], b[ib], and c[ic]. If the incremented index reaches its corresponding length, break the loop. If the new (a[ia], b[ib], c[ic]) is better than the best so far, update the best so far. End loop O(n log n), where n = max(na,nb,nc). Dave On Nov 29, 11:42 am, kumar raja rajkumar.cs...@gmail.com wrote: Given three arrays, find the triplet (containing one element from each array) with the minimum distance. The distance of a triplet (a,b,c) is defined is max(|a-b|, |b-c|, |c-a|) -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] What is the difference between portability and Platform Independence??
-- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] One small doubt??
Can someone explain the following terms and their differences clearly? 1) Array and List 2) Ordered array and Unordered Array 3) Ordered List and Unordered List -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] One small doubt??
So does list can be a linked list or similar data structure , right?? On 27 November 2011 11:17, saurabh singh saurab...@gmail.com wrote: ans 1) Array is a *contigous elements.*The elements of a list need not be contigous. ans 2)Ordered array is one in which the position of elements in array is constrained by some property.For example a sorted array where the property is relative magnitude of the element.In an unordered array the position of elements in the array is not constrained by anything i.e. given the position of an element in the array you cant say anything about it with reference to other elements.same goes for list. On Sun, Nov 27, 2011 at 10:07 AM, kumar raja rajkumar.cs...@gmail.comwrote: Can someone explain the following terms and their differences clearly? 1) Array and List 2) Ordered array and Unordered Array 3) Ordered List and Unordered List -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Threaded binary tree
How to convert a given binary tree into threaded binary tree?? what is the algorithm... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Threaded binary tree
Thanks Gene On 25 November 2011 04:28, Gene gene.ress...@gmail.com wrote: Perhaps the simplest way is to do a normal inorder traversal and, as you visit nodes, keep track of the last one visited in an external (global or class) variable. When you visit a new node and the last node has a NULL right child pointer, you can update it with the new node. If the new node has a NULL left child pointer, you can update it with the last node. // UNTESTED! // Last tree node visited in order static NODE *last; // local recursive tree walk static void do_enthreading(NODE *tree) { if (tree-left) do_enthreading(tree-left); else { tree-left_child_is_thread = TRUE; tree-left = last; } if (last last-right == NULL) { last-right_child_is_thread = TRUE; last-right = tree; } last = tree; if (tree-right) do_enthreading(tree-right) } // Start the recursion and clean up afterward. void enthread_tree(NODE *tree) { if (tree) { last = NULL; do_enthreading(tree); last-right_child_is_thread = TRUE; } } On Nov 25, 5:55 am, kumar raja rajkumar.cs...@gmail.com wrote: How to convert a given binary tree into threaded binary tree?? what is the algorithm... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding the repeated element
@kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
http://www.geeksforgeeks.org/archives/8858 On 24 November 2011 01:06, Ankuj Gupta ankuj2...@gmail.com wrote: Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding the repeated element
@ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding the repeated element
@shady : i am not sure , if u can do it with O(n) space as well it is fine for me . but once try whether it is possible in O(1) space. On 24 November 2011 05:42, shady sinv...@gmail.com wrote: find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Xor Linked lists
http://en.wikipedia.org/wiki/XOR_linked_list In this link i have seen about Xor linked list ,but my doubt is how will u perform xor on Address of nodes. I have tried to perform xor on addresses of two values ,so how is it possible to use that technique. Also tell me whether there are any extra rules to follow during insert,delete and search -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding the repeated element
@kunzmilan : Can u please maintain the clarity ?? How did u find the M if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it... On 24 November 2011 06:15, kunzmilan kunzmi...@atlas.cz wrote: On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding the repeated element
@Anup: Atleast u tell me how the M has formed??? On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com wrote: @kunzmilan Nice idea, how do you decide the row-size or column-size of the matrix? On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote: @kunzmilan : Can u please maintain the clarity ?? How did u find the M if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it... On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote: On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Maximize Subsquare
@Dark prince : what is meant by Allones(i,0.k) what subsquare he is considering here?? On 22 November 2011 23:57, DarkPrince darkprince...@gmail.com wrote: It means that the Borders of the mavximum rectangle should hav all 1s irrespective the elements inside the rectangles , it can be either 0 or 1 . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Finding the repeated element
In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the repeated element
@ankit : I think ur solution does not work because if the array is 4 2 8 9 5 1 9 sorting: 1 2 4 5 8 9 9 median is 5 ,but i want 9 as the answer that to median finding algorithm is O( n logn). On 23 November 2011 23:09, Ankit Sinha akki12...@gmail.com wrote: Only possible best solution seems to be sorting the array using median selection algorithm ( a varient of quicksort) and then comparing to find the elements. Cheers, Ankit!!! On Thu, Nov 24, 2011 at 11:32 AM, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Maximize Subsquare
@Vikas : what is the meaning of Allones function?? On 8 November 2011 15:13, Chunyuan Ge hhy...@gmail.com wrote: Say you define ur matrix in M then if (M(i,j) = 1) Sq(i,j) = min(Sq(i-1,j),Sq(i-1,j-1),Sq(i, j-1)) + 1 else Sq(i,j) = 0 On Tue, Nov 8, 2011 at 7:27 AM, vikas vikas.rastogi2...@gmail.com wrote: try this: sq(i, j)= k is maximum sqare possible ending at i, j and has length k in the matrix iXj sq(i, j) = k if {sq( i -1, j-1) AllOnes(i,0, k) AllOnes(0, j, k)} = 1 if sq(i, j) == 1 = 0 otherwise On Oct 31, 10:36 pm, SAMM somnath.nit...@gmail.com wrote: Any body got any idea of just how to approach It need a DP algo. On 10/30/11, SAMMM somnath.nit...@gmail.com wrote: Suppose u have a square matrix, where every cell is filled with 0 or 1 . U need to find the maximum subsquare such that all four borders are filled with all 1s. Ex:- 1 0 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 1 Here the maximum square (3X3) possible is from the TOP LEFT (2 3) TO BOTTOM RIGHT (4 5) . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Soritng
@Dave: let us leave about Radix sort ,for it there are specific constraints on the numbers. @Amol sharma: i dont know what is cycle sort? Convey your answer in well known sorting methods. Ankur garg:In the phase of merging it compares the sorted sub arrays to merge them .So it is not correct.. On 20 November 2011 22:56, Amol Sharma amolsharm...@gmail.com wrote: quoted from wiki While selection sort is preferable to insertion sort in terms of number of writes (Θ(*n*) swaps versus Ο(*n*2) swaps), it almost always far exceeds (and never beats) the number of writes that cycle sorthttp://en.wikipedia.org/wiki/Cycle_sortmakes, as cycle sort is theoretically optimal in the number of writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM http://en.wikipedia.org/wiki/EEPROM or Flashhttp://en.wikipedia.org/wiki/Flash_memorymemory, where every write lessens the lifespan of the memory. so i think answer for the second will be cycle sort -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99 On Mon, Nov 21, 2011 at 12:15 PM, Ankur Garg ankurga...@gmail.com wrote: I think Merge Sort doesnt require any swapping . So , for 3 my answer wud be Merge Sort On Mon, Nov 21, 2011 at 11:55 AM, Dave dave_and_da...@juno.com wrote: @Kumar: For question 1, the answer is radix sort. It doesn't use data comparisons at all. Dave On Nov 21, 12:04 am, kumar raja rajkumar.cs...@gmail.com wrote: if we have set of n elements then 1) which sorting method uses least number of comparisons?? 2) which sorting method uses least number of swaps?? 3) suppose the array is 2 8 4 6 5 9 if we want to swap 8 and 5 the cost is 2(5-2)=6 .here 5 and 2 are indices of 5 and 8. so what sorting method minimizes the cost, i want the answer in general case ,not for this particular array. it is also called least distance sorting -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] K-way merging...
Is k-way merging works same as Heap merging method or using tournament tree?? But how to construct a tournament tree in the programming?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Soritng
if we have set of n elements then 1) which sorting method uses least number of comparisons?? 2) which sorting method uses least number of swaps?? 3) suppose the array is 2 8 4 6 5 9 if we want to swap 8 and 5 the cost is 2(5-2)=6 .here 5 and 2 are indices of 5 and 8. so what sorting method minimizes the cost, i want the answer in general case ,not for this particular array. it is also called least distance sorting -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] what will be the focus of yahoo in written exam ,what to study for it. please respond ASAP..
-- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Does anyone know the written pattern of Amazon??
-- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Finding the indexes of a repeated element??
How to find the indexes of a repeated element in the sorted array in *log n*time.. e.g. a: 1 3 4 4 5 6 7 8 8 9 9 9 10 x=9 ouput is 10 and 12 (indexing from 1) -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] About suffix trees and suffix arrays
I have studied about it ,but could not understand why their construction is in linear time and support so many operations with less time complexity. i am quite confused. suggest me some good resource to learn about them with proper proof of time complexity for each and every operation.. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Does anyone know the written pattern of Amazon??
Thanks rahul On 8 November 2011 03:32, rahul sharma rahul23111...@gmail.com wrote: apti + technical + 3 prog (mainly linked list) On Tue, Nov 8, 2011 at 3:09 PM, kumar raja rajkumar.cs...@gmail.comwrote: -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a node of BST make it the root
@Dave : Wonderful answer sir.. On 31 October 2011 12:50, Dave dave_and_da...@juno.com wrote: @Ankuj: Your method would be O(n), where n is the number of nodes in the tree. However, it can be done with a sequence of tree rotations. If the desired node is not the root of the tree, rotate it with its parent. This preserves the BST property and makes the desired node one level closer to the root. A rotation can be done in constant time, so the work required is O(original level of the node), which would be O(log n) if the tree happened to be balanced. See http://en.wikipedia.org/wiki/Tree_rotation for algorithmic details. Dave On Oct 31, 11:43 am, Ankuj Gupta ankuj2...@gmail.com wrote: Given a node of a BST, modify it in such a way that the given node becomes the root. The tree should still be BST. One way I could get is store the Inoder traversal of the tree. Find that node in the traversal and recursively make the BST. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Intersection of arrays
How is it possible to create a hash map using elements as keys and their counts as values .If we give some key the value is automatically computed by hash function .If u are given an element/key its index/value is calculated by hash function.am i corrct?? On 27 October 2011 22:36, Nitin Garg nitin.garg.i...@gmail.com wrote: The hashing solution is similar to the 1st answer herehttp://stackoverflow.com/questions/2932979/find-a-common-element-within-n-arrays A sorting solution will take O(k.n.logn) time On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage ghat...@gmail.com wrote: Don, As you said, the intersection set, won't really be in sorted order as it depends on the elements of the second array, which are unsorted. Still, sorting them wouldn't be much different as it'd be worst case O(n logn).. [ Array 2 == Array 1 ] But sorting the First Array has already cost O(n logn) So I guess the worse case complexity has to be O(n logn) anyway.. On Thu, Oct 27, 2011 at 10:54 PM, Dan dant...@aol.com wrote: Hashing all of the K arrays seems like a bit much. How about this? You have K seperate arrays to start with, each array having N elements (is that correct?). 1) Sort the first array. 2) Step through the 2nd array, 1 element at a time say Array(2).element(i) Check to see if the value of Array(2).element(i) is in the first sorted array. If it is, add this numeric value to your list of intersection elements. As you pass through all elements of the 2nd array, the values found which are intersecting need to be saved ( maybe in the 1st arrays space to save memory). Ideally, these should be saved in sorted order as they are found. ( how you store the sorted array will affect speed of this check of course. I'd keep it simple on the 1st round, then optimize the code once everything appears to be working well, ie with buckets or pointers or whatever. How you determine if an element in array 2 intersects with an element of array 1 will depend on how you store your sorted array. You might do a linear search or a binary search or a bucket search of some sort ). 3) Now... step through the 3rd array, 1 element at a time, looking to see if each value is in the just created list of intersection elements 4) Do the save thing now with each of the remaining original K arrays. Dan:-) On Oct 24, 10:17 pm, kumar raja rajkumar.cs...@gmail.com wrote: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
suppose the problem is Problem 4: Find all unique pairs of element in an array that sum to S. For ex. If array = {2,4,6,4,6} and S = 8 then answer is {2,6, 4,4} suppose we use STL c++ hash class to solve the problem . In the first we hash all the elements . in the second pass we take each element and subtract it from '8' and then we search for that difference in the hash table. if it is found then the pair exists .otherwise it does not exist. My questions are 1) What is the space complexity used by hash table . is it O(n) becoz 'n' elements are hashed into hash table. 2) Does the time to search an element is hash table is still O(1) ,but there are 'n' elements in hash table .Then how could it be O(1) Please clear my above doubts .These doubts are haunting me .I am very thankful to them ... On 27 October 2011 06:18, Prem Krishna Chettri hprem...@gmail.com wrote: If N Element is already hashed and when you insert next element , Does hashing will take log N time to find the next available position? Actually the next insertion typically does not have any co-relation to pre-existing table content (Until your Hash function is badly designed to hash always on the same key everytime). So, its actually the design of Hash that has to be efficient.Hence every operation cannot be mapped to the number of data which is present in the existing table. On Thu, Oct 27, 2011 at 12:49 AM, ligerdave david.c...@gmail.com wrote: from high level and with a very few collisions, it's O(1). there isn't much to prove because this is based on a common sense. for example, have the world as a hashtable and all countries as the keys of it. boxes(storage) marked by different country names(key) and you know where to locate them. now, you are given a mail and asked to put it into the box which goes to its destination country. so how many operations does it take you to put a mail in the box? 1 if you realized the mail wasn't misplaced and you need to take it out, how many operations does it take you to take the mail out of the box? i hope this helps a bit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ZamCyJETdscJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
@Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G_0Wm4NQIyIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
I am asking for the above quesiton On 27 October 2011 07:38, kumar raja rajkumar.cs...@gmail.com wrote: @Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G_0Wm4NQIyIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Intersection of arrays
Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Intersection of arrays
Dheeraj can u please tell me how to keep track count for an element ,in hash table. I want the exact structure of the hash table The hash function uses the input as the elements value ,and stores it in some slot by computing hash function..then where is the question of storing count for that number. I am pretty much confused with this hashing and how these details are exactly implemented in STL hash map class. On 24 October 2011 23:32, Dheeraj Sharma dheerajsharma1...@gmail.comwrote: use hashing.. let the no. of array be 1 to K increment the count of element for that array..(in hash table) only if its count value in hash table is one less then the array no.(which means that..it is present in all the arrays..preceding it) now search the hash table..in which element count is equal to K On Tue, Oct 25, 2011 at 11:47 AM, kumar raja rajkumar.cs...@gmail.comwrote: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Questions on Hashing ...Share ur ideas...
Problem 1: Remove duplicate elements from an unsorted array of size N Problem 2: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. Problem 3: How to make a linked list support operations in O(1) time. The operations on linked list can be insertion after any arbitrary valued node, deletion of any arbitrary valued node Problem 4: Find all unique pairs of element in an array that sum to S. For ex. If array = {2,4,6,4,6} and S = 8 then answer is {2,6, 4,4} Problem 5: Consider an array containing unique elements. Find a triplet of elements in the array that sum to S (extension of problem 4). Can hashtables improve the running time of your algorithm. Problem 6: Consider two strings of size M, N. Perform string matching in size O(M+N). Problem 7: Find top K most frequent elements in an array of size N. Problem 8: Given a file with N integers. Find top K most frequent integers. Assume N to be very large such that all the N numbers cannot fit into memory. Design for the worst case. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Intersection of arrays
I have got an idea I will construct (k-1) hash tables for the 2 to k array elements. Now starting at the 1st element in 1st array i will search for it in all the (k-1) hash tables in O((k-1)*1) time. So for n elements it would take O( n*(k-1)) time.. Is my approach correct,please correct me if i am wrong... and two questions which are bothering me are 1)Does the space complexity in hash table to store all the 'n' elements is O(n) ?? i want the correct value. 2)what is the time complexity to search in hash table if 'n' numbers are stored .Is it still O(1) ??? i dont know how it is O(1) exactly it is a guess. On 24 October 2011 23:32, Dheeraj Sharma dheerajsharma1...@gmail.comwrote: use hashing.. let the no. of array be 1 to K increment the count of element for that array..(in hash table) only if its count value in hash table is one less then the array no.(which means that..it is present in all the arrays..preceding it) now search the hash table..in which element count is equal to K On Tue, Oct 25, 2011 at 11:47 AM, kumar raja rajkumar.cs...@gmail.comwrote: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Hash Table
I have read that Hash table provides storing/search operations in constant time. Is it true?? How to prove it?? I have not found any sort of proof for it... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Hash Table
When the number of elements increases gradually ,the complexity must increase .so it the situtaion is like it has to store all the 'n' elements then all the basic operations require O(log n) time.so how it is constant always i am not getting... On 24 October 2011 22:15, kumar raja rajkumar.cs...@gmail.com wrote: I have read that Hash table provides storing/search operations in constant time. Is it true?? How to prove it?? I have not found any sort of proof for it... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Code it...
Can someone give me an idea about how to see the range of segments like data ,heap,stack and text segments of an executable file.(a.out) Is there anyway to access the those segments from the program itself (while in execution), like using stack pointer for stack segment ?? On 18 October 2011 19:54, sravanreddy001 sravanreddy...@gmail.com wrote: @Don, Gene: very good insights, didn't even thought of the changing the executable, but it indeed is one way to do. :) @Don: agree with scripts and interpreted code.. :) [coming out of the same language helps answers some questions easily] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ONw7a6q9VRMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Code it...
you have to write a program which tell about how many times it has run. ex: if you run first time it will print 1. if you run second time it will print 2. like this. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] I want Pointers in C ebook. please forward it
-- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] THANX ALGOGEEKS !!!!!!
Congrats dude... On 22 September 2011 07:29, saurabh sah.saurab...@gmail.com wrote: I sincerely thank this group as i got selected in Microsoft IDC only because of this group . It was a wonderful experience for me at the interviews because the some of questions were closely related to the questions discussed here . And i also got to know about book Crackin the Coding Interviews which is more than sufficient for any company interviews from this group only . Finally i thank all those group members who shared their experiences and others who replied to their queries . GOOD LUCK to all Saurabh Sah Final Year, B.Tech MNIT JAIPUR -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Permuations and Combinations
(1) What is the efficient approach to generate permutations of a given sequence of numbers (may contain duplicates) in lexicographic order e.g. i/p: 5,1,6,1 o/p: 1 1 5 6 1 1 6 5 1 5 1 6 1 5 6 1 1 6 1 5 1 6 5 1 5 1 1 6 5 1 6 1 5 6 1 1 6 1 1 5 6 1 5 1 6 5 1 1 what is the time complexity of ur approach?/ (2)What is the efficient approach to generate combinations of a given sequence of numbers (may contain duplicates) in lexicographic order e.g. i/p: {3,2 ,1,5,1,7} and k=2 (2-size subsets) o/p: 1 1 1 2 1 3 1 5 1 7 2 3 2 5 2 7 3 5 3 7 5 7 ( {5,7} is same as {7,5} because it is a selection). what is the time complexity of the algorithm?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] I want resources to learn algorithms on Permutation and Combination problems and Graph algorithms except CLRS..
-- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] output
main(){printf(%s,printf(samsung)+fun());}fun(){return electronic;} The printf is a function which returns the number of printed characters , and scanf is a function which returns the number of inputs scanned . So after printing samsung it returns 7. fun() is returning a pointer to the constant string electronic , so it is like 7[electronic] so the %s prints that string from the 7th index onwards till end . So output is nic so the total output is samsungnic but i dont know why it is exiting with some error code.. On 13 September 2011 10:51, Rajeshwar Patra rajeshwarpa...@gmail.comwrote: http://codepad.org/erdnF74M can anyone explain the output ??? -- *Rajeshwar Patra,* *MCA final year,* *Nit Durgapur* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Exchanging bit values in a number
Suppose a number 'n' is given and two bits positions i,j present in binary representation of n . Then how to exchange the contents of the two bits i and j. E.g. n= 13 its binary representation is 1101 (just for now consider 8 bit number) i= 2,j=6 o/p : 0100 1001 = 73 please suggest some effective way to do this... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Exchanging bit values in a number
@Dave and Gene I am totally awkward at ur solutions ...How did u develop these solutions?? . Can u please quote some material/book on this topic.. On 13 September 2011 12:18, Sandy sandy.wad...@gmail.com wrote: @Ankit. n= 1101 i=2 j=3 x = (2^j + 2^i) = 1100 x^n = 0001 Answer should be 1101. On Wed, Sep 14, 2011 at 12:39 AM, Ankit Agarwal ankuagarw...@gmail.comwrote: let x = 2^j + 2 ^i new number after swapping the digits is x XOR n eg n = 1101 j = 6 i = 2 x = 0100 0100 new number = x XOR n = 0100 1001 -- Ankit Agarwal Computer Science Engg. Integrated Dual Degree, V yr Department of Electronics Computer Engineering Indian Institute of Technology Roorkee Ph. no. +91-9580098805 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Exchanging bit values in a number
@Dave and Gene sorry , i mean ur solutions are brilliant ,but i did not get those kind of ideas till now.. On 13 September 2011 12:31, kumar raja rajkumar.cs...@gmail.com wrote: @Dave and Gene I am totally awkward at ur solutions ...How did u develop these solutions?? . Can u please quote some material/book on this topic.. On 13 September 2011 12:18, Sandy sandy.wad...@gmail.com wrote: @Ankit. n= 1101 i=2 j=3 x = (2^j + 2^i) = 1100 x^n = 0001 Answer should be 1101. On Wed, Sep 14, 2011 at 12:39 AM, Ankit Agarwal ankuagarw...@gmail.comwrote: let x = 2^j + 2 ^i new number after swapping the digits is x XOR n eg n = 1101 j = 6 i = 2 x = 0100 0100 new number = x XOR n = 0100 1001 -- Ankit Agarwal Computer Science Engg. Integrated Dual Degree, V yr Department of Electronics Computer Engineering Indian Institute of Technology Roorkee Ph. no. +91-9580098805 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Sandeep Kumar,* ( Mobile +91-9866507368 *“I believe in smart work, Believe Me”* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Circular Left shift
Given an array of 'n' values you need to circular shift it 'k' times towards left. Input : 9 7 6 5 3 23 14 2 4 output : 5 3 23 14 2 4 9 7 6 n=9 , k= 3 constraints : Time complexity O(n) Space complexity O(1) The solutions with O(kn) time complexity and O(n) complexity with O(k) space complexity are already available. I want the O(n) solution with constant space.. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Circular Left shift
U have used c[3] extra array.It is already known solution. so it is using O(k) space .i want the solution with constant space.. On 10 September 2011 02:08, Ishan Aggarwal ishan.aggarwal.1...@gmail.comwrote: Solution :- void main(){int a[9]= {9,7,6,5,3,23,14,2,4} ;int n = 3;int c[3];int i;int k =0;for ( i=0;i3;i++) c[i]= a[i];for(i=3;i9;i++) a[i-3] =a[i];for(i=9-3;i9;i++) a[i] = c[k++];for(i=0;i9;i++)printf http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(\n%d,a[i]);} On Sat, Sep 10, 2011 at 2:09 PM, kumar raja rajkumar.cs...@gmail.comwrote: Given an array of 'n' values you need to circular shift it 'k' times towards left. Input : 9 7 6 5 3 23 14 2 4 output : 5 3 23 14 2 4 9 7 6 n=9 , k= 3 constraints : Time complexity O(n) Space complexity O(1) The solutions with O(kn) time complexity and O(n) complexity with O(k) space complexity are already available. I want the O(n) solution with constant space.. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Kind Regards Ishan Aggarwal [image: Aricent Group] Presidency Tower-A, M.G.Road,Sector-14 Gurgaon,Haryana.122015 INDIA Phone : +91-9654602663 ishan2.aggar...@aricent.com puneet.ar...@aricent.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Circular Left shift
@sarath: I did not get u .Could u please explain it with the example. On 10 September 2011 03:39, sarath prasath prasathsar...@gmail.com wrote: consider this approach.. first reverse the entire array... so it will be.. 4,2,14,23,3,5,6,7,9 and u want to shift k times right so u have to cut the array as n-k and reverse both the sides u ll get it.. so in ur scenario we are reversing upto the element 5 in array and reversing the remaining elements.. hope the complexity is of o(n).. On Sat, Sep 10, 2011 at 3:17 PM, kumar raja rajkumar.cs...@gmail.comwrote: U have used c[3] extra array.It is already known solution. so it is using O(k) space .i want the solution with constant space.. On 10 September 2011 02:08, Ishan Aggarwal ishan.aggarwal.1...@gmail.com wrote: Solution :- void main(){int a[9]= {9,7,6,5,3,23,14,2,4} ;int n = 3;int c[3];int i;int k =0;for ( i=0;i3;i++) c[i]= a[i];for(i=3;i9;i++) a[i-3] =a[i];for(i=9-3;i9;i++) a[i] = c[k++];for(i=0;i9;i++)printf http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(\n%d,a[i]);} On Sat, Sep 10, 2011 at 2:09 PM, kumar raja rajkumar.cs...@gmail.comwrote: Given an array of 'n' values you need to circular shift it 'k' times towards left. Input : 9 7 6 5 3 23 14 2 4 output : 5 3 23 14 2 4 9 7 6 n=9 , k= 3 constraints : Time complexity O(n) Space complexity O(1) The solutions with O(kn) time complexity and O(n) complexity with O(k) space complexity are already available. I want the O(n) solution with constant space.. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Kind Regards Ishan Aggarwal [image: Aricent Group] Presidency Tower-A, M.G.Road,Sector-14 Gurgaon,Haryana.122015 INDIA Phone : +91-9654602663 ishan2.aggar...@aricent.com puneet.ar...@aricent.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Circular Left shift
Ur idea does not work in the following case array : 7 5 3 6 9 2 11 n=7 and k=3 as per your explanation the answer would come 9 2 11 6 7 5 3 correct me if i am wrong... On 10 September 2011 04:54, bharatkumar bagana bagana.bharatku...@gmail.com wrote: swap k elements form 1 to k and n-k to n respectively... ex: k=3 temp=k; int a[9]= {9,7,6,5,3,23,14,2,4} ; has become {14,2,4,5,3,23,9,7,6}; now swap first k elements with k+1 to 2k elements ...now k=2k+1 , do this step again up to (kn-temp)... at last {5,3,23,14,2,4,9,7,6,} ; Time :O(n) and space O(1). On Sat, Sep 10, 2011 at 7:15 AM, kumar raja rajkumar.cs...@gmail.comwrote: @sarath: I did not get u .Could u please explain it with the example. On 10 September 2011 03:39, sarath prasath prasathsar...@gmail.comwrote: consider this approach.. first reverse the entire array... so it will be.. 4,2,14,23,3,5,6,7,9 and u want to shift k times right so u have to cut the array as n-k and reverse both the sides u ll get it.. so in ur scenario we are reversing upto the element 5 in array and reversing the remaining elements.. hope the complexity is of o(n).. On Sat, Sep 10, 2011 at 3:17 PM, kumar raja rajkumar.cs...@gmail.comwrote: U have used c[3] extra array.It is already known solution. so it is using O(k) space .i want the solution with constant space.. On 10 September 2011 02:08, Ishan Aggarwal ishan.aggarwal.1...@gmail.com wrote: Solution :- void main(){int a[9]= {9,7,6,5,3,23,14,2,4} ;int n = 3;int c[3];int i;int k =0;for ( i=0;i3;i++) c[i]= a[i];for(i=3;i9;i++) a[i-3] =a[i];for(i=9-3;i9;i++) a[i] = c[k++];for(i=0;i9;i++)printf http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(\n%d,a[i]);} On Sat, Sep 10, 2011 at 2:09 PM, kumar raja rajkumar.cs...@gmail.comwrote: Given an array of 'n' values you need to circular shift it 'k' times towards left. Input : 9 7 6 5 3 23 14 2 4 output : 5 3 23 14 2 4 9 7 6 n=9 , k= 3 constraints : Time complexity O(n) Space complexity O(1) The solutions with O(kn) time complexity and O(n) complexity with O(k) space complexity are already available. I want the O(n) solution with constant space.. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Kind Regards Ishan Aggarwal [image: Aricent Group] Presidency Tower-A, M.G.Road,Sector-14 Gurgaon,Haryana.122015 INDIA Phone : +91-9654602663 ishan2.aggar...@aricent.com puneet.ar...@aricent.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email
[algogeeks] Process memory Layout
char *p= hello world; When we try to modify the above string it will raise an error. I heard that the String constant is stored in the Data segment of the process . The data segment consists of two parts . 1)Initialized data segment 2)Uninitialized data segment If we use some other global variable in the same program say static int i=10; But it could be modified at later.So why not the string constant cant be modified??? Someone said that it is stored in Text/Code segment . I think thats wrong . the Text segment is only a set of machine instructions to execute the program ,but does not contain any data values. So, Where the above String constant is stored and why it cant be altered??? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Process memory Layout
What i am saying is if i write it like p[5]= 'a'; Then the compiler will raise an error . Because the memory where the string constant Hello world gets stored is read only. But it i do it like char s[] = hello world,*p; p=s; p[5]='a'; It is valid becoz the string is now stored in stack segment of program . So my doubt is where the string constant gets stored exactly in the first case...and why it cant be altered.. On 21 August 2011 22:06, Sanjay Rajpal srn...@gmail.com wrote: You can change the pointer only, not the content. But in case of static int, u can also change the value also. if u specify const, u can't change the value then. Sanju :) On Sun, Aug 21, 2011 at 9:56 PM, Dave dave_and_da...@juno.com wrote: @Kumar: You've declared a pointer, and you can change the pointer, just as in int i=10 declares an integer that you can change. Dave On Aug 21, 11:28 pm, kumar raja rajkumar.cs...@gmail.com wrote: char *p= hello world; When we try to modify the above string it will raise an error. I heard that the String constant is stored in the Data segment of the process . The data segment consists of two parts . 1)Initialized data segment 2)Uninitialized data segment If we use some other global variable in the same program say static int i=10; But it could be modified at later.So why not the string constant cant be modified??? Someone said that it is stored in Text/Code segment . I think thats wrong . the Text segment is only a set of machine instructions to execute the program ,but does not contain any data values. So, Where the above String constant is stored and why it cant be altered??? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.