[algogeeks] Facebook phone interview questions

[~*~VICKY~*~]

Hi guys pls share the quest you know that was asked in facebook phone
interview. Thank you.

-- 
Cheers,

  Vicky

-- 
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] finding element in array with minimum of comparing

[icy`]

nice solution, Dave!

@Umer -- if the sought ele is first, then Dave's code has it sitting in the 
variable temp for a little while.   Loop will stop when size is 0, since 
arr[0]==elem.  Now he throws temp back into arr[0], which will return index 
0 from the last compare line.

On Wednesday, October 3, 2012 2:08:56 AM UTC-4, Umer Farooq wrote:
>
> @Dave Thanks for pointing that out.
>
> But I still can't get what if elem is on first element or it is not 
> present in the array? How is your code going to handle that situation?
>
> @Atul, Well yes, In the given question, the number of iterations were 2n. 
> Which I have reduced to n+n/2.
>
>
>
>
>
> On Tue, Oct 2, 2012 at 11:13 PM, atul anand 
> > wrote:
>
>> @umer : how no. of comparison are reduced to half by moving both
>> sidesyou have 2 if condition inside, so you are making 2
>> comparisons at each iteration + n/2 comparison for while loop so
>> number of comparisons are n+n/2
>>
>> On 10/2/12, Umer Farooq > wrote:
>> > why don't we try it from both ends ... something like this:
>> >
>> > int i = 0; j = size-1;
>> >
>> > while (i != j)
>> > {
>> > if (arr[i] == elem)
>> >   return arr[i];
>> > if (arr[j] == elem)
>> >return arr[j];
>> > }
>> >
>> > this way, we have eliminated half of the comparisons in for loop? What 
>> do
>> > you guys say?
>> >
>> > On Tue, Oct 2, 2012 at 12:18 PM, rafi > 
>> wrote:
>> >
>> >> Vikas is right!
>> >> while (n) is equal to (while n!=0)
>> >> you have 2n compares!
>> >>
>> >> בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:
>> >>
>> >>> still there is no improvement, compiler will generate the code to
>> >>> compare
>> >>> with zero here. what you have accomplished is , hide it from human 
>> eyes
>> >>>
>> >>> On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:
>> 
>>  @atul:
>>  still it won't compare 0 th element. Slight modification in your 
>> code:
>> 
>>  n=*sizeof(arr)*;
>>  do
>>  {
>>   if(elem==arr[*--n*])
>>   print found;
>> 
>>  }while(n);
>> 
>>  On Mon, Oct 1, 2012 at 9:50 AM, atul anand  
>> wrote:
>> 
>> > yes, but there no need of checking outside the loop
>> >
>> > n=sizeof(arr)-1;
>> > do
>> > {
>> >  if(elem==arr[n])
>> >  print found;
>> > n--;
>> >
>> > }while(n);
>> >
>> >
>> >
>> > On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar
>> > wrote:
>> >
>> >> @atul: keep one more checking outside loop for element at 0 th 
>> index.
>> >> Because when n = 0  the your loop come out from the loop without
>> >> comparing
>> >> it.
>> >>
>> >>
>> >> On Mon, Oct 1, 2012 at 8:55 AM, atul anand
>> >> wrote:
>> >>
>> >>> n=sizeof(arr);
>> >>> n--;
>> >>>
>> >>> while(n)
>> >>> {
>> >>>  if(elem=arr[n])
>> >>>   print found;
>> >>>
>> >>> n--;
>> >>>
>> >>> }
>> >>>
>> >>> On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר 
>> >>> wrote:
>> >>>
>>  Hi
>>  i was in an interview and was given a simple function
>>  int arrExsits(int* arr,int size,int elem){
>>  for (int i=0;i>  if(elem==arr[i])
>> return i;
>>  return -1;
>>  }
>>  this function does 2n compares
>>  n- the if statment
>>  n-check that i is smaller then size
>>  i was suppose to give an optimal (less compares) solution so i 
>> gave
>> 
>>  int arrExsits(int* arr,int size,int elem){
>>  if (arr[size-1]==elem)
>>  return size-1;
>>  arr[size-1]=elem]
>>  for (int i=0;;++i)
>>  if(elem==arr[i]){
>>  if (i!=size-1)
>>  return i;
>>  return -1;
>>  }
>>  this solution works and it has n+2 compares the first one 
>> another n
>>  and the second inner if.
>>  they told me it's good (and I've passed) but they told just for 
>> my
>>  knowledge that there is a better N compare solution.
>>  I've searched the web but couldn't find it.
>>  anybody knows?
>>  Thanks
>> 
>>  --
>>  You received this message because you are subscribed to the 
>> Google
>>  Groups "Algorithm Geeks" group.
>>  To post to this group, send email to algo...@googlegroups.com.
>>  To unsubscribe from this group, send email to
>>  algogeeks+...@googlegroups.com**.
>>  For more options, visit this group at 
>> http://groups.google.com/**
>>  group/algogeeks?hl=en<
>> 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 algo...@googlegro

[algogeeks] Re: Missing Number Problem

[icy`]

