Re: [algogeeks] Re: Amazon Interview Question

[Gary Drocella]

A bit vector is basically just a sequence of bits such as a word or even an 
array of words.  Here is an example...
 
int x = 5;   // 32 bit word size on Intel IA-32 Architecture In C 
programming language.
 
A variable in C will be either located in a register in memory or in Main 
Memory.  You can even have bit vector data structures
reside on the hard disk. It just looks like this
 
10010101010010101...
 
If I'm interpreting the solution properly you will index into the bit 
vector based on the number found in the array A that is
 
for j = 1... A.size
currentNumber = A[j]  // The jth array element
bitVector[currentNumber] = ~ bitVector[currentNumber]   ; // Toggle the 
currentNumber bit
end for
 
Although this is a big memory save, you're still not using constant memory 
because the size of your memory is dependent on the size of a word let's 
say k
 
In worst case the space complexity will be 2*2^k = O(2^(K+1))

On Wednesday, April 3, 2013 9:58:23 AM UTC-8, ashekhar007 wrote:

> hi sourab please explain what bit vector1 and bit vector 2 really are can 
> you give an example please?
>
> On Saturday, February 16, 2013 11:20:59 PM UTC+5:30, sourabh wrote:
>>
>> you can solve this problem using bitvector/bitset.
>>
>> first scan :
>> scan the array set the bit on odd occurrence and unset on even or 
>> 0 occurrence.
>>
>> second scan :
>> shift all the odd occurring elements in beginning of array and even 
>> towards end.
>>
>> third scan : till end of odd occurring elements.
>> take another bit vector 
>> on first occurence :if bit is set in bv1 then unset it and set it in bv2.
>> on second occurence : if bv1 is not set and bv2 is set then these are the 
>> array elements occuring 3rd time. 
>>
>>
>>
>>
>>
>> On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh wrote:
>>
>>> Yes, thats a valid point Don.
>>> Thats what i meant when i wrote  "//is that correct?" in the comments on 
>>> the array line in code.
>>>
>>>
>>>  int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
>>>
>>>
>>> On Wed, Feb 13, 2013 at 9:09 PM, Don  wrote:
>>>
 The xor approach only works if there are no values which occur only
 once. But the problem statement indicates that some numbers occur
 once, some occur twice, and one occurs three times. So you will end up
 with prod equal to the xor of all of the values which occur once or
 three times. Put that in your input array and you'll find that you
 don't get the desired output.

 I don't know of a solution better than sorting and scanning the array.

 Don

 On Feb 12, 3:14 pm, prakhar singh  wrote:
 > #include
 >
 > int main()
 > {
 >int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
 >int prod=a[0];int i;
 >for(i=1;i<(int)sizeof(a)/sizeof(a[0]);i++)
 >{
 >   prod ^= a[i];
 >}
 >printf("%d\n",prod);   //outputs 3, algorithm works as Sachin 
 described
 > it;
 >
 > }
 >
 > On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
 > wrote:
 >
 >
 >
 >
 >
 >
 >
 > > use ex-or operation for all array elements..
 > > a^a=0
 > > a^a^a=a
 >
 > > On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B <
 mohanabala...@gmail.com>wrote:
 >
 > >> can use counting sort
 >
 > >> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota <
 santoshthot...@gmail.com>wrote:
 >
 > >>> If we can retrieve ith prime efficiently, we can do the 
 following...
 > >>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th 
 prime
 > >>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
 > >>>else prod=prod*ith_prime;
 > >>> 3.repeat it till end
 >
 > >>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
 >
 >  Given an array of integers where some numbers repeat once, some 
 numbers
 >  repeat twice and only one number repeats thrice, how do you find 
 the number
 >  that gets repeated 3 times?
 >
 >  Does this problem have an O(n) time and O(1) space solution?
 >  No hashmaps please!
 >
 > >>>  --
 > >>> 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/-/TSPSKlD0FDsJ.
 >
 > >>> 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.
 >
 > >>  --
 > >> You received this message because you are subscribed to the Google 
 Groups
 > >> "Algorithm Geeks" group.
 > >> To unsubscribe from this group and stop receiving emails from it, 
 send an
 > >> email to 

Re: [algogeeks] Re: Amazon Interview Question

[Gary Drocella]

Counting sort does not run in O(1) space though.  Optimally it will run in 
O(K) space, where A is an array of integer numbers and K = max(A) - min(A)

On Saturday, February 9, 2013 9:52:01 PM UTC-5, Mohanabalan wrote:

> can use counting sort
>
>
> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
> 
> > wrote:
>
>> If we can retrieve ith prime efficiently, we can do the following...
>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>>else prod=prod*ith_prime;
>> 3.repeat it till end 
>>
>>
>>
>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>  
>>> Given an array of integers where some numbers repeat once, some numbers 
>>> repeat twice and only one number repeats thrice, how do you find the number 
>>> that gets repeated 3 times?
>>>
>>> Does this problem have an O(n) time and O(1) space solution? 
>>> No hashmaps please!
>>>
>> -- 
>> 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/-/TSPSKlD0FDsJ. 
>>
>> 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.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[Parag Khanna]

use XOR



On Tue, Apr 30, 2013 at 6:12 AM, Gary Drocella  wrote:

> This will only work if each element in the array are relatively prime to
> one another, that is for any two elements x, y in array A the gcd(x,y) = 1,
> which is also just another way of saying no number divides another number
> in the array.  Once this rule is broken, then
> the algorithm will no longer work.  Here is a counter example
>
> A = { 4,3,4,2,4,2 } = {2^2, 3, 2^2, 2, 2^2, 2}
>
> You might be able to see now why this algorithm breaks down.  It is
> because the final product = 2^8*3^1 and of course 2^3 will easily divide
> this number, but would return the wrong solution.  It was of course a very
> good try!
>
> On Thursday, July 12, 2012 11:46:50 PM UTC-8, jatin wrote:
>
>>
>> 1)Find product of the array and store it in say prod  o(n) and o(1)
>> 2)now traverse the array and check if
>>
>> static int i;
>> tag:
>> while(i> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>> break;
>> //this may be the required element
>> //e-o-while
>>
>> //now check is this is the element that is occuring three times o(n)
>> if(number is not the required one then)
>> goto tag;
>>
>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>
>>> Given an array of integers where some numbers repeat once, some numbers
>>> repeat twice and only one number repeats thrice, how do you find the number
>>> that gets repeated 3 times?
>>>
>>> Does this problem have an O(n) time and O(1) space solution?
>>> No hashmaps please!
>>>
>>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
regards

Parag Khanna

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: Amazon Interview Question

[Gary Drocella]

This will only work if each element in the array are relatively prime to 
one another, that is for any two elements x, y in array A the gcd(x,y) = 1, 
which is also just another way of saying no number divides another number 
in the array.  Once this rule is broken, then
the algorithm will no longer work.  Here is a counter example
 
A = { 4,3,4,2,4,2 } = {2^2, 3, 2^2, 2, 2^2, 2}
 
You might be able to see now why this algorithm breaks down.  It is because 
the final product = 2^8*3^1 and of course 2^3 will easily divide this 
number, but would return the wrong solution.  It was of course a very good 
try!

On Thursday, July 12, 2012 11:46:50 PM UTC-8, jatin wrote:

>  
> 1)Find product of the array and store it in say prod  o(n) and o(1) 
> 2)now traverse the array and check if  
>  
> static int i;
> tag:
> while(i if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
> break;
> //this may be the required element
> //e-o-while
>  
> //now check is this is the element that is occuring three times o(n)
> if(number is not the required one then)
> goto tag;
>
> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>
>> Given an array of integers where some numbers repeat once, some numbers 
>> repeat twice and only one number repeats thrice, how do you find the number 
>> that gets repeated 3 times?
>>
>> Does this problem have an O(n) time and O(1) space solution?
>> No hashmaps please!
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon interview question

[BackBencher]

:O "the final required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * 
a2 + a1" how ? , did i missed something id yes can you paste the link or 
explain ?


Thanks
Shashank

On Wednesday, April 10, 2013 5:09:41 AM UTC+5:30, Shachindra A C wrote:
>
> Consider n = 5. Naming the array elements as a1,a2,a3,a4,a5 , the final 
> required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * a2 + a1.
>
> That is nothing but the pattern of a binomial expansion. Using this 
> method, the complexity can be reduced to O(n).
>
> Correct me if I'm wrong!
>
> On Tue, Apr 9, 2013 at 1:51 PM, Shashwat Kumar 
> 
> > wrote:
>
>> Recursion and iteration don't differ in this algorithm. But avoid using 
>> recursion if same can be done using iteration. In practical cases, system 
>> does not allow very large depth in recursion. So for large values of n, 
>> there can occur segmentation fault.
>>
>>
>> On Tue, Apr 9, 2013 at 11:43 AM, rahul sharma 
>> 
>> > wrote:
>>
>>> If you have any other solution ..please post that...i thnik recursion is 
>>> ok with base case...we need to scan again after first iteration...??
>>>
>>>
>>> On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma 
>>> 
>>> > wrote:
>>>
 i forgot to add base case..can add wen 2 elemnts are there then there 
 sum is stored and we reurn from there...i m in hurry,,,sry for that,,


 On Wed, Apr 10, 2013 at 12:11 AM, Don >>> >wrote:

> It is O(N^2) because the inner loop takes N steps to execute and that
> loop will be executed N times.
>
> However, I would suggest not using recursion. There is no reason to
> not do it iteratively. Your recursive solution has no base case so it
> will recurse until your computer runs out of stack space, at which
> point it will crash.
>
> Don
>
> On Apr 9, 2:29 pm, rahul sharma  wrote:
> >  A = {5, 3, 8, 9, 16}
> > After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
> > After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
> > Given an array, return sum after n iterations
> >
> > my sol/
> > void abc(int arr[],n)
> > {
> > for(i=0;i > arr[i]=arr[i+1]-arr[i];
> > abc(arr,n-1);
> >
> > }
> >
> > I wana ask that the complexity is o(n) or o(n)2..as loop is 
> executed n
> > times..say n is 10...so fxn is called 10 timesi.e  10 n..and 
> ignoring n
> > it comes out to be...n..but if we implemeted with 2 loops then
> > complexity is n2 ...and both sol are taking same no of 
> iterations...please
> > tell whether complexity is n or n2 for above codeif it is n2 
> then how???
>
> --
> You received this message because you are subscribed to the Google 
> Groups "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send 
> an email to algogeeks+...@googlegroups.com .
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

>>>  -- 
>>> You received this message because you are subscribed to the Google 
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send 
>>> an email to algogeeks+...@googlegroups.com .
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>  
>>>  
>>>
>>
>>
>>
>> -- 
>> Shashwat Kumar
>> Third year Undergraduate student
>> Department of Computer Science and Engineering
>> IIT Kharagpur
>>
>>
>>
>>
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to algogeeks+...@googlegroups.com .
>> For more options, visit https://groups.google.com/groups/opt_out.
>>  
>>  
>>
>
>
>
> -- 
> Regards,
> Shachindra A C
>  

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon interview question

[Shashwat Anand]

On 4/13/13 10:05 PM, pankaj joshi wrote:

in this Problem if the array is
A[n] = {a0,a1,a(n-1),a(n)}

after the second iteration,
the value will be
{a0 -2*a2+a3, a2 -2*a3 + a4, a3-2*a4+a5,, a(n-2)-2a(n-1)+a(n)}

if we add all these terms then
all the middle elements will be canceled out so the remaining will be.

{a0-a2  - a(n-1)+a(n)}
which can be written as a general form
solution: - {a(n)-a(n-1)} - {a2-a0}
this will solve the problem in time complexity in O(1).

example:  A = {5, 3, 8, 9, 16}
solution : - {16-9}-{3-5}
  {7} - {-2}
   9


No.

Your assertion is valid only for first two iteration.
Iteration 1: { a1 - a0, a2 - a1, ... an - an-1 } = an - a0
Iteration 2: { a2 - 2a1 + a0,  an - 2an-1 + an-2 } = (an - an-1) - 
(a1 - a0)
Iteration 3: an - 2an-1 +an-1 - a2 + 2a1 - a0, thereby nullifying the 
above observation.


At any state T, we need to find f (n, T) where coefficient of T is 0, to 
make it O(1) solution.

That does not seems to be the case here.

Say, for 4th iteration, what will be your answer ?  I don't see any 
closed form here.




On Wed, Apr 10, 2013 at 7:03 AM, Shashwat Anand > wrote:


On 4/10/13 12:13 AM, rahul sharma wrote:

If you have any other solution ..please post that...i thnik
recursion is ok with base case...we need to scan again after
first iteration...??

First of all, the array size and number of iteration both won't be
N or else the answer will always be 0.
I take the following assumption, array have K elements and number
of iteration is N.
Now, if N >= K, the return value will always be 0.
For rest, we can decompose the array following the rule of
adjacent element difference.

Solution with O(NK) time complexity follows:

int
doit (vector  v, int N) {
int k = (int) v.size () - 1;
if (N > k) return 0;
int c = 1;
while (N--) {
for (int i = k; i >= c; i--)
v [i] -= v [i - 1];
for (int i = 0; i < c; i++)
v [i] = 0;
c++;
}
return accumulate (v.begin (), v.end (), 0);
}

int
main ()

int a [] = { 5, 3, 8, 9, 16 };
vector  v (a, a + sizeof (a) / sizeof (a [0]));
assert (doit (v, 0) == 41);
assert (doit (v, 1) == 11);
assert (doit (v, 2) == 9);
assert (doit (v, 3) == -1);
assert (doit (v, 4) == 21);
assert (doit (v, 5) == 0);

return 0;
}

However, I /strongly believe/ the solution can be done in *linear
time*.  To code this with quadratic time complexity is a no-brainer.

So, I took the array with K = 6 elements and decomposed.

N = 0: [a1, a2, a3, a4, a5, a6]  => a1 + a2 + a3 + a4 + a4 + a6
N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] => a6 - a1
N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 -
2a5 + a4] => a6 - a5 - a2 + a1 => (a6 - a5) - (a2 - a1)
N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5
+ 3a4 - a3] => a6 - 2a5 +a4 - a3 + 2a2 - a1
N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 -
4a3 + a2] => a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1
N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] => a6 -
5a5 + 10a4 - 10a3 + 5a2 - a1
N >= 6: [0, 0, 0, 0, 0, 0] => 0

The resulting solution does show some property of Binomial
coefficient as pointed out by @Don in his hint (Pascal triangle). 
I suppose this shall be the way to attack this problem.



On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma
mailto:rahul23111...@gmail.com>> wrote:

i forgot to add base case..can add wen 2 elemnts are there
then there sum is stored and we reurn from there...i m in
hurry,,,sry for that,,


On Wed, Apr 10, 2013 at 12:11 AM, Don mailto:dondod...@gmail.com>> wrote:

It is O(N^2) because the inner loop takes N steps to
execute and that
loop will be executed N times.

However, I would suggest not using recursion. There is no
reason to
not do it iteratively. Your recursive solution has no
base case so it
will recurse until your computer runs out of stack space,
at which
point it will crash.

Don

On Apr 9, 2:29 pm, rahul sharma mailto:rahul23111...@gmail.com>> wrote:
>  A = {5, 3, 8, 9, 16}
> After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
> After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
> Given an array, return sum after n iterations
>
> my sol/
> void abc(int arr[],n)
> {
> for(i=0;i arr[i]=arr[i+1]-arr[i];
> abc(arr,n-1);
>
> }
>
> I wana ask that the complexity is o(n) or o(n)2..as
loop is executed n
  

Re: [algogeeks] Re: Amazon interview question

[pankaj joshi]

in this Problem if the array is
A[n] = {a0,a1,a(n-1),a(n)}

after the second iteration,
the value will be
{a0 -2*a2+a3, a2 -2*a3 + a4, a3-2*a4+a5,, a(n-2)-2a(n-1)+a(n)}

if we add all these terms then
all the middle elements will be canceled out so the remaining will be.

{a0-a2  - a(n-1)+a(n)}
which can be written as a general form
solution: - {a(n)-a(n-1)} - {a2-a0}

this will solve the problem in time complexity in O(1).

example:  A = {5, 3, 8, 9, 16}
solution : - {16-9}-{3-5}
{7} - {-2}
 9


On Wed, Apr 10, 2013 at 7:03 AM, Shashwat Anand  wrote:

>  On 4/10/13 12:13 AM, rahul sharma wrote:
>
> If you have any other solution ..please post that...i thnik recursion is
> ok with base case...we need to scan again after first iteration...??
>
> First of all, the array size and number of iteration both won't be N or
> else the answer will always be 0.
> I take the following assumption, array have K elements and number of
> iteration is N.
> Now, if N >= K, the return value will always be 0.
> For rest, we can decompose the array following the rule of adjacent
> element difference.
>
> Solution with O(NK) time complexity follows:
>
> int
> doit (vector  v, int N) {
> int k = (int) v.size () - 1;
> if (N > k) return 0;
> int c = 1;
> while (N--) {
> for (int i = k; i >= c; i--)
> v [i] -= v [i - 1];
> for (int i = 0; i < c; i++)
> v [i] = 0;
> c++;
> }
> return accumulate (v.begin (), v.end (), 0);
> }
>
> int
> main ()
>
> int a [] = { 5, 3, 8, 9, 16 };
> vector  v (a, a + sizeof (a) / sizeof (a [0]));
> assert (doit (v, 0) == 41);
> assert (doit (v, 1) == 11);
> assert (doit (v, 2) == 9);
> assert (doit (v, 3) == -1);
> assert (doit (v, 4) == 21);
> assert (doit (v, 5) == 0);
>
> return 0;
> }
>
> However, I *strongly believe* the solution can be done in *linear time*.
> To code this with quadratic time complexity is a no-brainer.
>
> So, I took the array with K = 6 elements and decomposed.
>
> N = 0: [a1, a2, a3, a4, a5, a6]  => a1 + a2 + a3 + a4 + a4 + a6
> N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] => a6 - a1
> N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 - 2a5 + a4]
> => a6 - a5 - a2 + a1 => (a6 - a5) - (a2 - a1)
> N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5 + 3a4 -
> a3] => a6 - 2a5 +a4 - a3 + 2a2 - a1
> N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 - 4a3 + a2]
> => a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1
> N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] => a6 - 5a5 +
> 10a4 - 10a3 + 5a2 - a1
> N >= 6: [0, 0, 0, 0, 0, 0] => 0
>
> The resulting solution does show some property of Binomial coefficient as
> pointed out by @Don in his hint (Pascal triangle).  I suppose this shall be
> the way to attack this problem.
>
>
>
> On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma wrote:
>
>> i forgot to add base case..can add wen 2 elemnts are there then there sum
>> is stored and we reurn from there...i m in hurry,,,sry for that,,
>>
>>
>> On Wed, Apr 10, 2013 at 12:11 AM, Don  wrote:
>>
>>> It is O(N^2) because the inner loop takes N steps to execute and that
>>> loop will be executed N times.
>>>
>>> However, I would suggest not using recursion. There is no reason to
>>> not do it iteratively. Your recursive solution has no base case so it
>>> will recurse until your computer runs out of stack space, at which
>>> point it will crash.
>>>
>>> Don
>>>
>>> On Apr 9, 2:29 pm, rahul sharma  wrote:
>>> >  A = {5, 3, 8, 9, 16}
>>> > After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
>>> > After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
>>> > Given an array, return sum after n iterations
>>> >
>>> > my sol/
>>> > void abc(int arr[],n)
>>> > {
>>> > for(i=0;i>> > arr[i]=arr[i+1]-arr[i];
>>> > abc(arr,n-1);
>>> >
>>> > }
>>> >
>>> > I wana ask that the complexity is o(n) or o(n)2..as loop is
>>> executed n
>>> > times..say n is 10...so fxn is called 10 timesi.e  10 n..and
>>> ignoring n
>>> > it comes out to be...n..but if we implemeted with 2 loops then
>>> > complexity is n2 ...and both sol are taking same no of
>>> iterations...please
>>> > tell whether complexity is n or n2 for above codeif it is n2 then
>>> how???
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
>
>  --
> You 

Re: [algogeeks] Re: Amazon interview question

[Shashwat Anand]

On 4/10/13 12:13 AM, rahul sharma wrote:
If you have any other solution ..please post that...i thnik recursion 
is ok with base case...we need to scan again after first iteration...??
First of all, the array size and number of iteration both won't be N or 
else the answer will always be 0.
I take the following assumption, array have K elements and number of 
iteration is N.

Now, if N >= K, the return value will always be 0.
For rest, we can decompose the array following the rule of adjacent 
element difference.


Solution with O(NK) time complexity follows:

int
doit (vector  v, int N) {
int k = (int) v.size () - 1;
if (N > k) return 0;
int c = 1;
while (N--) {
for (int i = k; i >= c; i--)
v [i] -= v [i - 1];
for (int i = 0; i < c; i++)
v [i] = 0;
c++;
}
return accumulate (v.begin (), v.end (), 0);
}

int
main ()

int a [] = { 5, 3, 8, 9, 16 };
vector  v (a, a + sizeof (a) / sizeof (a [0]));
assert (doit (v, 0) == 41);
assert (doit (v, 1) == 11);
assert (doit (v, 2) == 9);
assert (doit (v, 3) == -1);
assert (doit (v, 4) == 21);
assert (doit (v, 5) == 0);

return 0;
}

