Re: [algogeeks] Re: MS Interview
Could someone illustrate the XOR for question 2. I am a beginner to this. Many thanks! On Thu, Jun 9, 2011 at 4:58 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Xoring it twice ...once with the elements in the file and then from i=1 to 4,000,000,000..the answer left is the missing number On Thu, Jun 9, 2011 at 4:46 PM, Dumanshu duman...@gmail.com wrote: I dont think numbers are sorted in the 1st question. btw @sunny: how will xor-ing give the ans? for 1st ques? On Jun 9, 3:34 pm, sunny agrawal sunny816.i...@gmail.com wrote: yes, but using xor no need of ULL :) 2011/6/9 • » νιρυℓ « • vipulmehta.1...@gmail.com Sum wont overflow, ULL range will include sum. On Thu, Jun 9, 2011 at 3:52 PM, sunny agrawal sunny816.i...@gmail.comwrote: sum can overflow Xor method can also be applied to Q1. no need of numbers to be sorted. 2011/6/9 • » νιρυℓ « • vipulmehta.1...@gmail.com For 1. sum the numbers in the file, subtract it from sum of first 4 billion numbers. On Thu, Jun 9, 2011 at 3:44 PM, Navneet Gupta navneetn...@gmail.comwrote: The answer to second question is simple. XORing all the elements should do it for you. On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu duman...@gmail.com wrote: Q1. I have a file in which there are supposed to be 4 billion numbers, starting from 1 to 4,000,000,000 but unfortunately one number is missing, i.e there are only 3,999,999,999 numbers, I need to find the missing number. Q2. I have an array consisting of 2n+1 elements. n elements in it are married, i.e they occur twice in the array, however there is one element which only appears once in the array. I need to find that number in a single pass using constant memory. {assume all are positive numbers} Eg :- 3 4 1 3 1 7 2 2 4 Ans:- 7 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Vipul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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, Vipul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. 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 post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group,
Re: [algogeeks] MS Q
I think RGGB is invalid as we have 4 different colors. On Fri, Jun 10, 2011 at 10:10 AM, Harshal hc4...@gmail.com wrote: #includeiostream #includestring using namespace std; void mastermind(char* guess, char* sol, int *hits, int *pseudohits) { int temp[256] = {0}; int len1=strlen(sol); int len2=strlen(guess); while(--len1+1) (guess[len1]==sol[len1]) ? ((*hits)+=1,temp[len1] = 1) : (temp[sol[len1]] += 1); while(--len2+1) if(temp[len2]!=1 temp[guess[len2]] 0) (*pseudohits)++, temp[guess[len2]] -= 1; } int main() { int hits=0,pseudo=0; mastermind(RGGB,YRGB,hits,pseudo); couthits pseudo; } On Fri, Jun 10, 2011 at 2:31 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Game of master mind: you have four balls, and four different colors, as a solution. The user tries to guess the solution. If they guess the right color for the right spot, it counts as a 'hit'. If it's the right color, but the wrong spot, it counts as a psuedo-hit. For example: if the solution is 'RGGB' and the user guesses 'YRGB' they have 2 hits and one pseudo hit. Write a program to, given a solution and a guess, calculate the number of hits and pseudo hits. -- *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. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] GOOGLE Q
How will BFS give a rearrangement ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Application of Data Structure System Design
int max_calls[no_of_customers][30]; On any phone call -- max_calls[customer_id][day]++; On hangup -- max_call[customer_id][day]--; This would store max calls for each customer on each day. Does the length of the call have to be taken into account ? Your question is not clear on that. On Tue, Mar 29, 2011 at 3:51 PM, bittu shashank7andr...@gmail.com wrote: Pretend you work for a phone company. At your company, yoy u have a satellite that routes phone calls. We want to bill customers by the maximum number of simultaneous phone calls they make in a single day. ( clarifying questions with the following information: assume no calls last more than 24 hours and that at midnight each night all the calls are automatically dropped. In the event that one call ends as soon as another starts). What information should the satellite store for each phone call? Define a data structure for this (e.g. write a struct). Write a function that finds the maximum number of simultaneous phone calls from a given customer. (Hint: typical solution is O(nlogn), but if you use an absurd amount of memory it can be done in O(n)). Best Designing DS, Approach Will b highly Appreciated Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Application of Data Structure System Design
no this is wrong. maintain 2 arrays int max_calls[no of cust][31] int current_no_of_calls[no of customers] both array of customers are initialized to zero. on call current_no_of_calls[cust_id]++; if above max[id][day] then max_calls[id][day] = above on hangup current_no_of_calls[cust_id]--; On Tue, Mar 29, 2011 at 4:29 PM, Ashim Kapoor ashimkap...@gmail.com wrote: int max_calls[no_of_customers][30]; On any phone call -- max_calls[customer_id][day]++; On hangup -- max_call[customer_id][day]--; This would store max calls for each customer on each day. Does the length of the call have to be taken into account ? Your question is not clear on that. On Tue, Mar 29, 2011 at 3:51 PM, bittu shashank7andr...@gmail.com wrote: Pretend you work for a phone company. At your company, yoy u have a satellite that routes phone calls. We want to bill customers by the maximum number of simultaneous phone calls they make in a single day. ( clarifying questions with the following information: assume no calls last more than 24 hours and that at midnight each night all the calls are automatically dropped. In the event that one call ends as soon as another starts). What information should the satellite store for each phone call? Define a data structure for this (e.g. write a struct). Write a function that finds the maximum number of simultaneous phone calls from a given customer. (Hint: typical solution is O(nlogn), but if you use an absurd amount of memory it can be done in O(n)). Best Designing DS, Approach Will b highly Appreciated Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] finds a pair of close numbers
On Fri, Apr 1, 2011 at 6:02 PM, snehal jain learner@gmail.com wrote: For a set S of n real numbers, a pair of elements x, y belong to S, where x y, are said to be close if y – x = ( max(S) – min(S) ) / (n-1) Suppose you are given an unsorted array A[1 : n] of distinct real numbers. Design an algorithm that finds a pair of close numbers in A in O(n) time. Take any 2 no.s a and b say 1st and 2nd then a-b = max(S) - min(S) divide by n-1 (a-b) / (n-1) = (Max - min) /(n-1) Solution : Any 2 no.s will do Am I incorrect somewhere ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Check out One More Interesting Challenging Question...Longest Consecutive Elements Sequence.
One more query, insert into bst is O(n) and then do inorder to get them in sorted order. This is an example of sorting in O(n) time. is this correct? On Mon, Mar 28, 2011 at 6:06 PM, Ashim Kapoor ashimkap...@gmail.com wrote: How do you use inorder traversal to find longest sub sequence? On Mon, Mar 28, 2011 at 6:03 PM, bittu shashank7andr...@gmail.com wrote: its (not aplicable). sorting nlogn i said time O(n) O(1) space i think we can use BST , put all elements in BST O(n) then do inorderto find longest sub sequence still O(n) ..no no no its Ol(ogn) suggest another way to solve it Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Check out One More Interesting Challenging Question...Longest Consecutive Elements Sequence.
How do you use inorder traversal to find longest sub sequence? On Mon, Mar 28, 2011 at 6:03 PM, bittu shashank7andr...@gmail.com wrote: its (not aplicable). sorting nlogn i said time O(n) O(1) space i think we can use BST , put all elements in BST O(n) then do inorder to find longest sub sequence still O(n) ..no no no its Ol(ogn) suggest another way to solve it Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: finds a pair of close numbers
Hi , Use Hashing for That , for sum =12 arr[]={2,4,3,6,5,8,7}; store in to hashtable for each index=0 in loop find sum-arr[index] so fro sum =12 if we do index=1 a[1]=4 sum-a[1]=8 so stop it we have done..hope make d perfect code. time Complxity o(n) space size of hashtable Let me me if anything wrong ?? It's not clear to me. Can you please explain in simple words? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Application of Prime Number . An Interesting For Geeks
Dear Shashank, What you are trying to do is called Goldbach's conjecture . Google for it. There is a million dollar prize to prove it. Ashim On Thu, Mar 24, 2011 at 8:03 PM, ligerdave david.c...@gmail.com wrote: I have to say: to prove the correctness of this hypotheses is a wrong question and there isn't an algorithm for proving something that's infinity. even number is 2n, where n=1 to infinity. you can only prove the hypotheses through mathematical methods. you can verify the correctness. it's like a P=NP kinda thing. On Mar 24, 1:49 am, bittu shashank7andr...@gmail.com wrote: yesterday one of the my friends asked this Q to me prove with correctness that Every even integer greater than 2 can be expressed as the sum of two primes e.g 4 = 2 + 2 6 = 3 + 3 10 = 7 + 3 or 5 + 5 14 = 3 + 11 or 7 + 7 Explain Derive The Time ,Space Complexity of Algorithm it seems to be that we have to find all possible prime factor of number prints it its not big task , so by checking that number we have to generate the all prime factor of it seems O(n) ..Hope i m clear corrcet me if i am wrong here.?? But problem come when even number become bigger say 1 billion 10^9 so for this choosing the a number as a prime factor has probability of 1/ln(n) so say if for 1 billion number out of 21 only 1 is prime. .y question is we have to prove the time complexity for two choosing a number nearby such big number is 1/ln(n)..?? with Heuristic justification it can be explained ro induction might help but guarantee here but i need some mathematical proof for this Thank Regards Shashank Mani CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Pairwise Sum Array
I think the output is wrong. It should be 1 3 4 9 n in no call them ai's a[1] to a[n] 4 5 10 7 12 13 m in no call them bi's b[1] to b[m] I assume starting from 1 to make manipulation easier n(n-1)/2= m n(n-1)=2m n2 -n -2m=0 using quadratic formula:- n=1 + sqrt( 1+8m)/2 This will always be a whole no if it isnt then error. Once I know n then what remains is algebraic manipulation. fill in the following matrix :- a1+a2 a1+a3 ... a1+an = b1 .. bn NOTE! n not m a2+a3 .. a2+an = b(n+1)..b(2n) an-1+an=bm 12 13 1n 23 2n (n-1)n 1st ALL C[i][j]=0; i : 1 to n-1 and j : 2 to n offset=0 Then for( i=1; i=(n-1) ; i++) for( j=i+1; j=n ; j++) { C[i][j] = b[ offset + j - 1 ] ; } offset= offset+j-1; } for( i=1; i=(n-1) ; i++) for( j=i+1; j=n ; j++) { D[i][j] = C[i][j] - C[i+1][j]; } } now C[i][j] = a[i] + a[j] D[i][j+1] = a[i]-a[j] We may solve for the a[i]'s. ( see rough figure below) Subtract R i+1 from R i a1+a2 (a1-a2) ... a1-a2 = RHS a2+a3 ...a2-a3 = RHS an-2+an-1 an-2-an-1 =RHS an-1+an=RHS I am in a hurry as I have to go home now, sorry, but I think people will see the solution. Is there a better way? Ashim. On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan radhakrishnance...@gmail.com wrote: This s a topcoder problem :) On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9 Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Pairwise Sum Array
That is exactly what my solution is doing. On Thu, Feb 24, 2011 at 5:09 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: There must be another good solution..please let me know . Thanks On Thu, Feb 24, 2011 at 5:09 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: I think.. As like no are a,b,c,d,e so sum will be a+b,a+c,a+d,a+e,b+c,b+d,b+e,c+d,c+e,d+e; so maximuum value will be d+e which is last element of array given take last three value 1.c+d 2.c+e 3.d+e eq(1)-eq(2)=d-e; solving it with 3rd eq will give d and e and with these value we can get other values On Thu, Feb 24, 2011 at 2:52 AM, radha krishnan radhakrishnance...@gmail.com wrote: This s a topcoder problem :) On Wed, Feb 23, 2011 at 7:16 PM, bittu shashank7andr...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9 Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Application Data Structure In Collision Detection
also since each object is a rigid body each point in any one object will have the same equation of motion. On Wed, Feb 16, 2011 at 8:04 PM, Ashim Kapoor ashimkap...@gmail.com wrote: Here is my attempt it's very naive but maybe someone can improve each object be a pointer to a set of points { these points are the boundary of the object } Collision detection : Sweep through each pair of pointers to check for equality of the boundary points. an example , there are 3 objects a1,a2,a3. a1={p1,p2,,pn} a2={q1,,qn1} a3={r1,...,rn2} for each pair ai,aj we have to check if any 2 points in the corressponding lists are equal the question then becomes What is the fastest way to compare through n arrays. I dont have a sophisticated way of doing this. Maybe someone can help me ? On Wed, Feb 16, 2011 at 5:29 PM, bittu shashank7andr...@gmail.com wrote: many irregular shape objects are moving in random direction. provide data structure and algo to detect collision. Remember that objects are in million. Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Application Data Structure In Collision Detection
Here is my attempt it's very naive but maybe someone can improve each object be a pointer to a set of points { these points are the boundary of the object } Collision detection : Sweep through each pair of pointers to check for equality of the boundary points. an example , there are 3 objects a1,a2,a3. a1={p1,p2,,pn} a2={q1,,qn1} a3={r1,...,rn2} for each pair ai,aj we have to check if any 2 points in the corressponding lists are equal the question then becomes What is the fastest way to compare through n arrays. I dont have a sophisticated way of doing this. Maybe someone can help me ? On Wed, Feb 16, 2011 at 5:29 PM, bittu shashank7andr...@gmail.com wrote: many irregular shape objects are moving in random direction. provide data structure and algo to detect collision. Remember that objects are in million. Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] program for evaluation of remainders
Let me try. Any thing involving n would leave no remainder. so (1 + 2 ! + ... + n ! + + N !) mod n = (1 + 2 ! + ... + (n-1)! ) mod n This should be computed from a loop. I don't know how to reduce it further. Ashim. On Wed, Dec 8, 2010 at 6:49 PM, ankit sablok ankit4...@gmail.com wrote: Q) can anyboy find me the solution to this problem Given an integer N and an another integer n we have to write a program to find the remainder of the following problems (1! + 2! + 3! + 4! + . + N!)mod(n) N=100 n=1000; please help me write a program for this problem thanx in advance -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Interview Question
What if we have an array :- index - 1 2 3 4 5 value - 1 2 3 4 5 How will ANY logn solution determine all ALL elements are equal to it's index value ? Maybe I misunderstand. Thank you, Ashim On Sat, Dec 4, 2010 at 5:38 PM, ankit sablok ankit4...@gmail.com wrote: u can then move to other advance data structures On Sat, Dec 4, 2010 at 4:58 PM, mo...@ismu mohan...@gmail.com wrote: in worst case it takes o(n)time if all the elemets match with their indexes -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Interview Question
yaar I can use simple O(n) sweep to find out who all are equal, I think it can't be less than this On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote: 2010/12/4 ankit sablok ankit4...@gmail.com: as all the elements are sorted in the array make a min heap of the array elements and as min heap is a tree of keys querying a min heap or a binary search tree requires operations with time equal to the height of the tree which is log(n) hence time for querying a min heap I think you might be use a log(n) time to find out a element whose value is equal to some certain index, so the complexity could be n*log(n)? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Mathematics Puzzle
Do you mean if the rank of a student is better than the rank of the prev student then he/she gets a lollipop? Thank you, Ashim On Sun, Nov 21, 2010 at 6:57 PM, vamsee marpu marpu.vam...@gmail.comwrote: Does anybody know the solution for the following problem : *A headmaster of a primary school performs an activity with the students of a class to encourage them to perform better in academics. He asks them to stand in queue, starts calling the students out one by one and asks them their rank in class. Each one has a unique rank in class. If the rank of a student is better than his/her previous best rank, then he awards him/ her a lollipop (students love lollipops). Note that the first one in the queue will always get a lollipop and the students arrange themselves in random order in the queue. What is the expected number of lollipops the headmaster will have to distribute among students if the total number of students in the class is 69? Note that the answer can be a fractional number.* Thanks and Regards, M. Vamsee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] student introduction problems
Is'nt this solvable by the majority vote algorithm already discussed in this list? Ashim. On Sun, Nov 7, 2010 at 3:42 AM, lichenga2404 lichenga2...@gmail.com wrote: There are many secret groups in College A.Every student at college A is a member or these secret group, though membership in one excludes a student from joining any other group. You wish to determine if any one of these groups contains more than half of the student population. To achieve this , you will introduce 2 students to each other: if they are members of different group , they will smile. If different group , they will nod. How to determine if any one group has more than half of the student population as members in O(n) introductions . And justify 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Yahoo coding round question
I'm not sure what a 2 hash table is. Can you please explain ? On Tue, Oct 19, 2010 at 10:36 PM, MOHIT mohit...@gmail.com wrote: o(n) soln Lets say A is the array of length N. Create an array sum of length N and initialize it to 0. Create an array product of length N and initialize it to 1. now sum[i]=sum[i-1]+A[i]; sum[0]=A[0]; product[i]=product[i-1]+A[I]product[0]=A[0]; make a two hash table for product and sum array ; in product arrary traverse i=0 to n ; divide result=product[i]/P and check result is present in hash table or not if yes then get index of result . suppose k then checkabsolute(sum[i]-sum[k])==S if yes then we got sub array. else ..keep do this untill array end ; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Drawing a graph
what is this red book ?full name please? On Fri, Sep 17, 2010 at 1:01 PM, vikas kumar vikas.kumar...@gmail.comwrote: use opengl library to draw the graph or whatever. take RED BOOK for reference. On Sep 14, 5:54 pm, Mithun avmit...@gmail.com wrote: Can anyone help me with the code for drawing a graph in C or CPP (using graphics) Input is an Adjacency matrix -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question
How would you define 50% or more similarity ? On Sun, Sep 12, 2010 at 6:49 PM, Chi c...@linuxdna.com wrote: trie On Sep 12, 3:09 pm, sharad kumar aryansmit3...@gmail.com wrote: pagerank algo On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me thesnoop...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Aricent question
The majority vote program ( discussed a couple of days ago ) would work in this case I think. In the end we would have the modal element with count = 0 (n - n ). Please correct me if I am wrong. On Sat, Sep 11, 2010 at 3:00 PM, bittu shashank7andr...@gmail.com wrote: Given an array of 2n elements of which n elements are same and the remaining n elements are all different. Write a C program to find out the value which is present n times in the array. There is no restriction on the elements in the array. They are random (In particular they not sequential). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] cyclic String
I can do it in 2 O(n)sweeps if all elements are distinct. 12345 23451 Sweep one to find the 1st element of string 1 in string 2. Sweep 2 to compare each element of the 2 strings from the position mod n found in the 1st sweep. I dont know how to do it if elements are repeated. but the way Praveen does it is really cool i think. Sat, Sep 11, 2010 at 1:54 PM, Praveen Baskar praveen200...@gmail.comwrote: str=hello; str1=lloeh; if (str+str).subString(str1) is true then the string is cyclic string of another On Sat, Sep 11, 2010 at 1:52 PM, bittu shashank7andr...@gmail.com wrote: How will you check if a string is cyclic string of another solution O(n)..???/?? or even less compraiosn.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] DeShaw Question....tough One
int a[]={11,9,8,2,10,7,3,4,5} max_length = 1 ; current_length = 1; first_position=0 ; last_position = 0 ; first_position_max=0; // Sweep one to find the length of the longest subsequence. for ( i = 1 ; i n ; i++ ) { if ( a[i] a[i-1] ) { last_position=i-1; current_length=last_position- first_position+1; max_length = current_length max_length ? current_length : max_length; first_position_max = current_length max_length ? first_position : first_position_max; first_position= i; } } // Sweep two to print the longest subsequence. for ( i = first_position ; i max_length ; i ++ ) { cout a[i]; } On Mon, Sep 6, 2010 at 2:01 PM, bittu shashank7andr...@gmail.com wrote: u are given an array and u have to print the longest increasing scattered subsequence...eg..{11,9,8,2,10,7,3,4,5}. Solve it O(n); -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] kth smallest element in a heap x
sure, but the implementation is confusing. My question is does not the 2nd count overwrite the 1st value of count in side the function? Thank you. On Sun, Aug 22, 2010 at 1:04 AM, Harshal ..Bet oN iT!! hc4...@gmail.comwrote: if it is a min heap,, then traversing down from the root node, it takes O(k) time to reach the kth smallest element. so, i think its just that straight!!! plz correct me if m wrong??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] kth smallest element in a heap x
Dear All, I found this in the book by skeina. Problem: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. the solution is given as follows. int heap_compare(priority_queue *q, int i, int count, int x) { if ((count = 0) || (i q-n) return(count); if (q-q[i] x) { count = heap_compare(q, pq_young_child(i), count-1, x); count = heap_compare(q, pq_young_child(i)+1, count, x); } return(count); } The explanation is given as follows: This procedure searches the children of all nodes of weight smaller than x until either (a) we have found k of them, when it returns 0, or (b) they are exhausted, when it returns a value greater than zero. Thus it will find enough small elements if they exist. But how long does it take? The only nodes whose children we look at are those x, and at most k of these in total. Each have at most visited two children, so we visit at most 3k nodes, for a total time of O(k). I dont see how it works. In particular I dont see why count is reset according to the 2 children of the current node. I am new to this. can some1 explain me what's happening? Many thank, Ashim -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] minimum window containing charecters
I am not sure, but can I do this using a suffix trie ? any comments ? On Sun, Aug 1, 2010 at 2:29 PM, Ashish Goel ashg...@gmail.com wrote: solution could be to find the charcter position from both sides for each char of s2 then from the 2*n array, find the smallest index from left and largest from right, within these two indexes all chars would be there one case where one of the chars can be missing can be found if a row in this 2-d array remains unmodified Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Jul 31, 2010 at 10:22 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote: At the moment, I can only think of an O(n^3) algo. Maybe if you can find a hash function which computes the hash value depending on the unique characters the string contains, you can reduce it to O(n^2). On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg srikanthini...@gmail.comwrote: given two string , find the minimum width in string 1 containing the all characters of string 2 , they may present in different order string 1-HELLO string 2- LE answer-2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the mode in a set of integers
are you referring to the lectures by Dr Naveen Garg ? Or are these lectures different? Please clarify. Thank you, Ashim. On Sat, Apr 17, 2010 at 5:43 AM, rahul rai raikra...@gmail.com wrote: On 4/16/10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Just got another O(n) solution. Find the n/2 th largest element in the array using the Median of Medians Selection algorithm. =? takes O(n) That's It ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Work out the CDEEP Algorithms course lectures . It will give all basics -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
I think it can be done in logn time ( I assume the list is sorted, is there an order log n sorting algo, then i can even sort it in log n time ? ( I am new to algorithms ) ). 1. binary search for low=x1. 2. binary search for high=x2. both will take log n time. Print all values between them then in O(x2-x1) time. Is this correct? On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: With only this info and without preprocessing , you need to scan all the N integers in the list atleast once. Hence cannot be better than O(n). If preprocessing is allowed you can compute the answers for all n^2 pairs of x1,x2 and when some one asks , return the corresponding list. In that case it would be better that O(n). !! -Rohit On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.