Re: [algogeeks] Constant time solution needed

[adarsh kumar]

Sum of the integers meaning? Do you mind giving an example test case?

regards.

On Sat, Aug 11, 2012 at 7:10 PM, Srividhya  wrote:

> hi all:)
>
> The coordinates of a rectangle will be specified. there is a matrix of
> integers. yo should find the sum of the integers that fall in the region
> specified by the  coordinates .
>
> The solution to be in constant time .
>
> --
> 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/-/qHSmXBshmS4J.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] merging

[adarsh kumar]

Cos, if they are stored as a vector of strings like a1, b1, etc. then u can
use insertion sort like technique.
Insert bi and ci between ai and a(i+1), for i=1,2,3n.
This can be done simply by modifyin insertion  sort code. Pl let me know in
case of any flaw! cos it seems to be so simple this way.

On Mon, Aug 6, 2012 at 1:02 AM, adarsh kumar  wrote:

> vector*
>
>
> On Mon, Aug 6, 2012 at 1:02 AM, adarsh kumar  wrote:
>
>>
>> Can you care to explain as to how exactly the elements are stored? Is it
>> a vactor of strings??
>>
>> On Mon, Aug 6, 2012 at 12:32 AM, Navin Kumar wrote:
>>
>>> Actually i wanted to do it inplace. Using extra space it is much  easier
>>> problem.
>>>
>>>
>>> On Mon, Aug 6, 2012 at 12:27 AM, payal gupta wrote:
>>>
>>>> int merge(int arr[],int n)
>>>> {
>>>> int l=0;
>>>> int j=(n/3);
>>>> int k=2*(n/3);
>>>> int *a=(int*)malloc(sizeof(int)*n);
>>>> for(int i=0;i>>> {
>>>> a[l++]=arr[i];
>>>> a[l++]=arr[j++];
>>>> a[l++]=arr[k++];
>>>> }
>>>> for(int i=0;i>>> arr[i]=a[i];
>>>> free(a);
>>>> }
>>>> cud be dun be dun recursively also to minimize d space complexity...
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> On Sat, Aug 4, 2012 at 8:20 AM, Navin Kumar 
>>>> wrote:
>>>>
>>>>> In given array of elements like 
>>>>> [a1,a2,a3,..an,b1,b2,b3,..bn,c**1,c2,c3,...cn]
>>>>> .Write an efficient program to merge them like
>>>>> [a1,b1,c1,a2,b2,c2,...an,bn,cn**].
>>>>>
>>>>> --
>>>>> 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/-/gVCyxQV1IhAJ.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from 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] merging

[adarsh kumar]

vector*

On Mon, Aug 6, 2012 at 1:02 AM, adarsh kumar  wrote:

>
> Can you care to explain as to how exactly the elements are stored? Is it a
> vactor of strings??
>
> On Mon, Aug 6, 2012 at 12:32 AM, Navin Kumar wrote:
>
>> Actually i wanted to do it inplace. Using extra space it is much  easier
>> problem.
>>
>>
>> On Mon, Aug 6, 2012 at 12:27 AM, payal gupta  wrote:
>>
>>> int merge(int arr[],int n)
>>> {
>>> int l=0;
>>> int j=(n/3);
>>> int k=2*(n/3);
>>> int *a=(int*)malloc(sizeof(int)*n);
>>> for(int i=0;i>> {
>>> a[l++]=arr[i];
>>> a[l++]=arr[j++];
>>> a[l++]=arr[k++];
>>> }
>>> for(int i=0;i>> arr[i]=a[i];
>>> free(a);
>>> }
>>> cud be dun be dun recursively also to minimize d space complexity...
>>>
>>>
>>>
>>>
>>>
>>> On Sat, Aug 4, 2012 at 8:20 AM, Navin Kumar wrote:
>>>
>>>> In given array of elements like 
>>>> [a1,a2,a3,..an,b1,b2,b3,..bn,c**1,c2,c3,...cn]
>>>> .Write an efficient program to merge them like
>>>> [a1,b1,c1,a2,b2,c2,...an,bn,cn**].
>>>>
>>>> --
>>>> 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/-/gVCyxQV1IhAJ.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from 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] merging

[adarsh kumar]

Can you care to explain as to how exactly the elements are stored? Is it a
vactor of strings??
On Mon, Aug 6, 2012 at 12:32 AM, Navin Kumar wrote:

> Actually i wanted to do it inplace. Using extra space it is much  easier
> problem.
>
>
> On Mon, Aug 6, 2012 at 12:27 AM, payal gupta  wrote:
>
>> int merge(int arr[],int n)
>> {
>> int l=0;
>> int j=(n/3);
>> int k=2*(n/3);
>> int *a=(int*)malloc(sizeof(int)*n);
>> for(int i=0;i> {
>> a[l++]=arr[i];
>> a[l++]=arr[j++];
>> a[l++]=arr[k++];
>> }
>> for(int i=0;i> arr[i]=a[i];
>> free(a);
>> }
>> cud be dun be dun recursively also to minimize d space complexity...
>>
>>
>>
>>
>>
>> On Sat, Aug 4, 2012 at 8:20 AM, Navin Kumar wrote:
>>
>>> In given array of elements like 
>>> [a1,a2,a3,..an,b1,b2,b3,..bn,c**1,c2,c3,...cn]
>>> .Write an efficient program to merge them like
>>> [a1,b1,c1,a2,b2,c2,...an,bn,cn**].
>>>
>>> --
>>> 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/-/gVCyxQV1IhAJ.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] Appropriate data structure

[adarsh kumar]

For using a stack in order to achieve O(n) time, we can modify push and pop
as follows(assuming we want max):
While pushing, compare the top of the stack with the element to be
pushed(say x). If x>top, just push normally. Else, pop elements until
top>x. Keep an eye on the border cases as well. Thus top will always be
containing the maximum, which can be retrieved obviously in O(1) time.
Similar algo  for pop can be formulated.
regards.

On Tue, Jul 17, 2012 at 9:19 AM, Tushar  wrote:

> can you please elaborate on usage of stack to do it in O(1)?
>
>
>  --
> 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/-/8jTvBVdzsmYJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Appropriate data structure

[adarsh kumar]

Oh ya sorry. I thought we have to retrieve kth min and max, in which case
heap can be used.

Here, we can either use stack or map. Map can be from a date(which
increases by 1 daily) to a value, as only one value is received per day.
Keeping in mind memory constraints, stack is better. Map is an otherwise
safe solution.
regards.

On Sun, Jul 15, 2012 at 6:24 PM, Navin Kumar wrote:

> I think stack would solve the purpose. please comment.
>
>
> On Sun, Jul 15, 2012 at 5:42 PM, enchantress wrote:
>
>> It says K days if you keep heap the order of values gets disturbed. How
>> are last k values accessed then?
>>
>>
>> On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote:
>>>
>>> Min or max heap accordingly. This will do the job in O(log n) time.
>>>
>>> On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar 
>>> wrote:
>>>
>>>> A set of integer values are being received (1 per day). Store these
>>>> values and at any given time, retrieve the min and max value over the last
>>>> k days. What data structures would you use for storing and retrieving ?
>>>>
>>>> --
>>>> 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/-/2AhV1Xn3jD8J<https://groups.google.com/d/msg/algogeeks/-/2AhV1Xn3jD8J>
>>>> .
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>>> googlegroups.com .
>>>> For more options, visit this group at http://groups.google.com/**
>>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>.
>>>>
>>>
>>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/peWhqjKLIH8J.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Appropriate data structure

[adarsh kumar]

Min or max heap accordingly. This will do the job in O(log n) time.

On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar wrote:

> A set of integer values are being received (1 per day). Store these values
> and at any given time, retrieve the min and max value over the last k days.
> What data structures would you use for storing and retrieving ?
>
> --
> 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/-/2AhV1Xn3jD8J.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[adarsh kumar]

+1.

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

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


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

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

RE: [algogeeks] Re: Amazon Interview Question

[adarsh kumar]

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

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

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

> @jatin:
> Your first method may be proved wrong.
>
> Here is a counter test case:
>
> Suppose the array is:
>
> 27 729 19683 2 3 3 27 3 81 729
>
> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice,
> 27 occurs twice, and 3 occurs thrice.
>
> You are supposed to return 3
> But as per your method, the product will be computed as
> 729*19683*2*3*3*27*3*81*729=product(say)
>
> Upon traversing the second time, it will return 27, as product%(27*27*27)
> is equal to zero!
>
> regards.
>
>
>
> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>
>> Or we can make a BST from array list in o(n)
>> then traverse it inorder-o(logn)
>>
>> but this solution requires o(logn) space though.
>>
>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>
>>>
>>> 1)Find product of the array and store it in say prod  o(n) and o(1)
>>> 2)now traverse the array and check if
>>>
>>> static int i;
>>> tag:
>>> while(i>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>> break;
>>> //this may be the required element
>>> //e-o-while
>>>
>>> //now check is this is the element that is occuring three times o(n)
>>> if(number is not the required one then)
>>> goto tag;
>>>
>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>
>>>> Given an array of integers where some numbers repeat once, some numbers
>>>> repeat twice and only one number repeats thrice, how do you find the number
>>>> that gets repeated 3 times?
>>>>
>>>> Does this problem have an O(n) time and O(1) space solution?
>>>> No hashmaps please!
>>>>
>>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Vindhya Chhabra



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

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

Re: [algogeeks] Re: Amazon Interview Question

[adarsh kumar]

@jatin:
Your first method may be proved wrong.

Here is a counter test case:

Suppose the array is:

27 729 19683 2 3 3 27 3 81 729

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

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

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

regards.



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

> Or we can make a BST from array list in o(n)
> then traverse it inorder-o(logn)
>
> but this solution requires o(logn) space though.
>
> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>
>>
>> 1)Find product of the array and store it in say prod  o(n) and o(1)
>> 2)now traverse the array and check if
>>
>> static int i;
>> tag:
>> while(i> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>> break;
>> //this may be the required element
>> //e-o-while
>>
>> //now check is this is the element that is occuring three times o(n)
>> if(number is not the required one then)
>> goto tag;
>>
>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>
>>> Given an array of integers where some numbers repeat once, some numbers
>>> repeat twice and only one number repeats thrice, how do you find the number
>>> that gets repeated 3 times?
>>>
>>> Does this problem have an O(n) time and O(1) space solution?
>>> No hashmaps please!
>>>
>> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Max sum circular array

[adarsh kumar]

This is similar to maximum sum contiguous subarray problem. Consider the
circular array as a normal array, except that once you reach the end of the
array, if the sum found upto that element(using Kandane's algo, refer Wiki)
is negative, then try including elements from the beginning of the
array(circular fashion), until you find a sum that is greater. Keeping
track of the sum is obvious necessity. Finally return the sum.



On Tue, Jul 10, 2012 at 10:58 AM, deepikaanand wrote:

> What is best approach to find max sum in a circular 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.
>
>

-- 
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] C o/p

[adarsh kumar]

Sorry, its 6/6 and not 6/5,

regds.

On Sun, Jul 8, 2012 at 10:39 PM, adarsh kumar  wrote:

> Firstly, this is ambiguous and expressions with multiple
> increment/decrement operators will get executed according to the compiler.
>
> Even if you consider the normal way, as we(humans) percieve it, it will be
> evaluated as
> (++i)/(i++), which is 6/5, which is 1.
>
> Simple!
>
>
>
> On Sun, Jul 8, 2012 at 10:23 PM, rahul sharma wrote:
>
>> int i=5;
>> i=++i/i++;
>> print i;
>>
>>
>> i=1
>>
>> how?
>>
>> --
>> 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] C o/p