However, I /strongly believe/ the solution can be done in *linear 
time*.  To code this with quadratic time complexity is a no-brainer.


So, I took the array with K = 6 elements and decomposed.

N = 0: [a1, a2, a3, a4, a5, a6]  => a1 + a2 + a3 + a4 + a4 + a6
N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] => a6 - a1
N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 - 2a5 + 
a4] => a6 - a5 - a2 + a1 => (a6 - a5) - (a2 - a1)
N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5 + 3a4 
- a3] => a6 - 2a5 +a4 - a3 + 2a2 - a1
N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 - 4a3 + 
a2] => a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1
N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] => a6 - 5a5 + 
10a4 - 10a3 + 5a2 - a1

N >= 6: [0, 0, 0, 0, 0, 0] => 0

The resulting solution does show some property of Binomial coefficient 
as pointed out by @Don in his hint (Pascal triangle).  I suppose this 
shall be the way to attack this problem.



On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma 
mailto:rahul23111...@gmail.com>> wrote:


i forgot to add base case..can add wen 2 elemnts are there then
there sum is stored and we reurn from there...i m in hurry,,,sry
for that,,


On Wed, Apr 10, 2013 at 12:11 AM, Don mailto:dondod...@gmail.com>> wrote:

It is O(N^2) because the inner loop takes N steps to execute
and that
loop will be executed N times.

However, I would suggest not using recursion. There is no
reason to
not do it iteratively. Your recursive solution has no base
case so it
will recurse until your computer runs out of stack space, at which
point it will crash.

Don

