On Thu, Jun 9, 2011 at 5:01 PM, <[email protected]> wrote:
> Today's Topic Summary > > Group: http://groups.google.com/group/algogeeks/topics > > - need help in Desktop applications <#130742ba4deca0ba_group_thread_0>[1 > Update] > - MS Interview <#130742ba4deca0ba_group_thread_1> [13 Updates] > - Million Numbers <#130742ba4deca0ba_group_thread_2> [1 Update] > - Finding total number of inversions in an array in O(nlogn) complexity > . <#130742ba4deca0ba_group_thread_3> [6 Updates] > - [brain teaser ] Secret Code puzzle 9 > june<#130742ba4deca0ba_group_thread_4>[2 Updates] > - Please Ban Sohail <#130742ba4deca0ba_group_thread_5> [1 Update] > - Regular Expressions Implementation <#130742ba4deca0ba_group_thread_6>[1 > Update] > > Topic: need help in Desktop > applications<http://groups.google.com/group/algogeeks/t/20a566a2a84ca02b> > > karan sachan <[email protected]> Jun 09 04:59PM +0530 > ^<#130742ba4deca0ba_digest_top> > > Hi Snehi...Follow following links to kick-start your Swing!! > > > > http://www.herongyang.com/Swing/Introduction-First-Swing-Program-SwingHello.html > < > > http://www.herongyang.com/Swing/Introduction-First-Swing-Program-SwingHello.html > > > http://www.dreamincode.net/forums/topic/206319-first-swing-application/ > > We may further help if you can tell us more about ur App which ur > planning > to create!! > > > -- > > Thanks & Regards, > Karan Sachan | System Engineer > Infosys Technologies Ltd.| Bangalore > Mobile: +91 9663373478 > > > > Topic: MS > Interview<http://groups.google.com/group/algogeeks/t/c09368ab62023765> > > Dumanshu <[email protected]> Jun 09 02:45AM -0700 > ^<#130742ba4deca0ba_digest_top> > > 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 > > > > > Ershad K <[email protected]> Jun 09 09:59AM +0530 > ^<#130742ba4deca0ba_digest_top> > > On Thursday 09 June 2011 03:15 PM, Dumanshu wrote: > > missing, > > i.e there are only 3,999,999,999 numbers, I need to find the missing > > number. > > Is the array sorted? > > -- > Sincerely, > Ershad K > http://ershadk.wordpress.com > > > > > Ershad K <[email protected]> Jun 09 10:00AM +0530 > ^<#130742ba4deca0ba_digest_top> > > On Thursday 09 June 2011 09:59 AM, Ershad K wrote: > >> i.e there are only 3,999,999,999 numbers, I need to find the missing > >> number. > > > Is the array sorted? > > Apology for the previous reply. I mean, is the numbers in the file > sorted? > > Thanks. > -- > Sincerely, > Ershad K > http://ershadk.wordpress.com > > > > > Freak Algo <[email protected]> Jun 09 03:37PM +0530 > ^<#130742ba4deca0ba_digest_top> > > For Q2 "Bitwise X-OR" operation of all input numbers does the trick. > > --- On Thu, 9/6/11, Dumanshu <[email protected]> wrote: > > From: Dumanshu <[email protected]> > Subject: [algogeeks] MS Interview > To: "Algorithm Geeks" <[email protected]> > Date: Thursday, 9 June, 2011, 9:45 AM > > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > Navneet Gupta <[email protected]> Jun 09 03:44PM +0530 > ^<#130742ba4deca0ba_digest_top> > > The answer to second question is simple. XORing all the elements > should do it for you. > > > > -- > --Navneet > > > > > varun pahwa <[email protected]> Jun 09 03:47PM +0530 > ^<#130742ba4deca0ba_digest_top> > > 2nd part can be done just take the xor of all the numbers same number > xor > returns 0 so only seven will remain. > 1st part can be done in O(n) because estimate sum -> n*(n+1)/2. now sub > from > estimated sum each array element. the last value remained is the > missing > number. > correct me if i am wrong. > > > -- > Varun Pahwa > B.Tech (IT) > 7th Sem. > Indian Institute of Information Technology Allahabad. > Ph : 09793899112 ,08011820777 > Official Email :: [email protected] > Another Email :: [email protected] > > People who fail to plan are those who plan to fail. > > > > > "• » νιρυℓ « •" <[email protected]> Jun 09 03:49PM +0530 > ^<#130742ba4deca0ba_digest_top> > > For 1. > sum the numbers in the file, subtract it from sum of first 4 billion > numbers. > > > -- > Regards, > Vipul > > > > > Naveen Kumar <[email protected]> Jun 09 03:51PM +0530 > ^<#130742ba4deca0ba_digest_top> > > I think numbers in question1 are in sequence (ascending order). > > 2011/6/9 • » νιρυℓ « • <[email protected]> > > > -- > Cheers > Naveen Kumar > > > > > sunny agrawal <[email protected]> Jun 09 03:52PM +0530 > ^<#130742ba4deca0ba_digest_top> > > sum can overflow.... > Xor method can also be applied to Q1. no need of numbers to be sorted. > > 2011/6/9 • » νιρυℓ « • <[email protected]> > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > > > > "• » νιρυℓ « •" <[email protected]> Jun 09 04:02PM +0530 > ^<#130742ba4deca0ba_digest_top> > > Sum wont overflow, ULL range will include sum. > > > -- > Regards, > Vipul > > > > > sunny agrawal <[email protected]> Jun 09 04:04PM +0530 > ^<#130742ba4deca0ba_digest_top> > > yes, but using xor no need of ULL :) > > 2011/6/9 • » νιρυℓ « • <[email protected]> > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > > > > Dumanshu <[email protected]> Jun 09 04:16AM -0700 > ^<#130742ba4deca0ba_digest_top> > > I dont think numbers are sorted in the 1st question. btw > @sunny: how will xor-ing give the ans? for 1st ques? > > > > > > Piyush Sinha <[email protected]> Jun 09 04:58PM +0530 > ^<#130742ba4deca0ba_digest_top> > > 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 > > > -- > *Piyush Sinha* > *IIIT, Allahabad* > *+91-8792136657* > *+91-7483122727* > *https://www.facebook.com/profile.php?id=100000655377926 * > > > > Topic: Million > Numbers<http://groups.google.com/group/algogeeks/t/3f689b5f7cbc17d4> > > Dumanshu <[email protected]> Jun 09 04:24AM -0700 > ^<#130742ba4deca0ba_digest_top> > > Given a file containing roughly 300 million social security numbers(9- > digit numbers) find a 9-digit number that isnt there in the file. You > have unlimited drive space but only 2mb of RAM. > > Solution is as follows: > In the first step, we build an array of 2^16 integers that is > initialized to 0 and for every number in the file we take its 16 most > significant > bit to index into this array and increment that number. Since there > are less than 2^32 numbers in the file there is bound to be one number > in the array that is less than 2^16 . This tells us that there is at > least one number missing among the possible numbers with those upper > bits. In the second pass, we can focus only on the numbers that match > this criterion and use a bit-vector of size 2^16 to identify one of > the missing numbers. > > Someone plz explain this solution( may be using some small values > numbers) or suggest another approach. > > > > Topic: Finding total number of inversions in an array in O(nlogn) > complexity . <http://groups.google.com/group/algogeeks/t/c612b167bc8a8dba> > > "D.N.Vishwakarma@IITR " <[email protected]> Jun 09 04:05PM +0530 > ^<#130742ba4deca0ba_digest_top> > > Inversion means pair(i,j) such that i<j and A[i]>A[j] > > -- > **With Regards > Deoki Nandan Vishwakarma > IITR MCA > * > * > > > > > sunny agrawal <[email protected]> Jun 09 04:08PM +0530 > ^<#130742ba4deca0ba_digest_top> > > Discussed many times, > 1) add some lines to merge sort > 2) use Binary indexed tree for a faster version (i have not tried but > get to > know it can be done using binary indexed tree) > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > > > > "D.N.Vishwakarma@IITR " <[email protected]> Jun 09 04:22PM +0530 > ^<#130742ba4deca0ba_digest_top> > > thanx for suggestion > > > -- > **With Regards > Deoki Nandan Vishwakarma > IITR MCA > * > * > > > > > Navneet Gupta <[email protected]> Jun 09 04:27PM +0530 > ^<#130742ba4deca0ba_digest_top> > > Insertion sort also would do. > > > -- > --Navneet > > > > > "D.N.Vishwakarma@IITR " <[email protected]> Jun 09 04:29PM +0530 > ^<#130742ba4deca0ba_digest_top> > > how insertion sort will do in O(nlogn)? > > > -- > **With Regards > Deoki Nandan Vishwakarma > IITR MCA > * > * > > > > > Navneet Gupta <[email protected]> Jun 09 04:24AM -0700 > ^<#130742ba4deca0ba_digest_top> > > Ohh. Missed out the nlogn condition you mentioned. It will do but in > n^2 > > Sent from my Windows Phone > ------------------------------ > From: D.N.Vishwakarma@IITR > Sent: Thursday, 9 June 2011 4:29 PM > To: [email protected] > Subject: Re: [algogeeks] Finding total number of inversions in an array > in > O(nlogn) complexity . > > how insertion sort will do in O(nlogn)? > > > [email protected]. > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > -- > **With Regards > Deoki Nandan Vishwakarma > IITR MCA > * > * > > -- > You received this message because you are subscribed to the Google > Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > Topic: [brain teaser ] Secret Code puzzle 9 > june<http://groups.google.com/group/algogeeks/t/9b30bedad752a65f> > > nicks <[email protected]> Jun 09 02:19AM -0700 > ^<#130742ba4deca0ba_digest_top> > > Simple Problem :( > > > > > > varun pahwa <[email protected]> Jun 09 03:25PM +0530 > ^<#130742ba4deca0ba_digest_top> > > please explain abt the order what if i say first number as ones, second > tens,.... so can this be also a answer 85647.please correct me if i am > wrong. > > > -- > Varun Pahwa > B.Tech (IT) > 7th Sem. > Indian Institute of Information Technology Allahabad. > Ph : 09793899112 ,08011820777 > Official Email :: [email protected] > Another Email :: [email protected] > > People who fail to plan are those who plan to fail. > > > > Topic: Please Ban > Sohail<http://groups.google.com/group/algogeeks/t/fcd5a641f22d77ed> > > Naveen Kumar <[email protected]> Jun 09 03:10PM +0530 > ^<#130742ba4deca0ba_digest_top> > > Hi Moderators, > Can you please Ban Sohail from algogeeks? > We are receiving a lot of spams from him. > [email protected] > > -- > Cheers > Naveen Kumar > > > > Topic: Regular Expressions > Implementation<http://groups.google.com/group/algogeeks/t/400314518978bc7e> > > Navneet Gupta <[email protected]> Jun 09 02:56PM +0530 > ^<#130742ba4deca0ba_digest_top> > > So i assume your ask is given a string, check if it can be formed with > the > regular expression you have. Is that correct? > > The above can be implemented easily with stacks. > Ex - Reg Expression - a*bc* > And String - aabccc > > Put all instances of char that are consecutive on the stack and then > pop the > top element and match it with the regex element (assume some pointer we > have > for regex), now you increment the regex pointer, if you see a different > character and your stack is not empty, we get false condition. > > If we see a *, we keep popping all instances of last seen character. > Once > all such characters are popped, you are ready to process remaining of > string > anf regex in similar fashion. > > Thanks, > Navneet > > P.S. This example only had a *, while regex can have more such symbols > such > as ? etc and problem will become little more complicated if we have > multiple > such characters. > > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > MS part 1 can be done in O(n) complexity as calculating the sum and subtracting it from 4,000,000,000 would give the result -- *Thanks & Regards* *Ankit Arun Final Year Information Technology NIT Durgapur BLOG*: www.obeyurthirst.blogspot.com <http://www.obeyankit.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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
