Re: [algogeeks] Re: Amazon Job openings

[Rahul Vatsa]

It's great to see this group active after such a long time, though it was
not for discussing an algo, but I think it's fine if a member in the group
needs some help in his/her professional career and asks for the same here.
Many members in this group are in this industry from more than a decade or
so and are definitely able to help the new guys.
I think I joined this group 12 years back and in those days it used to be
very active. Over time it has become a silent group, let it be a useful
forum in some way.

On Fri, Jul 16, 2021 at 3:46 PM Artemij Art  wrote:

> Hello, guys!
> Have a nice day. Greetings from Russia.
>
> пт, 16 июл. 2021 г., 09:19 Himanshu Singh :
>
>> Hello Guys,
>>
>> Sorry to say pls stop spamming whole group.
>>
>> Thanks.
>>
>>
>> On Fri, Jul 16, 2021, 11:46 AM Yash Khandelwal <
>> khandelwalyash...@gmail.com> wrote:
>>
>>> Done kindly check the mail
>>>
>>> On Fri, Jul 16, 2021, 11:41 AM immanuel kingston <
>>> kingston.imman...@gmail.com> wrote:
>>>
 Please send a note to me on king...@amazon.com

 Thanks,
 Kingston

 On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
 kingston.imman...@gmail.com> wrote:

> Hi all,
>
> I am a hiring manager at Amazon. We are hiring for SDE and Applied
> Science roles in my team. Please send a short note about yourself, the 
> role
> you wish to apply for and your updated CV.
>
> Thanks,
> Kingston
>
 --
 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.
 To view this discussion on the web visit
 https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.com
 
 .

>>> --
>>> 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.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/algogeeks/CAJKd1Pcup_HeQNq%2B3f%2BCcnT8puZ9zwZytnGhwkPHJzsLDdiR_g%40mail.gmail.com
>>> 
>>> .
>>>
>> --
>> 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.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/algogeeks/CAHwkYYrM7DdSXb1e_Mqis_K-_Y8HUwVJeCKSD0YpLeWiQUA5Vg%40mail.gmail.com
>> 
>> .
>>
> --
> 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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/algogeeks/CABbfMraU624PR_fKEs5RJ%3DwQd1NGw_gmiCBCV_i5beheNB91GA%40mail.gmail.com
> 
> .
>

-- 
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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CAK%2BYZjJK64zB0D8-wwWHrbasygLm7yJevzfA9dA8KVbcW1B12A%40mail.gmail.com.

Re: [algogeeks] Re: Amazon Job openings

[Artemij Art]

Hello, guys!
Have a nice day. Greetings from Russia.

пт, 16 июл. 2021 г., 09:19 Himanshu Singh :

> Hello Guys,
>
> Sorry to say pls stop spamming whole group.
>
> Thanks.
>
>
> On Fri, Jul 16, 2021, 11:46 AM Yash Khandelwal <
> khandelwalyash...@gmail.com> wrote:
>
>> Done kindly check the mail
>>
>> On Fri, Jul 16, 2021, 11:41 AM immanuel kingston <
>> kingston.imman...@gmail.com> wrote:
>>
>>> Please send a note to me on king...@amazon.com
>>>
>>> Thanks,
>>> Kingston
>>>
>>> On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
>>> kingston.imman...@gmail.com> wrote:
>>>
 Hi all,

 I am a hiring manager at Amazon. We are hiring for SDE and Applied
 Science roles in my team. Please send a short note about yourself, the role
 you wish to apply for and your updated CV.

 Thanks,
 Kingston

>>> --
>>> 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.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.com
>>> 
>>> .
>>>
>> --
>> 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.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/algogeeks/CAJKd1Pcup_HeQNq%2B3f%2BCcnT8puZ9zwZytnGhwkPHJzsLDdiR_g%40mail.gmail.com
>> 
>> .
>>
> --
> 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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/algogeeks/CAHwkYYrM7DdSXb1e_Mqis_K-_Y8HUwVJeCKSD0YpLeWiQUA5Vg%40mail.gmail.com
> 
> .
>

-- 
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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CABbfMraU624PR_fKEs5RJ%3DwQd1NGw_gmiCBCV_i5beheNB91GA%40mail.gmail.com.

Re: [algogeeks] Re: Amazon Job openings

[Himanshu Singh]

Hello Guys,

Sorry to say pls stop spamming whole group.

Thanks.


On Fri, Jul 16, 2021, 11:46 AM Yash Khandelwal 
wrote:

> Done kindly check the mail
>
> On Fri, Jul 16, 2021, 11:41 AM immanuel kingston <
> kingston.imman...@gmail.com> wrote:
>
>> Please send a note to me on king...@amazon.com
>>
>> Thanks,
>> Kingston
>>
>> On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
>> kingston.imman...@gmail.com> wrote:
>>
>>> Hi all,
>>>
>>> I am a hiring manager at Amazon. We are hiring for SDE and Applied
>>> Science roles in my team. Please send a short note about yourself, the role
>>> you wish to apply for and your updated CV.
>>>
>>> Thanks,
>>> Kingston
>>>
>> --
>> 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.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.com
>> 
>> .
>>
> --
> 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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/algogeeks/CAJKd1Pcup_HeQNq%2B3f%2BCcnT8puZ9zwZytnGhwkPHJzsLDdiR_g%40mail.gmail.com
> 
> .
>

-- 
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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CAHwkYYrM7DdSXb1e_Mqis_K-_Y8HUwVJeCKSD0YpLeWiQUA5Vg%40mail.gmail.com.

Re: [algogeeks] Re: Amazon Job openings

[Yash Khandelwal]

Done kindly check the mail

On Fri, Jul 16, 2021, 11:41 AM immanuel kingston <
kingston.imman...@gmail.com> wrote:

> Please send a note to me on king...@amazon.com
>
> Thanks,
> Kingston
>
> On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
> kingston.imman...@gmail.com> wrote:
>
>> Hi all,
>>
>> I am a hiring manager at Amazon. We are hiring for SDE and Applied
>> Science roles in my team. Please send a short note about yourself, the role
>> you wish to apply for and your updated CV.
>>
>> Thanks,
>> Kingston
>>
> --
> 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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.com
> 
> .
>

-- 
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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CAJKd1Pcup_HeQNq%2B3f%2BCcnT8puZ9zwZytnGhwkPHJzsLDdiR_g%40mail.gmail.com.

[algogeeks] Re: Amazon Job openings

[immanuel kingston]

Please send a note to me on king...@amazon.com

Thanks,
Kingston

On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
kingston.imman...@gmail.com> wrote:

> Hi all,
>
> I am a hiring manager at Amazon. We are hiring for SDE and Applied Science
> roles in my team. Please send a short note about yourself, the role you
> wish to apply for and your updated CV.
>
> Thanks,
> Kingston
>

-- 
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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.com.

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 
 santosh...@gmail.comjavascript:
  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.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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