[adarsh kumar]

Firstly, this is ambiguous and expressions with multiple
increment/decrement operators will get executed according to the compiler.

Even if you consider the normal way, as we(humans) percieve it, it will be
evaluated as
(++i)/(i++), which is 6/5, which is 1.

Simple!



On Sun, Jul 8, 2012 at 10:23 PM, rahul sharma wrote:

> int i=5;
> i=++i/i++;
> print i;
>
>
> i=1
>
> how?
>
> --
> 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] Finding intersection of 2 linked lists

[adarsh kumar]

Hope the following will be of help:
http://www.geeksforgeeks.org/archives/18615

regds.

On Thu, Jul 5, 2012 at 4:32 PM, Abhishek Sharma wrote:

> @nishant, you wrote "until both the distance becomes equal".Which
> distances ? Could you please elaborate ?
>
>
> On Thu, Jul 5, 2012 at 12:52 PM, Ashish Goel  wrote:
>
>> struct node* intersection( struct node *pL1, struct node* pL2)
>> {
>>if ((!pL1) || (!pl2)) return NULL;
>>struct node * pL3 = NULL;
>>struct node* pL3Tail = NULL;
>>while(pL1)&&(pL2) {
>> if (pL1->data< pL2->data) pL1=pL1->next;
>> else if  (pL1->data > pL2->data) pL2=pL2->next;
>> else {
>>struct node *pNew = (struct node*)malloc(sizeof(struct node));
>>if !pNew return NULL; //scary
>>pNew->data = pL1->data; pNew->next = NULL;
>>if ( !pL3) pL3= pNew;
>>else pL3Tail->next = pNew;
>>pL3Tail = pNew;
>>}
>>return pL3;
>> }
>>
>>
>>
>>
>> }
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>> On Wed, Jul 4, 2012 at 10:41 PM, Abhi  wrote:
>>
>>> Any efficient algorithm to find intersection of two linked
>>> lists.Example:
>>> Linked List 1)  1 -> 2 -> 3 -> 4 -> 5 -> 6
>>> Linked List 2)  3 -> 4 -> 5
>>>
>>> Intersection 4 -> 5 -> 6
>>>
>>> --
>>> 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/-/-8_lnGA-ZhgJ.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>>
>
>
>
> --
> Abhishek Sharma
> Under-Graduate Student,
> PEC University of Technology
>
>  --
> 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] Amazon Interview Question

