Re: [algogeeks] Re: MS interview

[GAURAV CHAWLA]

@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  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  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  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.

Re: [algogeeks] Re: MS interview

[Karthikeyan Muthu]

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  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  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  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.

Re: [algogeeks] Re: MS interview

[Ashish Goel]

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  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:

[sunny agrawal]

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 
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 
wrote:
> anyone??
>
> On Tue, Jul 26, 2011 at 11:36 PM, geek forgeek 
> 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

[Ashish Goel]

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  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 
> wrote:
>
>> 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 wrote:
>>
>>> 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 
>>> wrote:
>>>
 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  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  wrote:
> > yes, but using xor no need of ULL :)
> >
> > 2011/6/9 • » νιρυℓ « • 
>
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > 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 • » νιρυℓ « • 
>
> >
> > >>> 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 
> 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
>

Re: [algogeeks] Re: MS Interview

[Supraja Jayakumar]

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 wrote:

> 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 wrote:
>
>> 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 wrote:
>>
>>> 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  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  wrote:
 > yes, but using xor no need of ULL :)
 >
 > 2011/6/9 • » νιρυℓ « • 

 >
 >
 >
 >
 >
 >
 >
 >
 >
 > > 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 • » νιρυℓ « • 

 >
 > >>> 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 
 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 t

Re: [algogeeks] Re: MS Interview

[Wladimir Tavares]

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  wrote:

> 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 wrote:
>
>> 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  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  wrote:
>>> > yes, but using xor no need of ULL :)
>>> >
>>> > 2011/6/9 • » νιρυℓ « • 
>>>
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > 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 • » νιρυℓ « • 
>>>
>>> >
>>> > >>> 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 
>>> 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-T

Re: [algogeeks] Re: MS Interview

[Wladimir Tavares]

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 wrote:

> 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  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  wrote:
>> > yes, but using xor no need of ULL :)
>> >
>> > 2011/6/9 • » νιρυℓ « • 
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > 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 • » νιρυℓ « • 
>> >
>> > >>> 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 
>> 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*
> *+

Re: [algogeeks] Re: MS Interview

[Wladimir Tavares]

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  wrote:

> @kunal... yeah it will work. thnx :)
>
> On Jun 10, 11:41 pm, Kunal Patil  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

[Ashim Kapoor]

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 wrote:

> 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  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  wrote:
>> > yes, but using xor no need of ULL :)
>> >
>> > 2011/6/9 • » νιρυℓ « • 
>>
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > 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 • » νιρυℓ « • 
>>
>> >
>> > >>> 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 
>> 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

Re: [algogeeks] Re: MS Interview

[Kunal Patil]

@ 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.

Re: [algogeeks] Re: MS Interview

[hary rathor]

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.

Re: [algogeeks] Re: MS Interview

[Freak Algo]

Is not it O(n)?

--- On Thu, 9/6/11, ankit arun  wrote:

From: ankit arun 
Subject: [algogeeks] Re: MS Interview
To: "Algorithm Geeks" 
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  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.

Re: [algogeeks] Re: MS Interview

[Piyush Sinha]

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  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  wrote:
> > yes, but using xor no need of ULL :)
> >
> > 2011/6/9 • » νιρυℓ « • 
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > Sum wont overflow, ULL range will include sum.
> >
> > > On Thu, Jun 9, 2011 at 3:52 PM, sunny agrawal  >wrote:
> >
> > >> sum can overflow
> > >> Xor method can also be applied to Q1. no need of numbers to be sorted.
> >
> > >> 2011/6/9 • » νιρυℓ « • 
> >
> > >>> 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  >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 
> 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.