[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 prakhars...@gmail.comwrote:

 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 dond...@gmail.com 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 prakharsngh.1...@gmail.com wrote:
  #includestdio.h
 
  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
  sachinchital...@gmail.comwrote:
 
 
 
 
 
 
 
   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.comwrote:
 
   can use counting sort
 
   On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
 santoshthot...@gmail.comwrote:
 
   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, 

[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(in)
 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

[Parag Khanna]

use XOR



On Tue, Apr 30, 2013 at 6:12 AM, Gary Drocella gdroc...@gmail.com 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(in)
 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.

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 
 shashwa...@gmail.comjavascript:
  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 
 rahul2...@gmail.comjavascript:
  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 
 rahul2...@gmail.comjavascript:
  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 dond...@gmail.com 
 javascript: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 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;in;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 javascript:.
 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 javascript:.
 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 javascript:.
 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

[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 m...@shashwat.me 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 int 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 int 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 rahul23111...@gmail.comwrote:

 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 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 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;in;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

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 m...@shashwat.me 
mailto:m...@shashwat.me 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 int 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 int 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
rahul23111...@gmail.com 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 dondod...@gmail.com
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 rahul23111...@gmail.com
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;in;i++)
 arr[i]=arr[i+1]-arr[i];
 abc(arr,n-1);

 }

   

[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 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;in;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

[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 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 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;in;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]

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 rahul23111...@gmail.comwrote:

 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 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 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;in;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]

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 rahul23111...@gmail.com 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 rahul23111...@gmail.comwrote:







  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 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 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;in;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

[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 rahul23111...@gmail.comwrote:

 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 rahul23111...@gmail.comwrote:

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

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 shashwatkmr@gmail.comwrote:

 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 rahul23111...@gmail.comwrote:

 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 
 rahul23111...@gmail.comwrote:

 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 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 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;in;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 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 int 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 int 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 
rahul23111...@gmail.com 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 dondod...@gmail.com
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 rahul23111...@gmail.com
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;in;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
mailto:algogeeks%2bunsubscr...@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

[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 
 prakhars...@gmail.comjavascript:
  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 dond...@gmail.com javascript: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 prakharsngh.1...@gmail.com wrote:
  #includestdio.h
 
  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
  sachinchital...@gmail.comwrote:
 
 
 
 
 
 
 
   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.comwrote:
 
   can use counting sort
 
   On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
 santoshthot...@gmail.comwrote:
 
   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.comjavascript:
 .
   To unsubscribe from this group, send email to
   algogeeks+...@googlegroups.com javascript:.
   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 javascript:.
   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 javascript:.
   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 javascript:.
 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 javascript:.
 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 

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
sandeepkumar1...@gmail.comwrote:

 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 Questions

[Nishant Pandey]

Ans to *Boundary traversal of a tree. Write the code.

*1) you need to for preoder oder for left most tree with flag and post
order traversal for right most tree with flag.
2) the role of flag would be to decide wther to print or not like in case
of left subtree ,flag would be tree as u knw that
in preorder traversal left element would be boundary and once u go
right make it false .. same for right subtree:

Code snippet would look like this :

void printleft (struct node *root, bool flag) {
  if (!root) return;
  if (flag || (!root-left  !root-right)) {
cout root-data;
  }
  printleft(root-left, true);
  printleft(root-right, false);
}

this is preorder for left subtree , do post order for right subtree like :

void printright (struct node *root, bool flag) {
  if (!root) return;
  printright(root-left, false);
  printright(root-right, true);
  if (flag || (!root-left  !root-right)) cout root-data;

}
*
*let me knw if anything seems confusing.
On Sun, Mar 10, 2013 at 4:59 PM, Nishant Pandey 
nishant.bits.me...@gmail.com wrote:

 i have few questions regarding ur problems pratik :

 1) A tree with only parent pointer, how to find LCA?
 Doubt : do u mean only root of the tree is given , i am assuming root
 along with two nodes address whose lca need to
  find too is given , i am right ?

 2) Find top k searched elements from a continuous stream of data.
 Doubt : what do u mean by top k search element can u please explain
 little bit with exmple.


 I would love to post solution for you provided clear my doubts 
 may i knw which Amazon's round questions are they ?


 On Mon, Feb 18, 2013 at 1:28 AM, Tushar tushicom...@gmail.com wrote:

 It looks as if you have just pasted some Amazon interview questions on
 this forum.
 These are pretty common questions.
 Try to come up with your own answers.
 Do some research on google and previous posts on this forum. You'll get
 answers to all of them.

 If you have some idea and want to discuss that, then post different posts
 for each questions as arun recommended along with your understanding of the
 question and your approach.

 All the best


 On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:

 Hi All,
 I need ur help in solving few questions.

 Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC
 BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*


 *
 *

  *a. Kadane’s Algo.*

  *
 *

 *b. Linked-list intersection point.*

 *
 [A tree with only parent pointer, how to find LCA?]
 *

 *

 *

 *
 c. Design a stack which can perform findMax in O(1).
 *

 *

 *

 *d. Set of stocks for each day have been given. Need to find the days
 on which I buy and sell share to earn max profit, alongwith finding the max
 profit.*


 *
 e. Find top k searched elements from a continuous stream of data.
 *

 *

 *

 *f. Given a linked-list and 2 integers k  m. Reverse the linked-list
 till k elements and then traverse till m elements and repeat.*

 *Write production quality code.*

 *
 *

 *g. An array of elements have been given. Find for each element, first
 max element to its right.*

 *
 *

 *h. Boundary traversal of a tree. Write the code.*


 Please help me out...

 Thanks in advance...

 Thanks  Regards,
 Pratik Mayur Mehta.

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

[Nishant Pandey]

i have few questions regarding ur problems pratik :

1) A tree with only parent pointer, how to find LCA?
Doubt : do u mean only root of the tree is given , i am assuming root along
with two nodes address whose lca need to
 find too is given , i am right ?

2) Find top k searched elements from a continuous stream of data.
Doubt : what do u mean by top k search element can u please explain
little bit with exmple.


I would love to post solution for you provided clear my doubts 
may i knw which Amazon's round questions are they ?

On Mon, Feb 18, 2013 at 1:28 AM, Tushar tushicom...@gmail.com wrote:

 It looks as if you have just pasted some Amazon interview questions on
 this forum.
 These are pretty common questions.
 Try to come up with your own answers.
 Do some research on google and previous posts on this forum. You'll get
 answers to all of them.

 If you have some idea and want to discuss that, then post different posts
 for each questions as arun recommended along with your understanding of the
 question and your approach.

 All the best


 On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:

 Hi All,
 I need ur help in solving few questions.

 Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC
 BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*


 *
 *

 *a. Kadane’s Algo.*

 *
 *

 *b. Linked-list intersection point.*

 *
 [A tree with only parent pointer, how to find LCA?]
 *

 *

 *

 *
 c. Design a stack which can perform findMax in O(1).
 *

 *

 *

 *d. Set of stocks for each day have been given. Need to find the days on
 which I buy and sell share to earn max profit, alongwith finding the max
 profit.*


 *
 e. Find top k searched elements from a continuous stream of data.
 *

 *

 *

 *f. Given a linked-list and 2 integers k  m. Reverse the linked-list
 till k elements and then traverse till m elements and repeat.*

 *Write production quality code.*

 *
 *

 *g. An array of elements have been given. Find for each element, first
 max element to its right.*

 *
 *

 *h. Boundary traversal of a tree. Write the code.*


 Please help me out...

 Thanks in advance...

 Thanks  Regards,
 Pratik Mayur Mehta.

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

[rohit jangid]

these questions were asked for software dev. in amazon ? which round .
looks like straight easy questions...


