Re: [algogeeks] Re: Microsoft :)
@harshal: the link which u posted requires an invitation.. pls see to it On Mon, Aug 8, 2011 at 12:51 AM, KK kunalkapadi...@gmail.com wrote: @Harshal: Thanx -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Million Numbers
@ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Re: Million Numbers
@ankit: think u missed heapify.. time complexity is O(n logn) On Fri, Jun 10, 2011 at 12:55 PM, ankit sambyal ankitsamb...@gmail.comwrote: Lets say we have 9 numbers from 1 to 10 and one number is missing. We hv a RAM which can accomodate only 3 nos. 9,6,7,4,3,2,1,5,10 So, we split the file into 3 smaller files each containing 3 nos. File1: 9,6,7 File2: 4,3,2 File3: 1,5,10 Now take each file into memory one by one and min heapify them and put them back in the memory. File1: 6,9,7 File2: 2,3,4 File3: 1,5,10 The 1st element in each file is min in each file. Now make a file temp containing the 1st element of each file and remove the 1st element from the files 1,2 and 3.Min heapify each file.. Temp: 1,6,2 File1: 7,9 File2: 3,4 File3: 5,10 Now remove 1 from file Temp and take element from File3 because 1 belonged to File3 originally. Again min Heapify them. Temp: 2,6,5 File1: 7,9 File2: 3,4 File3: 10 Now remove 2 Temp: 3,5,6 File1: 7,9 File2: 4 File3: 10 Now remove 3 Temp: 4,6,5 File1: 7,9 File2: File3: 10 Now going on this way we will find that after we remove 7, we could not find 8. So, 8 is the missing no. Ankit Sambyal BITS Pilani On Fri, Jun 10, 2011 at 12:11 AM, varun pahwa varunpahwa2...@gmail.com wrote: can anyone explain 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. in dumanshu's solution. On Fri, Jun 10, 2011 at 12:39 PM, varun pahwa varunpahwa2...@gmail.com wrote: @ankit :please explain by taking an example. On Fri, Jun 10, 2011 at 12:13 PM, Vetri Balaji vetribal...@gmail.com wrote: @ankit: pls explain the time complexity.. i dont think its O(log n) On Thu, Jun 9, 2011 at 11:57 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Dumanshu: In each iteration, we r removing the smallest number. If at any iteration we can't find the next smallest no., it means that no. is missing. On Thu, Jun 9, 2011 at 10:54 AM, Dumanshu duman...@gmail.com wrote: hey... we have 300 million (9- digit) numbers. So we have to print a number which isn't already there in the file. We are not given that number beforehand. You are saying to check u are going to check whether a number N exist . On Jun 9, 4:46 pm, radha krishnan radhakrishnance...@gmail.com wrote: Ma approach is to xor the given number with all numbers in the file !! This takes O(n) I think we cant achieve a complexity O(n) we have to scan the file at least once Or move to this problem Instead of a file with numbers you have a stream of numbers Create a Trie and insert every number from the stream by reversing the digits of the number Now u have a Trie (left as 0 bit right as 1 bit ) u are going to check whether a number N exist reverse the bits of N search for appropriate bit in the Trie if all bit are matched then there is a number !! else No But Space Complexity Of Trie is high we need (32 *(O(n)) assuming each integer is of 32 bits On Thu, Jun 9, 2011 at 4:54 PM, Dumanshu duman...@gmail.com wrote: 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Re: [algogeeks] Reverse the bits.
int flip(int j,int k,int n)
{
int t1=(1j)-1;
int t2=(1k)-1;
t1=t2^t1;
return n^t1;
}
correct me if im wrong
On Fri, Jun 10, 2011 at 10:09 PM, Kunal Patil kp101...@gmail.com wrote:
How about this???
*
unsigned int flip_j_to_k_bits (unsigned int n,unsigned int j,unsigned int
k)
{
unsigned int temp;
int num_of_on_bits = k-j+1;
temp = (1num_of_on_bits)-1;
temp = j;
return (n^temp);
}*
I dont know whether shift operation is O(1) or not !
But i think this is the best possible that can be done !!!
On Fri, Jun 10, 2011 at 8:40 PM, dinesh bansal bansal...@gmail.comwrote:
How do you reverse the bits between j to k in a 32 bit integer.
For e.g.:
n = 11100011; j = 2 and k = 5
output: 1101 (bits from 2 to 5 are reversed.)
n = 11010110; j = 1 and k = 5
output: 11101000
O(1) method is preferred.
Thanks,
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the best way.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Reverse the bits.
no..it will work just fine
On Sat, Jun 11, 2011 at 3:31 AM, Anika Jain anika.jai...@gmail.com wrote:
@balaji: right , just one change required i think so coz in question they
are asking for change of one more bit i.e. for j=2,k=5.. bits 2,3,4,5 are
modified..ur code is doing i guess only 2,3,4.. i think just one change
needed int t2=(1(k+1))-1;
On Fri, Jun 10, 2011 at 10:22 PM, Vetri Balaji vetribal...@gmail.comwrote:
int flip(int j,int k,int n)
{
int t1=(1j)-1;
int t2=(1k)-1;
t1=t2^t1;
return n^t1;
}
correct me if im wrong
On Fri, Jun 10, 2011 at 10:09 PM, Kunal Patil kp101...@gmail.com wrote:
How about this???
*
unsigned int flip_j_to_k_bits (unsigned int n,unsigned int j,unsigned int
k)
{
unsigned int temp;
int num_of_on_bits = k-j+1;
temp = (1num_of_on_bits)-1;
temp = j;
return (n^temp);
}*
I dont know whether shift operation is O(1) or not !
But i think this is the best possible that can be done !!!
On Fri, Jun 10, 2011 at 8:40 PM, dinesh bansal bansal...@gmail.comwrote:
How do you reverse the bits between j to k in a 32 bit integer.
For e.g.:
n = 11100011; j = 2 and k = 5
output: 1101 (bits from 2 to 5 are reversed.)
n = 11010110; j = 1 and k = 5
output: 11101000
O(1) method is preferred.
Thanks,
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the best way.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
Re: [algogeeks] If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
thanks!! On Wed, Mar 23, 2011 at 8:25 AM, Anand anandut2...@gmail.com wrote: Thanks!! On Tue, Mar 22, 2011 at 7:11 PM, D.N.Vishwakarma@IITR deok...@gmail.comwrote: thanx... On 3/22/11, Himanshu Neema potential.himansh...@gmail.com wrote: -- Forwarded message -- From: Himanshu Neema potential.himansh...@gmail.com Date: Tue, Mar 22, 2011 at 11:13 PM Subject: Re: [algogeeks] If any one have algorithms for interviews by adnan aziz ebook... Please mail ... To: Abhishek Goswami zeal.gosw...@gmail.com Its a 15.4MB pdf so would take time to download if you have slow internet connection , otherwise i checked the link its working. But I have also uploaded it on Google docs as Abhishek suggested here : https://docs.google.com/viewer?a=vpid=explorerchrome=truesrcid=0B--bA2TobuKZNGU5Njk5OTctZWEyYi00NWMwLTk0OGItMzhkMTI1ZTk0Mjg2hl=enauthkey=CL_1msUI On Tue, Mar 22, 2011 at 11:01 PM, Abhishek Goswami zeal.gosw...@gmail.comwrote: can you upload this file into google docs or attach this file. i tried to download this file but did not get any success for open this file Thanks Abhishek On Tue, Mar 22, 2011 at 10:41 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Turns out that I cant send file larger than 4 MB , please download it from here , let me know if you're still unable to download: http://dl.dropbox.com/u/2681370/Algorithms%2Bfor%2BInterviews%2B%28scan%2Bocr%29%20%281%29.pdf have fun ! On Tue, Mar 22, 2011 at 10:21 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Enjoy :) On Tue, Mar 22, 2011 at 10:09 PM, Saravanan T mail2sarava...@gmail.comwrote: ++ On Tue, Mar 22, 2011 at 9:51 PM, Anurag atri anu.anurag@gmail.comwrote: and me too :) On Tue, Mar 22, 2011 at 9:28 PM, Nikhil Mishra mishra00...@gmail.comwrote: count me too On Tue, Mar 22, 2011 at 11:16 AM, kunal srivastav kunal.shrivas...@gmail.com wrote: plz send it to me too On Tue, Mar 22, 2011 at 11:14 AM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: -- *With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com . To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- thezeitgeistmovement.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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group.
Re: [algogeeks] If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
is there any other books that can help in placements?? On Wed, Mar 23, 2011 at 9:25 AM, Gaurav Saxena grvsaxena...@gmail.comwrote: Thanks a lot. On Wed, Mar 23, 2011 at 8:41 AM, Vetri Balaji vetribal...@gmail.comwrote: thanks!! On Wed, Mar 23, 2011 at 8:25 AM, Anand anandut2...@gmail.com wrote: Thanks!! On Tue, Mar 22, 2011 at 7:11 PM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: thanx... On 3/22/11, Himanshu Neema potential.himansh...@gmail.com wrote: -- Forwarded message -- From: Himanshu Neema potential.himansh...@gmail.com Date: Tue, Mar 22, 2011 at 11:13 PM Subject: Re: [algogeeks] If any one have algorithms for interviews by adnan aziz ebook... Please mail ... To: Abhishek Goswami zeal.gosw...@gmail.com Its a 15.4MB pdf so would take time to download if you have slow internet connection , otherwise i checked the link its working. But I have also uploaded it on Google docs as Abhishek suggested here : https://docs.google.com/viewer?a=vpid=explorerchrome=truesrcid=0B--bA2TobuKZNGU5Njk5OTctZWEyYi00NWMwLTk0OGItMzhkMTI1ZTk0Mjg2hl=enauthkey=CL_1msUI On Tue, Mar 22, 2011 at 11:01 PM, Abhishek Goswami zeal.gosw...@gmail.comwrote: can you upload this file into google docs or attach this file. i tried to download this file but did not get any success for open this file Thanks Abhishek On Tue, Mar 22, 2011 at 10:41 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Turns out that I cant send file larger than 4 MB , please download it from here , let me know if you're still unable to download: http://dl.dropbox.com/u/2681370/Algorithms%2Bfor%2BInterviews%2B%28scan%2Bocr%29%20%281%29.pdf have fun ! On Tue, Mar 22, 2011 at 10:21 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Enjoy :) On Tue, Mar 22, 2011 at 10:09 PM, Saravanan T mail2sarava...@gmail.comwrote: ++ On Tue, Mar 22, 2011 at 9:51 PM, Anurag atri anu.anurag@gmail.comwrote: and me too :) On Tue, Mar 22, 2011 at 9:28 PM, Nikhil Mishra mishra00...@gmail.comwrote: count me too On Tue, Mar 22, 2011 at 11:16 AM, kunal srivastav kunal.shrivas...@gmail.com wrote: plz send it to me too On Tue, Mar 22, 2011 at 11:14 AM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: -- *With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- thezeitgeistmovement.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. -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