[adarsh kumar]

Have answered inline:
Q1) Given a newspaper and a set of ‘l’ words, give an efficient
algorithm to find the ‘l’ words in the newspaper.

Trivial hash-dictionary search operation. Takes O(m*l), where m=length
of maximum length word in the set l.

Q2) Find the next higher number in set of permutations of a given number.

Sorting and just returning next element, takes O(nlogn).
Hashing takes O(n). Just iterate through the list, and as and when you
encounter a number, check if its a permuation of the given number. If
yes, update min(a variable thats used to keep track of the minimum
found upto that element), else just pass that element simply. Finally,
return min.

Q3) Given preorder of a BST, find if each non-leaf node has just one
child or not. To be done in linear time.

If the word non-leaf node is strictly considered, the root should also
be included. Thus, traverse the given preorder of the BST, and in case
any violation happens, the answer is no, otherwise yes. Violation
meaning, if you pass a node that is less than the root(which will
subsequently be updated to the current node as you iterate through the
loop), you should never encounter a value that is greater than the
root(or, again, any subsequent node encountered).


On 7/4/12, Decipher  wrote:
> Q1) Given a newspaper and a set of ‘l’ words, give an efficient algorithm
> to find the ‘l’ words in the newspaper.
>
> Q2) Find the next higher number in set of permutations of a given number.
>
> Q3) Given preorder of a BST, find if each non-leaf node has just one child
> or not. To be done in linear time.
>
> Q4) Given a dictionary of words, two APIs
> Is_word(string)
> Is_prefix(string)
> And a NxN matrix with each postion consisting of a character. If from any
> position (i,j) you can move
> in any of the four directions, find out the all the valid words that can be
>
> formed in the matrix.
> (looping is not allowed, i.e. for forming a word position if you start from
>
> (i,j) and move to (i-1,j) then
> from this position you cannot go back to (i,j))
>
> Q5) Given that there are n players and each one of them has played exactly
> one game with every
> other player. Also given is an API that tells whether player ‘a’ won or
> lost to player ‘b’, where ‘a’ and
> ‘b’ could be any of the players. Arrange the n players in a length n array
> such that player at position
> ‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’.
>
> --
> 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/-/LzG-OrtjDmoJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] serialize a binary tree