On Sun, Mar 10, 2013 at 5:58 PM, Nishant Pandey 
nishant.bits.me...@gmail.com wrote:

 Ans to *Boundary traversal of a tree. Write the code.

 *1) you need to for preoder oder for left most tree with flag and post
 order traversal for right most tree with flag.
 2) the role of flag would be to decide wther to print or not like in case
 of left subtree ,flag would be tree as u knw that
 in preorder traversal left element would be boundary and once u go
 right make it false .. same for right subtree:

 Code snippet would look like this :

 void printleft (struct node *root, bool flag) {
   if (!root) return;
   if (flag || (!root-left  !root-right)) {
 cout root-data;
   }
   printleft(root-left, true);
   printleft(root-right, false);
 }

 this is preorder for left subtree , do post order for right subtree like :

 void printright (struct node *root, bool flag) {
   if (!root) return;
   printright(root-left, false);
   printright(root-right, true);
   if (flag || (!root-left  !root-right)) cout root-data;

 }
 *
 *let me knw if anything seems confusing.

 On Sun, Mar 10, 2013 at 4:59 PM, Nishant Pandey 
 nishant.bits.me...@gmail.com wrote:

 i have few questions regarding ur problems pratik :

 1) A tree with only parent pointer, how to find LCA?
 Doubt : do u mean only root of the tree is given , i am assuming root
 along with two nodes address whose lca need to
  find too is given , i am right ?

 2) Find top k searched elements from a continuous stream of data.
 Doubt : what do u mean by top k search element can u please explain
 little bit with exmple.


 I would love to post solution for you provided clear my doubts 
 may i knw which Amazon's round questions are they ?


 On Mon, Feb 18, 2013 at 1:28 AM, Tushar tushicom...@gmail.com wrote:

 It looks as if you have just pasted some Amazon interview questions on
 this forum.
 These are pretty common questions.
 Try to come up with your own answers.
 Do some research on google and previous posts on this forum. You'll get
 answers to all of them.

 If you have some idea and want to discuss that, then post different
 posts for each questions as arun recommended along with your understanding
 of the question and your approach.

 All the best


 On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:

 Hi All,
 I need ur help in solving few questions.

 Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC
 BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*


 *
 *

  *a. Kadane’s Algo.*

  *
 *

 *b. Linked-list intersection point.*

 *
 [A tree with only parent pointer, how to find LCA?]
 *

 *

 *

 *
 c. Design a stack which can perform findMax in O(1).
 *

 *

 *

 *d. Set of stocks for each day have been given. Need to find the days
 on which I buy and sell share to earn max profit, alongwith finding the max
 profit.*


 *
 e. Find top k searched elements from a continuous stream of data.
 *

 *

 *

 *f. Given a linked-list and 2 integers k  m. Reverse the linked-list
 till k elements and then traverse till m elements and repeat.*

 *Write production quality code.*

 *
 *

 *g. An array of elements have been given. Find for each element, first
 max element to its right.*

 *
 *

 *h. Boundary traversal of a tree. Write the code.*


 Please help me out...

 Thanks in advance...

 Thanks  Regards,
 Pratik Mayur Mehta.

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






-- 
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India

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

[Tushar]

It looks as if you have just pasted some Amazon interview questions on this 
forum.
These are pretty common questions. 
Try to come up with your own answers.
Do some research on google and previous posts on this forum. You'll get 
answers to all of them.

If you have some idea and want to discuss that, then post different posts 
for each questions as arun recommended along with your understanding of the 
question and your approach.

All the best

On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:

 Hi All,
 I need ur help in solving few questions.

 Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC 
 BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*


 *
 *

 *a. Kadane’s Algo.*

 *
 *

 *b. Linked-list intersection point.*

 *
 [A tree with only parent pointer, how to find LCA?]
 *

 *

 *

 *
 c. Design a stack which can perform findMax in O(1).
 *

 *

 *

 *d. Set of stocks for each day have been given. Need to find the days on 
 which I buy and sell share to earn max profit, alongwith finding the max 
 profit.*


 *
 e. Find top k searched elements from a continuous stream of data.
 *

 *

 *

 *f. Given a linked-list and 2 integers k  m. Reverse the linked-list 
 till k elements and then traverse till m elements and repeat.*

 *Write production quality code.*

 *
 *

 *g. An array of elements have been given. Find for each element, first 
 max element to its right.*

 *
 *

 *h. Boundary traversal of a tree. Write the code.*


 Please help me out...

 Thanks in advance...

 Thanks  Regards,
 Pratik Mayur Mehta.


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

