[algogeeks] Re: Directi Question
@maddy: The students should be assigned consecutive books only. That is, u CANNOT assign book 1, 2 and 5 to a single student. either assign book 1, 2 and 3 or 1 and 2 or any such combination of consecutive numbers. On Thursday, June 14, 2012 12:26:09 PM UTC+5:30, algogeek wrote: In a library there are N books with the number of pages in i th book given by bi . These books are to be distributed among K students such that the difference between the largest sum of pages in the books assigned to any student and the smallest sum of number of pages in the books assigned to any student is minimum for the given input. Also the books are arranged in a certain order and this order must never be changed. For eg: suppose B[ ] contains the number of pages in each book. then N=6 K=3 B={3,7,8,2,6,4} then the output will be 0 as we can give book 1 and 2 to student 1 and book 3 and 4 to student 2 and the remaining to student 3. That makes 10 pages for student 1 10 for 2 and 10 for 3 and thus the difference is 0 similarly if B={3,6,8,2,6,4} then the minimum difference will be 1 . -- 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/-/7jAw-C4JI1AJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] expectation values..
What is the expected number of throws of his die while it has N sides so that each number is rolled at least once? e.g for n=2 ans 3.00 n=12 ans is 37.24... i refrd to expectation tutuorial at http://www.codechef.com/wiki/tutorial-expectation but still couldnt get the logic... any help? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Interview Question
could u explain how would you use a trie for this?? On Thursday, June 14, 2012 1:01:00 PM UTC+5:30, Mohit Rathi wrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1,* *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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/-/-BW4cpALLgIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Interview Question
Store each of the words in array in a trie and mark the end of the word by its corresponding entry in the second array. Now if u are searching for a word it'll take O(length of word) if there is a mismatch at any point you know the word is not present in array1 and add it to the trie or else the entire string might match but not terminate in an index implying the word being searched for is a prefix for a word already present. Add the entry if not present to the trie as well as to the array append the index of the word in trie with value entered by the user. On Saturday, 16 June 2012 20:36:42 UTC+5:30, algogeek wrote: could u explain how would you use a trie for this?? On Thursday, June 14, 2012 1:01:00 PM UTC+5:30, Mohit Rathi wrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1,* *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- 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/-/mJL9Nk2nSM4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Explain the output of this code:
#includestdio.h main() { int a[] = {0,1,2,3,4}; int *p[] = {a,a+1,a+2,a+3,a+4}; int **pp= p; printf(%d, %d, %d , *pp-a, pp-p, **pp); pp++; pp++;; ++pp; *++pp; printf(%d, %d, %d , pp-p, *pp-a, **pp); } output:0 ,0 ,0 ,4 ,4 ,4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Explain the output of this code:
*p[] is an array of pointers pointing to the address of array a[] .. i.e p[0] pointing to a[0]..p[1] to a[1] and so on. *pp is a pointer to a pointer. It is storing the address of array of pointers p. 1. *pp gives value at pointed by p[0]. This is 'a'. So when 'a' is subtracted from it, it returns 0. 2. pp gives the address of pointer p. This is same as 'p' as it also denotes address of pointer p. Therefore 0 again. 3. **pp gives value at pointer p[0]. That is it gives value a[0] which is 0. pp++, ++p, *++p ..all these increment address of pp pointing to and not the value. So, it increments pp to +4 address of what it was previously pointing to. 4. pp-p means subtracting address of old pp and new pp, which must be four as address p+4 = address new pp. 5. (*pp -a) means subtract value where pp is pointing -'a' . As pp is incremented 4 times, it is pointing to 'a+4' . So ans is a+4-a which is 4. 6. Lastly, **pp gives the value of address stored at (*p) i.e. *(a+4) which is a[4]. Value of a[4] = 4 and so in the answer ;) On 16 June 2012 22:25, Shubham Sandeep s.shubhamsand...@gmail.com wrote: #includestdio.h main() { int a[] = {0,1,2,3,4}; int *p[] = {a,a+1,a+2,a+3,a+4}; int **pp= p; printf(%d, %d, %d , *pp-a, pp-p, **pp); pp++; pp++;; ++pp; *++pp; printf(%d, %d, %d , pp-p, *pp-a, **pp); } output:0 ,0 ,0 ,4 ,4 ,4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sajal Choudhary Undergraduate Student, Division of Computer Engineering, Netaji Subhas Institute of Technology, New Delhi. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Can anyone plz explain how we get this output
If you evaluate the expressions from right to left and print the result from left to right , it will be clear. On Thursday, June 14, 2012 11:41:04 AM UTC+5:30, Ajesh js wrote: main() { int a=10,b=5; printf(%d %d %d\n,a++,a,++a); printf(%d %d %d\n,++b,b,b++); } output 11 12 12 7 7 5 -- 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/-/rpQU8ga6Ev4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] expectation values..
This problem is similar to Coupan collector problem. http://en.wikipedia.org/wiki/Coupon_collector%27s_problem In your case the answer is [image: For N-Dice ; \newline \sum_{i=1}^{N} N/i \newline for\; N =~2 ; \newline \sum_{i=1}^{2} 2/i = 2/1 + 2/2 = 3 \newline] Hope it helps! -- Amitesh On Sat, Jun 16, 2012 at 5:18 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: What is the expected number of throws of his die while it has N sides so that each number is rolled at least once? e.g for n=2 ans 3.00 n=12 ans is 37.24... i refrd to expectation tutuorial at http://www.codechef.com/wiki/tutorial-expectation but still couldnt get the logic... any help? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Analysis of Partial Sorting.
Hi Guys, *Problem: *Rearrange a given array with n elements, so that m places contain the m smallest elements in ascending order. *Solution 2:* using QuickSort method approach. [image: n = r -p + 1] [image: \bold{PARTIAL-QUICKSORT(A,p,r,m)}: \newline if\; pr \newline q \leftarrow RANDOMIZED-PARTITION(A,p,r) \newline PARTIAL-QUICKSORT(A,p,q-1,m) \newline if \; qm-1 \newline PARTIAL-QUICKSORT(A,q+1,r,m)] http://amiteshsingh.wordpress.com/2012/06/16/partial-sorting/ I know if m = n, then complexity of Partial sorting is same as QuickSort. but what would be the *average case analysis* in terms of n and m? Any suggestion would be highly appreciated. -- Amitesh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] expectation values..
just curious to know if this question is asked in any interviews? Google interview? -- Amitesh On Sun, Jun 17, 2012 at 12:09 AM, Amitesh Singh singh.amit...@gmail.comwrote: This problem is similar to Coupan collector problem. http://en.wikipedia.org/wiki/Coupon_collector%27s_problem In your case the answer is [image: For N-Dice ; \newline \sum_{i=1}^{N} N/i \newline for\; N =~2 ; \newline \sum_{i=1}^{2} 2/i = 2/1 + 2/2 = 3 \newline] Hope it helps! -- Amitesh On Sat, Jun 16, 2012 at 5:18 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: What is the expected number of throws of his die while it has N sides so that each number is rolled at least once? e.g for n=2 ans 3.00 n=12 ans is 37.24... i refrd to expectation tutuorial at http://www.codechef.com/wiki/tutorial-expectation but still couldnt get the logic... any help? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Directi question-centre of the tree
I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/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/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Adobe interiew question
Also, goto cannot jump across functions , which imposes a major setback for its use in exception handling -- 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/-/RKXWsjworqEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the Max from each sub-array of size k
@ALL can be solved using segment tree . :-) On Fri, Sep 2, 2011 at 9:49 AM, Anup Ghatage ghat...@gmail.com wrote: I just checked Shashank's blog post. The Deque solution is awesome :) -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.