[adarsh kumar]

Serialisation meaning? Numbering the nodes. Any specific order, or as
in level order??

On 7/4/12, Ashish Goel  wrote:
> a] How would you serialize a binary tree in a file(improve it)
> b] serialization that you have chosen, write a code to reconstruct the tree
> 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 post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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]

[adarsh kumar]

l-values(left, literal meaning) appear on the lhs of a statement, and
r-values vice versa. Essentially, l-values are identifiers. The memory
location that will be thereby allocated can vary for r-values. Put in
short, all l-values are r-values but not all r-values are l-values.

And ++x++, will cause a compiler error saying "non-lvalue in increment", if
x is predefined. This means lvalues cannot be modified as such, like const
ones.
On Fri, Jun 29, 2012 at 4:28 PM, vindhya chhabra
wrote:

> please someone explain lvalue and rvalue with example...
> for llvalue..please explain ++x++ also..
> thanks.
>
> --
> 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.

[algogeeks] Switch doubt in C

[adarsh kumar]

Doubt, very trivial though:
#include
int main()
{
int x=3;
switch(x)
{
 case 1:
x=1;
break;
 case 2:
x=2;
break;
 case 3:
x=3;
break;
 default:
 x=0;
 break;
 case 4:
x=4;
break;
}
printf("%d",x)
return 0;
}
gives an output of 3. But,
#include
using namespace std;
int main()
{
int x=3;
switch(x)
{
 case 1:
x=1;
 case 2:
x=2;
 case 3:
x=3;
 default:
 x=0;
 case 4:
x=4;
}
   printf("%d",x);
getch();
return 0;
}
gives an output of 4.
My doubt is, in spite of the missing break statements in the second case,
how will it enter case 4, as it should check if x=4 before doing that,
which is not true.