[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 dondod...@gmail.com 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 prakharsngh.1...@gmail.com wrote:
  #includestdio.h
 
  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
  sachinchital...@gmail.comwrote:
 
 
 
 
 
 
 
   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.comwrote:
 
   can use counting sort
 
   On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
 santoshthot...@gmail.comwrote:
 
   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.

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
prakharsngh.1...@gmail.comwrote:

 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 dondod...@gmail.com 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 prakharsngh.1...@gmail.com wrote:
  #includestdio.h
 
  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
  sachinchital...@gmail.comwrote:
 
 
 
 
 
 
 
   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.comwrote:
 
   can use counting sort
 
   On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
 santoshthot...@gmail.comwrote:
 
   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 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 
 mohana...@gmail.comjavascript:
  wrote:

 can use counting sort


 On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
 santosh...@gmail.comjavascript:
  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.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 javascript:.
 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

[sourabh jain]

Search for BitSet/BitVector in java .

On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
sachinchital...@gmail.comwrote:

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

 can use counting sort


 On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
 santoshthot...@gmail.comwrote:

 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

[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 
 mohana...@gmail.comjavascript:
  wrote:

 can use counting sort


 On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
 santosh...@gmail.comjavascript:
  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.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 javascript:.
 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.

[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 prakharsngh.1...@gmail.com wrote:
 #includestdio.h

 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
 sachinchital...@gmail.comwrote:







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

  can use counting sort

  On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
  santoshthot...@gmail.comwrote:

  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

[Mohanabalan D B]

can use counting sort


On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santoshthot...@gmail.comwrote:

 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.

[algogeeks] Re: Amazon Dynamic Programming problem

[siva]

Thanks all for solutions, but this problem can also be solved using DP 
right ???

On Wednesday, 16 January 2013 01:57:26 UTC+5:30, Don wrote:

 Sprague–Grundy theorem 

 On Jan 12, 6:28 pm, Nguyễn Thành Danh danhnguyen0...@gmail.com 
 wrote: 
  Can you please explain by which theorem you use to find out that? 
  
  
  
  
  
  
  
  On Sat, Jan 12, 2013 at 11:41 AM, Lucifer sourabhd2...@gmail.com 
 wrote: 
   if (n%3 == 0) 
 Player 1 will lose 
   else 
 Player 1 will win. The no. of balls picked in the first turn 
 will 
   be n%3 


-- 

[algogeeks] Re: Amazon Dynamic Programming problem

[Don]

Sure, but why? The solution is n%3. DP will by more complex and
slower.


On Jan 16, 11:43 am, siva sivavikne...@gmail.com wrote:
 Thanks all for solutions, but this problem can also be solved using DP
 right ???







 On Wednesday, 16 January 2013 01:57:26 UTC+5:30, Don wrote:

  Sprague–Grundy theorem

  On Jan 12, 6:28 pm, Nguyễn Thành Danh danhnguyen0...@gmail.com
  wrote:
   Can you please explain by which theorem you use to find out that?

   On Sat, Jan 12, 2013 at 11:41 AM, Lucifer sourabhd2...@gmail.com
  wrote:
if (n%3 == 0)
      Player 1 will lose
else
      Player 1 will win. The no. of balls picked in the first turn
  will
be n%3

-- 

[algogeeks] Re: Amazon Dynamic Programming problem

[siva]

Ya I'm aware, Just wanted to confirm. Suppose if the problem can't be 
reduced to a mathematical formulae , then DP must be the reliable solution 
for this kind of problems.
That's why wanted to know exact DP solution also..

On Wednesday, 16 January 2013 22:42:52 UTC+5:30, Don wrote:

 Sure, but why? The solution is n%3. DP will by more complex and 
 slower. 


 On Jan 16, 11:43 am, siva sivavikne...@gmail.com wrote: 
  Thanks all for solutions, but this problem can also be solved using DP 
  right ??? 
  
  
  
  
  
  
  
  On Wednesday, 16 January 2013 01:57:26 UTC+5:30, Don wrote: 
  
   Sprague–Grundy theorem 
  
   On Jan 12, 6:28 pm, Nguyễn Thành Danh danhnguyen0...@gmail.com 
   wrote: 
Can you please explain by which theorem you use to find out that? 
  
On Sat, Jan 12, 2013 at 11:41 AM, Lucifer sourabhd2...@gmail.com 
   wrote: 
 if (n%3 == 0) 
   Player 1 will lose 
 else 
   Player 1 will win. The no. of balls picked in the first 
 turn 
   will 
 be n%3 


-- 

[algogeeks] Re: Amazon Dynamic Programming problem

[Don]

The DP solution is to mark the winning position as winning. Then mark
any positions which can move to a winning position as losing and the
rest as winning.

On Jan 16, 12:21 pm, siva sivavikne...@gmail.com wrote:
 Ya I'm aware, Just wanted to confirm. Suppose if the problem can't be
 reduced to a mathematical formulae , then DP must be the reliable solution
 for this kind of problems.
 That's why wanted to know exact DP solution also..







 On Wednesday, 16 January 2013 22:42:52 UTC+5:30, Don wrote:

  Sure, but why? The solution is n%3. DP will by more complex and
  slower.

  On Jan 16, 11:43 am, siva sivavikne...@gmail.com wrote:
   Thanks all for solutions, but this problem can also be solved using DP
   right ???

   On Wednesday, 16 January 2013 01:57:26 UTC+5:30, Don wrote:

Sprague–Grundy theorem

On Jan 12, 6:28 pm, Nguyễn Thành Danh danhnguyen0...@gmail.com
wrote:
 Can you please explain by which theorem you use to find out that?

 On Sat, Jan 12, 2013 at 11:41 AM, Lucifer sourabhd2...@gmail.com
wrote:
  if (n%3 == 0)
        Player 1 will lose
  else
        Player 1 will win. The no. of balls picked in the first
  turn
will
  be n%3

-- 

Re: [algogeeks] Re: Amazon Dynamic Programming problem

[Nikhil Karnwal]

This is a impartial game similar to *Take Away Game* that can be solved
using game theory.
solution of *lucifier* is correct.

On Wed, Jan 16, 2013 at 1:57 AM, Don dondod...@gmail.com wrote:

 Sprague–Grundy theorem

 On Jan 12, 6:28 pm, Nguyễn Thành Danh danhnguyen0...@gmail.com
 wrote:
  Can you please explain by which theorem you use to find out that?
 
 
 
 
 
 
 
  On Sat, Jan 12, 2013 at 11:41 AM, Lucifer sourabhd2...@gmail.com
 wrote:
   if (n%3 == 0)
 Player 1 will lose
   else
 Player 1 will win. The no. of balls picked in the first turn
 will
   be n%3

 --




-- 

[algogeeks] Re: Amazon Job openings

[Abhishek]

Are these openings for present final year students(2013 batch) as well???

regards
Abhishek

On Tuesday, 15 January 2013 16:47:01 UTC+5:30, sahil madaan wrote:

 Hi all,

 There are multiple openings for SDE1 and SDE2 for Amazon hyderabad and 
 Bangalore location. Interested candidates please send your resume to 
 sahilma...@gmail.com javascript:

 Thanks
 sahil


-- 

[algogeeks] Re: Amazon Job openings

[marti]

Are they opening for interns as well?



On Tuesday, January 15, 2013 4:47:01 PM UTC+5:30, sahil madaan wrote:

 Hi all,

 There are multiple openings for SDE1 and SDE2 for Amazon hyderabad and 
 Bangalore location. Interested candidates please send your resume to 
 sahilma...@gmail.com javascript:

 Thanks
 sahil


-- 

Re: [algogeeks] Re: Amazon Dynamic Programming problem

[Nguyễn Thành Danh]

Can you please explain by which theorem you use to find out that?
On Sat, Jan 12, 2013 at 11:41 AM, Lucifer sourabhd2...@gmail.com wrote:

 if (n%3 == 0)
   Player 1 will lose
 else
   Player 1 will win. The no. of balls picked in the first turn will
 be n%3


-- 

[algogeeks] Re: Amazon Dynamic Programming problem

[Don]

Sprague–Grundy theorem

On Jan 12, 6:28 pm, Nguyễn Thành Danh danhnguyen0...@gmail.com
wrote:
 Can you please explain by which theorem you use to find out that?







 On Sat, Jan 12, 2013 at 11:41 AM, Lucifer sourabhd2...@gmail.com wrote:
  if (n%3 == 0)
        Player 1 will lose
  else
        Player 1 will win. The no. of balls picked in the first turn will
  be n%3

-- 

[algogeeks] Re: Amazon Dynamic Programming problem

[Don]

If it is your turn and there are 1 or 2 balls in the basket you take
them and win.
If it is your turn an there are 3 balls in the basket, you must leave
1 or 2 after your turn, so you lose.
If the number of balls on your turn is not divisible by 3, you can
take 1 or 2 balls and make it divisible by three. Your opponent will
then have to make it not divisible by three, so the process repeats
until you win.

So the first player wins if N is not divisible by 3.

Don

On Jan 12, 8:03 am, siva sivavikne...@gmail.com wrote:
 consider there are N balls in a basket. 2 players play the turns
 alternatively ..AT each turn,the player

 can take 1 or 2 balls from the basket. the first player starts the game..
 Both the players play optimally.

    i)   Given N,tell whether the 1st player win or loss ?

    ii) If player 1 wins, how many balls he should take at this first turn(1
 or 2) ?

-- 

[algogeeks] Re: Amazon Dynamic Programming problem

[Don]

This problem was a team challenge in Survivor Amazon, except they were
allowed to take 1,2,3, or 4 flags. The winning strategy is to leave a
multiple of 5 flags. But none of the contestants figured it out.
Don

On Jan 12, 8:03 am, siva sivavikne...@gmail.com wrote:
 consider there are N balls in a basket. 2 players play the turns
 alternatively ..AT each turn,the player

 can take 1 or 2 balls from the basket. the first player starts the game..
 Both the players play optimally.

    i)   Given N,tell whether the 1st player win or loss ?

    ii) If player 1 wins, how many balls he should take at this first turn(1
 or 2) ?

-- 

[algogeeks] Re: Amazon Dynamic Programming problem

[Lucifer]

@siva..

if (n%3 == 0) 
  Player 1 will lose
else
  Player 1 will win. The no. of balls picked in the first turn will be 
n%3 


On Saturday, 12 January 2013 18:33:45 UTC+5:30, siva wrote:

 consider there are N balls in a basket. 2 players play the turns 
 alternatively ..AT each turn,the player 

 can take 1 or 2 balls from the basket. the first player starts the game.. 
 Both the players play optimally. 

i)   Given N,tell whether the 1st player win or loss ?

ii) If player 1 wins, how many balls he should take at this first 
 turn(1 or 2) ?


-- 

[algogeeks] Re: Amazon Dynamic Programming problem

[Lucifer]

@siva..

if (n%3 == 0) 
  Player 1 will lose
else
  Player 1 will win. The no. of balls picked in the first turn will be 
n%3 

-- 

Re: [algogeeks] Re: Amazon Dynamic Programming problem

[kumar anurag]

