[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
Monish, please take a look at a similar problem about poor elephants in the neighboring topic started today. I believe the problem has a similar solution. Each start point increases the no. of active intervals by one; each end point decreases it. So, we do the following: 1. Convert the input array of pairs (BTW, the points don't have to be of an integral type!) into the following vector: { {2,+1}, {3,-1}, {3, +1}, {4, -1}...} This takes O(N) time and O(N) additional memory 2. Sort the vector by: a) ascending .first; b) descending .second -- this makes sure we count the intervals properly in case multiple intervals start and end at the same point. Complexity is O(N*logN). 3. Convert relative counters to absolute; complexity is O(N). int count = 0; for (int i = 0; i v.size(); ++i) { count += v.second; assert (count =0); v.second = count; } assert (count == 0); 4. After this preparation work ( O(N*logN) time, O(N) memory), answering the question about the number of intervals for any numbers takes O(logN) -- use lower_bound() to binary search in the sorted vector. On Sunday, June 9, 2013 3:20:46 AM UTC-4, Monish Gupta wrote: There are n Intervals. Given a set of m numbers, tell in how many intervals does each number exists. Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11} For 2 - 1 as 2 lies only in 1 interval [2,3] For 4 - 3 as 4 lies in 3 intervals For 11 - 0 as 11 lies in none of the given 4 intervals. It can be easily done in O(m*n) by traversing n intervals for each number in the given set of m numbers. How would improve this? Note: I could not fully recall, but I have seen very similar question in codechef but could not find the same. -- 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: Google Interview Question: In how many intervals does a number exists
Can you tell the 'size' of your array 'f' if the intervals are [0, 10], [10, 9223372036854775808] ? Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the scripture of this age. On Mon, Jun 10, 2013 at 10:12 PM, sunny sharadsin...@gmail.com wrote: yeah interval tree and binary indexed tree is a one solution which will give you answer in log(n) time for each query ,but if i got all the interval at the beigning of time i can get solution in O(1) time by O(n ) preprocessing take array f initialize with zero,now for each interval(l,r) do f[l]++ and f[r+1]-- once you are done wi all queries take prefix sum value of each index will tell you in how many interval it was On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote: There are n Intervals. Given a set of m numbers, tell in how many intervals does each number exists. Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11} For 2 - 1 as 2 lies only in 1 interval [2,3] For 4 - 3 as 4 lies in 3 intervals For 11 - 0 as 11 lies in none of the given 4 intervals. It can be easily done in O(m*n) by traversing n intervals for each number in the given set of m numbers. How would improve this? Note: I could not fully recall, but I have seen very similar question in codechef but could not find the same. -- 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] Re: Google Interview Question: In how many intervals does a number exists
Adding to the question. See inline. On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote: There are n Intervals. *1 = n = 1,000,000.* *Limits of interval are within 64 bit signed int.* Given a set of m numbers, tell in how many intervals does each number exists. Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers 2,4,11 For 2 - 2 as 2 lies in *2* intervals. viz. [2,3], [1,4] For 4 - 3 as 4 lies in 3 intervals For 11 - 0 as 11 lies in none of the given 4 intervals. It can be easily done in O(m*n) by traversing n intervals for each number in the given set of m numbers. How would improve this? Note: I could not fully recall, but I have seen very similar question in codechef but could not find the same. -- 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] Re: Google Interview Question: In how many intervals does a number exists
yeah interval tree and binary indexed tree is a one solution which will give you answer in log(n) time for each query ,but if i got all the interval at the beigning of time i can get solution in O(1) time by O(n ) preprocessing take array f initialize with zero,now for each interval(l,r) do f[l]++ and f[r+1]-- once you are done wi all queries take prefix sum value of each index will tell you in how many interval it was On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote: There are n Intervals. Given a set of m numbers, tell in how many intervals does each number exists. Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11} For 2 - 1 as 2 lies only in 1 interval [2,3] For 4 - 3 as 4 lies in 3 intervals For 11 - 0 as 11 lies in none of the given 4 intervals. It can be easily done in O(m*n) by traversing n intervals for each number in the given set of m numbers. How would improve this? Note: I could not fully recall, but I have seen very similar question in codechef but could not find the same. -- 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] Re: Google Interview Question: In how many intervals does a number exists
typo mistake take prefix sum of f and see each index value...continue On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote: There are n Intervals. Given a set of m numbers, tell in how many intervals does each number exists. Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11} For 2 - 1 as 2 lies only in 1 interval [2,3] For 4 - 3 as 4 lies in 3 intervals For 11 - 0 as 11 lies in none of the given 4 intervals. It can be easily done in O(m*n) by traversing n intervals for each number in the given set of m numbers. How would improve this? Note: I could not fully recall, but I have seen very similar question in codechef but could not find the same. -- 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] Re: GOOGLE Q1
On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. Click on the following links or copy and paste them into your browser. Many interesting possibilities. https://www.google.com.au/search?client=ubuntuchannel=fsq=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1ie=utf-8oe=utf-8redir_esc=ei=GpQRUZXnJKaeiAen7oDYAw http://scholar.google.com/scholar?hl=enq=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.btnG=as_sdt=1%2C5as_sdtp= -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: GOOGLE Q1
In the first pass create a difference array of size n-1 where n is the size of the input array. D[i] = A[i+1] - A[i] Look for for the longest consecutive no. of times an element is repeated in the difference array. public void longestAP(int[] a, int n) { int[] diff = new int[n-1]; for(int i = 0; i n-1; i++) { diff[i] = a[i+1]-a[i]; } int maxDiff = diff[0], maxi = 0, maxCount = 1; int currentDiff = -1, currentCount = 0, currenti = -1; for(int i = 1; i n-1; i++) { if(diff[i] == maxDiff) { maxCount++; } else { if(diff[i] == currentDiff) { currentCount++; if (currentCount maxCount) { maxDiff = currentDiff; maxCount = currentCount; maxi = currenti;}} else { currentDiff = diff[i]; currenti = i; currentCount = 1; } } } System.out.print(Elements of the AP: ) ; for(int i = maxi; i = maxi+maxCount; i++) { System.out.print(a[i]+ ); } System.out.println(); } On Tue, Feb 5, 2013 at 5:33 PM, Ian Martin Ajzenszmidt iajzens...@gmail.com wrote: On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. Click on the following links or copy and paste them into your browser. Many interesting possibilities. https://www.google.com.au/search?client=ubuntuchannel=fsq=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1ie=utf-8oe=utf-8redir_esc=ei=GpQRUZXnJKaeiAen7oDYAw http://scholar.google.com/scholar?hl=enq=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.btnG=as_sdt=1%2C5as_sdtp= -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/**profile.php?id=10655377926https://www.facebook.com/profile.php?id=10655377926* -- 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. For more options, visit https://groups.google.com/groups/opt_out. -- Vandana Bachani Graduate Student, MSCE Computer Science Engineering Department Texas AM University, College Station -- 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: GOOGLE Q1
http://theory.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf On Fri, Nov 16, 2012 at 8:55 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I think its the stricter version of LIS , where when you see for the increasing number , just see the number which is greater with the number k than the previous one. Thanks , Rajesh Pandey On Fri, Nov 16, 2012 at 7:55 PM, bharat b bagana.bharatku...@gmail.comwrote: @deepak : all the numbers in the array should be continuous or those k elemenst can be any where ? On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra deepakmnni...@gmail.comwrote: On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/**profile.php?id=10655377926https://www.facebook.com/profile.php?id=10655377926* -- 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/-/umM2YKQz-9oJ. 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. --
Re: [algogeeks] Re: GOOGLE Q1
@deepak : all the numbers in the array should be continuous or those k elemenst can be any where ? On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra deepakmnni...@gmail.comwrote: On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/**profile.php?id=10655377926https://www.facebook.com/profile.php?id=10655377926* -- 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/-/umM2YKQz-9oJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: GOOGLE Q1
I think its the stricter version of LIS , where when you see for the increasing number , just see the number which is greater with the number k than the previous one. Thanks , Rajesh Pandey On Fri, Nov 16, 2012 at 7:55 PM, bharat b bagana.bharatku...@gmail.comwrote: @deepak : all the numbers in the array should be continuous or those k elemenst can be any where ? On Thu, Nov 15, 2012 at 2:18 PM, deepak mishra deepakmnni...@gmail.comwrote: On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/**profile.php?id=10655377926https://www.facebook.com/profile.php?id=10655377926* -- 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/-/umM2YKQz-9oJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: GOOGLE Q1
On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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/-/yoGvjEFsqc4J. 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: GOOGLE Q1
sdfsdfsdfsdfsdf On Monday, 11 July 2011 17:01:36 UTC+5:30, Sunny wrote: @Divye sir yeah that will work fine if D is in reasonable limits .. On Mon, Jul 11, 2011 at 4:26 PM, DK divye...@gmail.com javascript:wrote: @Ritu: Your solution is incorrect. Consider 1 3 41 43 47 49 90 100 110 Maximum repeated 'd' value: '2' for the pairs (1,3), (41,43), (47,49) = 3 repeats. However, the sequences themselves are not part of an AP. The longest AP is of size 3 - (90, 100, 110) with a d of 10. -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/FnebaYc_FbIJ. To post to this group, send email to algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/zUK_Qh6FshsJ. 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: GOOGLE Q1
On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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/-/Y0gqhC9c0I4J. 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: GOOGLE Q1
On Thursday, 7 July 2011 23:43:38 UTC+5:30, Piyush Sinha wrote: Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 i2 … ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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/-/umM2YKQz-9oJ. 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: Google Q : all anagrams next to each other
A solution given below taken from cracking the Coding interview book... Solution is create a Comparator and a small change in compare method is that u sort the characters of that string and then compare. and just sort the arrays, using this compareTo method instead of the usual one. Arrays.sort(array, new AnagramComparator()); public class AnagramComparator implements ComparatorString { public String sortChars(String s) { char[] content = s.toCharArray(); Arrays.sort(content); return new String(content); } public int compare(String s1, String s2) { return sortChars(s1).compareTo(sortChars(s2)); } } *Shashi Kant * ***Think positive and find fuel in failure* http://thinkndoawesome.blogspot.com/ *System/Software Engineer* *Hewlett-Packard India Software Operations. * On Sun, May 27, 2012 at 2:56 AM, Navin Gupta navin.nit...@gmail.com wrote: @jalaj :- we will be sorting a copy of the word and then matching the sorted_sequence with the sorted_sequence of the copy of other words. It will still be in-place, because we are using a space of Word size where the input is a dictionary. This is an amortized in-place. -- Navin Kumar Gupta Computer Science Engg. National Institute of Technology,Jamshedpur -- 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/-/n2tGzVxSLIYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: [Google question]
@vikas I believe that if we generalize the question saying that there are N students and K schools, such that each school can accommodate at max (N/K) students (which means each school needs to accommodate exactly (N/K) students. Given this we need to find the minimum distance. By O(n^3), in this case it means O((N/K ^ 3)) . Am I right ? On 1 Aug, 11:48, vikas rai vikasloves...@gmail.com wrote: There is a set of 9 students and 3 schools Every school can be alloted atmax 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum. We have to solve this in less than O(n^3) . -- 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: [Google question]
@ above small correction.. /* By O(n^3), in this case it means O((N/K ^ K)) . */ Therefore, N = 9, K=3.. hence (9/3)^3 = 27 On Aug 4, 4:24 am, Lucifer sourabhd2...@gmail.com wrote: @vikas I believe that if we generalize the question saying that there are N students and K schools, such that each school can accommodate at max (N/K) students (which means each school needs to accommodate exactly (N/K) students. Given this we need to find the minimum distance. By O(n^3), in this case it means O((N/K ^ 3)) . Am I right ? On 1 Aug, 11:48, vikas rai vikasloves...@gmail.com wrote: There is a set of 9 students and 3 schools Every school can be alloted atmax 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum. We have to solve this in less than O(n^3) . -- 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: [Google question]
What is N? This is a fixed-size problem so by definition, every solution will be constant time. Don On Aug 1, 2:48 am, vikas rai vikasloves...@gmail.com wrote: There is a set of 9 students and 3 schools Every school can be alloted atmax 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum. We have to solve this in less than O(n^3) . -- 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: [Google] Finds all the elements that appear more than n/3 times
I think it can be done by using some randomized algorithm. Divide the array into subarrays of equal size and then pick a random element from each group.Do it 3-4 times,if random number comes out equal for most of the times,return that element. I haven't tried it. On Fri, Jul 13, 2012 at 10:53 AM, Ganesh M ganesh.muniya...@gmail.comwrote: I guess the linkhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.htmltalks about modified quick sort approach. Remember, if your choise of pivot is bad everytime, this will have a worst case performance of O(n). You should refer to Selection Algorithmhttp://en.wikipedia.org/wiki/Selection_algorithmfor better worst case performance. On Wednesday, July 11, 2012 3:12:07 PM UTC+8, Navin Kumar wrote: @sachin: http://valis.cs.uiuc.edu/~**sariel/research/CG/applets/** linear_prog/median.htmlhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.com wrote: To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/PxIJd3So3tkJhttps://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/lZKI47459WgJ. 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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- 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: [Google] Finds all the elements that appear more than n/3 times
I guess the linkhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.htmltalks about modified quick sort approach. Remember, if your choise of pivot is bad everytime, this will have a worst case performance of O(n). You should refer to Selection Algorithmhttp://en.wikipedia.org/wiki/Selection_algorithmfor better worst case performance. On Wednesday, July 11, 2012 3:12:07 PM UTC+8, Navin Kumar wrote: @sachin: http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote: To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/PxIJd3So3tkJ. 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lZKI47459WgJ. 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: [Google] Finds all the elements that appear more than n/3 times
To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/PxIJd3So3tkJ. 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: [Google] Finds all the elements that appear more than n/3 times
@sachin: you can find median in linear sort. http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote: To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/PxIJd3So3tkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
@sachin: http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote: To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/PxIJd3So3tkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
can some body please explain voting algo to me . On Wed, Jul 11, 2012 at 12:42 PM, Navin Kumar algorithm.i...@gmail.comwrote: @sachin: http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote: To Mr. B how will you find median in O(n) time? please elaborate. On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote: I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/PxIJd3So3tkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case. 1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) = O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/OYZtR1iwbGQJ. 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: [Google] Finds all the elements that appear more than n/3 times
My previous email got sent accidentally.. Assume if we have 90 elements and need to find 30 elements that are repeating..as per Sanjay's algo,divide it to 45 elements.. To find majority in 45 elements, the number should repeat = 23 times.. This might not be valid since the number could repeat only 15 times if it's distributed uniformly across two sub arrays.. Let me know if am wrong.. Thanks, Balaji Apologies for brevity and spelling. On Jul 2, 2012, at 11:47 PM, Balaji Subramanian balaji.subraman...@gmail.com wrote: Seems to be a nice algorithm. But won't think it would work..Majority number element should repeat for more than n/2 times.. Apologies for brevity and spelling. On Jul 2, 2012, at 1:46 PM, sanjay pandey sanjaypandey...@gmail.com wrote: i think the concept of majority elemnt can be applied here . 1.divide array into 2 halves 2.apply majority in each 3.den from d two majority found do linear counts of dere frequency?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
we can use voting algorithm this.. maintain a variable count and a variable index.now make a scan for 1 to n-3.during a scan initialize count with 1 and index with 0.now if a[i]==a[index] then increment count else decrement count.when count reached 0.start again incrementing it when u get a new element and also update the indexes. now when the loop terminates then u might have got a suitable candidate.now u have to make 3 more scans in order to check the frequency of arr[index],arr[n-1] and arr[n]. On Sat, Jun 30, 2012 at 6:41 PM, saurabh singh saurab...@gmail.com wrote: @above On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/0myz4OIStO8J. 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 Lomash Goyal * * -- 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: [Google] Finds all the elements that appear more than n/3 times
@above On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- 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/-/0myz4OIStO8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Q : all anagrams next to each other
@jalaj :- we will be sorting a copy of the word and then matching the sorted_sequence with the sorted_sequence of the copy of other words. It will still be in-place, because we are using a space of Word size where the input is a dictionary. This is an amortized in-place. -- Navin Kumar Gupta Computer Science Engg. National Institute of Technology,Jamshedpur -- 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/-/n2tGzVxSLIYJ. 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: Google Q : all anagrams next to each other
This will work in fine, but multiplying primes requires arbitrary precision arithmetic for keys of any significant length. You don't need to compute a hash at all. Just maintain two buffers long enough to hold the longest word and an O(n) sort like counting sort. If you are using Latin (8-bit) characters, you don't even need to complete the counting sort. Just do the counting into arrays of 256 ints. You'll end up with character histograms. It's easy to compare these rather than sorted strings. They require O(2 log C) = O(log C) storage and comparing them needs O(log C) int comparisons, where C is the number of characters in the alphabet. Since C is a constant, this would normally be considered O(1) time and space. On May 26, 2:52 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: If you sort every word , then you will lose the original word as Ankita pointed out and if you keep a hashmap to track that it will not be inplace ., Is there any problem in the solution I gave Above , please point it out . On Fri, May 25, 2012 at 1:14 AM, Anika Jain anika.jai...@gmail.com wrote: I have a doubt. If u r doing inplace sorting of a word during checks for a word, wouldnt that change that word there itself? then how will the original anagram get restored to arrange in the output in sorted manner? On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar jitender...@gmail.comwrote: The complexity will be (N^2)W because the sorting can be done linear time O(W) for strings. On Thu, May 24, 2012 at 3:44 PM, WgpShashank bshashank7andr...@gmail.com wrote: Yeah , its the in-place approach strikes in mind at first look , just slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of words in array W is length of longest word in array , let me know i missed something ? original eat I ate att I the eel eth het after sorting I I ate att can eat eel eth het the output should be I I ate eat att can eel eth het the Shashank Mani Narayan Computer Science Engineering Birla Institute of Technology,Mesra Founder Cracking The Code Lab http://shashank7s.blogspot.com/; FB Pagehttp://www.facebook.com/pages/LestCode Google+http://gplus.to/wgpshashank Twitter https://twitter.com/wgpshashank; Puzzled Guy @ http://ashutosh7s.blogspot.com; FB Pagehttp://www.facebook.com/Puzzles.For.Puzzled.Minds On May 22, 8:18 am, Navin Gupta navin.nit...@gmail.com wrote: It can be done inplace, then Time Complexity will be O( N^2 x W ) where N is no. of words and W is word size. Start from the left and sort the current word. Keep a pointer PTR to the first index of the element left to process. Initially it will be 0.As we add words this pointer moves forwards. Now iterate the whole list of words to find all those words having same sorted sequence i.e. anagrams Whenver we get a word which is anagram of the current string, swap it with the string pointed by PTR, move PTR forward. pseudoCode :- func( vectorstring v) { int n=v.size(); for(int i=0;in;i++) { string currentWord = v[i]; sort(currentWord); for(int j=i+1;jn;j++) { if ( sort(v[j]) == currentWord ) // anagrams found, { swap( v[i] , v[j] ); //move this string to the position next to pos of currentWord i++; //and move the index of currentWord forward } } } -- 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. -- With regards, Jitender Kumar 3rd year (Computer Engineering) NIT Kurukshetra Kurukshetra- 136119 Mobile +91-8529035751 -- 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 Anika Jain -- 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, Jalaj Jaiswal Software Developer, Adobe Systems +91-9019947895 * * FACEBOOK http://www.facebook.com/jalaj.jaiswal89
Re: [algogeeks] Re: Google Q : all anagrams next to each other
I have a doubt. If u r doing inplace sorting of a word during checks for a word, wouldnt that change that word there itself? then how will the original anagram get restored to arrange in the output in sorted manner? On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar jitender...@gmail.comwrote: The complexity will be (N^2)W because the sorting can be done linear time O(W) for strings. On Thu, May 24, 2012 at 3:44 PM, WgpShashank shashank7andr...@gmail.comwrote: Yeah , its the in-place approach strikes in mind at first look , just slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of words in array W is length of longest word in array , let me know i missed something ? original eat I ate att I the eel eth het after sorting I I ate att can eat eel eth het the output should be I I ate eat att can eel eth het the Shashank Mani Narayan Computer Science Engineering Birla Institute of Technology,Mesra Founder Cracking The Code Lab http://shashank7s.blogspot.com/; FB Page http://www.facebook.com/pages/LestCode Google+ http://gplus.to/wgpshashank Twitter https://twitter.com/wgpshashank; Puzzled Guy @ http://ashutosh7s.blogspot.com; FB Page http://www.facebook.com/Puzzles.For.Puzzled.Minds On May 22, 8:18 am, Navin Gupta navin.nit...@gmail.com wrote: It can be done inplace, then Time Complexity will be O( N^2 x W ) where N is no. of words and W is word size. Start from the left and sort the current word. Keep a pointer PTR to the first index of the element left to process. Initially it will be 0.As we add words this pointer moves forwards. Now iterate the whole list of words to find all those words having same sorted sequence i.e. anagrams Whenver we get a word which is anagram of the current string, swap it with the string pointed by PTR, move PTR forward. pseudoCode :- func( vectorstring v) { int n=v.size(); for(int i=0;in;i++) { string currentWord = v[i]; sort(currentWord); for(int j=i+1;jn;j++) { if ( sort(v[j]) == currentWord )// anagrams found, { swap( v[i] , v[j] ); //move this string to the position next to pos of currentWord i++;//and move the index of currentWord forward } } } -- 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. -- With regards, Jitender Kumar 3rd year (Computer Engineering) NIT Kurukshetra Kurukshetra- 136119 Mobile +91-8529035751 -- 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 Anika Jain -- 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: Google Q : all anagrams next to each other
It can be done inplace, then Time Complexity will be O( N^2 x W ) where N is no. of words and W is word size. Start from the left and sort the current word. Keep a pointer PTR to the first index of the element left to process. Initially it will be 0.As we add words this pointer moves forwards. Now iterate the whole list of words to find all those words having same sorted sequence i.e. anagrams Whenver we get a word which is anagram of the current string, swap it with the string pointed by PTR, move PTR forward. pseudoCode :- func( vectorstring v) { int n=v.size(); for(int i=0;in;i++) { string currentWord = v[i]; sort(currentWord); for(int j=i+1;jn;j++) { if ( sort(v[j]) == currentWord )// anagrams found, { swap( v[i] , v[j] ); //move this string to the position next to pos of currentWord i++;//and move the index of currentWord forward } } } -- 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/-/h04_lKqCILQJ. 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: Google Q: longest word made of subwords within the list
@prem: can you please explain the approach clearly, I did't get the approach. regards Abhishek On May 23, 7:43 pm, Doom duman...@gmail.com wrote: I am trying to understand the question.. please let me know the answer for the following cases.. case1: test testlong testlongtest testlongtestlong testtesttest case2: test testlong testlongtest case3: test longest case4: test testtes ttes testtesttes On Tuesday, 22 May 2012 18:15:16 UTC+5:30, ashgoel wrote: write a program to find the longest word made of other words. For instance, If my file has the following words (sorted): test tester testertest testing testingtester The longest word should be testingtester. Trie is the solution, what is the best Order possible? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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: Google Question Invoice -bills
Atul, I think that your approach will work, although it may take a huge amount of time. One way to potentially make it faster is to select the invoices with the smallest number of combinations first. If you first select all of the invoices with exactly one possible combination, this will prevent you from wasting a lot of time considering combinations for other invoices which require those bills. After assigning all of the invoices with exactly one possible combination, you can clear out all combinations for the other invoices which use any of the assigned bills. That might result in more invoices with exactly one possible combination, but it will almost certainly narrow down the options significantly for the rest of the problem. This approach doesn't ensure a faster solution. I could come up with a diabolical input set which would defeat it. But in most cases it should speed things up a lot. Don On Mar 26, 11:32 pm, atul anand atul.87fri...@gmail.com wrote: @ankush: i told one approach above , but may i want clear . i am not saying this is the best approach to do so but it is one naive soln i came up with. so find all possible combination for each invoice and save it in some data structure. now start from 1st invoice and select 1st invoice combination say for invoice 80 = 50 + 30 now search in next invoice(210) combination , if there is any combination for this invoice which does not include 50 and 30 if yes there is one say 210= 10 + 10 +20 + 70 + 100 , we have a hit and do similar with other invoice . every time you move fwd make sure that you should search for combination which does not include any of those bill used in prev finding. if no, then we know that there is no point of moving fwd , so select another combination from prev invoice in this case its 80 and follow same as above. On Mon, Mar 26, 2012 at 5:56 PM, ankush.bago...@gmail.com wrote: ** You can use dp to find subsets . But how is dp used for the overall probkem Sent from BlackBerry® on Airtel -- *From: * atul anand atul.87fri...@gmail.com *Sender: * algogeeks@googlegroups.com *Date: *Mon, 26 Mar 2012 16:52:08 +0530 *To: *algogeeks@googlegroups.com *ReplyTo: * algogeeks@googlegroups.com *Subject: *Re: [algogeeks] Google Question Invoice -bills @umer : dp approach is given in above post. On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote: Well, they have specified in the question that you are dealing with big-data sets. So, recursion won't be a good option I guess. Can we solve it with dynamic programming technique? On Mon, Mar 26, 2012 at 2:24 PM, atul anand atul.87fri...@gmail.comwrote: one way to do it , is say first combination for invoice 80= 50 + 30 now remove 80 and 30 from the input bills while finding combination from 210 , check if it is possible if yes , we got one solution not select another invoice combination 80= 50 + 10 + 20 now dont consider these values while find combination for 210. i guess there can be better way to solve this.. On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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
Re: [algogeeks] Re: Google written test
@Hemesh : dats would be an over kill , you are converting O(n) solution to a subset sum problem which NP On Tue, Mar 20, 2012 at 7:35 PM, Hemesh Singh hemesh.mn...@gmail.comwrote: Isn't it a standard subset sum problem? You can generate the Fibonacci numbers and put them in an array. Now just apply the standard algorithm to find that which Fibonacci numbers add up to make the given sum. Please correct me if I am wrong. On Mon, Mar 19, 2012 at 8:58 PM, atul anand atul.87fri...@gmail.comwrote: @Gene : yeah i skipped ur updated code...its dere @shady : it is similar to fib encoding...you just need to reverse the output from gene code and append '1' at the end... while decoding it ...this extra '1' is not considered.. i am nt sure but maybe the reason for adding '1' at the end is to mark end of word On 19 Mar 2012 19:10, shady sinv...@gmail.com wrote: @gene it does show your updated code. @atul from the given input it seems different from Fibonacci encoding. On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote: Thanks. I noticed this too. If the n'th 1/0 digit is supposed to correspond with the n'th fibonacci number, then my original code would have been right. But the example isn't done this way. I fixed the code to match the example the evening of the 18th (Eastern time), but I guess the change is not showing on your server yet. On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote: @Gene : your code will work fine by changing the argument passed from main(), you just need to call rite f(n, 1, 1); from main instead of f(n, 1, 0); On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com wrote: @all : i guess question is on Fibonacci coding. here you can find the algo :- http://en.wikipedia.org/wiki/Fibonacci_coding On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.comwrote: @Ravi... there should be only one answer as for fibonacci representation of a number we have to include the part of the fibonacci number just less than the number then remaining part of the sum is filled by fibonacci numbers starting from 1 suppose we have to convert 6 into fibonacci representation then 6 has two sum sets as {1,2,3} or {1,5} then the fibonacci number just less than 6 is 5 so bit representing 5 is set then for completing the sum to 6 bit 1 is also set. so *fibonacci representation of 6 is 1001 .* not 0111 ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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. -- 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. -- Hemesh 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.
Re: [algogeeks] Re: Google written test
Isn't it a standard subset sum problem? You can generate the Fibonacci numbers and put them in an array. Now just apply the standard algorithm to find that which Fibonacci numbers add up to make the given sum. Please correct me if I am wrong. On Mon, Mar 19, 2012 at 8:58 PM, atul anand atul.87fri...@gmail.com wrote: @Gene : yeah i skipped ur updated code...its dere @shady : it is similar to fib encoding...you just need to reverse the output from gene code and append '1' at the end... while decoding it ...this extra '1' is not considered.. i am nt sure but maybe the reason for adding '1' at the end is to mark end of word On 19 Mar 2012 19:10, shady sinv...@gmail.com wrote: @gene it does show your updated code. @atul from the given input it seems different from Fibonacci encoding. On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote: Thanks. I noticed this too. If the n'th 1/0 digit is supposed to correspond with the n'th fibonacci number, then my original code would have been right. But the example isn't done this way. I fixed the code to match the example the evening of the 18th (Eastern time), but I guess the change is not showing on your server yet. On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote: @Gene : your code will work fine by changing the argument passed from main(), you just need to call rite f(n, 1, 1); from main instead of f(n, 1, 0); On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com wrote: @all : i guess question is on Fibonacci coding. here you can find the algo :- http://en.wikipedia.org/wiki/Fibonacci_coding On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.com wrote: @Ravi... there should be only one answer as for fibonacci representation of a number we have to include the part of the fibonacci number just less than the number then remaining part of the sum is filled by fibonacci numbers starting from 1 suppose we have to convert 6 into fibonacci representation then 6 has two sum sets as {1,2,3} or {1,5} then the fibonacci number just less than 6 is 5 so bit representing 5 is set then for completing the sum to 6 bit 1 is also set. so *fibonacci representation of 6 is 1001 .* not 0111 ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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. -- 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. -- Hemesh 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.
[algogeeks] Re: Google written test
Thanks. I noticed this too. If the n'th 1/0 digit is supposed to correspond with the n'th fibonacci number, then my original code would have been right. But the example isn't done this way. I fixed the code to match the example the evening of the 18th (Eastern time), but I guess the change is not showing on your server yet. On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote: @Gene : your code will work fine by changing the argument passed from main(), you just need to call rite f(n, 1, 1); from main instead of f(n, 1, 0); On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.comwrote: @all : i guess question is on Fibonacci coding. here you can find the algo :- http://en.wikipedia.org/wiki/Fibonacci_coding On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.comwrote: @Ravi... there should be only one answer as for fibonacci representation of a number we have to include the part of the fibonacci number just less than the number then remaining part of the sum is filled by fibonacci numbers starting from 1 suppose we have to convert 6 into fibonacci representation then 6 has two sum sets as {1,2,3} or {1,5} then the fibonacci number just less than 6 is 5 so bit representing 5 is set then for completing the sum to 6 bit 1 is also set. so *fibonacci representation of 6 is 1001 .* not 0111 ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google written test
@gene it does show your updated code. @atul from the given input it seems different from Fibonacci encoding. On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote: Thanks. I noticed this too. If the n'th 1/0 digit is supposed to correspond with the n'th fibonacci number, then my original code would have been right. But the example isn't done this way. I fixed the code to match the example the evening of the 18th (Eastern time), but I guess the change is not showing on your server yet. On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote: @Gene : your code will work fine by changing the argument passed from main(), you just need to call rite f(n, 1, 1); from main instead of f(n, 1, 0); On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com wrote: @all : i guess question is on Fibonacci coding. here you can find the algo :- http://en.wikipedia.org/wiki/Fibonacci_coding On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.com wrote: @Ravi... there should be only one answer as for fibonacci representation of a number we have to include the part of the fibonacci number just less than the number then remaining part of the sum is filled by fibonacci numbers starting from 1 suppose we have to convert 6 into fibonacci representation then 6 has two sum sets as {1,2,3} or {1,5} then the fibonacci number just less than 6 is 5 so bit representing 5 is set then for completing the sum to 6 bit 1 is also set. so *fibonacci representation of 6 is 1001 .* not 0111 ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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.
Re: [algogeeks] Re: Google written test
@Gene : yeah i skipped ur updated code...its dere @shady : it is similar to fib encoding...you just need to reverse the output from gene code and append '1' at the end... while decoding it ...this extra '1' is not considered.. i am nt sure but maybe the reason for adding '1' at the end is to mark end of word On 19 Mar 2012 19:10, shady sinv...@gmail.com wrote: @gene it does show your updated code. @atul from the given input it seems different from Fibonacci encoding. On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote: Thanks. I noticed this too. If the n'th 1/0 digit is supposed to correspond with the n'th fibonacci number, then my original code would have been right. But the example isn't done this way. I fixed the code to match the example the evening of the 18th (Eastern time), but I guess the change is not showing on your server yet. On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote: @Gene : your code will work fine by changing the argument passed from main(), you just need to call rite f(n, 1, 1); from main instead of f(n, 1, 0); On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.com wrote: @all : i guess question is on Fibonacci coding. here you can find the algo :- http://en.wikipedia.org/wiki/Fibonacci_coding On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.com wrote: @Ravi... there should be only one answer as for fibonacci representation of a number we have to include the part of the fibonacci number just less than the number then remaining part of the sum is filled by fibonacci numbers starting from 1 suppose we have to convert 6 into fibonacci representation then 6 has two sum sets as {1,2,3} or {1,5} then the fibonacci number just less than 6 is 5 so bit representing 5 is set then for completing the sum to 6 bit 1 is also set. so *fibonacci representation of 6 is 1001 .* not 0111 ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar | 9530739855 | -- 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. -- 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: Google written test
It looks from the example like you pick the largest (as if the digits were a binary number). Here's what I get: #include stdio.h unsigned f(unsigned n, unsigned fi, unsigned fim1) { if (fi n) return n; unsigned r = f(n, fi + fim1, fi); if (r = fi) { putchar('1'); return r - fi; } putchar('0'); return r; } int main(int argc, char *argv[]) { unsigned n; if (argc 1 sscanf(argv[1], %u, n) == 1) { f(n, 1, 0); putchar('\n'); } return 0; } On Mar 17, 2:08 pm, Ravi Ranjan ravi.cool2...@gmail.com wrote: @ if for a given number more than 1 answer exist then whats the answer??? -- 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: Google written test
It looks from the example like you pick the largest (as if the digits were a binary number). Here's what I get: #include stdio.h unsigned f(unsigned n, unsigned fi, unsigned fim1) { if (fi n) return n; unsigned r = f(n, fi + fim1, fi); if (r = fi) { putchar('1'); return r - fi; } putchar('0'); return r; } int main(int argc, char *argv[]) { unsigned n; if (argc 1 sscanf(argv[1], %u, n) == 1) { f(n, 1, 1); putchar('\n'); } return 0; } On Mar 17, 2:08 pm, Ravi Ranjan ravi.cool2...@gmail.com wrote: @ if for a given number more than 1 answer exist then whats the answer??? -- 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: Google
VCE hyderabad On Mon, Mar 5, 2012 at 3:28 PM, adarsh kumar algog...@gmail.com wrote: Which college? On Sun, Mar 4, 2012 at 10:16 AM, teja bala pawanjalsa.t...@gmail.comwrote: Google is visiting our campus 4 different roles As of now IT field technician is confirmed so how to approach 4 written test. ?? -- 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.
Re: [algogeeks] Re: Google
Which college? On Sun, Mar 4, 2012 at 10:16 AM, teja bala pawanjalsa.t...@gmail.comwrote: Google is visiting our campus 4 different roles As of now IT field technician is confirmed so how to approach 4 written test. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google
Google is visiting our campus 4 different roles As of now IT field technician is confirmed so how to approach 4 written test. ?? -- 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: google question
@Dave : is it a working code?? i have executed your code but getting wrong output...and value of s is becoming -ve inside loops. -- 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: google question
0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h - 1, i+1) ) i am not clear why the parents of a cup in upper row are consecutive? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote: G is just a helper function. You can in line this function and eliminate it. When you do this, you'll end up with F(h, i) = 0.5 * (l + r) where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else 0 and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0 Here l is the left parent's outflow and r is the right parent's. So you are always computing the h'th row in terms of the (h-1)'th. For many DPs this means you'll need 2 row buffers. In this one you only need 1 element back in the current row. You can save this element in a single variable and get by with one buffer. I.e. note l for a given value of i is always the previous value of r. And for i=0, l is always 0 because there is no left parent. So you end up with f[0] = L; // fill in the first row for (ih = 1; ih = h; ih++) { // loop thru rest of rows double l = 0; // left parent outflow at ii=0 is always 0. for (ii = 0; ii = ih; ii++) { // loop thru columns // new right parent outflow double r = (ii ih f[ii] C) ? f[ii] - C : 0; f[ii] = 0.5 * (l + r); l = r; // right parent is left of next row entry } } return (0 = i i = h) ? f[i] : 0; This is doing the same as Dave's code for all practical purposes. It's untested but ought to work. On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote: Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote: G(h - 1, i - 1) + G(h - 1, i) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google question
Well the OP is not clear. You could be right. I solved this problem once before, and there the glasses were arranged in a pyramid like they do at weddings in my country (this will only look right if you set the fixed-width font in Groups: U U U U U U U U U U U U U U U --- You pour in the wine at the top and each glass trickles down to the 2 below it. So in this version I assumed the OP meant the children were the ones below and to the right. I could be wrong. On Feb 28, 8:46 am, Ashish Goel ashg...@gmail.com wrote: 0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h - 1, i+1) ) i am not clear why the parents of a cup in upper row are consecutive? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote: G is just a helper function. You can in line this function and eliminate it. When you do this, you'll end up with F(h, i) = 0.5 * (l + r) where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else 0 and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0 Here l is the left parent's outflow and r is the right parent's. So you are always computing the h'th row in terms of the (h-1)'th. For many DPs this means you'll need 2 row buffers. In this one you only need 1 element back in the current row. You can save this element in a single variable and get by with one buffer. I.e. note l for a given value of i is always the previous value of r. And for i=0, l is always 0 because there is no left parent. So you end up with f[0] = L; // fill in the first row for (ih = 1; ih = h; ih++) { // loop thru rest of rows double l = 0; // left parent outflow at ii=0 is always 0. for (ii = 0; ii = ih; ii++) { // loop thru columns // new right parent outflow double r = (ii ih f[ii] C) ? f[ii] - C : 0; f[ii] = 0.5 * (l + r); l = r; // right parent is left of next row entry } } return (0 = i i = h) ? f[i] : 0; This is doing the same as Dave's code for all practical purposes. It's untested but ought to work. On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote: Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote: G(h - 1, i - 1) + G(h - 1, i) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google question
The previous proposed solutions all seem far too complicated. It is not necessary to use a graph data structure. We can simply use an array to store the quantities of the cups in a row, and update the array to move to the next row. It would look something like this: double cupQuan(double L, double C, int h, int i) // h is the row number of the cup in question, the top cup has h = 1. // i is the index of the cup in question; the first cup in a row has i = 0. { int j, k; double r, s; double* p; if( (L = 0) || (C = 0) || (h = 0) || (i 0) || (i = h) ) return 0.0; p = malloc(h * sizeof(double)); p[0] = L;// all liquid into top cup for( j = 1 ; j h ; ++j )// advance from row j to j+1 { r = 0.0; // nothing coming in from the left for( k = 0 ; k j ; ++k ) { s = p[k] - C; if( s = 0.0 ) {// if this cup does not overflow p[k] = r; // only overflow from previous cup r = 0.0; // no overflow to next cup in row } else { // if this cup does overflow p[k] = 0.5 * s + r; // overflow from this cup and previous r = 0.5 * s; // overflow to next cup in row } p[j] = r; // overflow into last cup in row } } s = p[i] = C ? p[i] : C; // result, but not C free(p); return s; } Dave On Feb 25, 5:35 am, Ravi Ranjan ravi.cool2...@gmail.com wrote: |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| Each cup has capacity C and once a cup gets full, it drops half extra amount to left child and half extra amount to right child for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C) will be divided equally to left and right child cup of next level i.e. C/2 to left child and C/2 to right child Write a function which takes input parameter as amount of liquid poured at top (L) and height of particular cup (h) index of that cup (i) and it should return amount of liquid absorbed in that cup. source http://www.careercup.com/question?id=12770661 whats exactly the qestion??? -- 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: google question
Dave, why the assumption that nothing is coming from left side. Every cup gets something from cup left above and right above itself when they have something extra? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote: // nothing coming in from the left -- 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: google question
@Ashish: I didn't make any assumption that nothing comes from the left. Does my code give the wrong answer? Dave On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote: Dave, why the assumption that nothing is coming from left side. Every cup gets something from cup left above and right above itself when they have something extra? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote: // nothing coming in from the left -- 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: google question
Dave's code is good. Here is a more abstract way of thinking about it. Maybe helpful? Number the rows starting at the top with h=0, and the left i=0. Then the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When h0, i0 or i h, the parent does not exist. Let F(h, i) be the amount that has flowed in to cup(h,i) after L went in at the top and let G(h, i) be the amount that has flowed out. So note that what flowed out is either what flowed in minus C or else nothing if less than C has flowed in. It's also zero if cup(h,i) doesn't exist: G(h,i) = { F(h, i) - C if 0 = i = h and F(h, i) C { 0 otherwise Now note that what flows in is equal to half of what flowed out of each parent unless we have the top cup, which means L flowed in! F(h, i) = { L if h = i = 0 { 0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) otherwise The answer we want is given by F. Dave's code is a nice implementation of this DP. On Feb 27, 5:23 pm, Dave dave_and_da...@juno.com wrote: @Ashish: I didn't make any assumption that nothing comes from the left. Does my code give the wrong answer? Dave On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote: Dave, why the assumption that nothing is coming from left side. Every cup gets something from cup left above and right above itself when they have something extra? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote: // nothing coming in from the left -- 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: google question
Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote: G(h - 1, i - 1) + G(h - 1, i) -- 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: google question
@Dave : my code is not that complicated ...if you ignore the helper function and check fillCup(); it just similar to preorder travesal and pour half to left and right child. here is the explanation :- node* fillCup(node *root,float pour,float capacity) { float temp; if(root==NULL) return NULL; if(root-data+pour = capacity) { if(root-data==0) // if cup is empty then fill cup to full and reduce pour value for the next level { root-data=capacity; pour=pour-capacity; } else { // if there is alreday some water in the cup , then it will fill the cup and reduce pour =pour - empty volume in partially filled cup. temp=capacity-(root-data); root-data=capacity; pour=pour-temp; if(pour==0) { return root; } } } else { // this is for the part where overflow will never happen , even after adding the poured quantity to the cup. root-data+=pour; return root; } fillCup(root-left,pour/2,capacity);// pour 1/2 to the left fillCup(root-right,pour/2,capacity); // pour 1/2 to the right } Time complexity = O(n). your approach is nice but it O(n^2) . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: google question
@Atul: I don't have an n in my algorithm, so I'm not sure what your assessment that my algorithm is O(n^2) means. My algorithm is O(h^2), where h is the height of the triangle of cups, but the number of cups is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is yours. You'll have to admit that my data structure, an array, is simpler than your graph. Dave On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote: @Dave : my code is not that complicated ...if you ignore the helper function and check fillCup(); it just similar to preorder travesal and pour half to left and right child. here is the explanation :- node* fillCup(node *root,float pour,float capacity) { float temp; if(root==NULL) return NULL; if(root-data+pour = capacity) { if(root-data==0) // if cup is empty then fill cup to full and reduce pour value for the next level { root-data=capacity; pour=pour-capacity; } else { // if there is alreday some water in the cup , then it will fill the cup and reduce pour =pour - empty volume in partially filled cup. temp=capacity-(root-data); root-data=capacity; pour=pour-temp; if(pour==0) { return root; } } } else { // this is for the part where overflow will never happen , even after adding the poured quantity to the cup. root-data+=pour; return root; } fillCup(root-left,pour/2,capacity); // pour 1/2 to the left fillCup(root-right,pour/2,capacity); // pour 1/2 to the right } Time complexity = O(n). your approach is nice but it O(n^2) . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: google question
G is just a helper function. You can in line this function and eliminate it. When you do this, you'll end up with F(h, i) = 0.5 * (l + r) where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else 0 and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0 Here l is the left parent's outflow and r is the right parent's. So you are always computing the h'th row in terms of the (h-1)'th. For many DPs this means you'll need 2 row buffers. In this one you only need 1 element back in the current row. You can save this element in a single variable and get by with one buffer. I.e. note l for a given value of i is always the previous value of r. And for i=0, l is always 0 because there is no left parent. So you end up with f[0] = L; // fill in the first row for (ih = 1; ih = h; ih++) { // loop thru rest of rows double l = 0; // left parent outflow at ii=0 is always 0. for (ii = 0; ii = ih; ii++) { // loop thru columns // new right parent outflow double r = (ii ih f[ii] C) ? f[ii] - C : 0; f[ii] = 0.5 * (l + r); l = r; // right parent is left of next row entry } } return (0 = i i = h) ? f[i] : 0; This is doing the same as Dave's code for all practical purposes. It's untested but ought to work. On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote: Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote: G(h - 1, i - 1) + G(h - 1, i) -- 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: google question
@Dave : yeah sorry its O(n) where n is number of nodes. yeah as i said before its a nice approach... On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote: @Atul: I don't have an n in my algorithm, so I'm not sure what your assessment that my algorithm is O(n^2) means. My algorithm is O(h^2), where h is the height of the triangle of cups, but the number of cups is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is yours. You'll have to admit that my data structure, an array, is simpler than your graph. Dave On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote: @Dave : my code is not that complicated ...if you ignore the helper function and check fillCup(); it just similar to preorder travesal and pour half to left and right child. here is the explanation :- node* fillCup(node *root,float pour,float capacity) { float temp; if(root==NULL) return NULL; if(root-data+pour = capacity) { if(root-data==0) // if cup is empty then fill cup to full and reduce pour value for the next level { root-data=capacity; pour=pour-capacity; } else { // if there is alreday some water in the cup , then it will fill the cup and reduce pour =pour - empty volume in partially filled cup. temp=capacity-(root-data); root-data=capacity; pour=pour-temp; if(pour==0) { return root; } } } else { // this is for the part where overflow will never happen , even after adding the poured quantity to the cup. root-data+=pour; return root; } fillCup(root-left,pour/2,capacity);// pour 1/2 to the left fillCup(root-right,pour/2,capacity); // pour 1/2 to the right } Time complexity = O(n). your approach is nice but it O(n^2) . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: google question
@Gene , @dave : +1 +1 On Tue, Feb 28, 2012 at 10:49 AM, atul anand atul.87fri...@gmail.comwrote: @Dave : yeah sorry its O(n) where n is number of nodes. yeah as i said before its a nice approach... On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote: @Atul: I don't have an n in my algorithm, so I'm not sure what your assessment that my algorithm is O(n^2) means. My algorithm is O(h^2), where h is the height of the triangle of cups, but the number of cups is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is yours. You'll have to admit that my data structure, an array, is simpler than your graph. Dave On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote: @Dave : my code is not that complicated ...if you ignore the helper function and check fillCup(); it just similar to preorder travesal and pour half to left and right child. here is the explanation :- node* fillCup(node *root,float pour,float capacity) { float temp; if(root==NULL) return NULL; if(root-data+pour = capacity) { if(root-data==0) // if cup is empty then fill cup to full and reduce pour value for the next level { root-data=capacity; pour=pour-capacity; } else { // if there is alreday some water in the cup , then it will fill the cup and reduce pour =pour - empty volume in partially filled cup. temp=capacity-(root-data); root-data=capacity; pour=pour-temp; if(pour==0) { return root; } } } else { // this is for the part where overflow will never happen , even after adding the poured quantity to the cup. root-data+=pour; return root; } fillCup(root-left,pour/2,capacity);// pour 1/2 to the left fillCup(root-right,pour/2,capacity); // pour 1/2 to the right } Time complexity = O(n). your approach is nice but it O(n^2) . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google question
You are assuming is to be a binary tree, its not. Some nodes will share a common pour. On Feb 25, 9:24 pm, atul anand atul.87fri...@gmail.com wrote: i guess this would work... n=number of nodes h=height; pour=quantity poured; capacity = capacity of each cup n=pow(2,h+1) -1; call(capacity,pour,0,n) node* fillCup(float capacity,float pour,int left,int right) { node *root; int mid; if(left right) return NULL; root=(node *)malloc(sizeof(node)); if(left==right) { if(pour =capacity) root-data=capacity; else root-data=pour; root-left=root-right=NULL;} else { mid=left+(right-left)/2; if(pour = capacity) { root-data=capacity; pour=pour-capacity; pour=pour/2;} else { root-data=pour; root-left=root-right=NULL; return root; } root-left=fillCup(capacity,pour,left,mid-1); root-right=fillCup(capacity,pour,mid+1,right); } return root; } On Sat, Feb 25, 2012 at 5:05 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| Each cup has capacity C and once a cup gets full, it drops half extra amount to left child and half extra amount to right child for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C) will be divided equally to left and right child cup of next level i.e. C/2 to left child and C/2 to right child Write a function which takes input parameter as amount of liquid poured at top (L) and height of particular cup (h) index of that cup (i) and it should return amount of liquid absorbed in that cup. source http://www.careercup.com/question?id=12770661 whats exactly the qestion??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: google question
@all same doubt qstn appears to be of binary tree DS but the diagram given in between qstn is not like Binary tree so sharing is there so how sharing is done plz explain?? -- 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: google question
@Ravi: checkout this code...i have created tree where there is sharing of nodes.. here is my code :- please let me know is case you find any bug. #includestdio.h typedef struct tree{ int idx; float data; struct tree *left; struct tree *right; }node; node *createNode(int index) { node *temp; temp=(node *)malloc(sizeof(node)); temp-idx=index; temp-data=0.0; temp-left=temp-right=NULL; return temp; } void inorder(node *root) { if(root!=NULL) { inorder(root-left); printf(%d ) %f \n,root-idx,root-data); inorder(root-right); } } node* fillCup(node *root,float pour,float capacity) { float temp; if(root==NULL) return NULL; if(root-data+pour = capacity) { if(root-data==0) { root-data=capacity; pour=pour-capacity; } else { temp=capacity-(root-data); root-data=capacity; pour=pour-temp; if(pour==0) { return root; } } } else { root-data+=pour; return root; } fillCup(root-left,pour/2,capacity); fillCup(root-right,pour/2,capacity); } int main() { node *root; float pour,capacity; root=createNode(1);//1 root-left=createNode(2);//2 root-right=createNode(3);//3 root-left-left=createNode(4);//4 root-left-left-left=createNode(7);//7 root-right-right=createNode(6);//6 root-right-right-right=createNode(10);//10 root-left-right=createNode(5);//5 root-right-left=root-left-right; root-left-left-right=createNode(8); // 8 root-left-right-left=root-left-left-right; root-left-right-right=createNode(9);//9 root-right-right-left=root-left-right-right; printf(\nEnter capacity = ); scanf(%f,capacity); printf(\nEnter quantity poured = ); scanf(%f,pour); fillCup(root,pour,capacity); printf(\nPrinting tree\n\n); inorder(root); printf(\n\n); return 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.
[algogeeks] Re: Google-Puzzle
buddy i said that kadane's algo(max subsum) wouldn't work.. On Feb 25, 1:31 pm, Ashish Goel ashg...@gmail.com wrote: max subsum problem Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Feb 25, 2012 at 1:03 PM, karthikeya s karthikeya.a...@gmail.comwrote: You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit. my logic: we can use an array having element as fuel(in km)-dist to next pit so now aim is to traverse the array as always having some +ve resultant sum.nd plz we cant use here kadane's algo.there are cases in which it will not hold here -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google-Puzzle
it will the diff is of fuel and dist forms the content of array which moves from 1 to 2n-1 elements(break the circle and instead of elem like 1,2,n have 1,2,n,1,2,...n-1 i.e. total 2n-1 so that mod stuff is not required. now find maxsubSum such that sum=0 and count of nodes is n not clear ehy it wont work. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Feb 25, 2012 at 2:54 PM, karthikeya s karthikeya.a...@gmail.comwrote: buddy i said that kadane's algo(max subsum) wouldn't work.. On Feb 25, 1:31 pm, Ashish Goel ashg...@gmail.com wrote: max subsum problem Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Feb 25, 2012 at 1:03 PM, karthikeya s karthikeya.a...@gmail.com wrote: You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit. my logic: we can use an array having element as fuel(in km)-dist to next pit so now aim is to traverse the array as always having some +ve resultant sum.nd plz we cant use here kadane's algo.there are cases in which it will not hold here -- 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.
Re: [algogeeks] Re: google questions
@all: how is the problem solved using a heap...can someone explain. did not understand what was on the net... On Thu, Feb 3, 2011 at 2:23 AM, Avik Mitra tutai...@gmail.com wrote: I am proposing a solution for problem 2.. 2. Given a text file, implement a solution to find out if a pattern similar to wild cards can be detected. fort example find if a*b*cd*, or *win or *def* exists in the text. Whatever be the pattern sort it must be regular expression. So in principle, there always exists a deterministic finite automata with exactly one finite state to accept the pattern. Thus, the problem can be solved. For example take the case for a*b*cd*. The automaton can can written as: 1.Set state=1. 2. Scan the string until end of string is reached. 2.1. If state is 1 and the letter is a then do not change the state. If the state is 1 and the letter is b then go to state 2. if the state is 1 and the letter is c then go to state 3. if the state is 1 and the letter is d then go to state 4. if the state is 2 and letter is a then go to state 4. if the state is 2 and the letter is b then do not change the state. if the state is 2 and the letter is c the go to state 3. if the state is 2 and the letter is d then go to state 4. if the state is 3 and the letter is a,b or c then go to state 4. if the state is 3 and the letter is d then do not change state. if the state is 4 then do not change state. 3. If the state is 3 output accept else output reject. -- 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. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- 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: Google Question--Suggest Algo
@Sourabh - whats the running time? On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote: Cool Solution...I was thinking of DP but wasnt clear on the recurrence... Nice thinking man and thanks :) On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote: Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this constraint is not satisfied then its not a valid candidate for the solution even if the partition produces the max value. 2 = ceil (n / 2k) = ceil (12/6) 6 = floor (3n / 2k) = floor (36/6) - As mentioned above the following equation : F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } /** For understanding how partitioning of the array is represented by the above equation: Say there is an array denoted by A[i] and it needs to be divided into 3 contiguous parts, one of the ways to do so would be to take the following steps : Let K(partition no.) be initialized to 3. Let array size N be 12. a) If N is 0, the goto step 'f' b) If K == 1 then call it as partition K and goto step 'e'. c) Lets take X no. of elements from the end of array A of size N and call it partition K. d) Decrement K by 1 and N by X { --K; and N-=X;} d) Goto step 'a' e) Valid partition and End. f) Not a valid partition and End. Now if the above set of steps is run for all values of X such that 2=X=6 , then it will generate all possible candidates (partitions) as per the given problem statement. And for all the valid partitions(the ones that will hit step 'e') we need to calculate the expected sum value. **/ can be translated into, // I am using 1-based array indexing for better clarity // A[x .. y] means all elements from A[y] to A[x].. F(12, 3) = MAX { ExpVal (A[12 .. 11]) + F(10, 2) , ExpVal (A[12 .. 10]) + F(9, 2) , ExpVal (A[12 .. 9])+ F(8, 2) , // this will yield the maximum sum.. ExpVal (A[12 .. 8])+ F(7, 2) , ExpVal (A[12 .. 7])+ F(6, 2) } which is nothing but, F(12, 3) = MAX { 1/2 + F(10, 2) , 2/3 + F(9, 2) , 2/4 + F(8, 2) , // this will yield the maximum sum.. 3/5 + F(7, 2) , 4/6 + F(6, 2) } Trace the above equation and you should get it.. On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote: Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution. This is can be handled by giving initial value to all such combination a value of -1. To store that the intermediate computations take an array Max[N][K], F(N,K) = Max[N][K] On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote: Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum
[algogeeks] Re: Google Question--Suggest Algo
O(N*K) On Nov 28, 1:04 pm, Nitin Garg nitin.garg.i...@gmail.com wrote: @Sourabh - whats the running time? On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote: Cool Solution...I was thinking of DP but wasnt clear on the recurrence... Nice thinking man and thanks :) On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote: Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this constraint is not satisfied then its not a valid candidate for the solution even if the partition produces the max value. 2 = ceil (n / 2k) = ceil (12/6) 6 = floor (3n / 2k) = floor (36/6) - As mentioned above the following equation : F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } /** For understanding how partitioning of the array is represented by the above equation: Say there is an array denoted by A[i] and it needs to be divided into 3 contiguous parts, one of the ways to do so would be to take the following steps : Let K(partition no.) be initialized to 3. Let array size N be 12. a) If N is 0, the goto step 'f' b) If K == 1 then call it as partition K and goto step 'e'. c) Lets take X no. of elements from the end of array A of size N and call it partition K. d) Decrement K by 1 and N by X { --K; and N-=X;} d) Goto step 'a' e) Valid partition and End. f) Not a valid partition and End. Now if the above set of steps is run for all values of X such that 2=X=6 , then it will generate all possible candidates (partitions) as per the given problem statement. And for all the valid partitions(the ones that will hit step 'e') we need to calculate the expected sum value. **/ can be translated into, // I am using 1-based array indexing for better clarity // A[x .. y] means all elements from A[y] to A[x].. F(12, 3) = MAX { ExpVal (A[12 .. 11]) + F(10, 2) , ExpVal (A[12 .. 10]) + F(9, 2) , ExpVal (A[12 .. 9]) + F(8, 2) , // this will yield the maximum sum.. ExpVal (A[12 .. 8]) + F(7, 2) , ExpVal (A[12 .. 7]) + F(6, 2) } which is nothing but, F(12, 3) = MAX { 1/2 + F(10, 2) , 2/3 + F(9, 2) , 2/4 + F(8, 2) , // this will yield the maximum sum.. 3/5 + F(7, 2) , 4/6 + F(6, 2) } Trace the above equation and you should get it.. On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote: Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution. This is can be handled by giving initial value to all such combination a value of -1. To store that the intermediate computations take an array Max[N][K], F(N,K) = Max[N][K] On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote: Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing
[algogeeks] Re: Google Question--Suggest Algo
Hi I may not have understood your solution properly. But i think that your solution is an implementation of brute force where you are dealing with all cases valid in the range n/2k and 3n/2k without any optimization with regard to DP. Am i right? On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote: Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this constraint is not satisfied then its not a valid candidate for the solution even if the partition produces the max value. 2 = ceil (n / 2k) = ceil (12/6) 6 = floor (3n / 2k) = floor (36/6) - As mentioned above the following equation : F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } /** For understanding how partitioning of the array is represented by the above equation: Say there is an array denoted by A[i] and it needs to be divided into 3 contiguous parts, one of the ways to do so would be to take the following steps : Let K(partition no.) be initialized to 3. Let array size N be 12. a) If N is 0, the goto step 'f' b) If K == 1 then call it as partition K and goto step 'e'. c) Lets take X no. of elements from the end of array A of size N and call it partition K. d) Decrement K by 1 and N by X { --K; and N-=X;} d) Goto step 'a' e) Valid partition and End. f) Not a valid partition and End. Now if the above set of steps is run for all values of X such that 2=X=6 , then it will generate all possible candidates (partitions) as per the given problem statement. And for all the valid partitions(the ones that will hit step 'e') we need to calculate the expected sum value. **/ can be translated into, // I am using 1-based array indexing for better clarity // A[x .. y] means all elements from A[y] to A[x].. F(12, 3) = MAX { ExpVal (A[12 .. 11]) + F(10, 2) , ExpVal (A[12 .. 10]) + F(9, 2) , ExpVal (A[12 .. 9]) + F(8, 2) , // this will yield the maximum sum.. ExpVal (A[12 .. 8]) + F(7, 2) , ExpVal (A[12 .. 7]) + F(6, 2) } which is nothing but, F(12, 3) = MAX { 1/2 + F(10, 2) , 2/3 + F(9, 2) , 2/4 + F(8, 2) , // this will yield the maximum sum.. 3/5 + F(7, 2) , 4/6 + F(6, 2) } Trace the above equation and you should get it.. On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote: Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution. This is can be handled by giving initial value to all such combination a value of -1. To store that the intermediate computations take an array Max[N][K], F(N,K) = Max[N][K] On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote: Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2).. The reasoning being say, We store all the values in a 2-d array of size N * K. Now to compute each element of the above array , we are looking N/K (3n/2k - n/2k) sub problems.. Hence, the running time would be, O( N * K * N / K ) i.e O( N^2)... On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote: I don't think it is O(N*K) It is O(N^2) Just to confirm if i have understood correctly Lets say n and k are given and are global to all subproblems Subproblem Definition F[i,j] - maximum expected sum that we can get by partitioning array from 0 to i into j subarrays. Each subarray satisfies the size bound [ceiling(n/2k),floor(3n/2k)] F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of subarray from i-r+1 to i} So to calculate every subsequent subproblem we need to check solutions to O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2) On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote: Hi I may not have understood your solution properly. But i think that your solution is an implementation of brute force where you are dealing with all cases valid in the range n/2k and 3n/2k without any optimization with regard to DP. Am i right? On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote: Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this constraint is not satisfied then its not a valid candidate for the solution even if the partition produces the max value. 2 = ceil (n / 2k) = ceil (12/6) 6 = floor (3n / 2k) = floor (36/6) - As mentioned above the following equation : F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } /** For understanding how partitioning of the array is represented by the above equation: Say there is an array denoted by A[i] and it needs to be divided into 3 contiguous parts, one of the ways to do so would be to take the following steps : Let K(partition no.) be initialized to 3. Let array size N be 12. a) If N is 0, the goto step 'f' b) If K == 1 then call it as partition K and goto step 'e'. c) Lets take X no. of elements from the end of array A of size N and call it partition K. d) Decrement K by 1 and N by X { --K; and N-=X;} d) Goto step 'a' e) Valid partition and End. f) Not a valid partition and End. Now if the above set of steps is run for all values of X such that 2=X=6 , then it will generate all possible candidates (partitions) as per the given problem statement. And for all the valid partitions(the ones that will hit step 'e') we need to calculate the expected sum value. **/ can be translated into, // I am using 1-based array indexing for better clarity // A[x .. y] means all elements from A[y] to A[x].. F(12, 3) = MAX { ExpVal (A[12 .. 11]) + F(10, 2) , ExpVal (A[12 .. 10]) + F(9, 2) , ExpVal (A[12 .. 9]) + F(8, 2) , // this will yield the maximum sum.. ExpVal (A[12 .. 8]) + F(7, 2) , ExpVal (A[12 .. 7]) + F(6, 2) } which is nothing but, F(12, 3) = MAX { 1/2 + F(10, 2) , 2/3 + F(9, 2) , 2/4 + F(8, 2) , // this will yield the maximum sum.. 3/5 + F(7, 2) , 4/6 + F(6, 2) } Trace the above equation and you should get it.. On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote: Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution.
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2).. The reasoning being say, We store all the values in a 2-d array of size N * K. Now to compute each element of the above array , we are looking at N/ K (3n/2k - n/2k) sub problems.. Hence, the running time would be, O( N * K * N / K ) i.e O( N^2)... On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote: I don't think it is O(N*K) It is O(N^2) Just to confirm if i have understood correctly Lets say n and k are given and are global to all subproblems Subproblem Definition F[i,j] - maximum expected sum that we can get by partitioning array from 0 to i into j subarrays. Each subarray satisfies the size bound [ceiling(n/2k),floor(3n/2k)] F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of subarray from i-r+1 to i} So to calculate every subsequent subproblem we need to check solutions to O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2) On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote: Hi I may not have understood your solution properly. But i think that your solution is an implementation of brute force where you are dealing with all cases valid in the range n/2k and 3n/2k without any optimization with regard to DP. Am i right? On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote: Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this constraint is not satisfied then its not a valid candidate for the solution even if the partition produces the max value. 2 = ceil (n / 2k) = ceil (12/6) 6 = floor (3n / 2k) = floor (36/6) - As mentioned above the following equation : F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } /** For understanding how partitioning of the array is represented by the above equation: Say there is an array denoted by A[i] and it needs to be divided into 3 contiguous parts, one of the ways to do so would be to take the following steps : Let K(partition no.) be initialized to 3. Let array size N be 12. a) If N is 0, the goto step 'f' b) If K == 1 then call it as partition K and goto step 'e'. c) Lets take X no. of elements from the end of array A of size N and call it partition K. d) Decrement K by 1 and N by X { --K; and N-=X;} d) Goto step 'a' e) Valid partition and End. f) Not a valid partition and End. Now if the above set of steps is run for all values of X such that 2=X=6 , then it will generate all possible candidates (partitions) as per the given problem statement. And for all the valid partitions(the ones that will hit step 'e') we need to calculate the expected sum value. **/ can be translated into, // I am using 1-based array indexing for better clarity // A[x .. y] means all elements from A[y] to A[x].. F(12, 3) = MAX { ExpVal (A[12 .. 11]) + F(10, 2) , ExpVal (A[12 .. 10]) + F(9, 2) , ExpVal (A[12 .. 9]) + F(8, 2) , // this will yield the maximum sum.. ExpVal (A[12 .. 8]) + F(7, 2) , ExpVal (A[12 .. 7]) + F(6, 2) } which is nothing but, F(12, 3) = MAX { 1/2 + F(10, 2) , 2/3 + F(9, 2) , 2/4 + F(8, 2) , // this will yield the maximum sum.. 3/5 + F(7, 2) , 4/6 + F(6, 2) } Trace the above equation and you should get it.. On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote: Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2).. The reasoning being say, We store all the values in a 2-d array of size N * K. Now to compute each element of the above array , we are looking at N/ K (3n/2k - n/2k) sub problems.. Hence, the running time will be, O( N * K * N / K ) i.e O( N^2)... On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote: I don't think it is O(N*K) It is O(N^2) Just to confirm if i have understood correctly Lets say n and k are given and are global to all subproblems Subproblem Definition F[i,j] - maximum expected sum that we can get by partitioning array from 0 to i into j subarrays. Each subarray satisfies the size bound [ceiling(n/2k),floor(3n/2k)] F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of subarray from i-r+1 to i} So to calculate every subsequent subproblem we need to check solutions to O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2) On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote: Hi I may not have understood your solution properly. But i think that your solution is an implementation of brute force where you are dealing with all cases valid in the range n/2k and 3n/2k without any optimization with regard to DP. Am i right? On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote: Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this constraint is not satisfied then its not a valid candidate for the solution even if the partition produces the max value. 2 = ceil (n / 2k) = ceil (12/6) 6 = floor (3n / 2k) = floor (36/6) - As mentioned above the following equation : F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } /** For understanding how partitioning of the array is represented by the above equation: Say there is an array denoted by A[i] and it needs to be divided into 3 contiguous parts, one of the ways to do so would be to take the following steps : Let K(partition no.) be initialized to 3. Let array size N be 12. a) If N is 0, the goto step 'f' b) If K == 1 then call it as partition K and goto step 'e'. c) Lets take X no. of elements from the end of array A of size N and call it partition K. d) Decrement K by 1 and N by X { --K; and N-=X;} d) Goto step 'a' e) Valid partition and End. f) Not a valid partition and End. Now if the above set of steps is run for all values of X such that 2=X=6 , then it will generate all possible candidates (partitions) as per the given problem statement. And for all the valid partitions(the ones that will hit step 'e') we need to calculate the expected sum value. **/ can be translated into, // I am using 1-based array indexing for better clarity // A[x .. y] means all elements from A[y] to A[x].. F(12, 3) = MAX { ExpVal (A[12 .. 11]) + F(10, 2) , ExpVal (A[12 .. 10]) + F(9, 2) , ExpVal (A[12 .. 9]) + F(8, 2) , // this will yield the maximum sum.. ExpVal (A[12 .. 8]) + F(7, 2) , ExpVal (A[12 .. 7]) + F(6, 2) } which is nothing but, F(12, 3) = MAX { 1/2 + F(10, 2) , 2/3 + F(9, 2) , 2/4 + F(8, 2) , // this will yield the maximum sum.. 3/5 + F(7, 2) , 4/6 + F(6, 2) } Trace the above equation and you should get it.. On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote: Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution.
[algogeeks] Re: Google Question--Suggest Algo
Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 Source - http://stackoverflow.com/questions/8189334/google-combinatorial-optim... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question--Suggest Algo
Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution. This is can be handled by giving initial value to all such combination a value of -1. To store that the intermediate computations take an array Max[N][K], F(N,K) = Max[N][K] On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote: Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 Source - http://stackoverflow.com/questions/8189334/google-combinatorial-optim... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Question--Suggest Algo
Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution. This is can be handled by giving initial value to all such combination a value of -1. To store that the intermediate computations take an array Max[N][K], F(N,K) = Max[N][K] On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote: Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 Source - http://stackoverflow.com/questions/8189334/google-combinatorial-optim... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question--Suggest Algo
Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this constraint is not satisfied then its not a valid candidate for the solution even if the partition produces the max value. 2 = ceil (n / 2k) = ceil (12/6) 6 = floor (3n / 2k) = floor (36/6) - As mentioned above the following equation : F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } /** For understanding how partitioning of the array is represented by the above equation: Say there is an array denoted by A[i] and it needs to be divided into 3 contiguous parts, one of the ways to do so would be to take the following steps : Let K(partition no.) be initialized to 3. Let array size N be 12. a) If N is 0, the goto step 'f' b) If K == 1 then call it as partition K and goto step 'e'. c) Lets take X no. of elements from the end of array A of size N and call it partition K. d) Decrement K by 1 and N by X { --K; and N-=X;} d) Goto step 'a' e) Valid partition and End. f) Not a valid partition and End. Now if the above set of steps is run for all values of X such that 2=X=6 , then it will generate all possible candidates (partitions) as per the given problem statement. And for all the valid partitions(the ones that will hit step 'e') we need to calculate the expected sum value. **/ can be translated into, // I am using 1-based array indexing for better clarity // A[x .. y] means all elements from A[y] to A[x].. F(12, 3) = MAX { ExpVal (A[12 .. 11]) + F(10, 2) , ExpVal (A[12 .. 10]) + F(9, 2) , ExpVal (A[12 .. 9])+ F(8, 2) , // this will yield the maximum sum.. ExpVal (A[12 .. 8])+ F(7, 2) , ExpVal (A[12 .. 7])+ F(6, 2) } which is nothing but, F(12, 3) = MAX { 1/2 + F(10, 2) , 2/3 + F(9, 2) , 2/4 + F(8, 2) , // this will yield the maximum sum.. 3/5 + F(7, 2) , 4/6 + F(6, 2) } Trace the above equation and you should get it.. On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote: Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution. This is can be handled by giving initial value to all such combination a value of -1. To store that the intermediate computations take an array Max[N][K], F(N,K) = Max[N][K] On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote: Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4
Re: [algogeeks] Re: Google Question--Suggest Algo
Cool Solution...I was thinking of DP but wasnt clear on the recurrence... Nice thinking man and thanks :) On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote: Consider the example that you have given: [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3 Now we need to partition the array into 3 contiguous sub arrays such that : a) The expected sum value is maximum b) and the size of each sub array should be between 2 and 6, both inclusive. In case, this constraint is not satisfied then its not a valid candidate for the solution even if the partition produces the max value. 2 = ceil (n / 2k) = ceil (12/6) 6 = floor (3n / 2k) = floor (36/6) - As mentioned above the following equation : F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } /** For understanding how partitioning of the array is represented by the above equation: Say there is an array denoted by A[i] and it needs to be divided into 3 contiguous parts, one of the ways to do so would be to take the following steps : Let K(partition no.) be initialized to 3. Let array size N be 12. a) If N is 0, the goto step 'f' b) If K == 1 then call it as partition K and goto step 'e'. c) Lets take X no. of elements from the end of array A of size N and call it partition K. d) Decrement K by 1 and N by X { --K; and N-=X;} d) Goto step 'a' e) Valid partition and End. f) Not a valid partition and End. Now if the above set of steps is run for all values of X such that 2=X=6 , then it will generate all possible candidates (partitions) as per the given problem statement. And for all the valid partitions(the ones that will hit step 'e') we need to calculate the expected sum value. **/ can be translated into, // I am using 1-based array indexing for better clarity // A[x .. y] means all elements from A[y] to A[x].. F(12, 3) = MAX { ExpVal (A[12 .. 11]) + F(10, 2) , ExpVal (A[12 .. 10]) + F(9, 2) , ExpVal (A[12 .. 9])+ F(8, 2) , // this will yield the maximum sum.. ExpVal (A[12 .. 8])+ F(7, 2) , ExpVal (A[12 .. 7])+ F(6, 2) } which is nothing but, F(12, 3) = MAX { 1/2 + F(10, 2) , 2/3 + F(9, 2) , 2/4 + F(8, 2) , // this will yield the maximum sum.. 3/5 + F(7, 2) , 4/6 + F(6, 2) } Trace the above equation and you should get it.. On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote: Hey Sourabh Could you please explain the solution in a bit detail perhaps using an example or so..It wud be really helpful ..Just logic not code On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote: Looks like a dynamic programming problem Say F(n,k) denotes the maximum expected sum value for an array of n elements and partition k , then F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k) { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r, k-1) } Base condition: 1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N = floor(3n/2k) 2) If any of the sub problems where the array size is not between ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid candidate for the final solution. This is can be handled by giving initial value to all such combination a value of -1. To store that the intermediate computations take an array Max[N][K], F(N,K) = Max[N][K] On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote: Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume
[algogeeks] Re: Google Interview Question
How was your interview? Can you please share the questions for benefit of others? On Oct 1, 3:37 pm, Siddhartha Banerjee thefourrup...@gmail.com wrote: lol!!! -- 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: google os ques on pipelining
585 + (160 + 5)for slowest transactions *999 for the rest of the instructions! On Tue, Sep 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote: You guys have the right idea except that since it's multiple choice you can do this with no math. With 1000 data items and only 4 stages, the bottleneck has to be the slowest pipeline stage with its register delay. So you can answer b in 10 seconds and move on to the next question! On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote: @bharat: for the second part where u multiplied (160+5) with 999, it should be 160*999 because it is max of (150,120,160,140,5). Correct me if i am wrong. On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com wrote: for the first instruction : 150+5+120+5+160+5+140=585 ns for the rest of the instructions , though pipeline max(150,120,160,140)=160 (160+5)*999=164835 ns we assume that there will be no extra stalls existed in our system -585 + 164835 =165420 ns =165.4 us... correct me if I'm wrong . On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.com wrote: A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds) respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will approximately be a. 120 us (micro seconds) b. 165 us c. 180 us d. 175 us ...plz give detailed explanation for the ans -- 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 *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumar http://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: google os ques on pipelining
clock period=(slowest stage delay)+(Buffer delay). slowest stage delay is 160 ns and Buffer delay is 5ns. Buffer delay will always be there between two stages . clock period=165ns. In the pipelining the time it takes =(k+n-1) * (clock period) k=number of stages and n=number of instructions(data items) hence time it takes=(4+1000-1)*(165)=165.4 microsec On Tue, Sep 27, 2011 at 11:51 AM, Aditya Virmani virmanisadi...@gmail.comwrote: 585 + (160 + 5)for slowest transactions *999 for the rest of the instructions! On Tue, Sep 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote: You guys have the right idea except that since it's multiple choice you can do this with no math. With 1000 data items and only 4 stages, the bottleneck has to be the slowest pipeline stage with its register delay. So you can answer b in 10 seconds and move on to the next question! On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote: @bharat: for the second part where u multiplied (160+5) with 999, it should be 160*999 because it is max of (150,120,160,140,5). Correct me if i am wrong. On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com wrote: for the first instruction : 150+5+120+5+160+5+140=585 ns for the rest of the instructions , though pipeline max(150,120,160,140)=160 (160+5)*999=164835 ns we assume that there will be no extra stalls existed in our system -585 + 164835 =165420 ns =165.4 us... correct me if I'm wrong . On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.com wrote: A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds) respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will approximately be a. 120 us (micro seconds) b. 165 us c. 180 us d. 175 us ...plz give detailed explanation for the ans -- 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 *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumar http://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com- Hide quoted text - - Show quoted text - -- 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.
Re: [algogeeks] Re: google os ques on pipelining
Thats right. Clock speed is governed by slowest processing stage + register delay. With clock cycle of (160+5) ns even the faster stages will be forced to run slowly. As a result 1st instruction will take 165*4 ns and rest of following 999 instructions will take 165*999 ns. On Tue, Sep 27, 2011 at 4:03 PM, praneethn praneeth...@gmail.com wrote: clock period=(slowest stage delay)+(Buffer delay). slowest stage delay is 160 ns and Buffer delay is 5ns. Buffer delay will always be there between two stages . clock period=165ns. In the pipelining the time it takes =(k+n-1) * (clock period) k=number of stages and n=number of instructions(data items) hence time it takes=(4+1000-1)*(165)=165.4 microsec On Tue, Sep 27, 2011 at 11:51 AM, Aditya Virmani virmanisadi...@gmail.com wrote: 585 + (160 + 5)for slowest transactions *999 for the rest of the instructions! On Tue, Sep 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote: You guys have the right idea except that since it's multiple choice you can do this with no math. With 1000 data items and only 4 stages, the bottleneck has to be the slowest pipeline stage with its register delay. So you can answer b in 10 seconds and move on to the next question! On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote: @bharat: for the second part where u multiplied (160+5) with 999, it should be 160*999 because it is max of (150,120,160,140,5). Correct me if i am wrong. On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com wrote: for the first instruction : 150+5+120+5+160+5+140=585 ns for the rest of the instructions , though pipeline max(150,120,160,140)=160 (160+5)*999=164835 ns we assume that there will be no extra stalls existed in our system -585 + 164835 =165420 ns =165.4 us... correct me if I'm wrong . On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.comwrote: A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds) respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will approximately be a. 120 us (micro seconds) b. 165 us c. 180 us d. 175 us ...plz give detailed explanation for the ans -- 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 *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumar http://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com- Hide quoted text - - Show quoted text - -- 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. -- 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: google os ques on pipelining
@bharat: for the second part where u multiplied (160+5) with 999, it should be 160*999 because it is max of (150,120,160,140,5). Correct me if i am wrong. On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com wrote: for the first instruction : 150+5+120+5+160+5+140=585 ns for the rest of the instructions , though pipeline max(150,120,160,140)=160 (160+5)*999=164835 ns we assume that there will be no extra stalls existed in our system -585 + 164835 =165420 ns =165.4 us... correct me if I'm wrong . On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.comwrote: A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds) respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will approximately be a. 120 us (micro seconds) b. 165 us c. 180 us d. 175 us ...plz give detailed explanation for the ans -- 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 *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 to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google os ques on pipelining
You guys have the right idea except that since it's multiple choice you can do this with no math. With 1000 data items and only 4 stages, the bottleneck has to be the slowest pipeline stage with its register delay. So you can answer b in 10 seconds and move on to the next question! On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote: @bharat: for the second part where u multiplied (160+5) with 999, it should be 160*999 because it is max of (150,120,160,140,5). Correct me if i am wrong. On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com wrote: for the first instruction : 150+5+120+5+160+5+140=585 ns for the rest of the instructions , though pipeline max(150,120,160,140)=160 (160+5)*999=164835 ns we assume that there will be no extra stalls existed in our system -585 + 164835 =165420 ns =165.4 us... correct me if I'm wrong . On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.comwrote: A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds) respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will approximately be a. 120 us (micro seconds) b. 165 us c. 180 us d. 175 us ...plz give detailed explanation for the ans -- 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 *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com- Hide quoted text - - Show quoted text - -- 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: google maps
@Sukran: Well, I would hire about 1000 smart people and let them do it. :-) Dave On Sep 20, 2:12 am, sukran dhawan sukrandha...@gmail.com wrote: How do you implement google maps ? -- 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: google maps
they are using a highly optimized A* algo for rout finding On Tue, Sep 20, 2011 at 10:01 PM, Dave dave_and_da...@juno.com wrote: @Sukran: Well, I would hire about 1000 smart people and let them do it. :-) Dave On Sep 20, 2:12 am, sukran dhawan sukrandha...@gmail.com wrote: How do you implement google maps ? -- 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. -- U.D.I.T Sent by Nokia OVI (c) -- 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: google maps
Well, I think its not that the algorithm be written with all Google maps features in place. Rather it is a open ended question, where interviewer is trying to find the candidates view of algorithm design. @Deepak: It should be fine even if some reasonably good algo is given. my 2 cents: For the shortest route finding feature: I would say: Create a graph with nodes as stations and graphs as the roads/paths between station. Now Dijkstra's algo can be used to find the shortest path On Tue, Sep 20, 2011 at 10:03 PM, Deepak Garg deepakgarg...@gmail.comwrote: they are using a highly optimized A* algo for rout finding On Tue, Sep 20, 2011 at 10:01 PM, Dave dave_and_da...@juno.com wrote: @Sukran: Well, I would hire about 1000 smart people and let them do it. :-) Dave On Sep 20, 2:12 am, sukran dhawan sukrandha...@gmail.com wrote: How do you implement google maps ? -- 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. -- U.D.I.T Sent by Nokia OVI (c) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re : google groups
hi, I am not able to add a person to the algogeeks group. Is there a limit on the number of people who could join a particular google groups ? At present there are 7960 people :) -- 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 : google groups
*no, there is no such limit *regards - Sumit Kumar Pathak (Sumit/ Pathak/ SKP ...) *Smile is only good contagious thing.* *Spread it*! On Fri, Sep 9, 2011 at 1:59 PM, shady sinv...@gmail.com wrote: hi, I am not able to add a person to the algogeeks group. Is there a limit on the number of people who could join a particular google groups ? At present there are 7960 people :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question:Given a BST and a number, Find the closest node to that number in the BST.
It seems Dipankar Algo is appropriate at this point of time. each time successor and predecessor check needs to be done at each node and the value need to be updated, This is O(log n) approach because once we check, we move into particular direction. On Aug 21, 4:59 pm, rahul aravind rahularavin...@gmail.com wrote: @Abhishek:nice algo dude.. On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav algowithabhis...@gmail.com wrote: Hey i tried it now and got to another solution O(log n) solution: 1. try searching for the number , if found,return the node, otherwise, you will ultimately reach a leaf node say 'nd' 2. Now the two candidates for the answer would be 1. TreeSuccessor(nd) 2. TreePredecessor(nd) Now compare the original number with these two and minimum would be the answer. (TreeSuccessor and TreePredecessor are the next and previous node resp. in the Inorder traversal of the tree.) On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro dip10c...@gmail.comwrote: why traverse the whole tree? at each root keep the difference in a min_diff and min_ele. if the entered value is less root then move to left or right. repeat above two until whole tree is checked or min_diff becomes 0. pseudo code: min_diff = INF; // global variables min_ele = 0; find_min_diff(node *root, int num) { if (root == null) return; // update the difference if(abs(root-val - num) min_diff) { min_diff = abs(root-val - num); min_ele = root-val; } if ( min_diff == 0) return; // search is over // proceed to next element in tree which might be closer to the num if ( num root- val) find_min_ele(root-left, num); else find_min_ele(root-right, num); } ^^ Complexity : O(logn) On 20 August 2011 12:36, Abhishek Yadav algowithabhis...@gmail.comwrote: yes, the interviewer said that there is a solution in O(log n) On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan sukrandha...@gmail.comwrote: ur traversing the tree once so it shud be o(n).does the question demand 0(logn) ? On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav algowithabhis...@gmail.com wrote: what would be the complexity of your solution O(n) or O(log n)..? On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan sukrandha...@gmail.com wrote: traverse bst inorder and each time u encounter a node find the difference between the element and given element in question . if the absolute difference is minimum after traversing the tree that is the element . u can getback the element using another element which keeps sign of the element so that original element can be obtained from diff On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav algowithabhis...@gmail.com wrote: Given a BST and a number, Find the closest node to that number in the BST. Give an algorithm for that. Let there be binary search tree having nodes with values 12,34,64,23,64,25,76,6 and the number given is 28, then the answer would be 25 as it is the closest node. -- 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. -- 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. -- ___ Please do not print
[algogeeks] Re: Google Interview Question
Here is O(n) alg... Does Waste Memory Though :) just don't have an array over 4G, and you should be good. proc Merge_Partition(A) B = {}; index = 0; count0 = 0; count1 = (n/2); while index to A.length B[index++] = A[count0++]; B[index++] = A[count1++]; end while return B end proc On Aug 1, 1:30 pm, Manmeet Singh mans.aus...@gmail.com wrote: Your code does not works proper;y for all cases On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan jalanha...@gmail.com wrote: Here is the recursive algo: Rearrange(A,p,q) 1. if p is not equal to q do the following 2. r ← (p+q)/2 3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2]. 4. Rearrange(A,p,r) 5. Rearrange(A,r+1,q) 6. return On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta gupta.abh...@gmail.comwrote: A is an array of size 2n such that first n elements are integers in any order and last n elements are characters. i.e. A={i1 i2 i3 in c1 c2 c3... cn} then we have to rearrange the elements such that final array is A ={ i1 c1 i2 c2 .. in cn} Example : input : A ={ 5,1,4,d,r,a}; output : A= {5,d,1,r,4,a}; -- Abhishek Gupta MCA NIT Calicut Kerela -- 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 : ROHIT JALAN B.E. Graduate, Computer Science Department, RVCE, Bangalore -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Interview Question
This is a simple merge, so what is the trick? Did you forget something? On Mon, Aug 1, 2011 at 3:19 PM, Gary Drocella gdroc...@gmail.com wrote: Here is O(n) alg... Does Waste Memory Though :) just don't have an array over 4G, and you should be good. proc Merge_Partition(A) B = {}; index = 0; count0 = 0; count1 = (n/2); while index to A.length B[index++] = A[count0++]; B[index++] = A[count1++]; end while return B end proc On Aug 1, 1:30 pm, Manmeet Singh mans.aus...@gmail.com wrote: Your code does not works proper;y for all cases On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan jalanha...@gmail.com wrote: Here is the recursive algo: Rearrange(A,p,q) 1. if p is not equal to q do the following 2. r ← (p+q)/2 3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2]. 4. Rearrange(A,p,r) 5. Rearrange(A,r+1,q) 6. return On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta gupta.abh...@gmail.comwrote: A is an array of size 2n such that first n elements are integers in any order and last n elements are characters. i.e. A={i1 i2 i3 in c1 c2 c3... cn} then we have to rearrange the elements such that final array is A ={ i1 c1 i2 c2 .. in cn} Example : input : A ={ 5,1,4,d,r,a}; output : A= {5,d,1,r,4,a}; -- Abhishek Gupta MCA NIT Calicut Kerela -- 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 : ROHIT JALAN B.E. Graduate, Computer Science Department, RVCE, Bangalore -- 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. -- --- Douglas Gameiro Diniz Engenheiro de Computação - 2003 - UNICAMP Mobile: (19) 92158777 Gtalk: dgdiniz Msn: thedougdi...@hotmail.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.
Re: [algogeeks] Re: Google Interview Question
@Diniz I guess they asked to do in inplace ( with no extra array ) On Mon, Aug 1, 2011 at 2:41 PM, Douglas Diniz dgdi...@gmail.com wrote: This is a simple merge, so what is the trick? Did you forget something? On Mon, Aug 1, 2011 at 3:19 PM, Gary Drocella gdroc...@gmail.com wrote: Here is O(n) alg... Does Waste Memory Though :) just don't have an array over 4G, and you should be good. proc Merge_Partition(A) B = {}; index = 0; count0 = 0; count1 = (n/2); while index to A.length B[index++] = A[count0++]; B[index++] = A[count1++]; end while return B end proc On Aug 1, 1:30 pm, Manmeet Singh mans.aus...@gmail.com wrote: Your code does not works proper;y for all cases On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan jalanha...@gmail.com wrote: Here is the recursive algo: Rearrange(A,p,q) 1. if p is not equal to q do the following 2. r ← (p+q)/2 3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2]. 4. Rearrange(A,p,r) 5. Rearrange(A,r+1,q) 6. return On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta gupta.abh...@gmail.comwrote: A is an array of size 2n such that first n elements are integers in any order and last n elements are characters. i.e. A={i1 i2 i3 in c1 c2 c3... cn} then we have to rearrange the elements such that final array is A ={ i1 c1 i2 c2 .. in cn} Example : input : A ={ 5,1,4,d,r,a}; output : A= {5,d,1,r,4,a}; -- Abhishek Gupta MCA NIT Calicut Kerela -- 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 : ROHIT JALAN B.E. Graduate, Computer Science Department, RVCE, Bangalore -- 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. -- --- Douglas Gameiro Diniz Engenheiro de Computação - 2003 - UNICAMP Mobile: (19) 92158777 Gtalk: dgdiniz Msn: thedougdi...@hotmail.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. -- 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: Google interview question
@Dave awesome..! On Sat, Jul 16, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote: @Anand: Assuming that the file contains unsigned 32-bit integers. Set an integer array a[65536] to zero, read through the file and tally the numbers based on their low-order 16 bits: a[j0x]++. Since 4.3 billion exceeds 2^32, by the pigeonhole principle, there will be at least one tally, say a[k], that has a value greater than 65536. Set the array to zero again. Read through the file again. Ignore all of the numbers whose low-order 16 bits are not k, and tally numbers based on their upper 16 bits: a[(j16)0x]++. Again by the pigeonhole principle, there will be at least one number that exceeds 1. Now you know the high-order 16 bits and the low-order 16 bits of a number that occurs at least twice. You can quit the second pass as soon as you have your first tally equalling 2. Dave On Jul 15, 8:28 pm, Anand Shastri anand.shastr...@gmail.com wrote: Given a file containing 4,300,000,000 integers, how can you *find **one* that *appears* at *least **twice* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google interview question
how about using voters algorithm? TC O(n) and SC O(1) On Jul 16, 6:28 am, Anand Shastri anand.shastr...@gmail.com wrote: Given a file containing 4,300,000,000 integers, how can you *find **one* that *appears* at *least **twice* -- 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: Google interview question
If the there are problems with hashing method, What about simply sorting the numbers then comparing the adjacent numbers ! Time complexity O(nlogn)+O(n)=O(nlogn) Cheers! -- 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/-/b2Z_3lJHz9wJ. 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: Google interview question
@Anand: Assuming that the file contains unsigned 32-bit integers. Set an integer array a[65536] to zero, read through the file and tally the numbers based on their low-order 16 bits: a[j0x]++. Since 4.3 billion exceeds 2^32, by the pigeonhole principle, there will be at least one tally, say a[k], that has a value greater than 65536. Set the array to zero again. Read through the file again. Ignore all of the numbers whose low-order 16 bits are not k, and tally numbers based on their upper 16 bits: a[(j16)0x]++. Again by the pigeonhole principle, there will be at least one number that exceeds 1. Now you know the high-order 16 bits and the low-order 16 bits of a number that occurs at least twice. You can quit the second pass as soon as you have your first tally equalling 2. Dave On Jul 15, 8:28 pm, Anand Shastri anand.shastr...@gmail.com wrote: Given a file containing 4,300,000,000 integers, how can you *find **one* that *appears* at *least **twice* -- 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: GOOGLE Q
Hi, here i maintained two pair of indexes with respect to a and b, reply if u found any test case which fails.. int npairs() { int a[] = {0,1,4,5,9,11,20}; int b[] = {0,2,3,6,8,11,15}; int c[20]; int len = sizeof(a)/sizeof(a[0]); int i1,j1,i2,j2; i1=len-1; j1=len-2; i2=len-2; j2=len-1; int count = 0; c[count++] = a[len-1]+b[len-1]; //obvious while(count=len) { if( (a[i1-1]+a[j2-1] a[i1]+b[j1]) (a[i1-1]+a[j2-1] a[i1]+b[j1]) ) { c[count++] = a[i1-1]+b[j2-1]; //highest sum with higher numbers have exhausted i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1; continue; } if(a[i1]+b[j1] = a[i2]+b[j2] ) { c[count++] = a[i1]+b[j1]; j1--; } else { c[count++] = a[i2]+b[j2]; i2--; } } for(int i =0;ilen;i++) printf(%d ,c[i]); return 0; } surender On Mon, Jul 11, 2011 at 10:46 AM, sunny agrawal sunny816.i...@gmail.comwrote: A = 0, 1, 4, 5, 9, 11, 20 B = 0, 2, 3, 6, 8, 13, 15 (20, 15) (20, 15) - (20,15) (20,13) (11,15) - (20,13) (20,8) (11,15) - (20,8) (20,6) (11,15) - assume (20,6) (20,3) (11,15) - (11,15) (20,3) (9,15)- (9,15) (20,3) (5,15)- (20,3) .problem (11,13) has higher value but did i missed something ?? -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: GOOGLE Q
Find the largest ceil(sqrt(n)) elements of A and B using a sliding window in time O(n) and then take their cross in time sqrt(n)^2 ie O(n). --Shambo On Mon, Jul 11, 2011 at 12:37 PM, surender sanke surend...@gmail.comwrote: Hi, here i maintained two pair of indexes with respect to a and b, reply if u found any test case which fails.. int npairs() { int a[] = {0,1,4,5,9,11,20}; int b[] = {0,2,3,6,8,11,15}; int c[20]; int len = sizeof(a)/sizeof(a[0]); int i1,j1,i2,j2; i1=len-1; j1=len-2; i2=len-2; j2=len-1; int count = 0; c[count++] = a[len-1]+b[len-1]; //obvious while(count=len) { if( (a[i1-1]+a[j2-1] a[i1]+b[j1]) (a[i1-1]+a[j2-1] a[i1]+b[j1]) ) { c[count++] = a[i1-1]+b[j2-1]; //highest sum with higher numbers have exhausted i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1; continue; } if(a[i1]+b[j1] = a[i2]+b[j2] ) { c[count++] = a[i1]+b[j1]; j1--; } else { c[count++] = a[i2]+b[j2]; i2--; } } for(int i =0;ilen;i++) printf(%d ,c[i]); return 0; } surender On Mon, Jul 11, 2011 at 10:46 AM, sunny agrawal sunny816.i...@gmail.comwrote: A = 0, 1, 4, 5, 9, 11, 20 B = 0, 2, 3, 6, 8, 13, 15 (20, 15) (20, 15) - (20,15) (20,13) (11,15) - (20,13) (20,8) (11,15) - (20,8) (20,6) (11,15) - assume (20,6) (20,3) (11,15) - (11,15) (20,3) (9,15)- (9,15) (20,3) (5,15)- (20,3) .problem (11,13) has higher value but did i missed something ?? -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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.
Re: [algogeeks] Re: GOOGLE Q
@Shambo: That doesn't work. Consider: A = 1 10 100 1000 B = 1 2 3 4 The top 4 pairs are: (1000,4), (1000,3), (1000,2) and (1000,1) -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/WyVibLRFx9kJ. 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: GOOGLE Q1
it has O(n2) solution take nxn matrix and for every a[j](j=1 to n) store the d (a[j]-a[i]) value for all i j the trick is that d of the longest AP will occur maximum number of times in matrix count the maximum occuring d value and reconstruct the sequence by going through matrix -Ritu -- 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: GOOGLE Q
@Sunny: Thanks for this counterexample. The O(N) algorithm currently seems unfeasible to me. @Piyush: Are you sure an O(N) algo exists? Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's algo as it doesn't generate duplicates) For arrays A = a1 a2 ... an B = b1 b2 bn Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this). Insert (an, bn). Repeat N Times { Pop off and output the max value from the priority queue. Let that be (ai, bj) // O(log N) if(i == j) { Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. // O(log n) } else if(i j) { Insert (ai-1, bj) in the priority queue. // O(log n) } else { Insert (ai, bj-1) in the priority queue. // O(log n) } } Time complexity: O(N log N) Space complexity: O(N) ?? -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/XCjyFaTFD-UJ. 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: GOOGLE Q
@Dk..i dint frame the question buddy...:P I found it over here http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-75 On Mon, Jul 11, 2011 at 3:14 PM, DK divyekap...@gmail.com wrote: @Sunny: Thanks for this counterexample. The O(N) algorithm currently seems unfeasible to me. @Piyush: Are you sure an O(N) algo exists? Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's algo as it doesn't generate duplicates) For arrays A = a1 a2 ... an B = b1 b2 bn Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this). Insert (an, bn). Repeat N Times { Pop off and output the max value from the priority queue. Let that be (ai, bj) // O(log N) if(i == j) { Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. // O(log n) } else if(i j) { Insert (ai-1, bj) in the priority queue. // O(log n) } else { Insert (ai, bj-1) in the priority queue. // O(log n) } } Time complexity: O(N log N) Space complexity: O(N) ?? -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/XCjyFaTFD-UJ. 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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: GOOGLE Q
small mistake change a to b if( (a[i1-1]+b[j2-1] a[i1]+b[j1]) (a[i1-1]+a[j2-1] a[i1]+b[j1]) ) surender On Mon, Jul 11, 2011 at 3:54 PM, DK divyekap...@gmail.com wrote: @surender: Your algo fails. See the counterexample posted by Sunny. -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/ITTX48LIzcUJ. 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.