-- 
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] MS Question: Segregrate positive and negative nos in array without changing order

[adarsh kumar]

Quick sort partition routine variation.

On Fri, Jun 29, 2012 at 3:06 PM, Ravi Ranjan wrote:

> one can modify dutch national flag algo for two colors(2 types positive n
> negative)
>
>  --
> 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] Is max distance between two leaves(diameter) in a tree is equal to max distance between any two node in that tree??

[adarsh kumar]

In general, diameter of a tree is defined as the maximum distance between
any 2 nodes in the tree. So, assuming h(x) is height of x(function), and
d(x) is diameter of x(function), where x is any general node of the tree,
d(root)=max((h(root->left)+h(root->right)+1),max(d(root->left),d(root->right))).

This gives diameter of the tree!


On Mon, Jun 25, 2012 at 2:43 PM, Mohit Khanna <
mohitkhanna3vinfin...@gmail.com> wrote:

> What would be the diameter in case of a left skewed or right skewed tree?
>
>
>
> On Mon, Jun 25, 2012 at 12:48 PM, atul anand wrote:
>
>> consider a case where tree is right skewed or left skewed , in dat case
>> max distance b/w two node found are root and leftmost or rightmost
>> node(left  or right skewed) . so its not alwayzz true
>>
>> On Sun, Jun 24, 2012 at 5:08 PM, Navin Kumar wrote:
>>
>>>
>>>  --
>>> 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/-/xM3mGdcfvi4J.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] Find peak element in log(n)

[adarsh kumar]

ahh yes, as prakhar says, if the array is bitonic, my approach will work
for O(log n).

On Sun, Jun 24, 2012 at 1:57 AM, Prakhar Jain  wrote:

> I think it can't be done in O(log n) as per given problem constraints.
> It can be done in O(log n) if additional information that "array is
> bitonic" is given.
>
> --
> Prakhar Jain
> IIIT Allahabad
> B.Tech IT 3rd Year
> Mob no: +91 9454992196
> E-mail: rit2009...@iiita.ac.in
>   jprakha...@gmail.com
>
>
>
> On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh 
> wrote:
>
>> @adarsh kumar
>>
>> are u sure it's worst case will be O (log n) ??
>> i think iff array is fully sorted O(n) will be required to say "NO
>> such element present"
>>
>> On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar  wrote:
>> > This is a variation of binary search, the difference being that we have
>> to
>> > search for an element that is greater than its immediate left one and
>> lesser
>> > than its immediate right one. Just implement binary search with these
>> > additional constraints, thereby giving O(log n).
>> > In case of any difficulty/error, let me know.
>> >
>> > On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared 
>> > wrote:
>> >>
>> >> Given an array of integers find a peak element of array in log(n) time.
>> >> for example if A={3,4,6,5,10} then peak element is 6  ( 6>5 & 6>4 ).
>> >>
>> >> Regards.
>> >>
>> >> --
>> >> 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/-/AQI6ahWgyOIJ.
>> >> To post to this group, send email to algogeeks@googlegroups.com.
>> >> To unsubscribe from 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] Find peak element in log(n)

[adarsh kumar]

This is a variation of binary search, the difference being that we have to
search for an element that is greater than its immediate left one and
lesser than its immediate right one. Just implement binary search with
these additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.

On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared wrote:

> Given an array of integers find a peak element of array in log(n) time.
> for example if A={3,4,6,5,10} then peak element is 6  ( 6>5 & 6>4 ).
>
> Regards.
>
> --
> 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/-/AQI6ahWgyOIJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Double Linked List Represented With Single Linked List

[adarsh kumar]

Simple!
Just traverse the doubly linked list and keep track of next and previous of
each node, and do XOR and save the result in a new pointer, what according
to you is "np".
Be careful about boundary cases, i.e head and tail, though.

On Wed, Jun 20, 2012 at 5:16 PM, Krishna Kishore
wrote:

> Explain how to implement doubly linked lists using only one pointer value*np[x
> *] per item instead of the usual two (next and prev). Assume that all
> pointer values can be interpreted as
> k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],* the
> k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented
> by 0.) Be sure to describe what information is needed to access the head of
> the list. Show how to implement the SEARCH, INSERT, and DELETE operations
> on such a list. Also show how to reverse such a list in O(1) time.
>
> This is the Question in the Book "*Introduction To Algorithms" *By CORMEN
> ( MIT Press ) Page Number : 209 , Problem No: 10.2-8.
>
> Thanks in Advance.
>
> --
> 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/-/Uj1E8KXljAQJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Directi question-centre of the tree

[adarsh kumar]

As you traverse along and find the diameter of the tree, keep track of the
number of nodes thereby traversed. Let that be equal to n.
Now, centre is the node corresponding to floor((n+1)/2).

On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey <
nishant.bits.me...@gmail.com> wrote:

> I am asking again .. can any one please suggest better method for getting
> the median on the longest path of the tree ..
> efficient method .
>
>
> On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey <
> nishant.bits.me...@gmail.com> wrote:
>
>>
>> for getting diameter we can simply add the max height of left subtree and
>> max height of the right sub tree .
>>
>> the main issue is how efficiently we find median on that longest path to
>> get the center of the tree .
>> can any bdy sugest optimized algo for that ?
>>
>>
>> On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey <
>> rajesh.pandey.i...@gmail.com> wrote:
>>
>>> I found it in some paper ;)
>>>
>>>  Diameter and center
>>> De nition 4. The diameter of tree is the length of the longest path.
>>> De nition 5. A center is a vertex v such that the longest path from v to
>>> a leaf is minimal
>>> over all vertices in the tree.Tree center(s) can be found using simple
>>> algorithm.
>>> Algorithm 1. (Centers of tree)
>>> 1: Choose a random root r.
>>> 2: Find a vertex v1 | the farthest form r.
>>> 3: Find a vertex v2 | the farthest form v1.
>>> 4: Diameter is a length of path from v1 to v2.
>>> 5: Center is a median element(s) of path from v1 to v2.
>>>
>>> This is O(n) algorithm. It is clear that we can't determine tree
>>> isomorphism faster
>>> than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism
>>> we can also
>>> obtain O(f(n)) algorithm for ordinary trees.
>>>
>>> On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote:

 I think this algorithm is used for calculating poset in graph.

 On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh 
 wrote:

> + 1 for DK's solution. Is that a standard algorithm coz I feel like I
> have heard it somewhere ??
>
>
> On Mon, Aug 8, 2011 at 1:37 AM, DK  wrote:
>
>> @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3).
>> Could you please state how you can use the traversals directly to get
>> the center? (And prove your correctness too?)
>>
>> The solution given by Wladimir (& expanded upon by me) is O(N) and
>> uses (somewhat) the inverse of a BFS as a traversal.
>>
>> --
>> DK
>>
>> http://twitter.com/divyekapoor
>> http://gplus.to/divyekapoor
>> http://www.divye.in
>>
>> --
>> 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/-/HnMOZtOrkqwJ.
>>
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to algogeeks+unsubscribe@*
>> *googlegroups.com .
>> For more options, visit this group at http://groups.google.com/**
>> group/algogeeks?hl=en
>> .
>>
>
>
>
> --
> Hemesh singh
>
> --
> 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 .
> 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/-/BWplK7bCatMJ.
>>>
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Cheers,
>>
>> Nishant Pandey |Specialist Tools Development  |  
>> npan...@google.com |
>> +91-9911258345
>>
>>
>>
>
>
> --
> Cheers,
>
> Nishant Pandey |Specialist Tools Development  |  
> npan...@google.com |
> +91-9911258345
>
>
>  --
> 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,

Re: [algogeeks] Re: Microsoft question

[adarsh kumar]

This can be done using the concept of median of medians, wherein we can
achieve linear time complexity in the worst case.
This is a concept used in parallel algorithms too, check it out.

On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan wrote:

> @enchantress : This problem can be solved using quicksort in O(nlogn). No
> need to go for selection sort.
> But O(n) solution is needed.
>
>
> On Mon, Jun 18, 2012 at 2:50 PM, enchantress wrote:
>
>>
>> Hi all,
>> A variation of selection sort can be used which takes O(nk) time.
>>
>> for i 1 to k
>>   min_index = i
>>   for j i+1 to n
>>  if a[j] < a[min_index]
>> min_index = j
>>   swap(a[i],a[min_index])
>>
>> required element : a[k]
>>
>> On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote:
>>
>>> Give an array of unsorted elements, find the kth smallest element in the
>>> array.
>>>
>>> The expected time complexity is O(n) and no extra memory space should be
>>> used.
>>>
>>> Quickselect algorithm can be used to obtain the solution. Can anyone
>>> explain how quickselect works?
>>>
>>  --
>> 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/-/FABBRabzVqMJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] I need