yes the below logic is correct
1- 1st(1)
2- 1st(2)
3- 2nd(1,2 or 2,1)
4- 1st (1,2,1 or 1,1,2)
5-1st(2, 1, 2 or 2, 2, 1)
6- 2nd(2, 1, 3) or 1, 2,3)) 2nd will win
7- 1st(1, 1, 2, 3 or 1, 2, 1,3  or .,.
8- 1st (2, 1, 2, 3 or 2, 2,1, 3 or ..

In above 3 can be (1,2) or (2,1)

Thanks
Kumar Anurag

On Sat, Jan 12, 2013 at 10:11 PM, Lucifer sourabhd2...@gmail.com wrote:


 @siva..

 if (n%3 == 0)
   Player 1 will lose
 else
   Player 1 will win. The no. of balls picked in the first turn will
 be n%3

 --






-- 
Kumar Anurag

-- 

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(ij)  swap(arr[i++],arr[j--]) ; // reversing the
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 amritsa...@gmail.com 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

[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 amritsa...@gmail.com 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 rforr...@gmail.com 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(ij)  swap(arr[i++],arr[j--]) ; // reversing the
 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 amritsa...@gmail.com 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)

-- 

[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 amritsa...@gmail.com 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]

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. 

-- 

Re: [algogeeks] Re: Amazon interview Question

[Shubham Sandeep]

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

On Sun, Dec 16, 2012 at 11:48 PM, marti amritsa...@gmail.com 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.

-- 

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]a[i+1]

2. find smallest digit from a[i+1 to n-1] just larger than a[i].
   lets assume it come out as a digit of index j.
3. swap a[i] and a[j].
Finally sort a[i+1 to n-1] in increasing order...

suppose a=5436782
so
after step 1, i=4
after step 2, j=5
after step 4, a=5436872
finally after sorting  a=5436827


--
Ram Chandra Sankhala | 3rd Year  | Computer Science  Engineering | IIT Roorkee

-- 

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

-- 

[algogeeks] Re: Amazon Question

[xyz]

have a look http://amnwidfrenz-thinkalways.blogspot.in/2012/09/string-
reduction.html



-- 
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: given col id, print col name in excel

[coolfrog$]

@shiva: Nice thinking, man... :)
@Yq Zhang: this similar to base 26 apporch, i have tested below code for
boundary cases ,
   0, 26(z), 27(aa), 26*26(yz), 26*27(zz)

public String getColName(int id) {
char ch[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w',
'x', 'y', 'z' };
int i = 0;
int arr[] = new int[256];
while (id  0) {
arr[i++] = (id-1) % 26;
id = (id-1) / 26;
}
String result = ;
for (int x = i - 1; x = 0; x--)
result = result + ch[arr[x]];
return result;
}

On Thu, Aug 16, 2012 at 11:32 PM, shady sinv...@gmail.com wrote:

 you can do it easily by counting the number that can be formed with 1
 digit = 26, then 2 digit = 26*26... similarly find the length of the answer
 and then can find the number by searching using bsearch over the number of
 different characters.

 if someone can do it with base % method,, then it is great :-P


 On Thu, Aug 16, 2012 at 11:19 PM, Wei.QI qiw...@gmail.com wrote:

 @yq, didn't I ask you this question before?

 On Fri, Aug 10, 2012 at 4:48 PM, yq Zhang zhangyunq...@gmail.com wrote:
  @shiv, your code is correct go compute the base 26 number. However, this
  question is not base 26 number obviously.
 
 
 
  On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan narayan.shiv...@gmail.com
 
  wrote:
 
  this is similar to conversion of no in base 26.( where digits are
  a,b,c,d...z) just think it like decimal to binary conversion here base
 is
  instead 26.
 
  char Carr[26]={a,b,c...z}
  i=0;
  int arr[];
  do
  {
  arrr[i++]=n%26;
  n/=2;
  }
  while(n) ;
  for(int i=n-1;i=0;i--)
  coutCarr[a[i]];
 
  correct me if i am wrong.
  On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:
 
  Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
  aac aax, aaz, aba, abc... (Its same as excel column names). Given
 an
  integer (n), generate n-th string from the above sequence.
 
 
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652
 
  --
  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/-/Z3kYiTZi_F8J.
 
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.

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


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




-- 
--*
*
Regards
**
*Divesh Dixit*
*Software Developer
Webaroo Technology India Pvt Ltd,
* *cell:* +91-773895195 | +91-8291302034
div...@webaroo.com | www.smsgupshup.com

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

[algogeeks] Re: Amazon Online Test

[sahitya agrawal]

On Friday, 17 August 2012 08:00:24 UTC+5:30, nick wrote:

 Hi All,

 Has anyone appeared for the online test of amazon recently??
  if(yes){
  Please share with us :)
  }
  


On Friday, 17 August 2012 08:00:24 UTC+5:30, nick wrote:

 Hi All,

 Has anyone appeared for the online test of amazon recently??
  if(yes){
  Please share with us :)
  }
  


On Friday, 17 August 2012 08:00:24 UTC+5:30, nick wrote:

 Hi All,

 Has anyone appeared for the online test of amazon recently??
  if(yes){
  Please share with us :)
  }
  


On Friday, 17 August 2012 08:00:24 UTC+5:30, nick wrote:

 Hi All,

 Has anyone appeared for the online test of amazon recently??
  if(yes){
  Please share with us :)
  }
  


-- 
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/-/1TGicgRb9i4J.
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 Online Test

[sahitya agrawal]

1. Given a linked list of letters arrange it in a way such that all vowels 
come before the consonants and in the same order of input (i.e. order of 
vowels should be same as they appear in input ).
  
ex- A-M-A-Z-O-N
  
o/p :- A-A-O-M-Z-N

2. Check parenthesis in a expression
  1. A square bracket can only enclose a square bracket or a curly bracket 
or parentheses.
  2. Similarly A curly bracket can only enclose a curly bracket 
or parentheses.
  3. A parentheses can only enclose a parentheses. 
  4. parenthesis should also be balanced.  
 return true or false.
  for ex:- 
(a+b)) will return false.
   (a)) will return false.
 [a+{b*(c-d)}] will return true.

On Friday, 17 August 2012 08:00:24 UTC+5:30, nick wrote:

 Hi All,

 Has anyone appeared for the online test of amazon recently??
  if(yes){
  Please share with us :)
  }
  


-- 
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/-/9HCY-Q5IAuAJ.
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: given col id, print col name in excel

[Wei.QI]

@yq, didn't I ask you this question before?

On Fri, Aug 10, 2012 at 4:48 PM, yq Zhang zhangyunq...@gmail.com wrote:
 @shiv, your code is correct go compute the base 26 number. However, this
 question is not base 26 number obviously.



 On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan narayan.shiv...@gmail.com
 wrote:

 this is similar to conversion of no in base 26.( where digits are
 a,b,c,d...z) just think it like decimal to binary conversion here base is
 instead 26.

 char Carr[26]={a,b,c...z}
 i=0;
 int arr[];
 do
 {
 arrr[i++]=n%26;
 n/=2;
 }
 while(n) ;
 for(int i=n-1;i=0;i--)
 coutCarr[a[i]];

 correct me if i am wrong.
 On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:

 Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
 aac aax, aaz, aba, abc... (Its same as excel column names). Given an
 integer (n), generate n-th string from the above sequence.


 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

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

 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: given col id, print col name in excel

[shady]

you can do it easily by counting the number that can be formed with 1 digit
= 26, then 2 digit = 26*26... similarly find the length of the answer and
then can find the number by searching using bsearch over the number of
different characters.

if someone can do it with base % method,, then it is great :-P


On Thu, Aug 16, 2012 at 11:19 PM, Wei.QI qiw...@gmail.com wrote:

 @yq, didn't I ask you this question before?

 On Fri, Aug 10, 2012 at 4:48 PM, yq Zhang zhangyunq...@gmail.com wrote:
  @shiv, your code is correct go compute the base 26 number. However, this
  question is not base 26 number obviously.
 
 
 
  On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan narayan.shiv...@gmail.com
  wrote:
 
  this is similar to conversion of no in base 26.( where digits are
  a,b,c,d...z) just think it like decimal to binary conversion here base
 is
  instead 26.
 
  char Carr[26]={a,b,c...z}
  i=0;
  int arr[];
  do
  {
  arrr[i++]=n%26;
  n/=2;
  }
  while(n) ;
  for(int i=n-1;i=0;i--)
  coutCarr[a[i]];
 
  correct me if i am wrong.
  On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:
 
  Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
  aac aax, aaz, aba, abc... (Its same as excel column names). Given
 an
  integer (n), generate n-th string from the above sequence.
 
 
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652
 
  --
  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/-/Z3kYiTZi_F8J.
 
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 
  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.

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



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

Re: [algogeeks] Re: AMAZON: given col id, print col name in excel

[shady]

nope, doesnt work
even taking a simpler case like
a, b, aa, ab, ba, bb, aaa, aab, aba, abb...

using base 2 doesn't give correct results