By "missing" I assume that the numbers are consecutive and we are at
least provided with a range.

Suppose for the sake of example, the range is 100,000 to 400,000 with
203,148 being the missing number.  They come to us shuffled up, and let us
suppose we are taking them from the hard drive instead of an array, one by
one.  Now if the range is known, there is an interesting property of XOR
that you can use.  A variable initialized to 0 can be XOR'd with every
element in the range, and then XOR'd with all the provided numbers.  It
will then become the missing number.   Ruby example (again, assume numbers
coming from hard drive or other source, one at a time, and not array in
memory):

[image: Inline image 1]

-- 
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: Facebook question!

[icy`]

At first I found this tricky, as the number of strings in the array is
unknown, and it can be hard to iterate over unknown items of unknown
length.  Since repeated combinations are included, we know the total number
of combinations (lengths of all strings multiplied).  In my Ruby example
below, I used strings "abcde", "123", and "YZ" .   My method was to set up
a resulting array of empty strings of length 30 (5*3*2).Then I examined
the kind of combinations we will make:
a1Y  a1Z  a2Y  a2Z  a3Y  a3Z ,  b1Y  etc.

Notice if we generate combinations in this order, a will repeat six times
in a row, and this is because the remaining elements are three and two
letters long (3*2).   Similarly, the numbers in "123" will be repeated
twice in a row, because the remaining (last) word has only two characters.
 This amount of repetition is assigned to variable *repeats* below. And
each element of  "YZ" repeats once in a row since there are no more
elements after.  If there is more room in the total combinations, then the
word will repeat again from the beginning; e.g. for "123"  the middle
characters of the answers will be 1,1, 2,2,3,3,1,1,2,2,3,3  until 30 is
reached.

The strings of the res array are slowly built in this way.   Ruby helps
deal with some of the other minor issues.  Pic below.

icy`

[image: Inline image 1]

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

[shady]

i am talking about t-test, z-test.. which are done when dataset is not
big.. can we avoid them ? When are these tests not required ?

On Fri, Oct 5, 2012 at 8:55 PM, shady  wrote:

> When can we avoid doing statistical significance testing ?
>
>

-- 
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: microsoft_c++_qstn

[Don]

One execution path has no return. Most compilers will issue a warning
on that.
If a function doesn't return a value, that is undefined behavior.
It's unclear if the intent is to return rec(d) or i.
Better style is to have exactly one return at the end of the function.
Don



On Sep 25, 11:57 am, Ravi Ranjan  wrote:
> #include
> int rec(int i)
> {
> static int d=1;
> if(i>=5)
> return i;
> d=d+i;
> i=i+i;
> rec(d);}
>
> int main()
> {
> cout< return 0;
>
> }
>
> various compilers give diffrent result... why so???
> n how d value is calculated by differnt compilers.. whhat is d correct
> output n which compiler to trust??

-- 
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: microsoft_c++_qstn

[Atul Singh]

May be because when u look at the code.. rect(8) only returns  and 8 is
stored into register but when it returns to rect(4) .it simply ends and
goes to rect(2) which in turn goes to rect(1).

So returned value is taken from that register that is filled with value
returned from it i.e 8.
May be that returning  recursive manner and filling that register is
dependent on compiler to compiler.

-- 

*ATul Singh** *
Mobile : +91-9410826039
[image: Facebook]  [image:
Twitter]
 [image: LinkedIn] 

-- 
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] Missing Number Problem

[vaibhav shukla]

external merge sort could be handy.

On Fri, Oct 5, 2012 at 8:51 PM, Raghavan  wrote:

> You mean 1 to 300million is given and any one number is missing midst of
> it?
>
>
> On Fri, Oct 5, 2012 at 12:19 AM, Sanjay Rajpal  wrote:
>
>> We are given 300 million 9-digit numbers and 2 MB of RAM. We have to find
>> the missing number. How do we approach this problem ?
>>
>> *Regards,*
>> *Sanjay Kumar*
>>
>>
>> * *
>>
>> **
>> *
>> *
>>
>>  --
>> 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.
>>
>
>
>
> --
> Thanks and Regards,
> Raghavan KL
>
>
>  --
> 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.
>



-- 
best wishes!!
 Vaibhav

-- 
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] Statistical Tests

[shady]

When can we avoid doing statistical significance testing ?

-- 
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] Missing Number Problem

[Raghavan]

You mean 1 to 300million is given and any one number is missing midst of it?

On Fri, Oct 5, 2012 at 12:19 AM, Sanjay Rajpal  wrote:

> We are given 300 million 9-digit numbers and 2 MB of RAM. We have to find
> the missing number. How do we approach this problem ?
>
> *Regards,*
> *Sanjay Kumar*
>
>
> * *
>
> **
> *
> *
>
>  --
> 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.
>



-- 
Thanks and Regards,
Raghavan KL

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