On Apr 9, 2:29 pm, rahul sharma mailto:rahul23111...@gmail.com>> wrote:
>  A = {5, 3, 8, 9, 16}
> After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
> After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
> Given an array, return sum after n iterations
>
> my sol/
> void abc(int arr[],n)
> {
> for(i=0;i arr[i]=arr[i+1]-arr[i];
> abc(arr,n-1);
>
> }
>
> I wana ask that the complexity is o(n) or o(n)2..as loop
is executed n
> times..say n is 10...so fxn is called 10 timesi.e  10
n..and ignoring n
> it comes out to be...n..but if we implemeted with 2
loops then
> complexity is n2 ...and both sol are taking same no of
iterations...please
> tell whether complexity is n or n2 for above codeif it
is n2 then how???

--
You received this message because you are subscribed to the
Google Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from
it, send an email to algogeeks+unsubscr...@googlegroups.com
.
For more options, visit https://groups.google.com/groups/opt_out.




--
You received this message because you are subscribed to the Google 
Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send 
an email to algogeeks+unsubscr...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.




--
You received this message because you are subscribed to the Google Groups "Algorithm 
Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon interview question

[Shachindra A C]

Consider n = 5. Naming the array elements as a1,a2,a3,a4,a5 , the final
required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * a2 + a1.

That is nothing but the pattern of a binomial expansion. Using this method,
the complexity can be reduced to O(n).

Correct me if I'm wrong!

On Tue, Apr 9, 2013 at 1:51 PM, Shashwat Kumar wrote:

> Recursion and iteration don't differ in this algorithm. But avoid using
> recursion if same can be done using iteration. In practical cases, system
> does not allow very large depth in recursion. So for large values of n,
> there can occur segmentation fault.
>
>
> On Tue, Apr 9, 2013 at 11:43 AM, rahul sharma wrote:
>
>> If you have any other solution ..please post that...i thnik recursion is
>> ok with base case...we need to scan again after first iteration...??
>>
>>
>> On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma 
>> wrote:
>>
>>> i forgot to add base case..can add wen 2 elemnts are there then there
>>> sum is stored and we reurn from there...i m in hurry,,,sry for that,,
>>>
>>>
>>> On Wed, Apr 10, 2013 at 12:11 AM, Don  wrote:
>>>
 It is O(N^2) because the inner loop takes N steps to execute and that
 loop will be executed N times.

 However, I would suggest not using recursion. There is no reason to
 not do it iteratively. Your recursive solution has no base case so it
 will recurse until your computer runs out of stack space, at which
 point it will crash.

 Don

 On Apr 9, 2:29 pm, rahul sharma  wrote:
 >  A = {5, 3, 8, 9, 16}
 > After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
 > After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
 > Given an array, return sum after n iterations
 >
 > my sol/
 > void abc(int arr[],n)
 > {
 > for(i=0;i>>> > arr[i]=arr[i+1]-arr[i];
 > abc(arr,n-1);
 >
 > }
 >
 > I wana ask that the complexity is o(n) or o(n)2..as loop is
 executed n
 > times..say n is 10...so fxn is called 10 timesi.e  10 n..and
 ignoring n
 > it comes out to be...n..but if we implemeted with 2 loops then
 > complexity is n2 ...and both sol are taking same no of
 iterations...please
 > tell whether complexity is n or n2 for above codeif it is n2 then
 how???

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+unsubscr...@googlegroups.com.
 For more options, visit https://groups.google.com/groups/opt_out.



>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> Shashwat Kumar
> Third year Undergraduate student
> Department of Computer Science and Engineering
> IIT Kharagpur
>
>
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Shachindra A C

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon interview question

[Shashwat Kumar]

Recursion and iteration don't differ in this algorithm. But avoid using
recursion if same can be done using iteration. In practical cases, system
does not allow very large depth in recursion. So for large values of n,
there can occur segmentation fault.


On Tue, Apr 9, 2013 at 11:43 AM, rahul sharma wrote:

> If you have any other solution ..please post that...i thnik recursion is
> ok with base case...we need to scan again after first iteration...??
>
>
> On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma wrote:
>
>> i forgot to add base case..can add wen 2 elemnts are there then there sum
>> is stored and we reurn from there...i m in hurry,,,sry for that,,
>>
>>
>> On Wed, Apr 10, 2013 at 12:11 AM, Don  wrote:
>>
>>> It is O(N^2) because the inner loop takes N steps to execute and that
>>> loop will be executed N times.
>>>
>>> However, I would suggest not using recursion. There is no reason to
>>> not do it iteratively. Your recursive solution has no base case so it
>>> will recurse until your computer runs out of stack space, at which
>>> point it will crash.
>>>
>>> Don
>>>
>>> On Apr 9, 2:29 pm, rahul sharma  wrote:
>>> >  A = {5, 3, 8, 9, 16}
>>> > After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
>>> > After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
>>> > Given an array, return sum after n iterations
>>> >
>>> > my sol/
>>> > void abc(int arr[],n)
>>> > {
>>> > for(i=0;i>> > arr[i]=arr[i+1]-arr[i];
>>> > abc(arr,n-1);
>>> >
>>> > }
>>> >
>>> > I wana ask that the complexity is o(n) or o(n)2..as loop is
>>> executed n
>>> > times..say n is 10...so fxn is called 10 timesi.e  10 n..and
>>> ignoring n
>>> > it comes out to be...n..but if we implemeted with 2 loops then
>>> > complexity is n2 ...and both sol are taking same no of
>>> iterations...please
>>> > tell whether complexity is n or n2 for above codeif it is n2 then
>>> how???
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Shashwat Kumar
Third year Undergraduate student
Department of Computer Science and Engineering
IIT Kharagpur

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: Amazon interview question

[Don]

int getsum(int *a, int n)
{
   while(--n)
   {
  for(int i = 0; i < n; ++i)
 a[i] = a[i+1] - a[i];
   }
   return a[0];
}

I'm not really clear about how it is intended to work. It seems that
if you start with an array of N values, each iteration reduces the
number of values by 1, so after N iterations there will be no values
left, so you could simply return 0. But I don't think that is the
intended solution.

Recursion is an elegant solution to some problems which involve
backtracking or a branching search. Using recursion to accomplish a
simple loop is wasteful and unnecessary.

For bonus points, can you determine how this problem relates to
Pascal's Triangle.

Don

On Apr 9, 2:43 pm, rahul sharma  wrote:
> If you have any other solution ..please post that...i thnik recursion is ok
> with base case...we need to scan again after first iteration...??
>
> On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma wrote:
>
>
>
>
>
>
>
> > i forgot to add base case..can add wen 2 elemnts are there then there sum
> > is stored and we reurn from there...i m in hurry,,,sry for that,,
>
> > On Wed, Apr 10, 2013 at 12:11 AM, Don  wrote:
>
> >> It is O(N^2) because the inner loop takes N steps to execute and that
> >> loop will be executed N times.
>
> >> However, I would suggest not using recursion. There is no reason to
> >> not do it iteratively. Your recursive solution has no base case so it
> >> will recurse until your computer runs out of stack space, at which
> >> point it will crash.
>
> >> Don
>
> >> On Apr 9, 2:29 pm, rahul sharma  wrote:
> >> >  A = {5, 3, 8, 9, 16}
> >> > After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
> >> > After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
> >> > Given an array, return sum after n iterations
>
> >> > my sol/
> >> > void abc(int arr[],n)
> >> > {
> >> > for(i=0;i >> > arr[i]=arr[i+1]-arr[i];
> >> > abc(arr,n-1);
>
> >> > }
>
> >> > I wana ask that the complexity is o(n) or o(n)2..as loop is
> >> executed n
> >> > times..say n is 10...so fxn is called 10 timesi.e  10 n..and
> >> ignoring n
> >> > it comes out to be...n..but if we implemeted with 2 loops then
> >> > complexity is n2 ...and both sol are taking same no of
> >> iterations...please
> >> > tell whether complexity is n or n2 for above codeif it is n2 then
> >> how???
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To unsubscribe from this group and stop receiving emails from it, send an
> >> email to algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visithttps://groups.google.com/groups/opt_out.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon interview question

[rahul sharma]

If you have any other solution ..please post that...i thnik recursion is ok
with base case...we need to scan again after first iteration...??


On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma wrote:

> i forgot to add base case..can add wen 2 elemnts are there then there sum
> is stored and we reurn from there...i m in hurry,,,sry for that,,
>
>
> On Wed, Apr 10, 2013 at 12:11 AM, Don  wrote:
>
>> It is O(N^2) because the inner loop takes N steps to execute and that
>> loop will be executed N times.
>>
>> However, I would suggest not using recursion. There is no reason to
>> not do it iteratively. Your recursive solution has no base case so it
>> will recurse until your computer runs out of stack space, at which
>> point it will crash.
>>
>> Don
>>
>> On Apr 9, 2:29 pm, rahul sharma  wrote:
>> >  A = {5, 3, 8, 9, 16}
>> > After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
>> > After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
>> > Given an array, return sum after n iterations
>> >
>> > my sol/
>> > void abc(int arr[],n)
>> > {
>> > for(i=0;i> > arr[i]=arr[i+1]-arr[i];
>> > abc(arr,n-1);
>> >
>> > }
>> >
>> > I wana ask that the complexity is o(n) or o(n)2..as loop is
>> executed n
>> > times..say n is 10...so fxn is called 10 timesi.e  10 n..and
>> ignoring n
>> > it comes out to be...n..but if we implemeted with 2 loops then
>> > complexity is n2 ...and both sol are taking same no of
>> iterations...please
>> > tell whether complexity is n or n2 for above codeif it is n2 then
>> how???
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon interview question

[rahul sharma]

i forgot to add base case..can add wen 2 elemnts are there then there sum
is stored and we reurn from there...i m in hurry,,,sry for that,,


On Wed, Apr 10, 2013 at 12:11 AM, Don  wrote:

> It is O(N^2) because the inner loop takes N steps to execute and that
> loop will be executed N times.
>
> However, I would suggest not using recursion. There is no reason to
> not do it iteratively. Your recursive solution has no base case so it
> will recurse until your computer runs out of stack space, at which
> point it will crash.
>
> Don
>
> On Apr 9, 2:29 pm, rahul sharma  wrote:
> >  A = {5, 3, 8, 9, 16}
> > After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
> > After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
> > Given an array, return sum after n iterations
> >
> > my sol/
> > void abc(int arr[],n)
> > {
> > for(i=0;i > arr[i]=arr[i+1]-arr[i];
> > abc(arr,n-1);
> >
> > }
> >
> > I wana ask that the complexity is o(n) or o(n)2..as loop is executed
> n
> > times..say n is 10...so fxn is called 10 timesi.e  10 n..and
> ignoring n
> > it comes out to be...n..but if we implemeted with 2 loops then
> > complexity is n2 ...and both sol are taking same no of
> iterations...please
> > tell whether complexity is n or n2 for above codeif it is n2 then
> how???
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: Amazon interview question

[Don]

It is O(N^2) because the inner loop takes N steps to execute and that
loop will be executed N times.

However, I would suggest not using recursion. There is no reason to
not do it iteratively. Your recursive solution has no base case so it
will recurse until your computer runs out of stack space, at which
point it will crash.

Don

On Apr 9, 2:29 pm, rahul sharma  wrote:
>  A = {5, 3, 8, 9, 16}
> After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
> After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
> Given an array, return sum after n iterations
>
> my sol/
> void abc(int arr[],n)
> {
> for(i=0;i arr[i]=arr[i+1]-arr[i];
> abc(arr,n-1);
>
> }
>
> I wana ask that the complexity is o(n) or o(n)2..as loop is executed n
> times..say n is 10...so fxn is called 10 timesi.e  10 n..and ignoring n
> it comes out to be...n..but if we implemeted with 2 loops then
> complexity is n2 ...and both sol are taking same no of iterations...please
> tell whether complexity is n or n2 for above codeif it is n2 then how???

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[ashekhar007]

hi sourab please explain what bit vector1 and bit vector 2 really are can 
you give an example please?

On Saturday, February 16, 2013 11:20:59 PM UTC+5:30, sourabh wrote:
>
> you can solve this problem using bitvector/bitset.
>
> first scan :
> scan the array set the bit on odd occurrence and unset on even or 
> 0 occurrence.
>
> second scan :
> shift all the odd occurring elements in beginning of array and even 
> towards end.
>
> third scan : till end of odd occurring elements.
> take another bit vector 
> on first occurence :if bit is set in bv1 then unset it and set it in bv2.
> on second occurence : if bv1 is not set and bv2 is set then these are the 
> array elements occuring 3rd time. 
>
>
>
>
>
> On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh 
> 
> > wrote:
>
>> Yes, thats a valid point Don.
>> Thats what i meant when i wrote  "//is that correct?" in the comments on 
>> the array line in code.
>>
>>
>>  int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
>>
>>
>> On Wed, Feb 13, 2013 at 9:09 PM, Don >wrote:
>>
>>> The xor approach only works if there are no values which occur only
>>> once. But the problem statement indicates that some numbers occur
>>> once, some occur twice, and one occurs three times. So you will end up
>>> with prod equal to the xor of all of the values which occur once or
>>> three times. Put that in your input array and you'll find that you
>>> don't get the desired output.
>>>
>>> I don't know of a solution better than sorting and scanning the array.
>>>
>>> Don
>>>
>>> On Feb 12, 3:14 pm, prakhar singh  wrote:
>>> > #include
>>> >
>>> > int main()
>>> > {
>>> >int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
>>> >int prod=a[0];int i;
>>> >for(i=1;i<(int)sizeof(a)/sizeof(a[0]);i++)
>>> >{
>>> >   prod ^= a[i];
>>> >}
>>> >printf("%d\n",prod);   //outputs 3, algorithm works as Sachin 
>>> described
>>> > it;
>>> >
>>> > }
>>> >
>>> > On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
>>> > wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > use ex-or operation for all array elements..
>>> > > a^a=0
>>> > > a^a^a=a
>>> >
>>> > > On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B <
>>> mohanabala...@gmail.com>wrote:
>>> >
>>> > >> can use counting sort
>>> >
>>> > >> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota <
>>> santoshthot...@gmail.com>wrote:
>>> >
>>> > >>> If we can retrieve ith prime efficiently, we can do the 
>>> following...
>>> > >>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th 
>>> prime
>>> > >>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>>> > >>>else prod=prod*ith_prime;
>>> > >>> 3.repeat it till end
>>> >
>>> > >>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>> >
>>> >  Given an array of integers where some numbers repeat once, some 
>>> numbers
>>> >  repeat twice and only one number repeats thrice, how do you find 
>>> the number
>>> >  that gets repeated 3 times?
>>> >
>>> >  Does this problem have an O(n) time and O(1) space solution?
>>> >  No hashmaps please!
>>> >
>>> > >>>  --
>>> > >>> 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/-/TSPSKlD0FDsJ.
>>> >
>>> > >>> 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.
>>> >
>>> > >>  --
>>> > >> You received this message because you are subscribed to the Google 
>>> Groups
>>> > >> "Algorithm Geeks" group.
>>> > >> To unsubscribe from this group and stop receiving emails from it, 
>>> send an
>>> > >> email to algogeeks+...@googlegroups.com .
>>> > >> For more options, visithttps://groups.google.com/groups/opt_out.
>>> >
>>> > > --
>>> > > Regards,
>>> > > Sachin Chitale
>>> > > Application Engineer SCJP, SCWCD
>>> > > Contact# : +91 8086284349, 9892159511
>>> > > Oracle Corporation
>>> >
>>> > > --
>>> > > You received this message because you are subscribed to the Google 
>>> Groups
>>> > > "Algorithm Geeks" group.
>>> > > To unsubscribe from this group and stop receiving emails from it, 
>>> send an
>>> > > email to algogeeks+...@googlegroups.com .
>>> > > For more options, visithttps://groups.google.com/groups/opt_out.
>>>
>>> --
>>> You received this message because you are subscribed to the Google 
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send 
>>> an email to algogeeks+...@googlegroups.com .
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and

Re: [algogeeks] Re: Amazon Interview Question

[sourabh jain]

@sandeep he is talking about constant space.

On Tue, Mar 19, 2013 at 5:31 PM, sandeep kumar
wrote:

> Hey what if while scanning through the array we create a BST n check
> simultaneously that :
>
> current node == current node's parent && current node == current node's
> left or right child
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[sandeep kumar]

Hey what if while scanning through the array we create a BST n check
simultaneously that :

current node == current node's parent && current node == current node's
left or right child

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[sourabh jain]

you can solve this problem using bitvector/bitset.

first scan :
scan the array set the bit on odd occurrence and unset on even or
0 occurrence.

second scan :
shift all the odd occurring elements in beginning of array and even towards
end.

third scan : till end of odd occurring elements.
take another bit vector
on first occurence :if bit is set in bv1 then unset it and set it in bv2.
on second occurence : if bv1 is not set and bv2 is set then these are the
array elements occuring 3rd time.





On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh
wrote:

> Yes, thats a valid point Don.
> Thats what i meant when i wrote  "//is that correct?" in the comments on
> the array line in code.
>
>
>  int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
>
>
> On Wed, Feb 13, 2013 at 9:09 PM, Don  wrote:
>
>> The xor approach only works if there are no values which occur only
>> once. But the problem statement indicates that some numbers occur
>> once, some occur twice, and one occurs three times. So you will end up
>> with prod equal to the xor of all of the values which occur once or
>> three times. Put that in your input array and you'll find that you
>> don't get the desired output.
>>
>> I don't know of a solution better than sorting and scanning the array.
>>
>> Don
>>
>> On Feb 12, 3:14 pm, prakhar singh  wrote:
>> > #include
>> >
>> > int main()
>> > {
>> >int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
>> >int prod=a[0];int i;
>> >for(i=1;i<(int)sizeof(a)/sizeof(a[0]);i++)
>> >{
>> >   prod ^= a[i];
>> >}
>> >printf("%d\n",prod);   //outputs 3, algorithm works as Sachin
>> described
>> > it;
>> >
>> > }
>> >
>> > On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
>> > wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > use ex-or operation for all array elements..
>> > > a^a=0
>> > > a^a^a=a
>> >
>> > > On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B <
>> mohanabala...@gmail.com>wrote:
>> >
>> > >> can use counting sort
>> >
>> > >> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota <
>> santoshthot...@gmail.com>wrote:
>> >
>> > >>> If we can retrieve ith prime efficiently, we can do the following...
>> > >>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th
>> prime
>> > >>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>> > >>>else prod=prod*ith_prime;
>> > >>> 3.repeat it till end
>> >
>> > >>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>> >
>> >  Given an array of integers where some numbers repeat once, some
>> numbers
>> >  repeat twice and only one number repeats thrice, how do you find
>> the number
>> >  that gets repeated 3 times?
>> >
>> >  Does this problem have an O(n) time and O(1) space solution?
>> >  No hashmaps please!
>> >
>> > >>>  --
>> > >>> 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/-/TSPSKlD0FDsJ.
>> >
>> > >>> 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 unsubscribe from this group and stop receiving emails from it,
>> send an
>> > >> email to algogeeks+unsubscr...@googlegroups.com.
>> > >> For more options, visithttps://groups.google.com/groups/opt_out.
>> >
>> > > --
>> > > Regards,
>> > > Sachin Chitale
>> > > Application Engineer SCJP, SCWCD
>> > > Contact# : +91 8086284349, 9892159511
>> > > Oracle Corporation
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To unsubscribe from this group and stop receiving emails from it,
>> send an
>> > > email to algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visithttps://groups.google.com/groups/opt_out.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group an

Re: [algogeeks] Re: Amazon Interview Question

[prakhar singh]

Yes, thats a valid point Don.
Thats what i meant when i wrote  "//is that correct?" in the comments on
the array line in code.

 int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?


On Wed, Feb 13, 2013 at 9:09 PM, Don  wrote:

> The xor approach only works if there are no values which occur only
> once. But the problem statement indicates that some numbers occur
> once, some occur twice, and one occurs three times. So you will end up
> with prod equal to the xor of all of the values which occur once or
> three times. Put that in your input array and you'll find that you
> don't get the desired output.
>
> I don't know of a solution better than sorting and scanning the array.
>
> Don
>
> On Feb 12, 3:14 pm, prakhar singh  wrote:
> > #include
> >
> > int main()
> > {
> >int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
> >int prod=a[0];int i;
> >for(i=1;i<(int)sizeof(a)/sizeof(a[0]);i++)
> >{
> >   prod ^= a[i];
> >}
> >printf("%d\n",prod);   //outputs 3, algorithm works as Sachin
> described
> > it;
> >
> > }
> >
> > On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
> > wrote:
> >
> >
> >
> >
> >
> >
> >
> > > use ex-or operation for all array elements..
> > > a^a=0
> > > a^a^a=a
> >
> > > On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B <
> mohanabala...@gmail.com>wrote:
> >
> > >> can use counting sort
> >
> > >> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota <
> santoshthot...@gmail.com>wrote:
> >
> > >>> If we can retrieve ith prime efficiently, we can do the following...
> > >>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th
> prime
> > >>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
> > >>>else prod=prod*ith_prime;
> > >>> 3.repeat it till end
> >
> > >>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
> >
> >  Given an array of integers where some numbers repeat once, some
> numbers
> >  repeat twice and only one number repeats thrice, how do you find
> the number
> >  that gets repeated 3 times?
> >
> >  Does this problem have an O(n) time and O(1) space solution?
> >  No hashmaps please!
> >
> > >>>  --
> > >>> 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/-/TSPSKlD0FDsJ.
> >
> > >>> 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 unsubscribe from this group and stop receiving emails from it,
> send an
> > >> email to algogeeks+unsubscr...@googlegroups.com.
> > >> For more options, visithttps://groups.google.com/groups/opt_out.
> >
> > > --
> > > Regards,
> > > Sachin Chitale
> > > Application Engineer SCJP, SCWCD
> > > Contact# : +91 8086284349, 9892159511
> > > Oracle Corporation
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To unsubscribe from this group and stop receiving emails from it, send
> an
> > > email to algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visithttps://groups.google.com/groups/opt_out.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: Amazon Interview Question

[Don]

The xor approach only works if there are no values which occur only
once. But the problem statement indicates that some numbers occur
once, some occur twice, and one occurs three times. So you will end up
with prod equal to the xor of all of the values which occur once or
three times. Put that in your input array and you'll find that you
don't get the desired output.

I don't know of a solution better than sorting and scanning the array.

Don

On Feb 12, 3:14 pm, prakhar singh  wrote:
> #include
>
> int main()
> {
>    int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
>    int prod=a[0];int i;
>    for(i=1;i<(int)sizeof(a)/sizeof(a[0]);i++)
>    {
>       prod ^= a[i];
>    }
>    printf("%d\n",prod);   //outputs 3, algorithm works as Sachin described
> it;
>
> }
>
> On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
> wrote:
>
>
>
>
>
>
>
> > use ex-or operation for all array elements..
> > a^a=0
> > a^a^a=a
>
> > On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B 
> > wrote:
>
> >> can use counting sort
>
> >> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
> >> wrote:
>
> >>> If we can retrieve ith prime efficiently, we can do the following...
> >>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
> >>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
> >>>            else prod=prod*ith_prime;
> >>> 3.repeat it till end
>
> >>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>
>  Given an array of integers where some numbers repeat once, some numbers
>  repeat twice and only one number repeats thrice, how do you find the 
>  number
>  that gets repeated 3 times?
>
>  Does this problem have an O(n) time and O(1) space solution?
>  No hashmaps please!
>
> >>>  --
> >>> 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/-/TSPSKlD0FDsJ.
>
> >>> 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 unsubscribe from this group and stop receiving emails from it, send an
> >> email to algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visithttps://groups.google.com/groups/opt_out.
>
> > --
> > Regards,
> > Sachin Chitale
> > Application Engineer SCJP, SCWCD
> > Contact# : +91 8086284349, 9892159511
> > Oracle Corporation
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to algogeeks+unsubscr...@googlegroups.com.
> > For more options, visithttps://groups.google.com/groups/opt_out.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[sourabh jain]

Search for BitSet/BitVector in java .

On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
wrote:

> use ex-or operation for all array elements..
> a^a=0
> a^a^a=a
>
>
> On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B 
> wrote:
>
>> can use counting sort
>>
>>
>> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
>> wrote:
>>
>>> If we can retrieve ith prime efficiently, we can do the following...
>>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
>>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>>>else prod=prod*ith_prime;
>>> 3.repeat it till end
>>>
>>>
>>>
>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>
 Given an array of integers where some numbers repeat once, some numbers
 repeat twice and only one number repeats thrice, how do you find the number
 that gets repeated 3 times?

 Does this problem have an O(n) time and O(1) space solution?
 No hashmaps please!

>>>  --
>>> 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/-/TSPSKlD0FDsJ.
>>>
>>> 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 unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> Regards,
> Sachin Chitale
> Application Engineer SCJP, SCWCD
> Contact# : +91 8086284349, 9892159511
> Oracle Corporation
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[BUBUN SHEKHAR]

Sachin Chitale,
Dude the xoring operation will give us xor of numbers with freq 1 and 3 
respectively. How do you filter out the number with the frequency 3??

On Tuesday, February 12, 2013 11:44:08 PM UTC+5:30, Sachin Chitale wrote:
>
> use ex-or operation for all array elements..
> a^a=0
> a^a^a=a
>
>
> On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B 
> 
> > wrote:
>
>> can use counting sort
>>
>>
>> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
>> 
>> > wrote:
>>
>>> If we can retrieve ith prime efficiently, we can do the following...
>>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
>>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>>>else prod=prod*ith_prime;
>>> 3.repeat it till end
>>>
>>>
>>>
>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>
 Given an array of integers where some numbers repeat once, some numbers 
 repeat twice and only one number repeats thrice, how do you find the 
 number 
 that gets repeated 3 times?

 Does this problem have an O(n) time and O(1) space solution?
 No hashmaps please!

>>>  -- 
>>> 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/-/TSPSKlD0FDsJ.
>>>
>>> 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.
>>>
>>
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to algogeeks+...@googlegroups.com .
>> For more options, visit https://groups.google.com/groups/opt_out.
>>  
>>  
>>
>
>
>
> -- 
> Regards,
> Sachin Chitale
> Application Engineer SCJP, SCWCD
> Contact# : +91 8086284349, 9892159511
> Oracle Corporation 
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[arun singh chauhan]

@Sachin Chitale : Very good approach dude .
thumbs up +1

-- 
Arun Singh Chauhan
Engineer (RnD 2), Samsung Electronics 
Software Engineering Lab, Noida


On Tuesday, February 12, 2013 11:44:08 PM UTC+5:30, Sachin Chitale wrote:
>
> use ex-or operation for all array elements..
> a^a=0
> a^a^a=a
>
>
> On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B 
> 
> > wrote:
>
>> can use counting sort
>>
>>
>> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
>> 
>> > wrote:
>>
>>> If we can retrieve ith prime efficiently, we can do the following...
>>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
>>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>>>else prod=prod*ith_prime;
>>> 3.repeat it till end
>>>
>>>
>>>
>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>
 Given an array of integers where some numbers repeat once, some numbers 
 repeat twice and only one number repeats thrice, how do you find the 
 number 
 that gets repeated 3 times?

 Does this problem have an O(n) time and O(1) space solution?
 No hashmaps please!

>>>  -- 
>>> 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/-/TSPSKlD0FDsJ.
>>>
>>> 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.
>>>
>>
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to algogeeks+...@googlegroups.com .
>> For more options, visit https://groups.google.com/groups/opt_out.
>>  
>>  
>>
>
>
>
> -- 
> Regards,
> Sachin Chitale
> Application Engineer SCJP, SCWCD
> Contact# : +91 8086284349, 9892159511
> Oracle Corporation 
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[Mohanabalan D B]

can use counting sort


On Sun, Jul 15, 2012 at 6:37 PM, santosh thota wrote:

> If we can retrieve ith prime efficiently, we can do the following...
> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>else prod=prod*ith_prime;
> 3.repeat it till end
>
>
>
> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>
>> Given an array of integers where some numbers repeat once, some numbers
>> repeat twice and only one number repeats thrice, how do you find the number
>> that gets repeated 3 times?
>>
>> Does this problem have an O(n) time and O(1) space solution?
>> No hashmaps please!
>>
>  --
> 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/-/TSPSKlD0FDsJ.
>
> 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 unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon interview Question

[Hariraman R]

Can anyone give me some idea if the given no is small like 12 then the next
one is 17


On Mon, Dec 24, 2012 at 7:56 PM, marti  wrote:

>
> I REPEAT, THERE is no need to SORT;
>
>
> http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration
>
>
> On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
>
>> For a given number, find the next greatest number which is just greater
>> than previous one and made up of same digits.
>
>  --
>
>
>

-- 

Re: [algogeeks] Re: Amazon interview Question

[Anurag Gupta]

Hi Ritesh

Yeah, you are right. we do not need to sort. my bad
Thank you for explaining clearly


On Thu, Dec 27, 2012 at 4:29 AM, Ritesh Mishra  wrote:

> @anurag : there is no need to SORT. as it will increase complexity O(n) to
> O(n log n).
> here is the correct code.. please look over it and notify me if i'm wrong .
>
> T.C. = O( n )
>
> // ex: "1 4 3 2 0" i'm explaining on behalf of it.
> bool permute (int *arr , int N )
> {
> if ( N<=1 ) return false;
>
> for ( int i = N-2 ; i >= 0 ; i-- )
> {
> if ( arr[i+1] > arr[i]) // now i points to 1
> {
> for ( int j = N-1 ; j > i ; j--)
> {
> if ( arr[i]< arr[j]) // now j points to 2(just greater
> than 1 )
> {
> swap(arr[i],arr[j]) ;//this will generate "2 4 3 1 0"
> since 4310 are already sorted in reverse
>  //thus no need to sort again in
> inc order rather than reversing
> i++ ; j = N-1;
> while(i seq 4..0 to 0..4
> return true ;
> }
> }
> }
> }
> return false ;
> }
>
>
> Regards,
>
> Ritesh Kumar Mishra
> Information Technology
> Third Year Undergraduate
> MNNIT Allahabad
>
>
> On Mon, Dec 24, 2012 at 7:56 PM, marti  wrote:
>
>>
>> I REPEAT, THERE is no need to SORT;
>>
>>
>> http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration
>>
>>
>> On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
>>
>>> For a given number, find the next greatest number which is just greater
>>> than previous one and made up of same digits.
>>
>>  --
>>
>>
>>
>
>  --
>
>
>



-- 
Regards
Anurag Gupta
IV Year Computer Engineering
Delhi Technological University
(Formerly Delhi College of Engineering)

-- 

Re: [algogeeks] Re: Amazon interview Question

[Ritesh Mishra]

@anurag : there is no need to SORT. as it will increase complexity O(n) to
O(n log n).
here is the correct code.. please look over it and notify me if i'm wrong .

T.C. = O( n )

// ex: "1 4 3 2 0" i'm explaining on behalf of it.
bool permute (int *arr , int N )
{
if ( N<=1 ) return false;

for ( int i = N-2 ; i >= 0 ; i-- )
{
if ( arr[i+1] > arr[i]) // now i points to 1
{
for ( int j = N-1 ; j > i ; j--)
{
if ( arr[i]< arr[j]) // now j points to 2(just greater than
1 )
{
swap(arr[i],arr[j]) ;//this will generate "2 4 3 1 0"
since 4310 are already sorted in reverse
 //thus no need to sort again in
inc order rather than reversing
i++ ; j = N-1;
while(i wrote:

>
> I REPEAT, THERE is no need to SORT;
>
>
> http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration
>
>
> On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
>
>> For a given number, find the next greatest number which is just greater
>> than previous one and made up of same digits.
>
>  --
>
>
>

-- 

[algogeeks] Re: Amazon interview Question

[marti]

I REPEAT, THERE is no need to SORT;

http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration


On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
>
> For a given number, find the next greatest number which is just greater 
> than previous one and made up of same digits. 

-- 

Re: [algogeeks] Re: Amazon interview Question

[Anurag Gupta]

@marti

your answer is completely wrong (check for 234987156221 ans is 2349871*61225
* whereas your answer would be 2349871*65225*)
and we do need to sort


On Mon, Dec 17, 2012 at 9:10 AM, marti  wrote:

> Yeah thanks Sandeep, theres an error in example...it should be
> 5436827.However there is no need to sort.
>
>
> On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
>
>> For a given number, find the next greatest number which is just greater
>> than previous one and made up of same digits.
>
>  --
>
>
>



-- 
Regards
Anurag Gupta
IV Year Computer Engineering
Delhi Technological University
(Formerly Delhi College of Engineering)

-- 

[algogeeks] Re: Amazon interview Question

[marti]

Yeah thanks Sandeep, theres an error in example...it should be 
5436827.However there is no need to sort.

On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
>
> For a given number, find the next greatest number which is just greater 
> than previous one and made up of same digits. 

-- 

Re: [algogeeks] Re: Amazon interview Question

[ramchandra sankhala]

Let the number is stored in an array a[n] with MSB at index 0...
1. i = n-1;
   reduce  i  till a[i]<=a[i-1] & i > 0.

If here i =0 means give number is largest possible number made out of digits
otherwise i is pointing to a digit such that a[i]

Re: [algogeeks] Re: Amazon interview Question

[Shubham Sandeep]

hello all... anwer to previous example would be "5436827" instead of
"5436872"please correct it :)

On Sun, Dec 16, 2012 at 11:48 PM, marti  wrote:

> Here is what you do
>
> EG: 5436782
>
> ans is 5436872
>
> how did we arrive?
>
> FInd least index i, such that a[i-1] >= a[i] starting from rigthmost
> 5436782
>   (8)
> Now , Find least index j such that a[j-1] <= a[i-1]:
>
> 5436782
>(7)
>
> swap them
>
> => 5436872
>
> Now swap all values between i and j.
>
> Pseudocode in Python:
>
> *def get_next(a):*
> *N = len(a)*
> *i = len(a)-1*
> *
> *
> *while a[i-1] >= a[i]:*
> *i -= 1*
> *
> *
> *j = N*
> *
> *
> *while a[j-1] <= a[i-1]:*
> *j -= 1*
> *
> *
> *a[i-1], a[j-1] = a[j-1], a[i-1]*
> *
> *
> *i += 1*
> *j = N*
> *
> *
> *while i < j:*
> *a[i-1], a[j-1] = a[j-1], a[i-1]*
> *i+=1*
> *j-=1*
> *
> *
> *return a*
>
>
> Source:
> http://nicolas-lara.blogspot.in/2009/01/permutations.html
>
>
> On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
>>
>> For a given number, find the next greatest number which is just greater
>> than previous one and made up of same digits.
>
>  --
>
>
>



-- 
Regards,
SHUBHAM SANDEEP
IT 3rd yr.
NIT ALD.

-- 

[algogeeks] Re: Amazon interview Question

[marti]

Here is what you do

EG: 5436782

ans is 5436872

how did we arrive?

FInd least index i, such that a[i-1] >= a[i] starting from rigthmost
5436782
  (8)
Now , Find least index j such that a[j-1] <= a[i-1]:

5436782
   (7)

swap them

=> 5436872

Now swap all values between i and j.

Pseudocode in Python:

*def get_next(a):*
*N = len(a)*
*i = len(a)-1*
*
*
*while a[i-1] >= a[i]:*
*i -= 1*
*
*
*j = N*
*
*
*while a[j-1] <= a[i-1]:*
*j -= 1*
*
*
*a[i-1], a[j-1] = a[j-1], a[i-1]*
*
*
*i += 1*
*j = N*
*
*
*while i < j:*
*a[i-1], a[j-1] = a[j-1], a[i-1]*
*i+=1*
*j-=1*
*
*
*return a*


Source:
http://nicolas-lara.blogspot.in/2009/01/permutations.html


On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
>
> For a given number, find the next greatest number which is just greater 
> than previous one and made up of same digits. 

-- 

[algogeeks] Re: Amazon Interview Question

[santosh thota]

If we can retrieve ith prime efficiently, we can do the following...
1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
2.check if (prod% (ith_prime * ith_prime )==0) then return i;
   else prod=prod*ith_prime;
3.repeat it till end


On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>
> Given an array of integers where some numbers repeat once, some numbers 
> repeat twice and only one number repeats thrice, how do you find the number 
> that gets repeated 3 times?
>
> Does this problem have an O(n) time and O(1) space solution?
> No hashmaps please!
>

-- 
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/-/TSPSKlD0FDsJ.
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: Amazon Interview Question

[santosh thota]

For the series like 2,4,3,9,4,16,5,25 ur algo runs in o(n*n/2) =o(n^2)

On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin wrote:
>
>  
> 1)Find product of the array and store it in say prod  o(n) and o(1) 
> 2)now traverse the array and check if  
>  
> static int i;
> tag:
> while(i if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
> break;
> //this may be the required element
> //e-o-while
>  
> //now check is this is the element that is occuring three times o(n)
> if(number is not the required one then)
> goto tag;
>
> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>
>> Given an array of integers where some numbers repeat once, some numbers 
>> repeat twice and only one number repeats thrice, how do you find the number 
>> that gets repeated 3 times?
>>
>> Does this problem have an O(n) time and O(1) space solution?
>> No hashmaps please!
>>
>

-- 
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/-/C-nyIi38SN0J.
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: Amazon Interview Question

[jatin]

ya that's right :( any other solution..
On Saturday, 14 July 2012 03:24:41 UTC+5:30, Dave wrote:
>
> @Jatin: Take the array {1, 2, 4, 8, ..., x, 2, 4, 8, ..., x, x}, where x 
> is the largest power of two that will fit in your integer data type. Here 1 
> occurs once, 2, 4, 8, ... each occur twice, and x occurs three times. 
> Ignoring that you can't calculate the product of the numbers due to 
> overflow, the cube of each number in the array will be a factor of the 
> product, so you will have to check every number to see if it occurs three 
> times. Those checks will be O(n), so the whole algorithm will be O(n^2). 
> Correct me if I am wrong.
>  
> As another example, just include a zero in the array and see if your 
> algorithm still works as written.
>  
> Dave
>
> On Friday, July 13, 2012 9:59:31 AM UTC-5, jatin sethi wrote:
>
>>  as long as we are using goto with proper comments to ensure that it 
>> won't decrease the readability we can use them and ther's no harm in it! 
>> Secondly the worst case for my algo is o(n) .?..correct me if i am wrong
>> On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote:
>>
>>> Ya I didn't see that part, sorry. And in general, using goto is not 
>>> advisable. 
>>> Plus this will exceed O(n) in the worst case, as we may keep visiting 
>>> the goto again and again. Not sure of its exact time complexity.
>>> ------
>>> From: vindhya chhabra
>>> Sent: 13-07-2012 17:46
>>> To: algogeeks@googlegroups.com
>>> Subject: Re: [algogeeks] Re: Amazon Interview Question
>>>
>>> @adarsh
>>> But i think jatin has asked to check for the number( we achieved in step 
>>> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt 
>>> the algo given by Jatin runs in O(n) time. please comment.
>>>
>>> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar wrote:
>>>
>>>> @jatin:
>>>> Your first method may be proved wrong. 
>>>>  
>>>> Here is a counter test case:
>>>>  
>>>> Suppose the array is:
>>>>  
>>>> 27 729 19683 2 3 3 27 3 81 729
>>>>  
>>>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs 
>>>> twice, 27 occurs twice, and 3 occurs thrice.
>>>>  
>>>> You are supposed to return 3 
>>>> But as per your method, the product will be computed as
>>>> 729*19683*2*3*3*27*3*81*729=product(say)
>>>>  
>>>> Upon traversing the second time, it will return 27, as 
>>>> product%(27*27*27) is equal to zero!
>>>>  
>>>> regards.
>>>>  
>>>>
>>>>  
>>>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>>>>
>>>>> Or we can make a BST from array list in o(n)
>>>>> then traverse it inorder-o(logn)
>>>>>  
>>>>> but this solution requires o(logn) space though. 
>>>>>
>>>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>>>>  
>>>>>>  
>>>>>> 1)Find product of the array and store it in say prod  o(n) and 
>>>>>> o(1) 
>>>>>> 2)now traverse the array and check if  
>>>>>>  
>>>>>> static int i;
>>>>>> tag:
>>>>>> while(i>>>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>>>>> break;
>>>>>> //this may be the required element
>>>>>> //e-o-while
>>>>>>  
>>>>>> //now check is this is the element that is occuring three times 
>>>>>> o(n)
>>>>>> if(number is not the required one then)
>>>>>> goto tag;
>>>>>>
>>>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>>>>
>>>>>>> Given an array of integers where some numbers repeat once, some 
>>>>>>> numbers repeat twice and only one number repeats thrice, how do you 
>>>>>>> find 
>>>>>>> the number that gets repeated 3 times?
>>>>>>>
>>>>>>> Does this problem have an O(n) time and O(1) space solution? 
>>>>>>> No hashmaps please!
>>>>>>>
>>>>>> -- 
>>>>> You received this message because you are subscribed to the Google 
>>>>> Groups &q

RE: [algogeeks] Re: Amazon Interview Question

[adarsh kumar]

+1.

--
From: Shruti Gupta
Sent: 14-07-2012 08:08
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview Question

@jatin: even i think it will b more than O(n).. infact it will be
O(n-square) in the worst case as if each hit is spurious(until the last
element of course) we will have to traverse the array for each spurious
hit.. thus giving the worst case time of O(n-square)


On Fri, Jul 13, 2012 at 8:29 PM, jatin  wrote:

>  as long as we are using goto with proper comments to ensure that it won't
> decrease the readability we can use them and ther's no harm in it!
> Secondly the worst case for my algo is o(n) .?..correct me if i am wrong
>
> On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote:
>
>> Ya I didn't see that part, sorry. And in general, using goto is not
>> advisable.
>> Plus this will exceed O(n) in the worst case, as we may keep visiting the
>> goto again and again. Not sure of its exact time complexity.
>> --
>> From: vindhya chhabra
>> Sent: 13-07-2012 17:46
>> To: algogeeks@googlegroups.com
>> Subject: Re: [algogeeks] Re: Amazon Interview Question
>>
>> @adarsh
>> But i think jatin has asked to check for the number( we achieved in step
>> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt
>> the algo given by Jatin runs in O(n) time. please comment.
>>
>> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar  wrote:
>>
>>> @jatin:
>>> Your first method may be proved wrong.
>>>
>>> Here is a counter test case:
>>>
>>> Suppose the array is:
>>>
>>> 27 729 19683 2 3 3 27 3 81 729
>>>
>>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice,
>>> 27 occurs twice, and 3 occurs thrice.
>>>
>>> You are supposed to return 3
>>> But as per your method, the product will be computed as
>>> 729*19683*2*3*3*27*3*81*729=**product(say)
>>>
>>> Upon traversing the second time, it will return 27, as
>>> product%(27*27*27) is equal to zero!
>>>
>>> regards.
>>>
>>>
>>>
>>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>>>
>>>> Or we can make a BST from array list in o(n)
>>>> then traverse it inorder-o(logn)
>>>>
>>>> but this solution requires o(logn) space though.
>>>>
>>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>>>
>>>>>
>>>>> 1)Find product of the array and store it in say prod  o(n) and
>>>>> o(1)
>>>>> 2)now traverse the array and check if
>>>>>
>>>>> static int i;
>>>>> tag:
>>>>> while(i>>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>>>> break;
>>>>> //this may be the required element
>>>>> //e-o-while
>>>>>
>>>>> //now check is this is the element that is occuring three times
>>>>> o(n)
>>>>> if(number is not the required one then)
>>>>> goto tag;
>>>>>
>>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>>>
>>>>>> Given an array of integers where some numbers repeat once, some
>>>>>> numbers repeat twice and only one number repeats thrice, how do you find
>>>>>> the number that gets repeated 3 times?
>>>>>>
>>>>>> Does this problem have an O(n) time and O(1) space solution?
>>>>>> No hashmaps please!
>>>>>>
>>>>> --
>>>> 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/-/lmzhJ-GSdigJ<https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ>.
>>>>
>>>>
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>>> 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.
>>> T

Re: [algogeeks] Re: Amazon Interview Question

[Shruti Gupta]

@jatin: even i think it will b more than O(n).. infact it will be
O(n-square) in the worst case as if each hit is spurious(until the last
element of course) we will have to traverse the array for each spurious
hit.. thus giving the worst case time of O(n-square)


On Fri, Jul 13, 2012 at 8:29 PM, jatin  wrote:

>  as long as we are using goto with proper comments to ensure that it won't
> decrease the readability we can use them and ther's no harm in it!
> Secondly the worst case for my algo is o(n) .?..correct me if i am wrong
>
> On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote:
>
>> Ya I didn't see that part, sorry. And in general, using goto is not
>> advisable.
>> Plus this will exceed O(n) in the worst case, as we may keep visiting the
>> goto again and again. Not sure of its exact time complexity.
>> --
>> From: vindhya chhabra
>> Sent: 13-07-2012 17:46
>> To: algogeeks@googlegroups.com
>> Subject: Re: [algogeeks] Re: Amazon Interview Question
>>
>> @adarsh
>> But i think jatin has asked to check for the number( we achieved in step
>> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt
>> the algo given by Jatin runs in O(n) time. please comment.
>>
>> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar  wrote:
>>
>>> @jatin:
>>> Your first method may be proved wrong.
>>>
>>> Here is a counter test case:
>>>
>>> Suppose the array is:
>>>
>>> 27 729 19683 2 3 3 27 3 81 729
>>>
>>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice,
>>> 27 occurs twice, and 3 occurs thrice.
>>>
>>> You are supposed to return 3
>>> But as per your method, the product will be computed as
>>> 729*19683*2*3*3*27*3*81*729=**product(say)
>>>
>>> Upon traversing the second time, it will return 27, as
>>> product%(27*27*27) is equal to zero!
>>>
>>> regards.
>>>
>>>
>>>
>>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>>>
>>>> Or we can make a BST from array list in o(n)
>>>> then traverse it inorder-o(logn)
>>>>
>>>> but this solution requires o(logn) space though.
>>>>
>>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>>>
>>>>>
>>>>> 1)Find product of the array and store it in say prod  o(n) and
>>>>> o(1)
>>>>> 2)now traverse the array and check if
>>>>>
>>>>> static int i;
>>>>> tag:
>>>>> while(i>>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>>>> break;
>>>>> //this may be the required element
>>>>> //e-o-while
>>>>>
>>>>> //now check is this is the element that is occuring three times
>>>>> o(n)
>>>>> if(number is not the required one then)
>>>>> goto tag;
>>>>>
>>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>>>
>>>>>> Given an array of integers where some numbers repeat once, some
>>>>>> numbers repeat twice and only one number repeats thrice, how do you find
>>>>>> the number that gets repeated 3 times?
>>>>>>
>>>>>> Does this problem have an O(n) time and O(1) space solution?
>>>>>> No hashmaps please!
>>>>>>
>>>>> --
>>>> 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/-/lmzhJ-GSdigJ<https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ>.
>>>>
>>>>
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>>> 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>>

Re: [algogeeks] Re: Amazon Interview Question

[algo bard]

No it's not O(n). Coz you're scanning the array and in case you do not find
a solution, you're jumping back to the start of the loop. That's equivalent
to a nested loop. And I think in the worst case...it'll turn out to be an
O(n^2) solution. Please correct me if I'm wrong.

On Fri, Jul 13, 2012 at 8:29 PM, jatin  wrote:

>  as long as we are using goto with proper comments to ensure that it won't
> decrease the readability we can use them and ther's no harm in it!
> Secondly the worst case for my algo is o(n) .?..correct me if i am wrong
>
> On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote:
>
>> Ya I didn't see that part, sorry. And in general, using goto is not
>> advisable.
>> Plus this will exceed O(n) in the worst case, as we may keep visiting the
>> goto again and again. Not sure of its exact time complexity.
>> --
>> From: vindhya chhabra
>> Sent: 13-07-2012 17:46
>> To: algogeeks@googlegroups.com
>> Subject: Re: [algogeeks] Re: Amazon Interview Question
>>
>> @adarsh
>> But i think jatin has asked to check for the number( we achieved in step
>> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt
>> the algo given by Jatin runs in O(n) time. please comment.
>>
>> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar  wrote:
>>
>>> @jatin:
>>> Your first method may be proved wrong.
>>>
>>> Here is a counter test case:
>>>
>>> Suppose the array is:
>>>
>>> 27 729 19683 2 3 3 27 3 81 729
>>>
>>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice,
>>> 27 occurs twice, and 3 occurs thrice.
>>>
>>> You are supposed to return 3
>>> But as per your method, the product will be computed as
>>> 729*19683*2*3*3*27*3*81*729=**product(say)
>>>
>>> Upon traversing the second time, it will return 27, as
>>> product%(27*27*27) is equal to zero!
>>>
>>> regards.
>>>
>>>
>>>
>>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>>>
>>>> Or we can make a BST from array list in o(n)
>>>> then traverse it inorder-o(logn)
>>>>
>>>> but this solution requires o(logn) space though.
>>>>
>>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>>>
>>>>>
>>>>> 1)Find product of the array and store it in say prod  o(n) and
>>>>> o(1)
>>>>> 2)now traverse the array and check if
>>>>>
>>>>> static int i;
>>>>> tag:
>>>>> while(i>>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>>>> break;
>>>>> //this may be the required element
>>>>> //e-o-while
>>>>>
>>>>> //now check is this is the element that is occuring three times
>>>>> o(n)
>>>>> if(number is not the required one then)
>>>>> goto tag;
>>>>>
>>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>>>
>>>>>> Given an array of integers where some numbers repeat once, some
>>>>>> numbers repeat twice and only one number repeats thrice, how do you find
>>>>>> the number that gets repeated 3 times?
>>>>>>
>>>>>> Does this problem have an O(n) time and O(1) space solution?
>>>>>> No hashmaps please!
>>>>>>
>>>>> --
>>>> 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/-/lmzhJ-GSdigJ<https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ>.
>>>>
>>>>
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>>> 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send em

Re: [algogeeks] Re: Amazon Interview Question

[Dave]

@Jatin: Take the array {1, 2, 4, 8, ..., x, 2, 4, 8, ..., x, x}, where x is 
the largest power of two that will fit in your integer data type. Here 1 
occurs once, 2, 4, 8, ... each occur twice, and x occurs three times. 
Ignoring that you can't calculate the product of the numbers due to 
overflow, the cube of each number in the array will be a factor of the 
product, so you will have to check every number to see if it occurs three 
times. Those checks will be O(n), so the whole algorithm will be O(n^2). 
Correct me if I am wrong.
 
As another example, just include a zero in the array and see if your 
algorithm still works as written.
 
Dave

On Friday, July 13, 2012 9:59:31 AM UTC-5, jatin sethi wrote:

>  as long as we are using goto with proper comments to ensure that it won't 
> decrease the readability we can use them and ther's no harm in it! 
> Secondly the worst case for my algo is o(n) .?..correct me if i am wrong
> On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote:
>
>> Ya I didn't see that part, sorry. And in general, using goto is not 
>> advisable. 
>> Plus this will exceed O(n) in the worst case, as we may keep visiting the 
>> goto again and again. Not sure of its exact time complexity.
>> --
>> From: vindhya chhabra
>> Sent: 13-07-2012 17:46
>> To: algogeeks@googlegroups.com
>> Subject: Re: [algogeeks] Re: Amazon Interview Question
>>
>> @adarsh
>> But i think jatin has asked to check for the number( we achieved in step 
>> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt 
>> the algo given by Jatin runs in O(n) time. please comment.
>>
>> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar  wrote:
>>
>>> @jatin:
>>> Your first method may be proved wrong. 
>>>  
>>> Here is a counter test case:
>>>  
>>> Suppose the array is:
>>>  
>>> 27 729 19683 2 3 3 27 3 81 729
>>>  
>>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 
>>> 27 occurs twice, and 3 occurs thrice.
>>>  
>>> You are supposed to return 3 
>>> But as per your method, the product will be computed as
>>> 729*19683*2*3*3*27*3*81*729=product(say)
>>>  
>>> Upon traversing the second time, it will return 27, as 
>>> product%(27*27*27) is equal to zero!
>>>  
>>> regards.
>>>  
>>>
>>>  
>>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>>>
>>>> Or we can make a BST from array list in o(n)
>>>> then traverse it inorder-o(logn)
>>>>  
>>>> but this solution requires o(logn) space though. 
>>>>
>>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>>>  
>>>>>  
>>>>> 1)Find product of the array and store it in say prod  o(n) and 
>>>>> o(1) 
>>>>> 2)now traverse the array and check if  
>>>>>  
>>>>> static int i;
>>>>> tag:
>>>>> while(i>>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>>>> break;
>>>>> //this may be the required element
>>>>> //e-o-while
>>>>>  
>>>>> //now check is this is the element that is occuring three times 
>>>>> o(n)
>>>>> if(number is not the required one then)
>>>>> goto tag;
>>>>>
>>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>>>
>>>>>> Given an array of integers where some numbers repeat once, some 
>>>>>> numbers repeat twice and only one number repeats thrice, how do you find 
>>>>>> the number that gets repeated 3 times?
>>>>>>
>>>>>> Does this problem have an O(n) time and O(1) space solution? 
>>>>>> No hashmaps please!
>>>>>>
>>>>> -- 
>>>> 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/-/lmzhJ-GSdigJ. 
>>>>
>>>> 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: Amazon Interview Question

[jatin]

 as long as we are using goto with proper comments to ensure that it won't 
decrease the readability we can use them and ther's no harm in it! 
Secondly the worst case for my algo is o(n) .?..correct me if i am wrong
On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote:

> Ya I didn't see that part, sorry. And in general, using goto is not 
> advisable. 
> Plus this will exceed O(n) in the worst case, as we may keep visiting the 
> goto again and again. Not sure of its exact time complexity.
> --
> From: vindhya chhabra
> Sent: 13-07-2012 17:46
> To: algogeeks@googlegroups.com
> Subject: Re: [algogeeks] Re: Amazon Interview Question
>
> @adarsh
> But i think jatin has asked to check for the number( we achieved in step 
> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt 
> the algo given by Jatin runs in O(n) time. please comment.
>
> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar  wrote:
>
>> @jatin:
>> Your first method may be proved wrong. 
>>  
>> Here is a counter test case:
>>  
>> Suppose the array is:
>>  
>> 27 729 19683 2 3 3 27 3 81 729
>>  
>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 
>> 27 occurs twice, and 3 occurs thrice.
>>  
>> You are supposed to return 3 
>> But as per your method, the product will be computed as
>> 729*19683*2*3*3*27*3*81*729=product(say)
>>  
>> Upon traversing the second time, it will return 27, as product%(27*27*27) 
>> is equal to zero!
>>  
>> regards.
>>  
>>
>>  
>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>>
>>> Or we can make a BST from array list in o(n)
>>> then traverse it inorder-o(logn)
>>>  
>>> but this solution requires o(logn) space though. 
>>>
>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>>  
>>>>  
>>>> 1)Find product of the array and store it in say prod  o(n) and o(1) 
>>>> 2)now traverse the array and check if  
>>>>  
>>>> static int i;
>>>> tag:
>>>> while(i>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>>> break;
>>>> //this may be the required element
>>>> //e-o-while
>>>>  
>>>> //now check is this is the element that is occuring three times o(n)
>>>> if(number is not the required one then)
>>>> goto tag;
>>>>
>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>>
>>>>> Given an array of integers where some numbers repeat once, some 
>>>>> numbers repeat twice and only one number repeats thrice, how do you find 
>>>>> the number that gets repeated 3 times?
>>>>>
>>>>> Does this problem have an O(n) time and O(1) space solution? 
>>>>> No hashmaps please!
>>>>>
>>>> -- 
>>> 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/-/lmzhJ-GSdigJ. 
>>>
>>> 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.
>>
>
>
>
> -- 
> Vindhya Chhabra
>
>
>
>  -- 
> 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/wYWXoPmf9_MJ.
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: Amazon Interview Question

[adarsh kumar]

Ya I didn't see that part, sorry. And in general, using goto is not
advisable.
Plus this will exceed O(n) in the worst case, as we may keep visiting the
goto again and again. Not sure of its exact time complexity.
--
From: vindhya chhabra
Sent: 13-07-2012 17:46
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: Amazon Interview Question

@adarsh
But i think jatin has asked to check for the number( we achieved in step 1)
occuring thrice or not..and in this check 27 will rule out.but i doubt the
algo given by Jatin runs in O(n) time. please comment.

On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar  wrote:

> @jatin:
> Your first method may be proved wrong.
>
> Here is a counter test case:
>
> Suppose the array is:
>
> 27 729 19683 2 3 3 27 3 81 729
>
> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice,
> 27 occurs twice, and 3 occurs thrice.
>
> You are supposed to return 3
> But as per your method, the product will be computed as
> 729*19683*2*3*3*27*3*81*729=product(say)
>
> Upon traversing the second time, it will return 27, as product%(27*27*27)
> is equal to zero!
>
> regards.
>
>
>
> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>
>> Or we can make a BST from array list in o(n)
>> then traverse it inorder-o(logn)
>>
>> but this solution requires o(logn) space though.
>>
>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>
>>>
>>> 1)Find product of the array and store it in say prod  o(n) and o(1)
>>> 2)now traverse the array and check if
>>>
>>> static int i;
>>> tag:
>>> while(i>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>> break;
>>> //this may be the required element
>>> //e-o-while
>>>
>>> //now check is this is the element that is occuring three times o(n)
>>> if(number is not the required one then)
>>> goto tag;
>>>
>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>
>>>> Given an array of integers where some numbers repeat once, some numbers
>>>> repeat twice and only one number repeats thrice, how do you find the number
>>>> that gets repeated 3 times?
>>>>
>>>> Does this problem have an O(n) time and O(1) space solution?
>>>> No hashmaps please!
>>>>
>>> --
>> 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/-/lmzhJ-GSdigJ.
>>
>> 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.
>



-- 
Vindhya Chhabra



 --
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: Amazon Interview Question

[vindhya chhabra]

@adarsh
But i think jatin has asked to check for the number( we achieved in step 1)
occuring thrice or not..and in this check 27 will rule out.but i doubt the
algo given by Jatin runs in O(n) time. please comment.

On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar  wrote:

> @jatin:
> Your first method may be proved wrong.
>
> Here is a counter test case:
>
> Suppose the array is:
>
> 27 729 19683 2 3 3 27 3 81 729
>
> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice,
> 27 occurs twice, and 3 occurs thrice.
>
> You are supposed to return 3
> But as per your method, the product will be computed as
> 729*19683*2*3*3*27*3*81*729=product(say)
>
> Upon traversing the second time, it will return 27, as product%(27*27*27)
> is equal to zero!
>
> regards.
>
>
>
> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>
>> Or we can make a BST from array list in o(n)
>> then traverse it inorder-o(logn)
>>
>> but this solution requires o(logn) space though.
>>
>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>
>>>
>>> 1)Find product of the array and store it in say prod  o(n) and o(1)
>>> 2)now traverse the array and check if
>>>
>>> static int i;
>>> tag:
>>> while(i>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>> break;
>>> //this may be the required element
>>> //e-o-while
>>>
>>> //now check is this is the element that is occuring three times o(n)
>>> if(number is not the required one then)
>>> goto tag;
>>>
>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>
 Given an array of integers where some numbers repeat once, some numbers
 repeat twice and only one number repeats thrice, how do you find the number
 that gets repeated 3 times?

 Does this problem have an O(n) time and O(1) space solution?
 No hashmaps please!

>>> --
>> 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/-/lmzhJ-GSdigJ.
>>
>> 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.
>



-- 
Vindhya Chhabra

-- 
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: Amazon Interview Question

[adarsh kumar]

@jatin:
Your first method may be proved wrong.

Here is a counter test case:

Suppose the array is:

27 729 19683 2 3 3 27 3 81 729

Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, 27
occurs twice, and 3 occurs thrice.

You are supposed to return 3
But as per your method, the product will be computed as
729*19683*2*3*3*27*3*81*729=product(say)

Upon traversing the second time, it will return 27, as product%(27*27*27)
is equal to zero!

regards.



On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:

> Or we can make a BST from array list in o(n)
> then traverse it inorder-o(logn)
>
> but this solution requires o(logn) space though.
>
> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>
>>
>> 1)Find product of the array and store it in say prod  o(n) and o(1)
>> 2)now traverse the array and check if
>>
>> static int i;
>> tag:
>> while(i> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>> break;
>> //this may be the required element
>> //e-o-while
>>
>> //now check is this is the element that is occuring three times o(n)
>> if(number is not the required one then)
>> goto tag;
>>
>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>
>>> Given an array of integers where some numbers repeat once, some numbers
>>> repeat twice and only one number repeats thrice, how do you find the number
>>> that gets repeated 3 times?
>>>
>>> Does this problem have an O(n) time and O(1) space solution?
>>> No hashmaps please!
>>>
>> --
> 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/-/lmzhJ-GSdigJ.
>
> 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: Amazon Interview Question

[@jatin]

Or we can make a BST from array list in o(n)
then traverse it inorder-o(logn)
 
but this solution requires o(logn) space though.
On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:

>  
> 1)Find product of the array and store it in say prod  o(n) and o(1) 
> 2)now traverse the array and check if  
>  
> static int i;
> tag:
> while(i if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
> break;
> //this may be the required element
> //e-o-while
>  
> //now check is this is the element that is occuring three times o(n)
> if(number is not the required one then)
> goto tag;
>
> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>
>> Given an array of integers where some numbers repeat once, some numbers 
>> repeat twice and only one number repeats thrice, how do you find the number 
>> that gets repeated 3 times?
>>
>> Does this problem have an O(n) time and O(1) space solution?
>> No hashmaps please!
>>
>

-- 
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/-/lmzhJ-GSdigJ.
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: Amazon Interview Question

[jatin sethi]

 
1)Find product of the array and store it in say prod  o(n) and o(1) 
2)now traverse the array and check if  
 
static int i;
tag:
while(i Given an array of integers where some numbers repeat once, some numbers 
> repeat twice and only one number repeats thrice, how do you find the number 
> that gets repeated 3 times?
>
> Does this problem have an O(n) time and O(1) space solution?
> No hashmaps please!
>

-- 
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/-/mzyzKs4UkjUJ.
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: Amazon Interview Question

[deepikaanand]

If the assumption is that there is only one element which occurs
once , some elements repeat twice and only one element which repeats
thrice

then following is the code according to the assumption made 

http://ideone.com/yseYy

-- 
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: Amazon Interview Question

[Dave]

@Algo bard: No. You can do an O(n) time, O(n) space solution with a radix 
sort, or you can do an O(n log n) time, O(1) space solution with a variety 
of sorts.
 
Dave

On Thursday, July 12, 2012 12:25:02 AM UTC-5, algo bard wrote:

> Given an array of integers where some numbers repeat once, some numbers 
> repeat twice and only one number repeats thrice, how do you find the number 
> that gets repeated 3 times?
>
> Does this problem have an O(n) time and O(1) space solution?
> No hashmaps please!
>

-- 
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/-/f5b-1deuwdMJ.
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: Amazon Interview Question

[enchantress]

Store each of the words in array in  a trie and mark the end of the word by 
its corresponding entry in the second array. Now if u are searching for a 
word it'll take O(length of word) if there is a mismatch at any point you 
know the word is not present in array1 and add it to the trie or else the 
entire string might match but not terminate in an index implying the word 
being searched for is a prefix for a word already present. Add the entry if 
not present to the trie as well as to the array append the index of the 
word in trie with value entered by the user.

On Saturday, 16 June 2012 20:36:42 UTC+5:30, algogeek wrote:
>
> could u explain how would you use a trie for this??
>
> On Thursday, June 14, 2012 1:01:00 PM UTC+5:30, Mohit Rathi wrote:
>>
>> Hi,
>>
>> *There are two arrays of length 100 each. Each of these has initially n 
>> (n<=100)
>> elements. First array contains names and the second array contains numbers
>> such that ith name in array1 corresponds to ith number in array2.
>> Write a program which asks the user to enter a name, finds it in array1,*
>>
>> *a. if it exists, then print the corresponding number in array2,
>> b. else ask the user to input its associated number and add the number and
>> name to array2 and array1 respectively, and update the size of list*
>>
>> I can think of solving it through linear walk to the array. Anyone with 
>> more optimized algorithm like BST or HashTable? 
>>
>> comments are welcome
>>
>>
>> Thanks
>>
>>

-- 
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/-/mJL9Nk2nSM4J.
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: Amazon Interview Question

[algogeek]

could u explain how would you use a trie for this??

On Thursday, June 14, 2012 1:01:00 PM UTC+5:30, Mohit Rathi wrote:
>
> Hi,
>
> *There are two arrays of length 100 each. Each of these has initially n 
> (n<=100)
> elements. First array contains names and the second array contains numbers
> such that ith name in array1 corresponds to ith number in array2.
> Write a program which asks the user to enter a name, finds it in array1,*
>
> *a. if it exists, then print the corresponding number in array2,
> b. else ask the user to input its associated number and add the number and
> name to array2 and array1 respectively, and update the size of list*
>
> I can think of solving it through linear walk to the array. Anyone with 
> more optimized algorithm like BST or HashTable? 
>
> comments are welcome
>
>
> Thanks
>
>

-- 
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/-/-BW4cpALLgIJ.
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: Amazon Interview Question

[Amol Sharma]

+1 for trie..
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 







On Fri, Jun 15, 2012 at 5:21 PM, enchantress  wrote:

> se a trie with end of word marked by its corresponding entry in array.

-- 
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: Amazon Interview Question

[enchantress]

You can use a trie with end of word marked by its corresponding entry in 
array.
On Thursday, 14 June 2012 13:01:00 UTC+5:30, Mohit Rathi wrote:
>
> Hi,
>
> *There are two arrays of length 100 each. Each of these has initially n 
> (n<=100)
> elements. First array contains names and the second array contains numbers
> such that ith name in array1 corresponds to ith number in array2.
> Write a program which asks the user to enter a name, finds it in array1,*
>
> *a. if it exists, then print the corresponding number in array2,
> b. else ask the user to input its associated number and add the number and
> name to array2 and array1 respectively, and update the size of list*
>
> I can think of solving it through linear walk to the array. Anyone with 
> more optimized algorithm like BST or HashTable? 
>
> comments are welcome
>
>
> Thanks
>
>

-- 
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/-/9qAftPBlTEEJ.
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: Amazon Interview Question

[Navin.nitjsr]

I think adjacency list can be implemented by vector of vector.
vector< vector > Nodes;
The size of vector Nodes is total no of nodes.
Every element of the vector will store all its adjacent edges.
Nodes[i] is a vector containing all the edges adjacent to node i.
So, we can copy the graph easily.

On Wednesday, 25 April 2012 17:40:16 UTC+5:30, Radhakrishnan IT wrote:
>
> How will you implement a graph data structure ? 
> Give an linked implementation  as we do not know how many nodes will be 
> there and how many edges will be there.
> Make a copy of this graph..
>
>
>

-- 
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/-/w49HbR_IySIJ.
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: Amazon Interview Question

[Asit Dhal]

Here, can we use function for comparison ??

-- 
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/-/ZgGYGAZwvcoJ.
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: Amazon Interview question

[Brijesh]

Please reply with your alog...!

-- 
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/-/OGVCUV_hutUJ.
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: Amazon Interview Question

[Wladimir Tavares]

Hi Guys,

The @pacific solution is the best?

Wladimir Araujo Tavares
*Federal University of Ceará

*




On Tue, Jun 28, 2011 at 7:26 AM, sunny agrawal wrote:

> you can initialize it to (Max-Min+1)
> where Max = max of all elements
> Min = min of all elements
>
> Or simple initialise it to a large integer like 0x7fff for 32 bit
> numbers.
>
>
>
> On Tue, Jun 28, 2011 at 3:32 PM, vikas  wrote:
>
>> what will be the oldDiff initially. can u plz explain with a egsample
>>
>> --
>> 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/-/NXQqyUTbdlkJ.
>>
>> 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.
>

-- 
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: Amazon Interview Question

[sunny agrawal]

you can initialize it to (Max-Min+1)
where Max = max of all elements
Min = min of all elements

Or simple initialise it to a large integer like 0x7fff for 32 bit
numbers.


On Tue, Jun 28, 2011 at 3:32 PM, vikas  wrote:

> what will be the oldDiff initially. can u plz explain with a egsample
>
> --
> 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/-/NXQqyUTbdlkJ.
>
> 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: Amazon Interview Question

[vikas]

what will be the oldDiff initially. can u plz explain with a egsample

-- 
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/-/NXQqyUTbdlkJ.
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: Amazon Interview Question

[anshu mishra]

@pacific you are perfectly right but the order is not o(kn) its is
O(k*n*log(n)) because to get the least number u have to use priority queue
nd at every iteration (from 1 to k*n) u have to push and pop one single
element.
-- 
Anshuman Mishra
IIIT Allahabad
-

anshumishra6...@gmail.com
rit2007...@iiita.ac.in

-- 
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: Amazon Interview Question

[pacific :-)]

My approach :

 Have a pointer to the start (smallest of the array) of each of the N
arrays.
 Until all pointers reach end of respective arrays :
take the smallest value from all of the pointers
and compute the difference between the smallest and the current pointers
of each of the arrays
let newdiff be the smallest among all the diffs
if newdiff < olddiff :
   olddiff = newdiff
   only advance the smallest number pointer

Correctness :

I believe that if the smallest difference occurs between a and b ,(a is
smallest) you will come across that comparison and find the least.

Complexity : 0(kn) , it should be the best because you atleast need to read
all of the input.

Please correct me if i'm wrong.


On Mon, May 9, 2011 at 8:55 PM, bittu  wrote:

> see here & let me know if anything wrong..??
>
>
> http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-difference-between.html
>
>
>
> Thanks & Regrads
> Shashank >> " the Best Way to Escape From The problem is to Solve it"
> Computer Science & Engg.
> BIT Mesra
>
> --
> 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,
chinna.

-- 
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: Amazon Interview Question

[bittu]

see here & let me know if anything wrong..??

http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-difference-between.html



Thanks & Regrads
Shashank >> " the Best Way to Escape From The problem is to Solve it"
Computer Science & Engg.
BIT Mesra

-- 
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: Amazon Interview question

[Harshith]

For an O(n) in place : http://arxiv.org/pdf/0805.1598

There are links to other algo's for the same problem with varying
degrees of difficulty. I think it would be a  very high expectation
indeed, if they expected this solution from the interviewee.

On Feb 28, 9:27 pm, Vinay Pandey  wrote:
> Hi,
>
> Here is my solution, let me know:
>
> /* a helper function */
> void swap(int* arr, int index1, int index2) {
> /* this is only to swap to integers */
> arr[index1] = arr[index1]^arr[index2];
> arr[index2] = arr[index1]^arr[index2];
> arr[index1] = arr[index1]^arr[index2];
>
> }
>
> /* Actual switching */
> void switch(int* arr, int length) {
> if(length%2!=0 && length<2) {
> cout<<"Cannot switch in this case";
> return;}
>
> int index = length-1, first=0, second=0;
> bool flag = 0;
> while(index>=2) {
> if(flag == 0) {
> swap(arr, (index+1)/2, index);}
>
> if(flag == 1) {
> swap(arr, index/2 + 1, index);
> swap(arr, (index+1)/2, index);}
>
> index-=2;
> flag=(flag==0)?1:0;
>
> }
> }
> On Mon, Feb 28, 2011 at 4:32 PM, Dave  wrote:
> > @Arpit: The problem is that for certain values of n, you get more than
> > one cycle, and the cycles are disjoint. You have to find all of the
> > disjoint cycles and move the elements in each one.
>
> > Dave
>
> > On Feb 28, 12:25 pm, Arpit Sood  wrote:
> > > well space complexity should be mentioned in the question then, anyway,
> > > start with the second element put it at its correct location(say x), then
> > > take x put it at its correct location, this was when you do this n-1
> > time,
> > > you will get the correct answer because it forms a cycle.
>
> > > On Mon, Feb 28, 2011 at 11:33 PM, bittu 
> > wrote:
> > > > @arpit otherwise it wont b amzon quest..
> > > >                 space dude..space is constants
>
> > > > Thanks
> > > > Shashank
>
> > > > --
> > > > 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.-Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > 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: Amazon Interview question

[Jammy]

@gaurav. They way I see it it's O(nlogn)?

you have n/4 for each level of the recursion tree and logn height. In
total its O(nlogn)



On Feb 28, 9:27 pm, Vinay Pandey  wrote:
> Hi,
>
> Here is my solution, let me know:
>
> /* a helper function */
> void swap(int* arr, int index1, int index2) {
> /* this is only to swap to integers */
> arr[index1] = arr[index1]^arr[index2];
> arr[index2] = arr[index1]^arr[index2];
> arr[index1] = arr[index1]^arr[index2];
>
> }
>
> /* Actual switching */
> void switch(int* arr, int length) {
> if(length%2!=0 && length<2) {
> cout<<"Cannot switch in this case";
> return;}
>
> int index = length-1, first=0, second=0;
> bool flag = 0;
> while(index>=2) {
> if(flag == 0) {
> swap(arr, (index+1)/2, index);}
>
> if(flag == 1) {
> swap(arr, index/2 + 1, index);
> swap(arr, (index+1)/2, index);}
>
> index-=2;
> flag=(flag==0)?1:0;
>
>
>
>
>
>
>
> }
> }
> On Mon, Feb 28, 2011 at 4:32 PM, Dave  wrote:
> > @Arpit: The problem is that for certain values of n, you get more than
> > one cycle, and the cycles are disjoint. You have to find all of the
> > disjoint cycles and move the elements in each one.
>
> > Dave
>
> > On Feb 28, 12:25 pm, Arpit Sood  wrote:
> > > well space complexity should be mentioned in the question then, anyway,
> > > start with the second element put it at its correct location(say x), then
> > > take x put it at its correct location, this was when you do this n-1
> > time,
> > > you will get the correct answer because it forms a cycle.
>
> > > On Mon, Feb 28, 2011 at 11:33 PM, bittu 
> > wrote:
> > > > @arpit otherwise it wont b amzon quest..
> > > >                 space dude..space is constants
>
> > > > Thanks
> > > > Shashank
>
> > > > --
> > > > 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.-Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > 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: Amazon Interview question

[Vinay Pandey]

Hi,

Here is my solution, let me know:


/* a helper function */
void swap(int* arr, int index1, int index2) {
/* this is only to swap to integers */
arr[index1] = arr[index1]^arr[index2];
arr[index2] = arr[index1]^arr[index2];
arr[index1] = arr[index1]^arr[index2];
}

/* Actual switching */
void switch(int* arr, int length) {
if(length%2!=0 && length<2) {
cout<<"Cannot switch in this case";
return;
}
int index = length-1, first=0, second=0;
bool flag = 0;
while(index>=2) {
if(flag == 0) {
swap(arr, (index+1)/2, index);
}
if(flag == 1) {
swap(arr, index/2 + 1, index);
swap(arr, (index+1)/2, index);
}
index-=2;
flag=(flag==0)?1:0;
}
}


On Mon, Feb 28, 2011 at 4:32 PM, Dave  wrote:

> @Arpit: The problem is that for certain values of n, you get more than
> one cycle, and the cycles are disjoint. You have to find all of the
> disjoint cycles and move the elements in each one.
>
> Dave
>
> On Feb 28, 12:25 pm, Arpit Sood  wrote:
> > well space complexity should be mentioned in the question then, anyway,
> > start with the second element put it at its correct location(say x), then
> > take x put it at its correct location, this was when you do this n-1
> time,
> > you will get the correct answer because it forms a cycle.
> >
> >
> >
> > On Mon, Feb 28, 2011 at 11:33 PM, bittu 
> wrote:
> > > @arpit otherwise it wont b amzon quest..
> > > space dude..space is constants
> >
> > > Thanks
> > > Shashank
> >
> > > --
> > > 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.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> 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: Amazon Interview question

[gaurav gupta]

Here is one recursive solution I propose :

consider example a1,a2,a3,a4,b1,b2,b3,b4

1. if n is even
swap second Half of first array with first half of second array
so it would be a1,a2,b1,b2,a3,a4,b3,b4
and it  can be solved recursively
so rearrange({a1,a2,a3,a4,b1,b2,b3,b4}) = rearrange({a1,a2,b1,b2}),
rearrange({a3,a4,b3,b4});
2. if n is odd (a1,a2,a3,a4,a5,b1,b2,b3,b4,b5)
swap second Half+1 of first array with first half+1 of second array
so it would be a1,a2,b1,b2,*b3,a3*,a4,a5,b4,b5
swap bolded elements( nth and n+1 th) a1,a2,b1,b2,a3,b3,a4,a5,b4,b5
and it  can be solved recursively by dividing in two sub parts
rearrange({a1,a2,a3,a4,a5,b1,b2,b3,b4,b5}) = swap(b3,a3),
rearrange({a1,a2,b1,b2}), rearrange({a4,a5,b4,b5});

limiting case would be
if n==2 //since the pair is in required order
return;

Time complexity analysis ( n is size of total array a+b):

T(n) = 2*T(n/2) + n/4   ( n/4 is swapping time of second Half of first array
with first half of second array)

T(n) = 2^k T(1) + n/4( 1+1/2+1/4+...+1/(2^k))
= 2^k+n/4( 1-1/(2^k))*2k = log(n)
=n+ (n-1)/2
=O(n)


What say?

On Mon, Feb 28, 2011 at 11:55 PM, Arpit Sood  wrote:

> well space complexity should be mentioned in the question then, anyway,
> start with the second element put it at its correct location(say x), then
> take x put it at its correct location, this was when you do this n-1 time,
> you will get the correct answer because it forms a cycle.
>
>
> On Mon, Feb 28, 2011 at 11:33 PM, bittu wrote:
>
>> @arpit otherwise it wont b amzon quest..
>> space dude..space is constants
>>
>>
>> Thanks
>> Shashank
>>
>> --
>> 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.
>



-- 
Thanks & Regards,
Gaurav Gupta
7676-999-350

"Quality is never an accident. It is always result of intelligent effort" -
John Ruskin

-- 
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: Amazon Interview question

[Vinay Pandey]

I forgot to mention
Time complexity: O(n), Space complexity: O(1)
Assuming you accept my solution :-)

On Mon, Feb 28, 2011 at 9:27 PM, Vinay Pandey  wrote:

> Hi,
>
> Here is my solution, let me know:
>
>
> /* a helper function */
> void swap(int* arr, int index1, int index2) {
> /* this is only to swap to integers */
>  arr[index1] = arr[index1]^arr[index2];
> arr[index2] = arr[index1]^arr[index2];
>  arr[index1] = arr[index1]^arr[index2];
> }
>
> /* Actual switching */
> void switch(int* arr, int length) {
> if(length%2!=0 && length<2) {
>  cout<<"Cannot switch in this case";
> return;
> }
>  int index = length-1, first=0, second=0;
> bool flag = 0;
> while(index>=2) {
>  if(flag == 0) {
> swap(arr, (index+1)/2, index);
> }
>  if(flag == 1) {
> swap(arr, index/2 + 1, index);
> swap(arr, (index+1)/2, index);
>  }
> index-=2;
> flag=(flag==0)?1:0;
>  }
> }
>
>
> On Mon, Feb 28, 2011 at 4:32 PM, Dave  wrote:
>
>> @Arpit: The problem is that for certain values of n, you get more than
>> one cycle, and the cycles are disjoint. You have to find all of the
>> disjoint cycles and move the elements in each one.
>>
>> Dave
>>
>> On Feb 28, 12:25 pm, Arpit Sood  wrote:
>> > well space complexity should be mentioned in the question then, anyway,
>> > start with the second element put it at its correct location(say x),
>> then
>> > take x put it at its correct location, this was when you do this n-1
>> time,
>> > you will get the correct answer because it forms a cycle.
>> >
>> >
>> >
>> > On Mon, Feb 28, 2011 at 11:33 PM, bittu 
>> wrote:
>> > > @arpit otherwise it wont b amzon quest..
>> > > space dude..space is constants
>> >
>> > > Thanks
>> > > Shashank
>> >
>> > > --
>> > > 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.- Hide quoted text -
>> >
>> > - Show quoted text -
>>
>> --
>> 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: Amazon Interview question

[Dave]

@Arpit: The problem is that for certain values of n, you get more than
one cycle, and the cycles are disjoint. You have to find all of the
disjoint cycles and move the elements in each one.

Dave

On Feb 28, 12:25 pm, Arpit Sood  wrote:
> well space complexity should be mentioned in the question then, anyway,
> start with the second element put it at its correct location(say x), then
> take x put it at its correct location, this was when you do this n-1 time,
> you will get the correct answer because it forms a cycle.
>
>
>
> On Mon, Feb 28, 2011 at 11:33 PM, bittu  wrote:
> > @arpit otherwise it wont b amzon quest..
> >                 space dude..space is constants
>
> > Thanks
> > Shashank
>
> > --
> > 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.- Hide quoted text -
>
> - Show quoted text -

-- 
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: Amazon Interview question

[Arpit Sood]

well space complexity should be mentioned in the question then, anyway,
start with the second element put it at its correct location(say x), then
take x put it at its correct location, this was when you do this n-1 time,
you will get the correct answer because it forms a cycle.

On Mon, Feb 28, 2011 at 11:33 PM, bittu  wrote:

> @arpit otherwise it wont b amzon quest..
> space dude..space is constants
>
>
> Thanks
> Shashank
>
> --
> 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: Amazon Interview question

[bittu]

@arpit otherwise it wont b amzon quest..
 space dude..space is constants


Thanks
Shashank

-- 
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: Amazon Interview question

[murthy.krishn...@gmail.com]

how abt dis guys ??

#include 
#include 
#define MAX 100

int main()
{
int n;
int i;
int j;
int it;
char input[MAX];
char tmp;

scanf("%s",input);

n = strlen(input);

i = j = n/2;

for(it=1; it wrote:

> Are there any constraints in the problem, because it seems straight
> forward.
>
> if number of elements are 2n indexed from 0 to 2n-1
>
> for i=0 to n-1:
>new_array[i*2]=old_array[i];
>new_array[i*2+1]=old_array[i+n];
>
> On Mon, Feb 28, 2011 at 7:41 PM, bittu  wrote:
>
>> @jalaj U needs to clarify becoz what i can say that dat is overwritten
>> in ur explanation so we loosing the original  data where we are saving
>> when we swapping the elements ur explanation seems to be right but
>> little confusing
>>
>> @ujjwal  i haven't tested ur code but i think its O(n^2)  then why not
>> try for this 20  Line Simple  code of O(n^2)
>>
>> Finally we wants O(n) better solution fro this which exist for
>> this ???
>>
>> #include
>>
>> void swap(char *c,char *p)
>> {
>>  char tmp;
>>  tmp=*c;
>>  *c=*p;
>>  *p=tmp;
>>
>> }
>>
>> int main (int argc, char const* argv[])
>> {
>>char str[] = "1234abcd";
>>int i,j;
>>int len = strlen(str)/2;
>>//swap str[len-1] and str[len] and so on
>>for ( i = 0; i < len-1; i += 1) {
>>for ( j = len-1-i; j <= len+i; j += 2)
>>{
>> printf("i=%d j=%d c1=%c \t c2=%c
>> \n",i,j,str[j],str[j+1]);
>>swap(&str[j],&str[j+1]);
>>}
>>}
>>printf("%s \n", str);
>>return 0;
>> }
>>
>> Time Complexcity O(n^2)  O(n) Needed..
>>
>>
>> Thanks & Regards
>> Shashank >> "The Best Way to escape From The Problem is Solve It"
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Amazon Interview question

[Arpit Sood]

Are there any constraints in the problem, because it seems straight forward.

if number of elements are 2n indexed from 0 to 2n-1

for i=0 to n-1:
   new_array[i*2]=old_array[i];
   new_array[i*2+1]=old_array[i+n];

On Mon, Feb 28, 2011 at 7:41 PM, bittu  wrote:

> @jalaj U needs to clarify becoz what i can say that dat is overwritten
> in ur explanation so we loosing the original  data where we are saving
> when we swapping the elements ur explanation seems to be right but
> little confusing
>
> @ujjwal  i haven't tested ur code but i think its O(n^2)  then why not
> try for this 20  Line Simple  code of O(n^2)
>
> Finally we wants O(n) better solution fro this which exist for
> this ???
>
> #include
>
> void swap(char *c,char *p)
> {
>  char tmp;
>  tmp=*c;
>  *c=*p;
>  *p=tmp;
>
> }
>
> int main (int argc, char const* argv[])
> {
>char str[] = "1234abcd";
>int i,j;
>int len = strlen(str)/2;
>//swap str[len-1] and str[len] and so on
>for ( i = 0; i < len-1; i += 1) {
>for ( j = len-1-i; j <= len+i; j += 2)
>{
> printf("i=%d j=%d c1=%c \t c2=%c
> \n",i,j,str[j],str[j+1]);
>swap(&str[j],&str[j+1]);
>}
>}
>printf("%s \n", str);
>return 0;
> }
>
> Time Complexcity O(n^2)  O(n) Needed..
>
>
> Thanks & Regards
> Shashank >> "The Best Way to escape From The Problem is Solve It"
>
> --
> 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: Amazon Interview question

[bittu]

@jalaj U needs to clarify becoz what i can say that dat is overwritten
in ur explanation so we loosing the original  data where we are saving
when we swapping the elements ur explanation seems to be right but
little confusing

@ujjwal  i haven't tested ur code but i think its O(n^2)  then why not
try for this 20  Line Simple  code of O(n^2)

Finally we wants O(n) better solution fro this which exist for
this ???

#include

void swap(char *c,char *p)
{
  char tmp;
  tmp=*c;
  *c=*p;
  *p=tmp;

}

int main (int argc, char const* argv[])
{
char str[] = "1234abcd";
int i,j;
int len = strlen(str)/2;
//swap str[len-1] and str[len] and so on
for ( i = 0; i < len-1; i += 1) {
for ( j = len-1-i; j <= len+i; j += 2)
{
 printf("i=%d j=%d c1=%c \t c2=%c \n",i,j,str[j],str[j+1]);
swap(&str[j],&str[j+1]);
}
}
printf("%s \n", str);
return 0;
}

Time Complexcity O(n^2)  O(n) Needed..


Thanks & Regards
Shashank >> "The Best Way to escape From The Problem is Solve It"

-- 
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: amazon interview question

[Senthilnathan Maadasamy]

@SoumyaNice Solution.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: amazon interview question

[Soumya Prasad Ukil]

O(m+n).
Search from rightmost top corner. Count the no of zero from right and go to
left, i.e. traverse through columns from right of the first row. When you
find a column having 0, go down to lower row. Check the correspondent column
is 1 or not. If it is, follow the above step or else go down to next lower
row.

On 24 December 2010 16:02, MAC  wrote:

> updated :)
>
> Given a boolean matrix with all the true elements on left side in the row
>> so that each row can be broken into two parts left part containing only true
>> elements and right part containing only false elements. Find the row with
>> max number of true elements in it.
>>
>>
>> 00011
>> 0
>> 1
>>
>> true is 0 false is 1 .. so we will say 2nd row has maximum 1  and 3rd row
>> has mximum 0
>>
>> --
>> thanks
>> --mac
>>
>>
>
>
> --
> thanks
> --mac
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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,
soumya prasad ukil

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: amazon interview question

[MAC]

updated :)

Given a boolean matrix with all the true elements on left side in the row so
> that each row can be broken into two parts left part containing only true
> elements and right part containing only false elements. Find the row with
> max number of true elements in it.
>
>
> 00011
> 0
> 1
>
> true is 0 false is 1 .. so we will say 2nd row has maximum 1  and 3rd row
> has mximum 0
>
> --
> thanks
> --mac
>
>


-- 
thanks
--mac

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question about Linked Lists

[soundar]

@shiva , U didn't check for the cycles.Since in question it is never
mentioned about cycles u can add few steps to check cycles.
(eg)

1 > 3 -> 5 >
|  |
|  |
|  |
4-3--3

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question about Linked Lists

[siva viknesh]

oh thank u :)

On Dec 22, 11:20 am, bittu  wrote:
> Xcellent Shiva..keep goin on..\
>
> Best Regards
> Shashank Mani Narayan
> BIT Mesra

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question about Linked Lists

[bittu]

Xcellent Shiva..keep goin on..\



Best Regards
Shashank Mani Narayan
BIT Mesra

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question about Linked Lists

[siva viknesh]

ya through down pointer we can print..coz each time i m making fwd as
NULL

On Dec 20, 2:33 pm, Rishi Agrawal  wrote:
> See inline ..
>
> On Sat, Dec 18, 2010 at 12:09 PM, siva viknesh wrote:
>
>
>
> >  Given a linked list structure where every node represents a linked list
> > and contains two pointers of its type:
> > (i) pointer to next node in the main list.
> > (ii) pointer to a linked list where this node is head.
>
> > Write a C function to flatten the list into a single linked list.
>
> > Eg.
>
> > If the given linked list is
> >  1 -- 5 -- 7 -- 10
> >  |       |      |
> >  2     6     8
> >  |       |
> >  3     9
> >  |
> >  4
>
> > then convert it to
>
> >  1 - 2 - 3 - 4 - 5 - 6 - 9 - 7 - 8 -10
>
> > My solution - not tested :
>
> > struct node
> > {
>
> >   int data;
>
> >   struct node *fwd; //pointer to next node in the main list.
>
> >   struct node *down; //pointer to a linked list where this node is head.
>
> > }*head,*temp,*temp2;
>
> > temp=head;
> > while(temp->fwd!=NULL)
>
> > {
> >     temp2=temp->fwd;
>
> >     while(temp->down!=NULL)
> >     {
>
> >         temp=temp->down;
> >     }
>
> >     temp->down=temp2;
>
> // how will the code access the flattened linked list by down or by fwd ? In
> this case there in no particular pointer by which the code can access the
> linked list. Try to write a function to print the flattened linked list.
>
>
>
> >     temp->fwd=NULL;
>
> >     temp=temp2;
>
> > }
>
> > plz notify me if anything...other solutions and optimizations are welcome
>
> > --
> > Regards,
> > $iva
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@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,
> Rishi Agrawal

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[saravana kumar]

It can be done easily by counting sort
On Wed, Dec 15, 2010 at 5:36 AM, Soumya Prasad Ukil
wrote:

> Have a look : http://geeksforgeeks.org/?p=1488
>
>
> On 15 December 2010 05:19, Saurabh Koar  wrote:
>
>> @ Bittu:
>>
>> Lets analyze your code with iterations:
>>
>> the array contains  1 3 3 1 2 3 5 2 3
>> count contains   0 2 2 4 0 1 0 0 0
>>
>> now 1st iteration:
>> i=8,7,6 the inner loop will nt be executed;
>>
>> i=5; so j=0 only; as count[5]=1;
>> Now arr[pos](i.e array[0])=5
>>
>> i=4; the inner loop fails
>>
>> i=3; so j=0 to 3 as count[3]=4
>> Now array[1]=array[2]=array[3]=array[4]=3
>>
>> i=2; so j=0 to 1 as count[2]=2
>> so array[5]=array[6]=2
>>
>> and likewise array[7]=array[8]=1
>>
>> so the final array 5 3 3 3 3 2 2 1 1
>>
>> It doesnt match with the desired output.
>>
>> Correct me if I m missing something.
>>
>>
>>
>> On 12/15/10, bittu  wrote:
>> > @ankur,saurabh,soumya..
>> >
>> > ya ankur i forget to remove range from dare also no need to find
>> > range  for this..\
>> >
>> > put size-1 intead of range so that malloc will alocate the memory to
>> > all  elements in array ..no hope its fine...
>> >
>> >
>> > what i did is that
>> > i took counter array  thta cvontains the  no of times particular
>> > elements  comes
>> > then i have sort d array in reverse  order...&  prints accoding to
>> > count array..thats it... and the last line  of actual question says..
>> >
>> > """..in case of a tie  print the number which occurred first ""..i
>> > don't think d way i hav solved dis..
>> >
>> > still please let me no..if m wrong..
>> >
>> > Regards
>> > Shashank Mani Narayan " Don't b evil U can earn while u Learn"
>> > Computer Science & enginerring
>> > BIrla Institute of Technology,Mesra
>> > Cell 9166674831
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algoge...@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 algoge...@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,
> soumya prasad ukil
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: Amazon Interview Question

[Soumya Prasad Ukil]

Have a look : http://geeksforgeeks.org/?p=1488

On 15 December 2010 05:19, Saurabh Koar  wrote:

> @ Bittu:
>
> Lets analyze your code with iterations:
>
> the array contains  1 3 3 1 2 3 5 2 3
> count contains   0 2 2 4 0 1 0 0 0
>
> now 1st iteration:
> i=8,7,6 the inner loop will nt be executed;
>
> i=5; so j=0 only; as count[5]=1;
> Now arr[pos](i.e array[0])=5
>
> i=4; the inner loop fails
>
> i=3; so j=0 to 3 as count[3]=4
> Now array[1]=array[2]=array[3]=array[4]=3
>
> i=2; so j=0 to 1 as count[2]=2
> so array[5]=array[6]=2
>
> and likewise array[7]=array[8]=1
>
> so the final array 5 3 3 3 3 2 2 1 1
>
> It doesnt match with the desired output.
>
> Correct me if I m missing something.
>
>
>
> On 12/15/10, bittu  wrote:
> > @ankur,saurabh,soumya..
> >
> > ya ankur i forget to remove range from dare also no need to find
> > range  for this..\
> >
> > put size-1 intead of range so that malloc will alocate the memory to
> > all  elements in array ..no hope its fine...
> >
> >
> > what i did is that
> > i took counter array  thta cvontains the  no of times particular
> > elements  comes
> > then i have sort d array in reverse  order...&  prints accoding to
> > count array..thats it... and the last line  of actual question says..
> >
> > """..in case of a tie  print the number which occurred first ""..i
> > don't think d way i hav solved dis..
> >
> > still please let me no..if m wrong..
> >
> > Regards
> > Shashank Mani Narayan " Don't b evil U can earn while u Learn"
> > Computer Science & enginerring
> > BIrla Institute of Technology,Mesra
> > Cell 9166674831
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@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 algoge...@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,
soumya prasad ukil

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[Saurabh Koar]

@ Bittu:

Lets analyze your code with iterations:

the array contains  1 3 3 1 2 3 5 2 3
count contains   0 2 2 4 0 1 0 0 0

now 1st iteration:
i=8,7,6 the inner loop will nt be executed;

i=5; so j=0 only; as count[5]=1;
Now arr[pos](i.e array[0])=5

i=4; the inner loop fails

i=3; so j=0 to 3 as count[3]=4
Now array[1]=array[2]=array[3]=array[4]=3

i=2; so j=0 to 1 as count[2]=2
so array[5]=array[6]=2

and likewise array[7]=array[8]=1

so the final array 5 3 3 3 3 2 2 1 1

It doesnt match with the desired output.

Correct me if I m missing something.



On 12/15/10, bittu  wrote:
> @ankur,saurabh,soumya..
>
> ya ankur i forget to remove range from dare also no need to find
> range  for this..\
>
> put size-1 intead of range so that malloc will alocate the memory to
> all  elements in array ..no hope its fine...
>
>
> what i did is that
> i took counter array  thta cvontains the  no of times particular
> elements  comes
> then i have sort d array in reverse  order...&  prints accoding to
> count array..thats it... and the last line  of actual question says..
>
> """..in case of a tie  print the number which occurred first ""..i
> don't think d way i hav solved dis..
>
> still please let me no..if m wrong..
>
> Regards
> Shashank Mani Narayan " Don't b evil U can earn while u Learn"
> Computer Science & enginerring
> BIrla Institute of Technology,Mesra
> Cell 9166674831
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: Amazon Interview Question

[bittu]

@ankur,saurabh,soumya..

ya ankur i forget to remove range from dare also no need to find
range  for this..\

put size-1 intead of range so that malloc will alocate the memory to
all  elements in array ..no hope its fine...


what i did is that
i took counter array  thta cvontains the  no of times particular
elements  comes
then i have sort d array in reverse  order...&  prints accoding to
count array..thats it... and the last line  of actual question says..

"""..in case of a tie  print the number which occurred first ""..i
don't think d way i hav solved dis..

still please let me no..if m wrong..

Regards
Shashank Mani Narayan " Don't b evil U can earn while u Learn"
Computer Science & enginerring
BIrla Institute of Technology,Mesra
Cell 9166674831

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[SVIX]

use a dictionary (available in C#... basically a collection of generic
key-value pairs where the key lookup is O(1) - hashed internally)

since "number that occurred first should be listed first" when
frequencies are the same, u need to record the first occurrence of
each number as well. Hence, the value could be a pair of integers, one
for frequency, one for first occurrence)

time complexity is O(n log n) for sorting.. space, thrice the size of
input (key, freq, first occurrence)

On Dec 14, 11:38 pm, Saurabh Koar  wrote:
> @Bittu:
>
> for(i=size-1;i>=0;i--)
>    {
>                      for(int j=0;j                      {
>                        array[pos]=i;
>                        pos++;
>                      }
>    }
>
> explain this part.
> You hv compared j for 5 integers is allocated in count via malloc.That means count[8] is
> undefined.
>
> Instead of code u plz explain the algorithm.It will be more understandable.
>
> On 12/15/10, Ankur Murarka  wrote:
>
>
>
>
>
>
>
> > I think ankur khanna's solution is appropriate. couldn't get what bittu was
> > trying to do completely.. could you just explain it once please!
>
> > On Wed, Dec 15, 2010 at 10:35 AM, Soumya Prasad Ukil
> > wrote:
>
> >> bittu, in stead of writing your code, put your logic here. It is not the
> >> place to show how capable one is to write a program.
>
> >> On 14 December 2010 11:00, bittu  wrote:
>
> >>> #include 
> >>> #include
> >>> #include
>
> >>> int main()
> >>> {
> >>>    int array[]={1,3,3,1,2,3,5,2,3};
> >>>    int size=sizeof(array)/sizeof(int);
> >>>    int min,max;
> >>>    max=min=array[0];
> >>>    int i=0;
>
> >>>  for(i = 1; i < size; i++)
> >>>  {
> >>>    if (array[i] < min)
> >>>      min = array[i];
> >>>    else if (array[i] > max)
> >>>      max = array[i];
> >>>  }
>
> >>>  int range = max - min + 1;
> >>>  int *count =(int *) malloc(range * sizeof(int));
>
> >>>    for(i = 0; i < size; i++)
> >>>    count[i] = 0;
>
> >>>    for(i = 0; i < size; i++)
> >>>    count[array[i]]++;
>
> >>>    int pos=0;
>
> >>>    for(i=size-1;i>=0;i--)
> >>>    {
> >>>                      for(int j=0;j >>>                      {
> >>>                        array[pos]=i;
> >>>                        pos++;
> >>>                      }
> >>>    }
> >>>    //free(count);
>
> >>>    for(int i=0;i >>>    printf("%d \n" ,array[i]);
>
> >>>    getch();
> >>> }
>
> >>> in case of a tie
> >>> print the number which occurred first  ...i think dis situation never
> >>> occurs...as ..array is sorted..
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algoge...@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com >>>  .com>
> >>> .
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> regards,
> >> soumya prasad ukil
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com >>  .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 algoge...@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 algoge...@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: Amazon Interview Question

[Saurabh Koar]

@Bittu:

for(i=size-1;i>=0;i--)
   {
 for(int j=0;j wrote:
> I think ankur khanna's solution is appropriate. couldn't get what bittu was
> trying to do completely.. could you just explain it once please!
>
> On Wed, Dec 15, 2010 at 10:35 AM, Soumya Prasad Ukil
> wrote:
>
>> bittu, in stead of writing your code, put your logic here. It is not the
>> place to show how capable one is to write a program.
>>
>> On 14 December 2010 11:00, bittu  wrote:
>>
>>> #include 
>>> #include
>>> #include
>>>
>>>
>>> int main()
>>> {
>>>int array[]={1,3,3,1,2,3,5,2,3};
>>>int size=sizeof(array)/sizeof(int);
>>>int min,max;
>>>max=min=array[0];
>>>int i=0;
>>>
>>>  for(i = 1; i < size; i++)
>>>  {
>>>if (array[i] < min)
>>>  min = array[i];
>>>else if (array[i] > max)
>>>  max = array[i];
>>>  }
>>>
>>>  int range = max - min + 1;
>>>  int *count =(int *) malloc(range * sizeof(int));
>>>
>>>for(i = 0; i < size; i++)
>>>count[i] = 0;
>>>
>>>for(i = 0; i < size; i++)
>>>count[array[i]]++;
>>>
>>>
>>>
>>>int pos=0;
>>>
>>>for(i=size-1;i>=0;i--)
>>>{
>>>  for(int j=0;j>>  {
>>>array[pos]=i;
>>>pos++;
>>>  }
>>>}
>>>//free(count);
>>>
>>>for(int i=0;i>>printf("%d \n" ,array[i]);
>>>
>>>getch();
>>> }
>>>
>>> in case of a tie
>>> print the number which occurred first  ...i think dis situation never
>>> occurs...as ..array is sorted..
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@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,
>> soumya prasad ukil
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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: Amazon Interview Question

[Ankur Murarka]

I think ankur khanna's solution is appropriate. couldn't get what bittu was
trying to do completely.. could you just explain it once please!

On Wed, Dec 15, 2010 at 10:35 AM, Soumya Prasad Ukil
wrote:

> bittu, in stead of writing your code, put your logic here. It is not the
> place to show how capable one is to write a program.
>
> On 14 December 2010 11:00, bittu  wrote:
>
>> #include 
>> #include
>> #include
>>
>>
>> int main()
>> {
>>int array[]={1,3,3,1,2,3,5,2,3};
>>int size=sizeof(array)/sizeof(int);
>>int min,max;
>>max=min=array[0];
>>int i=0;
>>
>>  for(i = 1; i < size; i++)
>>  {
>>if (array[i] < min)
>>  min = array[i];
>>else if (array[i] > max)
>>  max = array[i];
>>  }
>>
>>  int range = max - min + 1;
>>  int *count =(int *) malloc(range * sizeof(int));
>>
>>for(i = 0; i < size; i++)
>>count[i] = 0;
>>
>>for(i = 0; i < size; i++)
>>count[array[i]]++;
>>
>>
>>
>>int pos=0;
>>
>>for(i=size-1;i>=0;i--)
>>{
>>  for(int j=0;j>  {
>>array[pos]=i;
>>pos++;
>>  }
>>}
>>//free(count);
>>
>>for(int i=0;i>printf("%d \n" ,array[i]);
>>
>>getch();
>> }
>>
>> in case of a tie
>> print the number which occurred first  ...i think dis situation never
>> occurs...as ..array is sorted..
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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,
> soumya prasad ukil
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: Amazon Interview Question

[Soumya Prasad Ukil]

bittu, in stead of writing your code, put your logic here. It is not the
place to show how capable one is to write a program.

On 14 December 2010 11:00, bittu  wrote:

> #include 
> #include
> #include
>
>
> int main()
> {
>int array[]={1,3,3,1,2,3,5,2,3};
>int size=sizeof(array)/sizeof(int);
>int min,max;
>max=min=array[0];
>int i=0;
>
>  for(i = 1; i < size; i++)
>  {
>if (array[i] < min)
>  min = array[i];
>else if (array[i] > max)
>  max = array[i];
>  }
>
>  int range = max - min + 1;
>  int *count =(int *) malloc(range * sizeof(int));
>
>for(i = 0; i < size; i++)
>count[i] = 0;
>
>for(i = 0; i < size; i++)
>count[array[i]]++;
>
>
>
>int pos=0;
>
>for(i=size-1;i>=0;i--)
>{
>  for(int j=0;j  {
>array[pos]=i;
>pos++;
>  }
>}
>//free(count);
>
>for(int i=0;iprintf("%d \n" ,array[i]);
>
>getch();
> }
>
> in case of a tie
> print the number which occurred first  ...i think dis situation never
> occurs...as ..array is sorted..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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,
soumya prasad ukil

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[bittu]

#include 
#include
#include


int main()
{
int array[]={1,3,3,1,2,3,5,2,3};
int size=sizeof(array)/sizeof(int);
int min,max;
max=min=array[0];
int i=0;

  for(i = 1; i < size; i++)
  {
if (array[i] < min)
  min = array[i];
else if (array[i] > max)
  max = array[i];
  }

  int range = max - min + 1;
  int *count =(int *) malloc(range * sizeof(int));

for(i = 0; i < size; i++)
count[i] = 0;

for(i = 0; i < size; i++)
count[array[i]]++;



int pos=0;

for(i=size-1;i>=0;i--)
{
  for(int j=0;jhttp://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Amazon Interview Question

[Ankur Khurana]

what you can do is create a vector > and sort it on the
baisis of secondary key where it will be it's frequency. if tha range
is not given. If the range is in permissible limits, then hash table
is the answer. I suppose.

On Tue, Dec 14, 2010 at 11:45 PM, Ankur Khurana
 wrote:
> @sajj: if the range of number is not given then ?
>
> On Tue, Dec 14, 2010 at 11:41 PM, sajj  wrote:
>> you can use hash table for this dude.
>>
>> On Dec 14, 8:22 pm, Prims  wrote:
>>> given some positive numbers
>>> output the numbers in decreasing order of frequency..in case of a tie
>>> print the number which occurred first
>>>
>>> for eg: 1,3,3,1,2,3,5,2,3
>>> the output should be 11225
>>
>> --
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 algoge...@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: Amazon Interview Question

[Ankur Khurana]

@sajj: if the range of number is not given then ?

On Tue, Dec 14, 2010 at 11:41 PM, sajj  wrote:
> you can use hash table for this dude.
>
> On Dec 14, 8:22 pm, Prims  wrote:
>> given some positive numbers
>> output the numbers in decreasing order of frequency..in case of a tie
>> print the number which occurred first
>>
>> for eg: 1,3,3,1,2,3,5,2,3
>> the output should be 11225
>
> --
> You received this message because you are subscribed to the Google Groups 
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: Amazon Interview Question

[sajj]

you can use hash table for this dude.

On Dec 14, 8:22 pm, Prims  wrote:
> given some positive numbers
> output the numbers in decreasing order of frequency..in case of a tie
> print the number which occurred first
>
> for eg: 1,3,3,1,2,3,5,2,3
> the output should be 11225

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[Nikhil Agarwal]

@gene: can you do dry run a test case:

a[0]-a[n-1]
0 1 2 31 34 135

and if u c

On Tue, Dec 7, 2010 at 8:55 AM, Gene  wrote:

> I should have mentioned that this problem only makes sense if the
> array values must be unique.
>
> On Dec 6, 8:20 pm, Gene  wrote:
> > You guys are working too hard.  Think about the sequence of numbers
> > [ A[i] - i | i = 0,1,2,...n-1 ].  You are trying to probe this
> > sequence to find the number of zeros.  If you think about it for a
> > while, you will see that this sequence is non-decreasing.   It must be
> > a segment of zero or more negative numbers followed by a segment of
> > zero or more zeros followed by a segment of zero or more positive
> > numbers.  Therefore you can easily use two binary searches to find the
> > index of the leftmost and rightmost zeros.   This identifies all the
> > elements where A[i]=i in O(2 log n) = O(log n) time.  Of course if the
> > searches fail, you have no elements at all where A[i]=i.
> >
> > On Dec 5, 9:46 am, Nikhil Agarwal  wrote:
> >
> >
> >
> > > @Divesh I have updated my algo and Array A[1,2,3.n] is sorted with
> > > unique elements.CALL FIND_EQUAL(A,1,n)
> >
> > > int FIND_EQUAL(A,start,end)
> > > 1.Go to the middle element
> > > 2. If A[mid]>mid)
> > > 3.  if(start==mid)
> > > 4  return mid-1;
> > > 5return FIND_EQUAL(A,1,mid-1);
> > > 6  if(A[mid]=mid)
> > > 7if(mid==end)
> > > 8  return mid;
> > > 9return FIND_EQUAL(A,mid+1,end);
> >
> > > On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$
> > > wrote:
> >
> > > > @Nikhil
> > > > run you algo ..
> > > > on test case
> > > > index -> 1 2 3 4 5
> > > > value -> 1 2 3 4 5
> >
> > > > ouput is mid+1= 3+1=4
> > > > but it should be 5...
> > > > correct me if i am wrong... and u have assumed  all are positive,
> hence
> > > > base index should be 1
> >
> > > > On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal <
> nikhil.bhoja...@gmail.com>wrote:
> >
> > > >> If All the elements are unique and sorted in ascending order then we
> can
> > > >> design an algorithm for O(lgn) and all nos are positive.
> >
> > > >> Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
> >
> > > >> FIND_EQUAL(A,start,end)
> > > >> 1.Go to the middle element
> > > >> 2.If A[mid]==mid)
> > > >> return mid+1;
> > > >> if(A[mid]>mid)
> > > >>then FIND_EQUAL(A,start,mid-1)
> > > >> else
> > > >> FIND_EQUAL(A,mid+1,end)
> >
> > > >> Runs in O(lgn)
> >
> > > >> On Sun, Dec 5, 2010 at 12:20 PM, jai gupta  >wrote:
> >
> > > >>> Any algorithm must in worst case lead to O(n) if the elements are
> not
> > > >>> unique. Take the case:
> > > >>> 1 2 3 4 5 6
> > > >>> as all the elements satisfy the condition of of key==index . we
> must go
> > > >>> someway to each element.
> > > >>> Hence O(n).
> >
> > > >>> This may be somehow made less if the element are given to be unique
> by
> > > >>> using heap.
> >
> > > >>>  --
> > > >>> You received this message because you are subscribed to the Google
> Groups
> > > >>> "Algorithm Geeks" group.
> > > >>> To post to this group, send email to algoge...@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 & Regards
> > > >> Nikhil Agarwal
> > > >> Senior Undergraduate
> > > >> Computer Science & Engineering,
> > > >> National Institute Of Technology, Durgapur,India
> > > >>http://tech-nikk.blogspot.com
> > > >>http://beta.freshersworld.com/communities/nitd
> >
> > > >>  --
> > > >> You received this message because you are subscribed to the Google
> Groups
> > > >> "Algorithm Geeks" group.
> > > >> To post to this group, send email to algoge...@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.
> >
> > > > --
> > > > *Divesh*
> > > > (¨`·.·´¨) Always
> > > >   `·.¸(¨`·.·´¨ ) Keep
> > > >   (¨`·.·´¨)¸.·´Smiling!
> > > >`·.¸.·´" Life can give u 100's of reason 2cry,but u can give life
> 1000's
> >
> > > > of reasons 2Smile"
> >
> > > >  --
> > > > You received this message because you are subscribed to the Google
> Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algoge...@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 & Regards
> > > Nikhil Agarwal
> > > Senior Undergraduate
> > > Computer Science & Engineering,
> > > National Institute Of Technology,
> Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://
> beta.freshersworld.com/communitie...
>
> --
> You re

[algogeeks] Re: Amazon Interview Question

[Gene]

I should have mentioned that this problem only makes sense if the
array values must be unique.

On Dec 6, 8:20 pm, Gene  wrote:
> You guys are working too hard.  Think about the sequence of numbers
> [ A[i] - i | i = 0,1,2,...n-1 ].  You are trying to probe this
> sequence to find the number of zeros.  If you think about it for a
> while, you will see that this sequence is non-decreasing.   It must be
> a segment of zero or more negative numbers followed by a segment of
> zero or more zeros followed by a segment of zero or more positive
> numbers.  Therefore you can easily use two binary searches to find the
> index of the leftmost and rightmost zeros.   This identifies all the
> elements where A[i]=i in O(2 log n) = O(log n) time.  Of course if the
> searches fail, you have no elements at all where A[i]=i.
>
> On Dec 5, 9:46 am, Nikhil Agarwal  wrote:
>
>
>
> > @Divesh I have updated my algo and Array A[1,2,3.n] is sorted with
> > unique elements.CALL FIND_EQUAL(A,1,n)
>
> > int FIND_EQUAL(A,start,end)
> > 1.Go to the middle element
> > 2. If A[mid]>mid)
> > 3.      if(start==mid)
> > 4              return mid-1;
> > 5        return FIND_EQUAL(A,1,mid-1);
> > 6  if(A[mid]=mid)
> > 7        if(mid==end)
> > 8              return mid;
> > 9        return FIND_EQUAL(A,mid+1,end);
>
> > On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$
> > wrote:
>
> > > @Nikhil
> > > run you algo ..
> > > on test case
> > > index -> 1 2 3 4 5
> > > value -> 1 2 3 4 5
>
> > > ouput is mid+1= 3+1=4
> > > but it should be 5...
> > > correct me if i am wrong... and u have assumed  all are positive, hence
> > > base index should be 1
>
> > > On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal 
> > > wrote:
>
> > >> If All the elements are unique and sorted in ascending order then we can
> > >> design an algorithm for O(lgn) and all nos are positive.
>
> > >> Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
>
> > >> FIND_EQUAL(A,start,end)
> > >> 1.Go to the middle element
> > >> 2.If A[mid]==mid)
> > >> return mid+1;
> > >> if(A[mid]>mid)
> > >>        then FIND_EQUAL(A,start,mid-1)
> > >> else
> > >>             FIND_EQUAL(A,mid+1,end)
>
> > >> Runs in O(lgn)
>
> > >> On Sun, Dec 5, 2010 at 12:20 PM, jai gupta 
> > >> wrote:
>
> > >>> Any algorithm must in worst case lead to O(n) if the elements are not
> > >>> unique. Take the case:
> > >>> 1 2 3 4 5 6
> > >>> as all the elements satisfy the condition of of key==index . we must go
> > >>> someway to each element.
> > >>> Hence O(n).
>
> > >>> This may be somehow made less if the element are given to be unique by
> > >>> using heap.
>
> > >>>  --
> > >>> You received this message because you are subscribed to the Google 
> > >>> Groups
> > >>> "Algorithm Geeks" group.
> > >>> To post to this group, send email to algoge...@googlegroups.com.
> > >>> To unsubscribe from this group, send email to
> > >>> algogeeks+unsubscr...@googlegroups.com > >>>  .com>
> > >>> .
> > >>> For more options, visit this group at
> > >>>http://groups.google.com/group/algogeeks?hl=en.
>
> > >> --
> > >> Thanks & Regards
> > >> Nikhil Agarwal
> > >> Senior Undergraduate
> > >> Computer Science & Engineering,
> > >> National Institute Of Technology, Durgapur,India
> > >>http://tech-nikk.blogspot.com
> > >>http://beta.freshersworld.com/communities/nitd
>
> > >>  --
> > >> You received this message because you are subscribed to the Google Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algoge...@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com > >>  .com>
> > >> .
> > >> For more options, visit this group at
> > >>http://groups.google.com/group/algogeeks?hl=en.
>
> > > --
> > > *Divesh*
> > > (¨`·.·´¨) Always
> > >   `·.¸(¨`·.·´¨ ) Keep
> > >   (¨`·.·´¨)¸.·´Smiling!
> > >    `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 
> > > 1000's
>
> > > of reasons 2Smile"
>
> > >  --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com > >  .com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Thanks & Regards
> > Nikhil Agarwal
> > Senior Undergraduate
> > Computer Science & Engineering,
> > National Institute Of Technology, 
> > Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communitie...

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[Gene]

You guys are working too hard.  Think about the sequence of numbers
[ A[i] - i | i = 0,1,2,...n-1 ].  You are trying to probe this
sequence to find the number of zeros.  If you think about it for a
while, you will see that this sequence is non-decreasing.   It must be
a segment of zero or more negative numbers followed by a segment of
zero or more zeros followed by a segment of zero or more positive
numbers.  Therefore you can easily use two binary searches to find the
index of the leftmost and rightmost zeros.   This identifies all the
elements where A[i]=i in O(2 log n) = O(log n) time.  Of course if the
searches fail, you have no elements at all where A[i]=i.

On Dec 5, 9:46 am, Nikhil Agarwal  wrote:
> @Divesh I have updated my algo and Array A[1,2,3.n] is sorted with
> unique elements.CALL FIND_EQUAL(A,1,n)
>
> int FIND_EQUAL(A,start,end)
> 1.Go to the middle element
> 2. If A[mid]>mid)
> 3.      if(start==mid)
> 4              return mid-1;
> 5        return FIND_EQUAL(A,1,mid-1);
> 6  if(A[mid]=mid)
> 7        if(mid==end)
> 8              return mid;
> 9        return FIND_EQUAL(A,mid+1,end);
>
> On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$
> wrote:
>
>
>
>
>
> > @Nikhil
> > run you algo ..
> > on test case
> > index -> 1 2 3 4 5
> > value -> 1 2 3 4 5
>
> > ouput is mid+1= 3+1=4
> > but it should be 5...
> > correct me if i am wrong... and u have assumed  all are positive, hence
> > base index should be 1
>
> > On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal 
> > wrote:
>
> >> If All the elements are unique and sorted in ascending order then we can
> >> design an algorithm for O(lgn) and all nos are positive.
>
> >> Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
>
> >> FIND_EQUAL(A,start,end)
> >> 1.Go to the middle element
> >> 2.If A[mid]==mid)
> >> return mid+1;
> >> if(A[mid]>mid)
> >>        then FIND_EQUAL(A,start,mid-1)
> >> else
> >>             FIND_EQUAL(A,mid+1,end)
>
> >> Runs in O(lgn)
>
> >> On Sun, Dec 5, 2010 at 12:20 PM, jai gupta wrote:
>
> >>> Any algorithm must in worst case lead to O(n) if the elements are not
> >>> unique. Take the case:
> >>> 1 2 3 4 5 6
> >>> as all the elements satisfy the condition of of key==index . we must go
> >>> someway to each element.
> >>> Hence O(n).
>
> >>> This may be somehow made less if the element are given to be unique by
> >>> using heap.
>
> >>>  --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algoge...@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com >>>  .com>
> >>> .
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> Thanks & Regards
> >> Nikhil Agarwal
> >> Senior Undergraduate
> >> Computer Science & Engineering,
> >> National Institute Of Technology, Durgapur,India
> >>http://tech-nikk.blogspot.com
> >>http://beta.freshersworld.com/communities/nitd
>
> >>  --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com >>  .com>
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > *Divesh*
> > (¨`·.·´¨) Always
> >   `·.¸(¨`·.·´¨ ) Keep
> >   (¨`·.·´¨)¸.·´Smiling!
> >    `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
>
> > of reasons 2Smile"
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Thanks & Regards
> Nikhil Agarwal
> Senior Undergraduate
> Computer Science & Engineering,
> National Institute Of Technology, 
> Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[Nikhil Agarwal]

@Divesh I have updated my algo and Array A[1,2,3.n] is sorted with
unique elements.CALL FIND_EQUAL(A,1,n)

int FIND_EQUAL(A,start,end)
1.Go to the middle element
2. If A[mid]>mid)
3.  if(start==mid)
4  return mid-1;
5return FIND_EQUAL(A,1,mid-1);
6  if(A[mid]=mid)
7if(mid==end)
8  return mid;
9return FIND_EQUAL(A,mid+1,end);




On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$
wrote:

> @Nikhil
> run you algo ..
> on test case
> index -> 1 2 3 4 5
> value -> 1 2 3 4 5
>
> ouput is mid+1= 3+1=4
> but it should be 5...
> correct me if i am wrong... and u have assumed  all are positive, hence
> base index should be 1
>
>
> On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal 
> wrote:
>
>> If All the elements are unique and sorted in ascending order then we can
>> design an algorithm for O(lgn) and all nos are positive.
>>
>> Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
>>
>> FIND_EQUAL(A,start,end)
>> 1.Go to the middle element
>> 2.If A[mid]==mid)
>> return mid+1;
>> if(A[mid]>mid)
>>then FIND_EQUAL(A,start,mid-1)
>> else
>> FIND_EQUAL(A,mid+1,end)
>>
>> Runs in O(lgn)
>>
>>
>>
>>
>>
>> On Sun, Dec 5, 2010 at 12:20 PM, jai gupta wrote:
>>
>>> Any algorithm must in worst case lead to O(n) if the elements are not
>>> unique. Take the case:
>>> 1 2 3 4 5 6
>>> as all the elements satisfy the condition of of key==index . we must go
>>> someway to each element.
>>> Hence O(n).
>>>
>>> This may be somehow made less if the element are given to be unique by
>>> using heap.
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@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 & Regards
>> Nikhil Agarwal
>> Senior Undergraduate
>> Computer Science & Engineering,
>> National Institute Of Technology, Durgapur,India
>> http://tech-nikk.blogspot.com
>> http://beta.freshersworld.com/communities/nitd
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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.
>>
>
>
>
> --
> *Divesh*
> (¨`·.·´¨) Always
>   `·.¸(¨`·.·´¨ ) Keep
>   (¨`·.·´¨)¸.·´Smiling!
>`·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
>
> of reasons 2Smile"
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[Nikhil Agarwal]

@ashim please refer my post.I posted an o(lgn) algo.i.e. I am copying again
below with an update

If All the elements are unique and sorted in ascending order then we can
design an algorithm for O(lgn) and all nos are positive.

Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]

FIND_EQUAL(A,start,end)
1.Go to the middle element
2.If A[mid]==mid||mid==0)
{
if(mid==0&&A[0]!=0)
return 0;
return mid+1;
}
if(A[mid]>mid)
   then FIND_EQUAL(A,start,mid-1)
else
FIND_EQUAL(A,mid+1,end)

Runs in O(lgn)



On Sat, Dec 4, 2010 at 8:08 PM, Ashim Kapoor  wrote:

> yaar I can use  simple O(n) sweep to find out who all are equal, I think it
> can't be less than this
>
>
> On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun  wrote:
>
>> 2010/12/4 ankit sablok :
>> > as all the elements are sorted in the array make a min heap of the
>> > array elements and as min heap is a tree of keys querying a min heap
>> > or a binary search tree requires operations with time equal to the
>> > height of the tree which is log(n) hence time for querying a min heap
>> I think you might be use a log(n) time to find out a element whose
>> value is equal to some certain index, so the complexity could be
>> n*log(n)?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 algoge...@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 & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[coolfrog$]

@Nikhil
run you algo ..
on test case
index -> 1 2 3 4 5
value -> 1 2 3 4 5

ouput is mid+1= 3+1=4
but it should be 5...
correct me if i am wrong... and u have assumed  all are positive, hence base
index should be 1

On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal wrote:

> If All the elements are unique and sorted in ascending order then we can
> design an algorithm for O(lgn) and all nos are positive.
>
> Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
>
> FIND_EQUAL(A,start,end)
> 1.Go to the middle element
> 2.If A[mid]==mid)
> return mid+1;
> if(A[mid]>mid)
>then FIND_EQUAL(A,start,mid-1)
> else
> FIND_EQUAL(A,mid+1,end)
>
> Runs in O(lgn)
>
>
>
>
>
> On Sun, Dec 5, 2010 at 12:20 PM, jai gupta wrote:
>
>> Any algorithm must in worst case lead to O(n) if the elements are not
>> unique. Take the case:
>> 1 2 3 4 5 6
>> as all the elements satisfy the condition of of key==index . we must go
>> someway to each element.
>> Hence O(n).
>>
>> This may be somehow made less if the element are given to be unique by
>> using heap.
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 & Regards
> Nikhil Agarwal
> Senior Undergraduate
> Computer Science & Engineering,
> National Institute Of Technology, Durgapur,India
> http://tech-nikk.blogspot.com
> http://beta.freshersworld.com/communities/nitd
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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.
>



-- 
*Divesh*
(¨`·.·´¨) Always
  `·.¸(¨`·.·´¨ ) Keep
  (¨`·.·´¨)¸.·´Smiling!
   `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile"

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[Nikhil Agarwal]

If All the elements are unique and sorted in ascending order then we can
design an algorithm for O(lgn) and all nos are positive.

Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]

FIND_EQUAL(A,start,end)
1.Go to the middle element
2.If A[mid]==mid)
return mid+1;
if(A[mid]>mid)
   then FIND_EQUAL(A,start,mid-1)
else
FIND_EQUAL(A,mid+1,end)

Runs in O(lgn)





On Sun, Dec 5, 2010 at 12:20 PM, jai gupta  wrote:

> Any algorithm must in worst case lead to O(n) if the elements are not
> unique. Take the case:
> 1 2 3 4 5 6
> as all the elements satisfy the condition of of key==index . we must go
> someway to each element.
> Hence O(n).
>
> This may be somehow made less if the element are given to be unique by
> using heap.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Amazon Interview Question

[Ashim Kapoor]

yaar I can use  simple O(n) sweep to find out who all are equal, I think it
can't be less than this

On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun  wrote:

> 2010/12/4 ankit sablok :
> > as all the elements are sorted in the array make a min heap of the
> > array elements and as min heap is a tree of keys querying a min heap
> > or a binary search tree requires operations with time equal to the
> > height of the tree which is log(n) hence time for querying a min heap
> I think you might be use a log(n) time to find out a element whose
> value is equal to some certain index, so the complexity could be
> n*log(n)?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: Amazon Interview Question

[jai gupta]

Any algorithm must in worst case lead to O(n) if the elements are not
unique. Take the case:
1 2 3 4 5 6
as all the elements satisfy the condition of of key==index . we must go
someway to each element.
Hence O(n).

This may be somehow made less if the element are given to be unique by using
heap.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.