On Mon, Aug 13, 2012 at 3:33 AM, vivek rungta vivekrungt...@gmail.comwrote:

 its base 26 but little modification in code ...
 @shiv - nice solution .

 char Carr[26]={a,b,c...z}
 i=0;
 int arr[];
 do
 {
 arrr[i++]=n%26;
 n=(n/26)-1;
 }
 while(n) ;
 for(int i=n-1;i=0;i--)
 coutCarr[a[i]];



 On Sat, Aug 11, 2012 at 9:52 PM, yq Zhang zhangyunq...@gmail.com wrote:

 No. It's not base 26 at all. Given input 26, your code will return ba,
 but the result should be aa. It's not equivalent to a number.


 On Sat, Aug 11, 2012 at 2:57 AM, shiv narayan 
 narayan.shiv...@gmail.comwrote:

 yes actually we have to print a,b,c..z instead of nos , so for that i
 have stored nos in character array  so only characters will be printed not
 nos


 On Sat, Aug 11, 2012 at 2:18 AM, yq Zhang zhangyunq...@gmail.comwrote:

 @shiv, your code is correct go compute the base 26 number. However,
 this question is not base 26 number obviously.



 On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan narayan.shiv...@gmail.com
  wrote:

 this is similar to conversion of no in base 26.( where digits are
 a,b,c,d...z) just think it like decimal to binary conversion here base is
 instead 26.

 char Carr[26]={a,b,c...z}
 i=0;
 int arr[];
 do
 {
 arrr[i++]=n%26;
 n/=2;
 }
 while(n) ;
 for(int i=n-1;i=0;i--)
 coutCarr[a[i]];

 correct me if i am wrong.
 On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:

 Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
 aac aax, aaz, aba, abc... (Its same as excel column names). Given an
 integer (n), generate n-th string from the above sequence.

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

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

 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.




 --
 Shiv Narayan Sharma
 Jt. Secretary CSI-DTU
 +919971228389
 www.jugadengg.com




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


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


  --
 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: given col id, print col name in excel

[vivek rungta]

its base 26 but little modification in code ...
@shiv - nice solution .

char Carr[26]={a,b,c...z}
i=0;
int arr[];
do
{
arrr[i++]=n%26;
n=(n/26)-1;
}
while(n) ;
for(int i=n-1;i=0;i--)
coutCarr[a[i]];



On Sat, Aug 11, 2012 at 9:52 PM, yq Zhang zhangyunq...@gmail.com wrote:

 No. It's not base 26 at all. Given input 26, your code will return ba, but
 the result should be aa. It's not equivalent to a number.


 On Sat, Aug 11, 2012 at 2:57 AM, shiv narayan 
 narayan.shiv...@gmail.comwrote:

 yes actually we have to print a,b,c..z instead of nos , so for that i
 have stored nos in character array  so only characters will be printed not
 nos


 On Sat, Aug 11, 2012 at 2:18 AM, yq Zhang zhangyunq...@gmail.com wrote:

 @shiv, your code is correct go compute the base 26 number. However, this
 question is not base 26 number obviously.



 On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan 
 narayan.shiv...@gmail.comwrote:

 this is similar to conversion of no in base 26.( where digits are
 a,b,c,d...z) just think it like decimal to binary conversion here base is
 instead 26.

 char Carr[26]={a,b,c...z}
 i=0;
 int arr[];
 do
 {
 arrr[i++]=n%26;
 n/=2;
 }
 while(n) ;
 for(int i=n-1;i=0;i--)
 coutCarr[a[i]];

 correct me if i am wrong.
 On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:

 Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
 aac aax, aaz, aba, abc... (Its same as excel column names). Given an
 integer (n), generate n-th string from the above sequence.

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

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

 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.




 --
 Shiv Narayan Sharma
 Jt. Secretary CSI-DTU
 +919971228389
 www.jugadengg.com




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


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


-- 
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: given col id, print col name in excel

[shiv narayan]

yes actually we have to print a,b,c..z instead of nos , so for that i have
stored nos in character array  so only characters will be printed not nos

On Sat, Aug 11, 2012 at 2:18 AM, yq Zhang zhangyunq...@gmail.com wrote:

 @shiv, your code is correct go compute the base 26 number. However, this
 question is not base 26 number obviously.



 On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan narayan.shiv...@gmail.comwrote:

 this is similar to conversion of no in base 26.( where digits are
 a,b,c,d...z) just think it like decimal to binary conversion here base is
 instead 26.

 char Carr[26]={a,b,c...z}
 i=0;
 int arr[];
 do
 {
 arrr[i++]=n%26;
 n/=2;
 }
 while(n) ;
 for(int i=n-1;i=0;i--)
 coutCarr[a[i]];

 correct me if i am wrong.
 On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:

 Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
 aac aax, aaz, aba, abc... (Its same as excel column names). Given an
 integer (n), generate n-th string from the above sequence.

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

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

 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.




-- 
Shiv Narayan Sharma
Jt. Secretary CSI-DTU
+919971228389
www.jugadengg.com

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

Re: [algogeeks] Re: AMAZON: given col id, print col name in excel

[yq Zhang]

No. It's not base 26 at all. Given input 26, your code will return ba, but
the result should be aa. It's not equivalent to a number.

On Sat, Aug 11, 2012 at 2:57 AM, shiv narayan narayan.shiv...@gmail.comwrote:

 yes actually we have to print a,b,c..z instead of nos , so for that i have
 stored nos in character array  so only characters will be printed not nos


 On Sat, Aug 11, 2012 at 2:18 AM, yq Zhang zhangyunq...@gmail.com wrote:

 @shiv, your code is correct go compute the base 26 number. However, this
 question is not base 26 number obviously.



 On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan 
 narayan.shiv...@gmail.comwrote:

 this is similar to conversion of no in base 26.( where digits are
 a,b,c,d...z) just think it like decimal to binary conversion here base is
 instead 26.

 char Carr[26]={a,b,c...z}
 i=0;
 int arr[];
 do
 {
 arrr[i++]=n%26;
 n/=2;
 }
 while(n) ;
 for(int i=n-1;i=0;i--)
 coutCarr[a[i]];

 correct me if i am wrong.
 On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:

 Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
 aac aax, aaz, aba, abc... (Its same as excel column names). Given an
 integer (n), generate n-th string from the above sequence.

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

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

 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.




 --
 Shiv Narayan Sharma
 Jt. Secretary CSI-DTU
 +919971228389
 www.jugadengg.com




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


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

Re: [algogeeks] Re: AMAZON: given col id, print col name in excel

[yq Zhang]

@shiv, your code is correct go compute the base 26 number. However, this
question is not base 26 number obviously.



On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan narayan.shiv...@gmail.comwrote:

 this is similar to conversion of no in base 26.( where digits are
 a,b,c,d...z) just think it like decimal to binary conversion here base is
 instead 26.

 char Carr[26]={a,b,c...z}
 i=0;
 int arr[];
 do
 {
 arrr[i++]=n%26;
 n/=2;
 }
 while(n) ;
 for(int i=n-1;i=0;i--)
 coutCarr[a[i]];

 correct me if i am wrong.
 On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:

 Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
 aac aax, aaz, aba, abc... (Its same as excel column names). Given an
 integer (n), generate n-th string from the above sequence.

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

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

 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: given col id, print col name in excel

[shiv narayan]

this is similar to conversion of no in base 26.( where digits are 
a,b,c,d...z) just think it like decimal to binary conversion here base is 
instead 26.

char Carr[26]={a,b,c...z}
i=0;
int arr[];
do
{
arrr[i++]=n%26;
n/=2;
}
while(n) ;
for(int i=n-1;i=0;i--)
coutCarr[a[i]];

correct me if i am wrong.
On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:

 Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab, 
 aac aax, aaz, aba, abc... (Its same as excel column names). Given an 
 integer (n), generate n-th string from the above sequence.  

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