[adarsh kumar]

This is typical knapsack problem.

On Mon, Jun 18, 2012 at 10:33 AM, Rituraj  wrote:

> Hi,
> I am trying to solve this problem.
> http://www.spoj.pl/problems/SCUBADIV/
>  But I am getting a lot of WA!
>
> Any good logic(solution)  to solve the problem?
> Thanks in advance for your reply.
>
> --
> 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/-/WOiAgraJqi8J.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] adarsh kumar wants to chat

[adarsh kumar]

---

adarsh kumar wants to stay in better touch using some of Google's coolest new
products.

If you already have Gmail or Google Talk, visit:
http://mail.google.com/mail/b-838f0088c8-7ce2f0cfbf-whddt6Y3xfr109-a6qqOkRZmhu0
You'll need to click this link to be able to chat with adarsh kumar.

To get Gmail - a free email account from Google with over 7,500 megabytes of
storage - and chat with adarsh kumar, visit:
http://mail.google.com/mail/a-838f0088c8-7ce2f0cfbf-whddt6Y3xfr109-a6qqOkRZmhu0

Gmail offers:
- Instant messaging right inside Gmail
- Powerful spam protection
- Built-in search for finding your messages and a helpful way of organizing
  emails into "conversations"
- No pop-up ads or untargeted banners - just text ads and related information
  that are relevant to the content of your messages

All this, and it's yours for free. But wait, there's more! By opening a Gmail
account, you also get access to Google Talk, Google's instant messaging
service:

http://www.google.com/talk/

Google Talk offers:
- Web-based chat that you can use anywhere, without a download
- A contact list that's synchronized with your Gmail account
- Free, high quality PC-to-PC voice calls when you download the Google Talk
  client

We're working hard to add new features and make improvements, so we might also
ask for your comments and suggestions periodically. We appreciate your help in
making our products even better!

Thanks,
The Google Team

To learn more about Gmail and Google Talk, visit:
http://mail.google.com/mail/help/about.html
http://www.google.com/talk/about.html

(If clicking the URLs in this message does not work, copy and paste them into
the address bar of your browser).

-- 
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] Partition the array with equal average

[adarsh kumar]

You can reduce this problem to the sum-subset
problem
.

Let A be the array. Compute S = A[0] + ... + A[N-1], where N is the length
of A. For k from1 to N-1, let T_k = S * k / N. If T_k is an integer, then
find a subset of A of size k that sums to T_k. If you can do this, then
you're done. If you cannot do this for any k, then no such partitioning
exists.

On Fri, May 18, 2012 at 12:10 PM, Prem Krishna Chettri
wrote:

> I guess this is Subset minimization problem's Modification..
>
>
> Algo..
>
> 1> Get all the Subset of the particular array. Best Algo O(n2).
> 2> Now try to find the subsets having similar average. Again best algo
> known is O(n2).
>
>
> Anyone have better options??
>
> BR,
> Prem
>
>
> On Fri, May 18, 2012 at 12:05 PM, payal gupta  wrote:
>
>>  How do you partition an array into 2 parts such that the two parts have
>> equal average?...each partition may contain elements that are
>> non-contiguous in the array...
>>
>>  --
>> 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/-/fSAXqe-gkJcJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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: find where the two list connect

[adarsh kumar]

Simple, refer this:
http://www.geeksforgeeks.org/archives/2405

On Wed, May 2, 2012 at 1:12 AM, Abhishek Sharma wrote:

> @Bhupendra: your approach is correct but in case the linked lists contain
> millions of nodes then this might be an overhead.
>
> Another approach could be:
>
> - Start with the head of of both the lists.
> - Store (Hash) the addresses to which the current nodes are pointing to,
> in a hashtable.
> - while storing (Hashing) also check if the address already exists (for
> both of them). In case it exists in the hashtable, this address (or node)
> is the required node else, increment the pointers to the next nodes.
>
> This algo will not require traversing the whole lists and will save time.
>
> Regards,
> AB
>
>
> On Tue, May 1, 2012 at 9:36 PM, Umer Farooq  wrote:
>
>> You don't have to traverse the nodes of two lists simultaneously.
>>
>> You have to check if the every node of list one matches with the address
>> of any node of list two. The first matching address will be the output.
>>
>> The worst case running time of this algo will be O(n^2)
>>
>>
>> On Tue, May 1, 2012 at 8:47 PM, rafi  wrote:
>>
>>> i dont understan if i look in the pic i attached then the length of
>>> the first list is 5 and the length of the second list is 6.
>>> what should i do now?
>>> if i traverse the long list 5,6 nodes i dont get to the red node.
>>> what am i missing?
>>>
>>> On 1 מאי, 18:04, Bhupendra Dubey  wrote:
>>> > start from head of both and  as soon as one of the list is empty means
>>>  you
>>> > hit null
>>> > start counting the remaining number of nodes in the other list till
>>> that
>>> > gets empty.
>>> >
>>> > Now the number obtained  above is the difference in length of the two
>>> list
>>> > prior to the first common node (the red node). Now again traverse the
>>> > longer list corresponding to the above count and then start
>>>  traversing the
>>> > other list .Stop when two nodes become equal. Home!:)
>>> >
>>> > On Tue, May 1, 2012 at 7:55 PM, רפי וינר  wrote:
>>> > > you have two linked lists that some where combine in to one list.
>>> > > pic attached to illustrate
>>> > >  [image: Inline image 1]
>>> > > you need to find where the two list collide. (in the pic the red
>>> node)
>>> >
>>> > > --
>>> > > 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.
>>> >
>>> > --
>>> > bhupendra dubey
>>> >
>>> >  Untitled.png
>>> > 14Kהצגהורדה
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> Umer
>>
>> --
>> 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: Google

[adarsh kumar]

Which college?

On Sun, Mar 4, 2012 at 10:16 AM, teja bala wrote:

> Google is visiting our campus 4 different roles As  of now IT field
> technician is confirmed so how to approach 4 written test. ??
>
> --
> 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] OFF TOPIC(QUERY)

[adarsh kumar]

hi friends
I will be takng up amazon online test in a few days.
Can any1 temme wat r the areas to concentrate on for this,and for
their interviews?
It would be great if sum1 can provide some info regarding this.
regards,
adarsh.

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

[adarsh kumar]

U can easily find out the number of 1's in the numbers between 0 to
N(written in 2's complement form),by using a recurrence relation.Let it be
equal to ans(N).
Thus required answer is nothing but ans(N)-ans(N-1)+1.
correct me if im wrong.

On Fri, Jan 27, 2012 at 11:05 PM, Sourabh Singh wrote:

> @ALL
> //Imagine that you write down all numbers between A and B in 2's
> complement representation using 32 bits. How many 1's will you write
> down in all ?
>
> wat's wrong with this code
>
> working fine for all cases i tested but
>
> on
>
> http://www.spoj.pl/problems/CODESPTA/
>
> wrong answer..
> plz.. point out cases where it might fail . thanku..
> #include
> int find(int a)
> {   int ret=0;
>if(a>0)
>{
>   while(a)
>   {
>   if(a&1)
>  ret++;
>   a=a>>1;
>   }
>}
>else if(a==0)
> ret=0;
> else
> {
> a=~a;
> ret=32; //here ret is maximum bits in the representation
> of number and it varies from machine to machine
> while(a>0)
> {
>   if(a&1)
>  ret--;
>   a=a>>1;
> }
> }
>   return ret;
> }
> uint64_t solve(uint64_t a)
> {
>  if(a == 0) return 0 ;
>  if(a % 2 == 0) return solve(a - 1) + find(a) ;
>  return (a + 1) / 2 + 2 * solve(a / 2) ;
> }
>
> main()
> {
>int a,b,t;
>uint64_t in_a,in_b;
>scanf("%d",&t);
>while(t--)
>{   scanf("%d %d",&a,&b);
>if(a==-2147483648 & b==2147483647)
>  printf("18446744073709551616\n");
>else
>{
>if(a<0)
>{  a=-a;
>   in_a=(32*a-solve(a-1));
>   if(b<0)
>   {   b=-b;
>   in_b=(32*b-solve(b-1));
>
> printf("%llu\n",in_a-in_b+(32-find(b-1)));
>   }
>   else
>   {
>   in_b=solve(b);
>   printf("%llu\n",in_b+in_a);
>   }
>}
>else
>{
>in_a=solve(a);
>in_b=solve(b);
>printf("%llu\n",in_b-in_a+find(a));
>}
>}
>}
>return 0;
> }
>
> --
> 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.