Re: [algogeeks] Re: MS interview
@all .. i suggested him the hashing method... but was not convinced... he might be expecting something else.. something like tries.. etc.. @ Karthikeyan Muthu... can u explain it in detail with some ex ... On Thu, Aug 23, 2012 at 11:28 PM, Karthikeyan Muthu keyankarthi1...@gmail.com wrote: i would suggest using tires data structure, basically a n-nary tree to store the dictionary. Entire algo is as follows: 1) Create a trie http://en.wikipedia.org/wiki/Trie representing the dictionary. 2) create a aux array for the search key. as count [ key[i] ] ++; 3) Start a recursion from the root of the trie and pick a path if (count [ path ] 0 ) 3rd step ensures that we traverse only those valid paths (ie valid words, this would reduce n! checking of all combinations). On Thu, Aug 23, 2012 at 8:23 PM, Ashish Goel ashg...@gmail.com wrote: yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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. -- Regards, GAURAV CHAWLA +919992635751 +919654127192 -- 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: MS interview
Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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: MS interview
yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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: MS interview
i would suggest using tires data structure, basically a n-nary tree to store the dictionary. Entire algo is as follows: 1) Create a trie http://en.wikipedia.org/wiki/Trie representing the dictionary. 2) create a aux array for the search key. as count [ key[i] ] ++; 3) Start a recursion from the root of the trie and pick a path if (count [ path ] 0 ) 3rd step ensures that we traverse only those valid paths (ie valid words, this would reduce n! checking of all combinations). On Thu, Aug 23, 2012 at 8:23 PM, Ashish Goel ashg...@gmail.com wrote: yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS interview:
anyone?? On Tue, Jul 26, 2011 at 11:36 PM, geek forgeek geekhori...@gmail.comwrote: Function to display the directory structure in a user friendly way taking root dir as arg for a general OS. You may assume and state some basic APIs available in that OS -- 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: MS interview:
There is a Book: Advance Programming in Unix Environment by Richard Stevens in Chapter 2 i think there is a code that does the job of directory Listing for given Directory this is the code - for directory listing *#include dirent.h int main(int argc, char *argv[]) { DIR *dp; struct dirent *dirp; if (argc != 2) err_quit(usage: ls directory_name); if ((dp = opendir(argv[1])) == NULL) err_sys(can't open %s, argv[1]); while ((dirp = readdir(dp)) != NULL) printf(%s\n, dirp-d_name); closedir(dp); exit(0); }* for this Question u just need to change this code and use recursion for directory inside Directories there are some attributes that are used to identify some object as file, directory, root directory and parent directory. so in recursion u will take care for those On Wed, Jul 27, 2011 at 12:13 PM, geek forgeek geekhori...@gmail.com wrote: anyone?? On Tue, Jul 26, 2011 at 11:36 PM, geek forgeek geekhori...@gmail.com wrote: Function to display the directory structure in a user friendly way taking root dir as arg for a general OS. You may assume and state some basic APIs available in that OS -- 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.
Re: [algogeeks] Re: MS Interview
suppose numbers are 11,12,13,15 then you get some xor_val for xor of all these numbers after this for (int i=11;i=15;i++) xor_val ^=i; now xor_val is 14 Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jun 12, 2011 at 9:24 PM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi But does this work on bigger numbers ? I mean with [11-15] say 14 is missing. It is: 1011 1100 1101 0101 --- which is 5 ? Supraja J On Sat, Jun 11, 2011 at 8:14 AM, Wladimir Tavares wladimir...@gmail.comwrote: You can use the same idea: Suppose you want to find out what the missing number in the list [1 .. 5] : 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 XOR = 001 If the number 4 is missing: XOR = 001 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 3 = 011 XOR = 011 Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Jun 9, 2011 at 8:34 AM, Ashim Kapoor ashimkap...@gmail.comwrote: 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
Re: [algogeeks] Re: MS Interview
Hi But does this work on bigger numbers ? I mean with [11-15] say 14 is missing. It is: 1011 1100 1101 0101 --- which is 5 ? Supraja J On Sat, Jun 11, 2011 at 8:14 AM, Wladimir Tavares wladimir...@gmail.comwrote: You can use the same idea: Suppose you want to find out what the missing number in the list [1 .. 5]: 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 XOR = 001 If the number 4 is missing: XOR = 001 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 3 = 011 XOR = 011 Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Jun 9, 2011 at 8:34 AM, Ashim Kapoor ashimkap...@gmail.comwrote: 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
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] Re: MS Interview
Suppose you want to find out what the missing number in the list [1 .. 5]: 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 XOR = 001 If the number 4 is missing: XOR = 001 1 = 001 2 = 010 3 = 011 5 = 101 XOR = 100 You can see that the method works by properties of the XOR (you can see it?) . The same is true when only a number is doubled (Right?). Wladimir Araujo Tavares *Federal University of Ceará * On Fri, Jun 10, 2011 at 5:13 PM, Dumanshu duman...@gmail.com wrote: @kunal... yeah it will work. thnx :) On Jun 10, 11:41 pm, Kunal Patil kp101...@gmail.com wrote: @ Dumanshu: With memory restriction also XOR method works.. :) In this case difference is just that you will be working with 400/ X number of files..where X is size of the RAM...just maintain a variable Curr_XOR_value and go on XORing it with element read from the file. When you are done with reading all those numbers from 400/ X files.. (Curr_XOR_value) * XOR* (expected_XOR_value for 1 to 400) ... will give missing number... -- 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: MS Interview
You will use three properties of XOR on two issues: A XOR A = 0 A XOR B XOR B = A (commutativity) A XOR (B XOR C) = (A XOR B) XOR C (Associativity) Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Jun 9, 2011 at 8:28 AM, 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
[algogeeks] Re: MS Interview
Nothing is specified but lets take it as 2MB ram On Jun 10, 10:14 am, hary rathor harry.rat...@gmail.com wrote: dumnanshu you should first mention memory size in your computer so that i could know that how many number i can have in main memory at time -- 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: MS Interview
ex-or operation on all the elements give you the answer. On Jun 9, 5:45 am, 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.
Re: [algogeeks] Re: MS Interview
@ Dumanshu: With memory restriction also XOR method works.. :) In this case difference is just that you will be working with 400/ X number of files..where X is size of the RAM...just maintain a variable Curr_XOR_value and go on XORing it with element read from the file. When you are done with reading all those numbers from 400/ X files.. (Curr_XOR_value) * XOR* (expected_XOR_value for 1 to 400) ... will give missing number... -- 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: MS Interview
@kunal: could u plz explan ur XOR approach by using a small set of numbers. lets say we have numbers from 1 to 5 and one number is missing. so u mean 1 XOR 2 XOR 4 XOR 5 would give me 3??? On Jun 10, 11:41 pm, Kunal Patil kp101...@gmail.com wrote: @ Dumanshu: With memory restriction also XOR method works.. :) In this case difference is just that you will be working with 400/ X number of files..where X is size of the RAM...just maintain a variable Curr_XOR_value and go on XORing it with element read from the file. When you are done with reading all those numbers from 400/ X files.. (Curr_XOR_value) * XOR* (expected_XOR_value for 1 to 400) ... will give missing number... -- 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: MS Interview
@kunal... yeah it will work. thnx :) On Jun 10, 11:41 pm, Kunal Patil kp101...@gmail.com wrote: @ Dumanshu: With memory restriction also XOR method works.. :) In this case difference is just that you will be working with 400/ X number of files..where X is size of the RAM...just maintain a variable Curr_XOR_value and go on XORing it with element read from the file. When you are done with reading all those numbers from 400/ X files.. (Curr_XOR_value) * XOR* (expected_XOR_value for 1 to 400) ... will give missing number... -- 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: MS Interview
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.
Re: [algogeeks] Re: MS Interview
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.com wrote: 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.com wrote: 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.
[algogeeks] Re: MS Interview
part 1 can be solved in O(1) complexity.. first adding all the numbers and then subtracting it from 4,000,000,000 will give the result. On Jun 9, 2:45 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.
Re: [algogeeks] Re: MS Interview
Is not it O(n)? --- On Thu, 9/6/11, ankit arun talk.ankit...@gmail.com wrote: From: ankit arun talk.ankit...@gmail.com Subject: [algogeeks] Re: MS Interview To: Algorithm Geeks algogeeks@googlegroups.com Date: Thursday, 9 June, 2011, 11:49 AM part 1 can be solved in O(1) complexity.. first adding all the numbers and then subtracting it from 4,000,000,000 will give the result. On Jun 9, 2:45 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. -- 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.