-- 
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/-/Z3kYiTZi_F8J.
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] : constructing fully binary tree

[Aman Jain]

in one special case of binary tree where each internal node has 2 children;
we can construct binary tree from these pre and postorder traversals.

On Wed, Aug 8, 2012 at 12:11 PM, Navin Kumar algorithm.i...@gmail.comwrote:

 @shiv narayan: we are not going to create exact tree as original. You
 have to build full binary tree where as original tree may / may not be full
 binary tree.


 On Wed, Aug 8, 2012 at 2:31 AM, shiv narayan narayan.shiv...@gmail.comwrote:

 Preorder and postorder do not uniquely define a binary tree.
 so question is vague .

 On Sunday, 15 July 2012 01:41:15 UTC+5:30, Navin Kumar wrote:

 Given Preorder and postorder traversals of a tree. Device an algorithm
 to constuct a fully binary tree from these traversals.

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

 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


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


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

[algogeeks] Re: [Amazon] : constructing fully binary tree

[harsha]

Can u please explain the algorithm. is n't inorder always needed to 
construct a unique tree?

On Sunday, July 15, 2012 1:41:15 AM UTC+5:30, Navin Kumar wrote:

 Given Preorder and postorder traversals of a tree. Device an algorithm to 
 constuct a fully binary tree from these traversals.

-- 
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/-/oeCYjRX0MlYJ.
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] : constructing fully binary tree

[shiv narayan]

Preorder and postorder do not uniquely define a binary tree.
so question is vague .

On Sunday, 15 July 2012 01:41:15 UTC+5:30, Navin Kumar wrote:

 Given Preorder and postorder traversals of a tree. Device an algorithm to 
 constuct a fully binary tree from these traversals.

-- 
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/-/XkRghiAUWHEJ.
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] : constructing fully binary tree

[shiv narayan]

Preorder and postorder do not uniquely define a binary tree.
so question is vague .

On Sunday, 15 July 2012 01:41:15 UTC+5:30, Navin Kumar wrote:

 Given Preorder and postorder traversals of a tree. Device an algorithm to 
 constuct a fully binary tree from these traversals.

-- 
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/-/xaHfTySoo58J.
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]

[Navin Gupta]

@ankush, 
I think the worst case time complexity will be   [ (M+N) * L ]
this is beacuse, in the worst case all the 2-d arrays can probably contain 
the element.
Now searching the single 2-D array needs O ( M+N )
But since there can be L such 2-D arrays in the worst case,
Wors case TC- O[ (M+N) * L ]

-- 
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/-/4Iwl3b_WikMJ.
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]

[ankush sharma]

Hi,

I think the following approach will work.
1. As the array is sorted in all three directions, assume the 3D array to 
be a stack of rectangular arrays or 2D arrays.
Searching in a 2D array of size M*N is trivial - time complexity O(m + 
n). Provided that the 2D array is sorted, both row and column wise

2. Now the problems comes down to which 2D array to search. For this we can 
use binary search on the 3d dimension in the following way - 
- We know that if an element lies in a sorted 2D array, it value must 
lie between the top-left element arr[0][0] and bottom right element 
arr[m-1][n-1].
- Perform a binary search to find the probable rectangle (2D array) in 
which the given element lies. Let say the 3rd dimension is r. Check for the 
r/2th rectangle.
  If the top-left element and the bottom-right element of the r/2 2D 
array  element, search the lower half in the 3rd dimension.
  If the top-left element and the bottom-right element of the r/2 2D 
array  element, search the upper half in the 3rd dimension.
  If the top-left  element and the bottom-right element  element, 
this should be the probable 2D array.

3. Search for the 2D array find in the 2nd step, if element is found - 
Search is successful--:) else element doesn't exist
If no such 2D array is present as in the 2nd step, the element doesn't 
exist

Worst case complexity for an arr[l][m][n] - O(m+n)*logl 

The invariant in this approach is that for a 2D array, all its elements are 
= the previous 2D arrays. So if the minimum element of a 2D array i.e the 
top-left
element is smaller than element to be searched, there is no need to search 
for the earlier arrays. Similar is the case for greater than case. 

On Friday, July 20, 2012 11:24:08 AM UTC+5:30, Sakshi Agrawal wrote:

 How will you search an element in sorted 3D Array ?  ( Sorted in all the 3 
 directions )


-- 
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/-/XSZVSbXF2H8J.
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]

[yq Zhang]

@ankush, there can be multiple probable 2D array according to your
definition.

On Wed, Jul 25, 2012 at 7:01 AM, ankush sharma anks...@gmail.com wrote:

 Hi,

 I think the following approach will work.
 1. As the array is sorted in all three directions, assume the 3D array to
 be a stack of rectangular arrays or 2D arrays.
 Searching in a 2D array of size M*N is trivial - time complexity O(m +
 n). Provided that the 2D array is sorted, both row and column wise

 2. Now the problems comes down to which 2D array to search. For this we
 can use binary search on the 3d dimension in the following way -
 - We know that if an element lies in a sorted 2D array, it value must
 lie between the top-left element arr[0][0] and bottom right element
 arr[m-1][n-1].
 - Perform a binary search to find the probable rectangle (2D array) in
 which the given element lies. Let say the 3rd dimension is r. Check for the
 r/2th rectangle.
   If the top-left element and the bottom-right element of the r/2 2D
 array  element, search the lower half in the 3rd dimension.
   If the top-left element and the bottom-right element of the r/2 2D
 array  element, search the upper half in the 3rd dimension.
   If the top-left  element and the bottom-right element  element,
 this should be the probable 2D array.

 3. Search for the 2D array find in the 2nd step, if element is found -
 Search is successful--:) else element doesn't exist
 If no such 2D array is present as in the 2nd step, the element doesn't
 exist

 Worst case complexity for an arr[l][m][n] - O(m+n)*logl

 The invariant in this approach is that for a 2D array, all its elements
 are = the previous 2D arrays. So if the minimum element of a 2D array i.e
 the top-left
 element is smaller than element to be searched, there is no need to search
 for the earlier arrays. Similar is the case for greater than case.

 On Friday, July 20, 2012 11:24:08 AM UTC+5:30, Sakshi Agrawal wrote:

 How will you search an element in sorted 3D Array ?  ( Sorted in all the
 3 directions )

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

 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]

[deepikaanand]

every element in 3D array can be written in the form of *(*(*(a+i)+j)+k) = 
a[i][j][k]
ele = required element to be searched for 
say M = number of 3D matrices
R = number of row
C = number of col

First find the most probable matrix in which the element might be present
fix j = R-1
fix k = C-1 //as index starts from 0 
max = *(*(*(a+i)+j)+k) //which is a[i][R-1][C-1]
min = ***(a+i) //which is a[i][0][0]
where is varies from 0 to M-1 

now if ele =min  ele = max
then index = i; //index = required matrix number 
 Now search as u shall search in 2D matrix keeping i constant and varying j 
and k

-- 
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/-/Bo3X7D2XPPQJ.
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 support engineer

[Tushar]

this is interview street
post here freely

all the best


On Monday, 23 July 2012 19:40:12 UTC+5:30, rahul sharma wrote:

 Guys i am having amazon support engg. test tonyt...90 min 27 questions 
 mcq...plz tell how to prepare and wats dis profyl???reply asap..and sory 
 for posting it in algogeeks as i need quick response.waiting for +ve 
 response soon...
 thnx


-- 
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/-/qytHyFXxaSsJ.
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(in)
 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.

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

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 algog...@gmail.comwrote:

 @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 jatinseth...@gmail.com 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(in)
 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/-/r8KWdIC96ckJ.
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(in)
 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

[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 jatinseth...@gmail.com 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(in)
 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.

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 algog...@gmail.com 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 jatinseth...@gmail.com 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(in)
 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]

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 algog...@gmail.com 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 jatinseth...@gmail.com 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(in)
 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

[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 algog...@gmail.com 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 jatinseth...@gmail.com 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(in)
 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

[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 algog...@gmail.com 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 jatinseth...@gmail.com 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(in)
 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/-/n6oN4OI__CsJ.
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

[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 jatinseth...@gmail.com 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 algog...@gmail.com 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 jatinseth...@gmail.com 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(in)
 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-GSdigJhttps://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 algogeeks%2bunsubscr...@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@**
 googlegroups.com algogeeks%2bunsubscr...@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.




 --
 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+unsubscribe@**
 googlegroups.com algogeeks%2bunsubscr...@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 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.


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

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 jatinseth...@gmail.com 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 algog...@gmail.com 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 jatinseth...@gmail.com 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(in)
 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-GSdigJhttps://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 algogeeks%2bunsubscr...@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@**
 googlegroups.com algogeeks%2bunsubscr...@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.




 --
 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+unsubscribe@**
 googlegroups.com algogeeks%2bunsubscr...@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 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.


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

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 jatinseth...@gmail.com 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 algog...@gmail.com 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 jatinseth...@gmail.com 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(in)
 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-GSdigJhttps://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 algogeeks%2bunsubscr...@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@**
 googlegroups.com algogeeks%2bunsubscr...@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.




 --
 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+unsubscribe@**
 googlegroups.com algogeeks%2bunsubscr...@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 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.


 --
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group

[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

[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 ] Finding Sub segment

[rspr]

just have a look on segment tree ( u can found good study material on 
segment tree at topcoder algorithm tutorial)

On Monday, 25 June 2012 18:13:50 UTC+5:30, Navin Kumar wrote:

 please provide some good data structure  to solve this problem:

 http://www.careercup.com/question?id=14062676


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

[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

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

Re: [algogeeks] Re: Amazon Interview Question

[Amol Sharma]

+1 for trie..
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/






On Fri, Jun 15, 2012 at 5:21 PM, enchantress elaenjoy...@gmail.com 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.

Re: [algogeeks] Re: amazon interview questions

[Ashish Goel]

Hassan geke should not be a valid string. The question states  which have
the same substring following it  so here e follows e. There is no
precondition that it has to follow immediate.

Utsav: can you clarify?


Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote:

 yes It's valid, cuz  it doesn't have any repeated substring next together


 On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote:

 is geke is a invalid strng?


 On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote:

 Ashish:

 the algorithm passes over string and check if there is any substring
 with len=1 is repeated or not. if not, tries for substring with len 2,...
 and so on.
 max length of substring which can be repeated can be at most  N/2.


 Regards,


 On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.com wrote:

 The problem suggests that a character can't be more than once present
 and thereby it can be done by just having s bitmap and if a char repeats,
 any longer repeating substring will have those char repeated atleast twice,
 hence O(n) solution.


 Also, Hasaan: how is your algo O(n2) for for-while-for chain?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.com wrote:

 Hassan, can you explain your algo?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared 
 hmonfa...@gmail.comwrote:

 for



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


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




 --
 Regards

 Lomash Goyal

 *
 *


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

[atul anand]

nope geke is valid string..

here is the link from where question was taken

http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker

On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote:

 Hassan geke should not be a valid string. The question states  which
 have the same substring following it  so here e follows e. There is no
 precondition that it has to follow immediate.

 Utsav: can you clarify?


 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote:

 yes It's valid, cuz  it doesn't have any repeated substring next together


 On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote:

 is geke is a invalid strng?


 On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote:

 Ashish:

 the algorithm passes over string and check if there is any substring
 with len=1 is repeated or not. if not, tries for substring with len 2,...
 and so on.
 max length of substring which can be repeated can be at most  N/2.


 Regards,


 On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.com wrote:

 The problem suggests that a character can't be more than once present
 and thereby it can be done by just having s bitmap and if a char repeats,
 any longer repeating substring will have those char repeated atleast 
 twice,
 hence O(n) solution.


 Also, Hasaan: how is your algo O(n2) for for-while-for chain?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote:

 Hassan, can you explain your algo?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.com
  wrote:

 for



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


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




 --
 Regards

 Lomash Goyal

 *
 *


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


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


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


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

Re: [algogeeks] Re: amazon interview questions

[Hassan Monfared]

geke is valid. BTW if you changeif(i=len)  toif(i0) my code
outputs geke is invalid.( what you desired)
if geke is invalid regarding to the question, then you can achieve the
answer in nLogn by sorting strings :s[0..n-1], s[1..n-1],s[n-1..n-1]
and comparing adjacent members.
Regards


On Wed, Jun 6, 2012 at 11:52 AM, atul anand atul.87fri...@gmail.com wrote:

 nope geke is valid string..

 here is the link from where question was taken


 http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker


 On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote:

 Hassan geke should not be a valid string. The question states  which
 have the same substring following it  so here e follows e. There is no
 precondition that it has to follow immediate.

 Utsav: can you clarify?


 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote:

 yes It's valid, cuz  it doesn't have any repeated substring next together


 On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote:

 is geke is a invalid strng?


 On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared 
 hmonfa...@gmail.comwrote:

 Ashish:

 the algorithm passes over string and check if there is any substring
 with len=1 is repeated or not. if not, tries for substring with len 2,...
 and so on.
 max length of substring which can be repeated can be at most  N/2.


 Regards,


 On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.comwrote:

 The problem suggests that a character can't be more than once present
 and thereby it can be done by just having s bitmap and if a char repeats,
 any longer repeating substring will have those char repeated atleast 
 twice,
 hence O(n) solution.


 Also, Hasaan: how is your algo O(n2) for for-while-for chain?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote:

 Hassan, can you explain your algo?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared 
 hmonfa...@gmail.com wrote:

 for



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


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




 --
 Regards

 Lomash Goyal

 *
 *


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


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


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


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


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

Re: [algogeeks] Re: amazon interview questions

[Darpan Baweja]

@ashish:- geke is valid as repeated substrings should be immediate.

On Wed, Jun 6, 2012 at 1:44 PM, Hassan Monfared hmonfa...@gmail.com wrote:

 geke is valid. BTW if you changeif(i=len)  toif(i0) my code
 outputs geke is invalid.( what you desired)
 if geke is invalid regarding to the question, then you can achieve the
 answer in nLogn by sorting strings :s[0..n-1], s[1..n-1],s[n-1..n-1]
 and comparing adjacent members.
 Regards



 On Wed, Jun 6, 2012 at 11:52 AM, atul anand atul.87fri...@gmail.comwrote:

 nope geke is valid string..

 here is the link from where question was taken


 http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker


 On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote:

 Hassan geke should not be a valid string. The question states  which
 have the same substring following it  so here e follows e. There is no
 precondition that it has to follow immediate.

 Utsav: can you clarify?


 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote:

 yes It's valid, cuz  it doesn't have any repeated substring next
 together


 On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote:

 is geke is a invalid strng?


 On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared 
 hmonfa...@gmail.comwrote:

 Ashish:

 the algorithm passes over string and check if there is any substring
 with len=1 is repeated or not. if not, tries for substring with len 2,...
 and so on.
 max length of substring which can be repeated can be at most  N/2.


 Regards,


 On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.comwrote:

 The problem suggests that a character can't be more than once
 present and thereby it can be done by just having s bitmap and if a char
 repeats, any longer repeating substring will have those char repeated
 atleast twice, hence O(n) solution.


 Also, Hasaan: how is your algo O(n2) for for-while-for chain?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote:

 Hassan, can you explain your algo?

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared 
 hmonfa...@gmail.com wrote:

 for



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


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




 --
 Regards

 Lomash Goyal

 *
 *


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


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


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


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


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




-- 
*DARPAN BAWEJA*
*3rd year, I.T*
*MNNIT Allahabad*

-- 
You received