Re: [algogeeks] Distributed System problem

[Piyush Grover]

Lets assume there are n global caches and since the load is to be
distributed uniformly among the servers and duplicity needs to be avoided,
you need to write a hashfunction f which takes url as an input and returns
an integer value. You can store that url on the cache x where
x = value % n
each time you need to compute the hashvalue and based on that you need to
query on the particular cache x, if it's available bingo
else store that url to cache x.

Hope it helps.



On Sun, Dec 14, 2014 at 2:29 PM, atul anand  wrote:

> approach i have mentioned have flaws .  so what other approaches we can
> try to solve this ?
>
> On Sun, Dec 14, 2014 at 2:23 PM, SOMU  wrote:
>>
>> Then the Domain name is altered from abc to bbc .. That indirectly means
>> that the nameserver will change.
>>
>> So in that case the Cache will point to the New NameServer ..
>>
>> Thanks,
>> Somnath Singh
>>
>> On Sun, Dec 14, 2014 at 2:04 PM, atul anand 
>> wrote:
>>
>>> It is a system design problem .
>>>
>>> Suppose a http request  is sent to server . Now Server maintains cache
>>> for fast retrieval . if link is present int the cache then it just takes a
>>> data from cache and return it to user but if not , then user will fetch
>>> that http address and then store it in its cache and return same to the
>>> user .
>>>
>>> Problem is that there are many server and many global cache as expected
>>> in distributed system. Now when request is received by a server then how
>>> can we maintain global cache such that server can know which cache to query
>>> instead of querying each global cache as it will be inefficient.
>>>
>>> one approach can be.. maintain 26 global cache . Now when request is
>>> received by server it check the web link say , www.*a*bc.com ... here
>>> server will query cache-1 . Similarly cache-2 will take care of links with
>>> starts from "b"...www.*b*bc.com and so on
>>>
>>> above method will avoid duplicity in caches but will not be very
>>> efficient as a cache may have higher query rate than others...
>>>
>>>
>>> any other approach ??
>>>
>>> --
>>> 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.
>>>
>>  --
>> 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.
>>
>  --
> 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.
>



-- 
Piyush Grover

*"Be a traveler, not a tourist"*

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

Re: [algogeeks] optimization problem - N floors , N persons. minimum number of lift movements to move all persons in their respective floors

[Piyush Grover]

The problem is an array sorting problem.
You are given an array of size N containing values 1 to N only. Sort it in
O(N).

Start from floor 1 till ith floor until you find a person on the wrong
floor, take him to his respective floor
take the guy from that floor and take him to his respective floor do it
until you reach back to ith floor.
Keep a counter, if all the N persons have been moved you are done otherwise
repeat the procedure
starting from i+1 th floor.




On Fri, May 31, 2013 at 11:51 AM, bharat b wrote:

> There are N floors and N persons each one is tagged with some random
> unique number between 1 to N(represents floor number).
> We have a lift which can accommodate one person at a time. Every person is
> in some random floor.
> Initially lift is at floor 1 and all floors have single person. Problem
> here is.. we have to move the persons to their corresponding floor with
> minimum number of lift movements.
> Restriction : Lift can have at most one person at a time.
> While moving persons, at some point of time, we can keep more than one
> person at one floor.
>
> --
> 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.
>
>
>

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

[algogeeks] Re: Clustering set problem

[Piyush Grover]

correcting my last statement

"So basically the problem needs to be optimized on two aspects, minimizing
costs and maximizing the total weight of executed jobs.
so *Maximize ( 1 + (Total Weight of executed jobs in j-th iter/ Total Cost
incurred in j-th iter) )"*


On Sat, Apr 20, 2013 at 3:49 AM, Piyush Grover wrote:

> I have a practical problem, need an optimal solution for this
>
> *What is given?*
> Given *N* sets, each containing some jobs to be executed, such that no
> two sets are subsets of each other and number of jobs in *i-th* set is *ni
> << N*.
> The jobs can have values between *1...k where k << N*. Priority of each
> job is in the order of their value. i.e *priority(1) > priority(2).>
> priority(k) *so as the weights
> *w1 > w2 > .wi...> wk*
>
> *What are the constraints?*
> -> Every job in every set is executed independent of others.
> -> No job can be executed independent of its set i.e if a job needs to be
> executed, any
> set containing the job will be executed
> -> The cost of execution of *i-th* set is *ni*
> -> The probability of failing each job during execution is equal and
> unknown.
>
> *What is needed?*
> The jobs need to be executed but can be done in multiple iterations.
> So* *return the number of sets *mj <=M << N* (and set itself) to be added
> for the execution in the j*-th iteration.
> *Each iteration adds the additional cost to each set to be executed in a
> way such that
> *cost of execution of i-th set in the j-th iteration = ni + (j-1)*max(
> weights of failed jobs in i-th set)*
> If a set is executed (with/without failed jobs) that can not be used in
> further iterations
>
>
> So basically the problem needs to be optimized on two aspects, minimizing
> costs and maximizing the number of jobs to be executed.
>
>
> Regards
> Piyush
>

-- 
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] Clustering set problem

[Piyush Grover]

I have a practical problem, need an optimal solution for this

*What is given?*
Given *N* sets, each containing some jobs to be executed, such that no two
sets are subsets of each other and number of jobs in *i-th* set is *ni << N*
.
The jobs can have values between *1...k where k << N*. Priority of each job
is in the order of their value. i.e *priority(1) > priority(2).>
priority(k) *so as the weights
*w1 > w2 > .wi...> wk*

*What are the constraints?*
-> Every job in every set is executed independent of others.
-> No job can be executed independent of its set i.e if a job needs to be
executed, any
set containing the job will be executed
-> The cost of execution of *i-th* set is *ni*
-> The probability of failing each job during execution is equal and
unknown.

*What is needed?*
The jobs need to be executed but can be done in multiple iterations.
So* *return the number of sets *mj <=M << N* (and set itself) to be added
for the execution in the j*-th iteration.
*Each iteration adds the additional cost to each set to be executed in a
way such that
*cost of execution of i-th set in the j-th iteration = ni + (j-1)*max(
weights of failed jobs in i-th set)*
If a set is executed (with/without failed jobs) that can not be used in
further iterations


So basically the problem needs to be optimized on two aspects, minimizing
costs and maximizing the number of jobs to be executed.


Regards
Piyush

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

[Piyush Grover]

@Don can you give the logic of your rnd() function?

-- 
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: can we check a number has last digit 5 or not using bitwise operator.

[Piyush Grover]

forgot to assign:
m = n;

On Sun, Oct 14, 2012 at 2:27 AM, Piyush Grover wrote:

> The number which has 5 as last digit can be written as
> n = 4*a + b where b = 1 or 3
> so if 4*a + 1 == n or 4*a + 3 == n; then n has 5 as a last digit.
> So code looks like:
>
> void main()
> {
>  int n, m;
>  scanf("%d", &n);
>  m >>= 2;
> m <<= 2;
> if(add(m, 1) == n || add(m,3) == n)
> puts("yes");
> else
> puts("no");
> }
>
> int add(int x, int y) {
>
> int a, b;
>
> do {
>
> a = x & y; b = x ^ y; x = a << 1; y = b;
>
> }while(b);
>
> return b;
>
> }
>
>
> On Fri, Oct 12, 2012 at 12:46 AM, Dave  wrote:
>
>> @Jaspreet: The % operator is implemented using division, which is
>> considered an arithmetic operation, not a bitwise operation.
>>
>> On primitive chips, as may be used in specialized hardware, division may
>> not be implemented, in which case a non-division based algorithm may be
>> desired.
>>
>> The question may be based on that idea, or just on how to do it faster
>> than using division, which typically is a very slow instruction (compared
>> to other machine instructions).
>>
>> Dave
>>
>> On Thursday, October 11, 2012 4:14:17 AM UTC-5, Jaspreet Singh wrote:
>>
>>> Nice solution Dave sir .. but if you know can you please tell us what is
>>> the internal structure of "%" operator .. i mean it has also to be done by
>>> bitwise any way .. so can't we implement that in HHLs.
>>>
>>> Thanks
>>>
>>> On Thu, Oct 11, 2012 at 1:25 AM, Dave  wrote:
>>>
>>>> @Mohit: The decimal representation of a number ends in 5 if its low
>>>> order bit is 1 and it is divisibile by 5.
>>>>
>>>> An algorithm using bitwise operations to check for divisibility by 5 is
>>>> given at https://groups.google.com/d/**msg/algogeeks/I5HWmwKW_ks/**
>>>> n38FWJSd0l8J<https://groups.google.com/d/msg/algogeeks/I5HWmwKW_ks/n38FWJSd0l8J>.
>>>>
>>>>
>>>> It probably is not as fast as (n & 1) && (n % 5 == 0), though.
>>>>
>>>> Dave
>>>>
>>>> On Wednesday, October 10, 2012 4:06:28 AM UTC-5, mohit mishra 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/-/bRupe9F1MUIJ<https://groups.google.com/d/msg/algogeeks/-/bRupe9F1MUIJ>.
>>>>
>>>>
>>>> To post to this group, send email to algo...@googlegroups.com.
>>>> To unsubscribe from this group, send email to algogeeks+...@**
>>>> googlegroups.com.
>>>>
>>>> For more options, visit this group at http://groups.google.com/**
>>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>.
>>>>
>>>
>>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/XF05MQd7Ne4J.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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: can we check a number has last digit 5 or not using bitwise operator.

[Piyush Grover]

The number which has 5 as last digit can be written as
n = 4*a + b where b = 1 or 3
so if 4*a + 1 == n or 4*a + 3 == n; then n has 5 as a last digit.
So code looks like:

void main()
{
 int n, m;
 scanf("%d", &n);
 m >>= 2;
m <<= 2;
if(add(m, 1) == n || add(m,3) == n)
puts("yes");
else
puts("no");
}

int add(int x, int y) {

int a, b;

do {

a = x & y; b = x ^ y; x = a << 1; y = b;

}while(b);

return b;

}


On Fri, Oct 12, 2012 at 12:46 AM, Dave  wrote:

> @Jaspreet: The % operator is implemented using division, which is
> considered an arithmetic operation, not a bitwise operation.
>
> On primitive chips, as may be used in specialized hardware, division may
> not be implemented, in which case a non-division based algorithm may be
> desired.
>
> The question may be based on that idea, or just on how to do it faster
> than using division, which typically is a very slow instruction (compared
> to other machine instructions).
>
> Dave
>
> On Thursday, October 11, 2012 4:14:17 AM UTC-5, Jaspreet Singh wrote:
>
>> Nice solution Dave sir .. but if you know can you please tell us what is
>> the internal structure of "%" operator .. i mean it has also to be done by
>> bitwise any way .. so can't we implement that in HHLs.
>>
>> Thanks
>>
>> On Thu, Oct 11, 2012 at 1:25 AM, Dave  wrote:
>>
>>> @Mohit: The decimal representation of a number ends in 5 if its low
>>> order bit is 1 and it is divisibile by 5.
>>>
>>> An algorithm using bitwise operations to check for divisibility by 5 is
>>> given at https://groups.google.com/d/**msg/algogeeks/I5HWmwKW_ks/**
>>> n38FWJSd0l8J.
>>>
>>>
>>> It probably is not as fast as (n & 1) && (n % 5 == 0), though.
>>>
>>> Dave
>>>
>>> On Wednesday, October 10, 2012 4:06:28 AM UTC-5, mohit mishra 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/-/bRupe9F1MUIJ.
>>>
>>>
>>> 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 view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/XF05MQd7Ne4J.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Microsoft interview question

[Piyush Grover]

@Partha

try with:
A = {2, 2, 9}
B=  {1, 6, 6}



On Mon, May 21, 2012 at 7:08 PM, partha sarathi Mohanty <
partha.mohanty2...@gmail.com> wrote:

>  a[] = [-1,-3,4,0,7,0,36,2,-3]
>  b[] = [0,0,6,2,-1,9,28,1,6]
>  b1[] = [0,7,0,36,4,-6,3,0,0]
>  b2[] =[-1,-3,11,0,0,0,35,0,0]
>
>  suma = 42 proda = -84*72*3
>  sumb = 51 prodb = -84*72*3
>  sumb1 = 44 prodb1 = -84*72*3
>  sumb2 = 42 prodb2 = 33*35
>
>  do the sum and prod operation w/o 0s and compare the values.. if both are
> equal they are pormutations
>  if i am missing any corner cases related to 0 or -e numbers u can keep a
> track of them while traversalO(N) and constant space
>
>
>
> On Mon, May 21, 2012 at 6:40 PM, karthikeya s 
> wrote:
>
>> No way u can do it in O(1) space and O(n) time.sols above are not
>> gonna work..yeah, it is possible in O(n) space and O(n) time.
>>
>> On May 20, 12:29 am, HARSHIT PAHUJA  wrote:
>> > given 2 unsorted integer arrays a and b of equal size. Determine if b
>> is a
>> > permutation of a. Can this be done in O(n) time and O(1) space ?
>> >
>> > please help me with my solution
>> >
>> > suppose a --  3 5 4
>> >  b --  4 3 5
>> >
>> > now we replace a[i] with a[i]..th prime number  and b with b[i] .. th
>> prime
>> > number
>> >
>> >   now array  a becomes  5 11 7
>> >  array  b becomes  7 5 11
>> >
>> > now we take product of elements of array a and do the same with array  b
>> > elements
>> > if product is equal  then b is a permutation of a
>>
>> --
>> 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] kth largest element in an unsorted list

[Piyush Grover]

you can do it in nlogk or n+klogn time.

create a min-heap tree of size k with first k nodes.
Add k+1..n nodes in the tree. Everytime you insert a node in the tree check
if it's greater than the root node. If yes remove
root node and insert the new node (logk operations). So time complexity
will be nlogk.

another method with time complexity n+ klogn
create a max heap tree of size n. O(n)

keep on deleting the root node for k-1 operations by maintaining the heap
property. Finally you will be left with the kth largest mode at the root.
O(klogn)




On Sat, Jan 14, 2012 at 7:58 PM, Ashish Goel  wrote:

> Hi,
>
> how can we do so in O(n)
> forming a heap or a tree with each node keeping children in its left node
> still is nlogn
>
>
> 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] Re: Maximal possible subsets Algorithm

[Piyush Grover]

How to create the lookup table?
say if I have W = {2, 4, 6, 8} and Wmax = 3

0   1   2   3
0  1   0   0   0
1  1   1   1   0
2  1   1   1   1
3  1   1   1   1
4  1   1   1   1

Is this correct???

On Mon, Jan 9, 2012 at 2:55 PM, Lucifer  wrote:

> @All
>
> The same algo will work for both +ve and -ve nos.. no need for
> modification..
>
> For ex-
> Say the sum is 4 and the set is { 1, 2, 3, -2 }
>
> Now if u include -2 as part of ur solution then for the rest 3
> elements the sum would be 4-(-2) = 6, which is correct...
>
>
> On Jan 9, 2:20 pm, Siddhartha  wrote:
> > yup...that was what i was thinking... i guess for negative nos, we can
> > define Wmax= sum of modulus of weights,and then the  same algo works...
>
> --
> 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] Facebook interview question.

[Piyush Grover]

Hi Atul

Yes, I posted it earlier but couldn't keep track of it, thanks for the
link. I still have a doubt, does it give all the maximal subsets
or all the subsets. I couldn't get it from the algo posted by Lucifer.

On Mon, Jan 9, 2012 at 9:45 AM, atul anand  wrote:

> @Piyush :
> you are re-posting same problem which you had posted on 5 dec 2011.
>
> check this link :-
>
>
> http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b/ee74f8a4d7b68561?lnk=gst&q=Maximal+possible+subsets+Algorithm#ee74f8a4d7b68561
>
>
> On Mon, Jan 9, 2012 at 3:27 AM, Piyush Grover 
> wrote:
>
>> Given a set S, find all the maximal subsets whose sum <= k. For example,
>> if S = {1, 2, 3, 4, 5} and k = 7
>> Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}
>>
>> Hint:
>> - Output doesn't contain any set which is a subset of other.
>> - If X = {1, 2, 3} is one of the solution then all the subsets of X {1}
>> {2} {3} {1, 2} {1, 3} {2, 3} are omitted.
>> - Lexicographic ordering may be used to solve it
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

[algogeeks] Facebook interview question.

[Piyush Grover]

Given a set S, find all the maximal subsets whose sum <= k. For example, if
S = {1, 2, 3, 4, 5} and k = 7
Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

Hint:
- Output doesn't contain any set which is a subset of other.
- If X = {1, 2, 3} is one of the solution then all the subsets of X {1} {2}
{3} {1, 2} {1, 3} {2, 3} are omitted.
- Lexicographic ordering may be used to solve it

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

Re: [algogeeks] A bst problem

[Piyush Grover]

Hi Aman

Here is the working algo. I forgot to consider the case you mentioned. So
whenever a new node is getting added in the tree
we need to modify the inordersucc of the predecessor of the current node.
Here is the link:

you can try out different cases also:
http://www.ideone.com/MOxdl

-Piyush

On Sat, Dec 10, 2011 at 8:28 PM, AMAN AGARWAL  wrote:

> Hi.
>
> So can you please tell me the modifications required so it works correctly.
>
> Regards,
> Aman.
>
>
> On Sat, Dec 10, 2011 at 8:22 PM, Piyush Grover 
> wrote:
>
>> yup, you are right..
>>
>>
>> On Sat, Dec 10, 2011 at 8:09 PM, AMAN AGARWAL wrote:
>>
>>> Hi,
>>>
>>> After 22 you add 21 so
>>> 21->left=22->right=null  22->left=21 21->inorder=22.  but here if you
>>> draw the diagram you will see that inorder successor of 18 will
>>> now be 21 not 22. I think you have not taken that into consideration.
>>> Please correct me if I am wrong.
>>>
>>> Regards,
>>> Aman,
>>>
>>>
>>> On Sat, Dec 10, 2011 at 7:37 PM, Piyush Grover <
>>> piyush4u.iit...@gmail.com> wrote:
>>>
>>>> I don't think so.
>>>> First you added 15.
>>>> 15->left = null=15->right=15->succ;
>>>>
>>>> add 13. (13 < 15) so
>>>> 13->left = 13->right = null; 13->succ = 15; 15->left = 13;
>>>>
>>>> add 18 (18 > 15) so
>>>> 18->left = 18->right = null; 18->succ = 15->succ = null; 15->right =
>>>> 15->succ = 18
>>>>
>>>> add 22 (22 > 15) go to 15->right
>>>> (22 > 18) go to 18-> right
>>>> 22->left = 22->right = null; 22->succ = 18->succ = null; 18->right =
>>>> 18->succ = 22;
>>>> and so on...
>>>>
>>>>
>>>>
>>>> On Sat, Dec 10, 2011 at 6:49 PM, AMAN AGARWAL wrote:
>>>>
>>>>> Hi Piyush,
>>>>>
>>>>> I tried with the following data 15,13,18,22,21.  I think your code is
>>>>> not giving proper inorder succ of node 18.
>>>>> Please check it.
>>>>>
>>>>> Regards,
>>>>> Aman.
>>>>>
>>>>>
>>>>> On Sat, Dec 10, 2011 at 6:30 PM, Piyush Grover <
>>>>> piyush4u.iit...@gmail.com> wrote:
>>>>>
>>>>>> insertNode(node *head, int value){
>>>>>>node *new;
>>>>>> if(head == null){
>>>>>>  new = (node*)malloc(sizeof(node));
>>>>>>  new->data = value;
>>>>>>  new->left = new->right = new->inoredrsucc = null;
>>>>>>  head = new;
>>>>>>
>>>>>> }else{
>>>>>>node *root = head;
>>>>>>node *l, *r;
>>>>>>while(root != null){
>>>>>>
>>>>>>  if(root->data   >value){
>>>>>>
>>>>>>   l = root; r = null;
>>>>>>   root = root->left;
>>>>>>  }else{
>>>>>>
>>>>>>   r = root; l = null;
>>>>>>   root = root->right;
>>>>>>  }
>>>>>>} //endwhile
>>>>>>
>>>>>>if(l != null){
>>>>>> new = (node*)malloc(sizeof(node));
>>>>>> new->data = value;
>>>>>> new->left = new->right = null;
>>>>>> new->inordersucc = l;
>>>>>> l->left = new;
>>>>>> }else if(r != null){
>>>>>>new = (node*)malloc(sizeof(node));
>>>>>> new->data = value;
>>>>>> new->left = new->right = null;
>>>>>> new->inordersucc = r->inordersucc;
>>>>>> r->inordersucc = new;
>>>>>> r->right = new;
>>>>>>
>>>>>> }
>>>>>>  }
>>>>>> }
>>>>>>
>>>>&

Re: [algogeeks] A bst problem

[Piyush Grover]

yup, you are right..

On Sat, Dec 10, 2011 at 8:09 PM, AMAN AGARWAL  wrote:

> Hi,
>
> After 22 you add 21 so
> 21->left=22->right=null  22->left=21 21->inorder=22.  but here if you draw
> the diagram you will see that inorder successor of 18 will
> now be 21 not 22. I think you have not taken that into consideration.
> Please correct me if I am wrong.
>
> Regards,
> Aman,
>
>
> On Sat, Dec 10, 2011 at 7:37 PM, Piyush Grover 
> wrote:
>
>> I don't think so.
>> First you added 15.
>> 15->left = null=15->right=15->succ;
>>
>> add 13. (13 < 15) so
>> 13->left = 13->right = null; 13->succ = 15; 15->left = 13;
>>
>> add 18 (18 > 15) so
>> 18->left = 18->right = null; 18->succ = 15->succ = null; 15->right =
>> 15->succ = 18
>>
>> add 22 (22 > 15) go to 15->right
>> (22 > 18) go to 18-> right
>> 22->left = 22->right = null; 22->succ = 18->succ = null; 18->right =
>> 18->succ = 22;
>> and so on...
>>
>>
>>
>> On Sat, Dec 10, 2011 at 6:49 PM, AMAN AGARWAL wrote:
>>
>>> Hi Piyush,
>>>
>>> I tried with the following data 15,13,18,22,21.  I think your code is
>>> not giving proper inorder succ of node 18.
>>> Please check it.
>>>
>>> Regards,
>>> Aman.
>>>
>>>
>>> On Sat, Dec 10, 2011 at 6:30 PM, Piyush Grover <
>>> piyush4u.iit...@gmail.com> wrote:
>>>
>>>> insertNode(node *head, int value){
>>>>node *new;
>>>> if(head == null){
>>>>  new = (node*)malloc(sizeof(node));
>>>>  new->data = value;
>>>>  new->left = new->right = new->inoredrsucc = null;
>>>>  head = new;
>>>>
>>>> }else{
>>>>node *root = head;
>>>>node *l, *r;
>>>>while(root != null){
>>>>
>>>>  if(root->data   >value){
>>>>
>>>>   l = root; r = null;
>>>>   root = root->left;
>>>>  }else{
>>>>
>>>>   r = root; l = null;
>>>>   root = root->right;
>>>>  }
>>>>} //endwhile
>>>>
>>>>if(l != null){
>>>> new = (node*)malloc(sizeof(node));
>>>> new->data = value;
>>>> new->left = new->right = null;
>>>> new->inordersucc = l;
>>>> l->left = new;
>>>> }else if(r != null){
>>>>new = (node*)malloc(sizeof(node));
>>>> new->data = value;
>>>> new->left = new->right = null;
>>>> new->inordersucc = r->inordersucc;
>>>> r->inordersucc = new;
>>>> r->right = new;
>>>>
>>>> }
>>>>  }
>>>> }
>>>>
>>>> On Sat, Dec 10, 2011 at 4:04 PM, sayan nayak wrote:
>>>>
>>>>> @dheeraj: I have one doubt...
>>>>>  during implementation I assumed that inordersuccessor already exists
>>>>> for each node.
>>>>> So  there's no need to track inodersuccessor.
>>>>> Just finding the position is ok.Then u can do the needful to change
>>>>> the inordersuccessor for the parent and the added node.
>>>>> Pls correct me If I'm wrong
>>>>>
>>>>>
>>>>> On Sat, Dec 10, 2011 at 3:43 PM, Dheeraj Sharma <
>>>>> dheerajsharma1...@gmail.com> wrote:
>>>>>
>>>>>> My algorithm is like:
>>>>>>
>>>>>> 1.Take two pointers. one pointer track..where the node should be
>>>>>> inserted..and other..to keep track of inorder successor.
>>>>>>first pointer=root;
>>>>>>   second pointer=null;
>>>>>>
>>>>>> 2.if the first pointer moves to the left of a particular node(which
>>>>>> becomes its parent)..then the set the value of second pointer=parent.
>>>>>> else
>>>>>> if the first po

Re: [algogeeks] A bst problem

[Piyush Grover]

I don't think so.
First you added 15.
15->left = null=15->right=15->succ;

add 13. (13 < 15) so
13->left = 13->right = null; 13->succ = 15; 15->left = 13;

add 18 (18 > 15) so
18->left = 18->right = null; 18->succ = 15->succ = null; 15->right =
15->succ = 18

add 22 (22 > 15) go to 15->right
(22 > 18) go to 18-> right
22->left = 22->right = null; 22->succ = 18->succ = null; 18->right =
18->succ = 22;
and so on...


On Sat, Dec 10, 2011 at 6:49 PM, AMAN AGARWAL  wrote:

> Hi Piyush,
>
> I tried with the following data 15,13,18,22,21.  I think your code is not
> giving proper inorder succ of node 18.
> Please check it.
>
> Regards,
> Aman.
>
>
> On Sat, Dec 10, 2011 at 6:30 PM, Piyush Grover 
> wrote:
>
>> insertNode(node *head, int value){
>>node *new;
>> if(head == null){
>>  new = (node*)malloc(sizeof(node));
>>  new->data = value;
>>  new->left = new->right = new->inoredrsucc = null;
>>  head = new;
>>
>> }else{
>>node *root = head;
>>node *l, *r;
>>while(root != null){
>>
>>  if(root->data   >value){
>>
>>   l = root; r = null;
>>   root = root->left;
>>  }else{
>>
>>   r = root; l = null;
>>   root = root->right;
>>  }
>>} //endwhile
>>
>>if(l != null){
>> new = (node*)malloc(sizeof(node));
>> new->data = value;
>> new->left = new->right = null;
>> new->inordersucc = l;
>> l->left = new;
>> }else if(r != null){
>>new = (node*)malloc(sizeof(node));
>> new->data = value;
>> new->left = new->right = null;
>> new->inordersucc = r->inordersucc;
>> r->inordersucc = new;
>> r->right = new;
>>
>> }
>>  }
>> }
>>
>> On Sat, Dec 10, 2011 at 4:04 PM, sayan nayak wrote:
>>
>>> @dheeraj: I have one doubt...
>>>  during implementation I assumed that inordersuccessor already exists
>>> for each node.
>>> So  there's no need to track inodersuccessor.
>>> Just finding the position is ok.Then u can do the needful to change the
>>> inordersuccessor for the parent and the added node.
>>> Pls correct me If I'm wrong
>>>
>>>
>>> On Sat, Dec 10, 2011 at 3:43 PM, Dheeraj Sharma <
>>> dheerajsharma1...@gmail.com> wrote:
>>>
>>>> My algorithm is like:
>>>>
>>>> 1.Take two pointers. one pointer track..where the node should be
>>>> inserted..and other..to keep track of inorder successor.
>>>>first pointer=root;
>>>>   second pointer=null;
>>>>
>>>> 2.if the first pointer moves to the left of a particular node(which
>>>> becomes its parent)..then the set the value of second pointer=parent.
>>>> else
>>>> if the first pointer moves to the right of particular node (which
>>>> becomes its parent)..the let the value of second pointer as it is..
>>>>
>>>> finally when the node has been inserted at leaf..set the inorder
>>>> successor of the node=second pointer value
>>>>
>>>> Correct me if am wrong
>>>>
>>>>
>>>> On Sat, Dec 10, 2011 at 3:38 PM, sayan nayak wrote:
>>>>
>>>>> hi,
>>>>>here is the code:
>>>>> ==
>>>>>
>>>>> struct node
>>>>> {
>>>>> int data;
>>>>> struct node *left;
>>>>> struct node *right;
>>>>> struct node *inordersuccessor;
>>>>> };
>>>>>
>>>>> struct node *createnode(int info){
>>>>>  struct node* temp;
>>>>>  temp->data=info;
>>>>>  temp->left=temp->right=temp->inordersuccessor=NULL;
>>>>>  return temp;
>>>>> };
>>>>>
>>>>>
>>>>> struct node *addNode(struct node *node,int info){
>>>

Re: [algogeeks] A bst problem

[Piyush Grover]

insertNode(node *head, int value){
   node *new;
if(head == null){
 new = (node*)malloc(sizeof(node));
 new->data = value;
 new->left = new->right = new->inoredrsucc = null;
 head = new;

}else{
   node *root = head;
   node *l, *r;
   while(root != null){

 if(root->data   >value){

  l = root; r = null;
  root = root->left;
 }else{

  r = root; l = null;
  root = root->right;
 }
   } //endwhile

   if(l != null){
new = (node*)malloc(sizeof(node));
new->data = value;
new->left = new->right = null;
new->inordersucc = l;
l->left = new;
}else if(r != null){
   new = (node*)malloc(sizeof(node));
new->data = value;
new->left = new->right = null;
new->inordersucc = r->inordersucc;
r->inordersucc = new;
r->right = new;
}
 }
}

On Sat, Dec 10, 2011 at 4:04 PM, sayan nayak  wrote:

> @dheeraj: I have one doubt...
>  during implementation I assumed that inordersuccessor already exists for
> each node.
> So  there's no need to track inodersuccessor.
> Just finding the position is ok.Then u can do the needful to change the
> inordersuccessor for the parent and the added node.
> Pls correct me If I'm wrong
>
>
> On Sat, Dec 10, 2011 at 3:43 PM, Dheeraj Sharma <
> dheerajsharma1...@gmail.com> wrote:
>
>> My algorithm is like:
>>
>> 1.Take two pointers. one pointer track..where the node should be
>> inserted..and other..to keep track of inorder successor.
>>first pointer=root;
>>   second pointer=null;
>>
>> 2.if the first pointer moves to the left of a particular node(which
>> becomes its parent)..then the set the value of second pointer=parent.
>> else
>> if the first pointer moves to the right of particular node (which becomes
>> its parent)..the let the value of second pointer as it is..
>>
>> finally when the node has been inserted at leaf..set the inorder
>> successor of the node=second pointer value
>>
>> Correct me if am wrong
>>
>>
>> On Sat, Dec 10, 2011 at 3:38 PM, sayan nayak wrote:
>>
>>> hi,
>>>here is the code:
>>> ==
>>>
>>> struct node
>>> {
>>> int data;
>>> struct node *left;
>>> struct node *right;
>>> struct node *inordersuccessor;
>>> };
>>>
>>> struct node *createnode(int info){
>>>  struct node* temp;
>>>  temp->data=info;
>>>  temp->left=temp->right=temp->inordersuccessor=NULL;
>>>  return temp;
>>> };
>>>
>>>
>>> struct node *addNode(struct node *node,int info){
>>> struct node* temp=Createnode(info);
>>>
>>> if(node==NULL){
>>>  node=(struct node*)malloc(sizeof(struct node);
>>> if (node==NULL)
>>>  fatalerror("Out of space");
>>> else
>>>  {   node->data=info;
>>>  node->left=node->right=node->inordersuccessor=NULL;
>>>  }
>>> }
>>>
>>> if (node->left==NULL && info<(node->data)){
>>>  node->left=temp;
>>>  temp->inordersuccessor=node;
>>>}
>>> else if (node->right==NULL && info>(node->data)){
>>>
>>> node->right=temp;
>>> temp->inordersuccessor=node->inordersuccessor;
>>> node->inordersuccessor=temp;
>>> }
>>> else
>>> {
>>>  if (info<(node->data))
>>> node->left=addnode(node->left,info);
>>>  else
>>> node->right=addnode(node->right,info);
>>>
>>> }
>>> return node;
>>> }
>>>
>>> I have run a few test cases..It's working.Pls let me know in case of any
>>> failure test cases.
>>> I'm also checking.
>>>
>>> Regards,
>>> Sayan
>>>
>>>
>>> On Sat, Dec 10, 2011 at 1:33 PM, AMAN AGARWAL wrote:
>>>
 Hi,

 Construct a BST where each node has 3 pointers instead of 2.
 the structure is
 struct node
 {
 int data;
 struct node *left;
 struct node *right;
 struct node *inordersuccessor;
 }

 write a code to add nodes in a binary search tree . inordersuccessor
 pointing to inorder successor.

 Regards,
 Aman.
 --
 AMAN AGARWAL
 "Success is not final, Failure is not fatal: It is the courage to
 continue that counts!"

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

Re: [algogeeks] Re: Maximal possible subsets Algorithm

[Piyush Grover]

As I mentioned earlier solution with exponential time-complexity is the
obvious one. Is there any way to solve this problem by greedy/Dynamic algo?

On Mon, Dec 5, 2011 at 5:24 PM, WgpShashank wrote:

> @piyuesh , Saurabh isn't 3-Sum Suffics Here ?
>
> Another thought problem can also be thought by generating power set of
> given set e.g. if set has n elemnts its power set has  2^n elements , then
> finds the set that has sum up yo given weight isn't it ?  hope you know how
> to find power set efficiently ?
>
>
>
> correct if is missed anything ?
>
> Thanks
> Shashank
> Computer Science
> BIT Mesra
> http://www.facebook.com/wgpshashank
> http://shashank7s.blogspot.com/
>
>  --
> 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/-/a9F-gPQkjm0J.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Maximal possible subsets Algorithm

[Piyush Grover]

As such there's no significance for Vi, it's just to show that objects are
not identical. We don't need to maximize on V. For the sake of problem you
can ignore it. We can use the sum of values for other purpose.

Take an examole: S= {1, 2, 3, 4, 5} are weights (I am not using Values)
. Wmax = 8

Solution:
{1, 2, 3} {1, 2, 4} {1, 2, 5}  {1, 3,  4}  {3, 5}


On Mon, Dec 5, 2011 at 2:38 PM, sourabh  wrote:

> @ Piyush..
>
> I have a doubt... Is there any significance of the value Vi, if yes
> then can u give an example.
> If not, then is your question about finding all maximum subsets where
> the addition of the weights results in maximum (each weight being
> considered only once)...
> Say for ex-
> The max weight is X<=Wmax , then find all subsets which add up to X..
>
>
> On Dec 5, 1:51 pm, Piyush Grover  wrote:
> > Yeah but there's one more  condition where it says if subset x is a
> > solution then all the subsets of x will not be part of the solution.
> > It should make some difference, exponential time solution is an obvious
> one.
> >
> >
> >
> >
> >
> >
> >
> > On Mon, Dec 5, 2011 at 2:16 PM, saurabh singh 
> wrote:
> > > The possibility is ruled out by your question itself.There are
> exponential
> > > subsets of a set,so finding all subset is not possible in polynomail
> time.
> >
> > > A backtracking approach is what you should think on,
> >
> > > On Mon, Dec 5, 2011 at 12:51 PM, Piyush Grover <
> piyush4u.iit...@gmail.com>wrote:
> >
> > >> Given a set S of objects having weights Wi and values Vi, and given a
> > >> maximum weight Wmax.
> > >>  Find *ALL* the maximal subsets of set S such that Sum(Wi) <= Wmax.
> >
> > >>  Maximal subset means if {a, b, c} is a solution (such that Wa+Wb+Wc
> <=
> > >> Wmax) it means there doesn't exist any other object x in S such that
> > >> Wa+Wb+Wc+Wx <= Wmax and all the subsets of {a, b, c} e.g. {a, b}, {b,
> c},
> > >> {a, c}{c} are not the part of the solution set.
> >
> > >> P.S. Note that I am *not asking the knapsack problem* where we need to
> > >> find the optimal set.
> > >>  I am asking *ALL* the possible maximal subsets and looking for a good
> > >> algo (polynomial if exists).
> >
> > >> Thanks
> >
> > >> Piyush
> >
> > >> --
> > >> 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.
> >
> > > --
> > > Saurabh Singh
> > > B.Tech (Computer Science)
> > > MNNIT ALLAHABAD
> >
> > >  --
> > > 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] Maximal possible subsets Algorithm

[Piyush Grover]

Yeah but there's one more  condition where it says if subset x is a
solution then all the subsets of x will not be part of the solution.
It should make some difference, exponential time solution is an obvious one.

On Mon, Dec 5, 2011 at 2:16 PM, saurabh singh  wrote:

> The possibility is ruled out by your question itself.There are exponential
> subsets of a set,so finding all subset is not possible in polynomail time.
>
> A backtracking approach is what you should think on,
>
> On Mon, Dec 5, 2011 at 12:51 PM, Piyush Grover 
> wrote:
>
>> Given a set S of objects having weights Wi and values Vi, and given a
>> maximum weight Wmax.
>>  Find *ALL* the maximal subsets of set S such that Sum(Wi) <= Wmax.
>>
>>  Maximal subset means if {a, b, c} is a solution (such that Wa+Wb+Wc <=
>> Wmax) it means there doesn't exist any other object x in S such that
>> Wa+Wb+Wc+Wx <= Wmax and all the subsets of {a, b, c} e.g. {a, b}, {b, c},
>> {a, c}{c} are not the part of the solution set.
>>
>> P.S. Note that I am *not asking the knapsack problem* where we need to
>> find the optimal set.
>>  I am asking *ALL* the possible maximal subsets and looking for a good
>> algo (polynomial if exists).
>>
>> Thanks
>>
>> Piyush
>>
>> --
>> 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.
>>
>
>
>
> --
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT ALLAHABAD
>
>
>  --
> 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] Maximal possible subsets Algorithm

[Piyush Grover]

Given a set S of objects having weights Wi and values Vi, and given a
maximum weight Wmax.
 Find *ALL* the maximal subsets of set S such that Sum(Wi) <= Wmax.

 Maximal subset means if {a, b, c} is a solution (such that Wa+Wb+Wc <=
Wmax) it means there doesn't exist any other object x in S such that
Wa+Wb+Wc+Wx <= Wmax and all the subsets of {a, b, c} e.g. {a, b}, {b, c},
{a, c}{c} are not the part of the solution set.

P.S. Note that I am *not asking the knapsack problem* where we need to find
the optimal set.
 I am asking *ALL* the possible maximal subsets and looking for a good algo
(polynomial if exists).

Thanks
Piyush

-- 
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] Google Question--Suggest Algo

[Piyush Grover]

Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???



On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg  wrote:

> You have an array with *n* elements. The elements are either 0 or 1. You
> want to *split the array into kcontiguous subarrays*. The size of each
> subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
> k << n. After you split the array into k subarrays. One element of each
> subarray will be randomly selected.
>
> Devise an algorithm for maximizing the sum of the randomly selected
> elements from the k subarrays. Basically means that we will want to split
> the array in such way such that the sum of all the expected values for the
> elements selected from each subarray is maximum.
>
> You can assume that n is a power of 2.
>
> Example:
>
> Array: [0,0,1,1,0,0,1,1,0,1,1,0]
> n = 12
> k = 3
> Size of subarrays can be: 2,3,4,5,6
>
> Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
> Expected Value of the sum of the elements randomly selected from the 
> subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
>
> Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
> Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
>
>
> Source ->  
> http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm
>
>  --
> 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] LCA of a Binary tree not a binary search tree

[Piyush Grover]

@anshu

I was just replying to the earlier comments not to ur post.

On Tue, Nov 22, 2011 at 2:23 PM, abhishek kumar  wrote:

> If you maintain the parent, it'll be a simple problem.
> Just go to the two nodes and then trace their parents till you reach the
> common node.
>
>
> On Tue, Nov 22, 2011 at 1:59 PM, anshu mishra 
> wrote:
>
>> first try to understand the sol then comment. it is for binary tree not
>> for BST.
>>
>> On Mon, Nov 21, 2011 at 10:25 PM, Piyush Grover <
>> piyush4u.iit...@gmail.com> wrote:
>>
>>> For BST it would be rather simpler. find the first node which lies in
>>> between the two.
>>>
>>> On Wed, Nov 16, 2011 at 1:44 PM, anshu mishra >> > wrote:
>>>
>>>> Node *LCA(node *root, node *e1, node *e2, int &x)
>>>>
>>>> {
>>>>
>>>> Node *temp =NULL;
>>>>
>>>> Int y = 0;
>>>>
>>>> If (root->left) temp = LCA(root->left, e1, e2, y);
>>>>
>>>> x+=y;
>>>>
>>>> if (temp) return temp;
>>>>
>>>>if (x==2) return node;
>>>>
>>>> y = 0;
>>>>
>>>> If (root->right) temp = LCA(root->right, e1, e2, y);
>>>>
>>>> x+=y;
>>>>
>>>> if (temp) return temp;
>>>>
>>>> if (x==2) return node;
>>>>
>>>> If (root == e1 || root == e2) x++;
>>>>
>>>> Return null;
>>>>
>>>> }
>>>>
>>>> --
>>>> 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.
>>>
>>
>>
>>
>> --
>> Anshuman Mishra | Software Development Engineer | Amazon
>>
>>
>>  --
>> 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
> *Abhishek*
>
>  --
> 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] Linked List Problem-Suggest Algo

[Piyush Grover]

As you mentioned, the numbers designating the gaps can only be repeated
so in your example 2 20 can be broken into 19 1 but 19 is already there in
the list (the
first couplet) and it's not the one which describes the gap. can you please
clarify?

On Mon, Nov 21, 2011 at 5:23 AM, Ankur Garg  wrote:

> a linked list contains
> 2 19 _ _ 3 47 _ _ _ 2 20 _ _ ..and so on
> I have to fill those empty nodes with numbers whose sum is equal to the
> numbers
> occurring just before the gaps and the number of gaps is determined by the
> node
> which is at 2 distance before the gaps with the limitation that their
> would be no
> repetition in list only the nodes designating the number of gaps can be
> repeated
> for example 2 20 should be broken in two parts like 19 1
> 3 47 should be broken in three parts like 42 2 3
> and not in 44 1 2 because 1 already occurred in the list due previous
> partition
>
>
>
>  --
> 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] LCA of a Binary tree not a binary search tree

[Piyush Grover]

For BST it would be rather simpler. find the first node which lies in
between the two.

On Wed, Nov 16, 2011 at 1:44 PM, anshu mishra wrote:

> Node *LCA(node *root, node *e1, node *e2, int &x)
>
> {
>
> Node *temp =NULL;
>
> Int y = 0;
>
> If (root->left) temp = LCA(root->left, e1, e2, y);
>
> x+=y;
>
> if (temp) return temp;
>
>if (x==2) return node;
>
> y = 0;
>
> If (root->right) temp = LCA(root->right, e1, e2, y);
>
> x+=y;
>
> if (temp) return temp;
>
> if (x==2) return node;
>
> If (root == e1 || root == e2) x++;
>
> Return null;
>
> }
>
> --
> 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 -> array problem

[Piyush Grover]

sorry, one mistake...
mul = mul*A[i];

it should be

mul = mul*A[i+1]


On Fri, Sep 30, 2011 at 2:57 AM, Piyush Grover wrote:

> Given array A.
>
> Compute array B such that
>
> B[0] = 1;
> for(i = 1; i < n; i++)
> B[i] = B[i-1]*A[i-1]
>
> now,
> mul = 1;
> for (i = n-2; i >=0; i--){
>mul = mul*A[i];
>B[i] = B[i]*mul;
>
> }
>
>
> On Fri, Sep 30, 2011 at 2:18 AM, Hatta  wrote:
>
>> are the algorithm instance always a sequence incremented by one?
>>
>>
>>
>> On Thu, Sep 29, 2011 at 8:26 AM, raju  wrote:
>> > Given an integer array. { 1,2,3,4,5 }
>> > Compute array containing elements
>> > 120,60,40,30,24 (2*3*4*5,1*3*4*5, 1*2*4*5, 1*2*3*5, 1*2*3*4)
>> > We shouldn't use division operator( / )
>> > Time complexity O(n) .. Space complexity O(1)
>> >
>> > ~raju
>> >
>> > --
>> > 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.
>> >
>>
>>
>>
>> --
>> Hatta
>>
>> --
>> 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 -> array problem

[Piyush Grover]

Given array A.

Compute array B such that

B[0] = 1;
for(i = 1; i < n; i++)
B[i] = B[i-1]*A[i-1]

now,
mul = 1;
for (i = n-2; i >=0; i--){
   mul = mul*A[i];
   B[i] = B[i]*mul;
}


On Fri, Sep 30, 2011 at 2:18 AM, Hatta  wrote:

> are the algorithm instance always a sequence incremented by one?
>
>
>
> On Thu, Sep 29, 2011 at 8:26 AM, raju  wrote:
> > Given an integer array. { 1,2,3,4,5 }
> > Compute array containing elements
> > 120,60,40,30,24 (2*3*4*5,1*3*4*5, 1*2*4*5, 1*2*3*5, 1*2*3*4)
> > We shouldn't use division operator( / )
> > Time complexity O(n) .. Space complexity O(1)
> >
> > ~raju
> >
> > --
> > 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.
> >
>
>
>
> --
> Hatta
>
> --
> 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: random function

[Piyush Grover]

as such there is no specific method to generate random number but if you
have to implement it then you can generate a pseudo random generator
using cur_time_value_in_mili_seconds mod n.

On Mon, Sep 19, 2011 at 9:24 PM, Don  wrote:

> The most common way that it works would be that random(n) returns the
> equivalent of a random integer mod n, so 0<=x standard for how they work, so know what you are dealing with.
>
> Don
>
> On Sep 19, 10:12 am, prasanth n  wrote:
> > @don:
> > suppose if give like random(5)-> it must give any number between 0 and
> 5..
> >
> >
> >
> > On Mon, Sep 19, 2011 at 8:22 PM, Don  wrote:
> > > You mean a pseudo-random generator.
> > > Without special hardware you won't get a real random generator.
> > > Use Mersenne Twister.
> >
> > > Don
> >
> > > On Sep 19, 9:43 am, prasanth n  wrote:
> > > > anyone give an algorithm of how to generate a random
> number..probability
> > > of
> > > > occurrence of each no should be the same..
> >
> > > > --
> > > > *prasanth*
> >
> > > --
> > > 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.
> >
> > --
> > *prasanth*
>
> --
> 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: Microsoft Question

[Piyush Grover]

sry, in the findWord function all a's are different e.g
a0, a1a7

and if(!a) is actually if(a0||a1||...||a7)

thnx
piyush

On Mon, Sep 19, 2011 at 1:10 AM, Piyush Grover wrote:

> for(i = 0; i < n; i++)
>for(j = 0; j < n; j++){
>   setColor(i, j) = black;
>if(A[i][j] == str[0]){
>   setColor(i, j) = blue;
>   a =  findWord(A, i, j, str, 1)
>   if(!a) setColor(i, j) = black;
>else break;
> }
>}
>
> findWord(A, i, j, str, k){
> if(k == strlen(str))
>   return true;
>
>  if(A[i-1][j-1] == str[k] && getColor(i-1, j-1) != blue)
>   setColor(i-1, j-1) = blue;
>   a = findWord(A, i-1, j-1, str, k+1);
>
>  if(A[i-1][j] == str[k] && getColor(i-1, j) != blue)
>  setColor(i-1, j) = blue;
>   a = findWord(A, i-1, j, str, k+1);
>
>  if(A[i-1][j+1] == str[k] && getColor(i-1, j+1) != blue)
>   setColor(i-1, j+1) = blue;
>   a = findWord(A, i-1, j+1, str, k+1);
>
>  if(A[i][j-1] == str[k] && getColor(i, j-1) != blue)
>  setColor(i, j-1) = blue;
>   a = findWord(A, i, j-1, str, k+1);
>
>  if(A[i][j+1] == str[k] && getColor(i, j+1) != blue)
>   setColor(i, j+1) = blue;
>   a = findWord(A, i, j+1, str, k+1);
>
>   if(A[i+1][j-1] == str[k] && getColor(i+1, j-1) != blue)
>   setColor(i+1, j-1) = blue;
>   a = findWord(A, i+1, j-1, str, k+1);
>
>   if(A[i+1][j] == str[k] && getColor(i+1, j) != blue)
>   setColor(i+1, j) = blue;
>   a = findWord(A, i+1, j, str, k+1);
>
>   if(A[i+1][j+1] == str[k] && getColor(i+1, j+1) != blue)
>setColor(i+1, j+1) = blue;
>a = findWord(A, i+1, j+1, str, k+1);
>
>if(!a)  setColor(i, j) = black;
>
>   return a;
> }
>
> This is a pseudo code. I haven't considered the boundary cases to make it
> understandable.
>
>
>
> On Mon, Sep 19, 2011 at 12:21 AM, vikas wrote:
>
>> hmm, nice questions, can we create an  efficient DS to query the
>> strings ??
>>
>>
>> tried using trie but memory prints are very large ( O(n^2) )? :-((
>>
>>
>>
>> On Sep 18, 12:59 pm, Anup Ghatage  wrote:
>> > For the mentioned scenario, it seems to be the only feasible solution.
>> >
>> > On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana <
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > bagana.bharatku...@gmail.com> wrote:
>> > > @anup : the time complexity will be very high ...
>> O(n*M*M)...n=#characters
>> > > to be checked...M=size of the matrix ...
>> >
>> > > On Sat, Sep 17, 2011 at 8:30 AM, Anup Ghatage 
>> wrote:
>> >
>> > >> As WgpShashank once pointed out.
>> >
>> > >> Search the whole matrix for the first character instances, for each
>> > >> instance, send the array, string and that char's position to a
>> function that
>> > >> will recursively check its direct neighbors for the next character.
>> > >> Exhaustively check like that for each starting characters appearance
>> till
>> > >> you find the string, if any.
>> >
>> > >> On Fri, Sep 16, 2011 at 11:55 PM, Ankur Garg > >wrote:
>> >
>> > >>> In a matrix of. characters, find an string. String can be in any way
>> (all
>> > >>> 8 neighbours to be considered)
>> > >>> like find Microsoft in below matrix.
>> >
>> > >>>  A
>> > >>> C
>> > >>> P
>> > >>> *R
>> > >>> *C*
>> > >>> *X
>> > >>> *S
>> > >>> **O
>> > >>> *P
>> > >>> *C*
>> > >>> V
>> > >>> *O*
>> > >>> V
>> > >>> N
>> > >>> *I*
>> > >>> W
>> > >>>  G
>> > >>> *F
>> > >>> **M
>> > >>> *N
>> > >>> Q
>> > >>>  A
>> > >>> *T*
>> > >>> I
>> > >>> T
>> >
>> > >>>  *Any Ideas How to Solve/Approach this problem ?*
>> >
>> > >>>  --
>> > >>> You received this message because you are subscribed to the Google
>> Groups
>> > >

Re: [algogeeks] Re: Microsoft Question

[Piyush Grover]

for(i = 0; i < n; i++)
   for(j = 0; j < n; j++){
  setColor(i, j) = black;
   if(A[i][j] == str[0]){
  setColor(i, j) = blue;
  a =  findWord(A, i, j, str, 1)
  if(!a) setColor(i, j) = black;
   else break;
}
   }

findWord(A, i, j, str, k){
if(k == strlen(str))
  return true;

 if(A[i-1][j-1] == str[k] && getColor(i-1, j-1) != blue)
  setColor(i-1, j-1) = blue;
  a = findWord(A, i-1, j-1, str, k+1);

 if(A[i-1][j] == str[k] && getColor(i-1, j) != blue)
 setColor(i-1, j) = blue;
  a = findWord(A, i-1, j, str, k+1);

 if(A[i-1][j+1] == str[k] && getColor(i-1, j+1) != blue)
  setColor(i-1, j+1) = blue;
  a = findWord(A, i-1, j+1, str, k+1);

 if(A[i][j-1] == str[k] && getColor(i, j-1) != blue)
 setColor(i, j-1) = blue;
  a = findWord(A, i, j-1, str, k+1);

 if(A[i][j+1] == str[k] && getColor(i, j+1) != blue)
  setColor(i, j+1) = blue;
  a = findWord(A, i, j+1, str, k+1);

  if(A[i+1][j-1] == str[k] && getColor(i+1, j-1) != blue)
  setColor(i+1, j-1) = blue;
  a = findWord(A, i+1, j-1, str, k+1);

  if(A[i+1][j] == str[k] && getColor(i+1, j) != blue)
  setColor(i+1, j) = blue;
  a = findWord(A, i+1, j, str, k+1);

  if(A[i+1][j+1] == str[k] && getColor(i+1, j+1) != blue)
   setColor(i+1, j+1) = blue;
   a = findWord(A, i+1, j+1, str, k+1);

  if(!a)  setColor(i, j) = black;

  return a;
}

This is a pseudo code. I haven't considered the boundary cases to make it
understandable.



On Mon, Sep 19, 2011 at 12:21 AM, vikas  wrote:

> hmm, nice questions, can we create an  efficient DS to query the
> strings ??
>
>
> tried using trie but memory prints are very large ( O(n^2) )? :-((
>
>
>
> On Sep 18, 12:59 pm, Anup Ghatage  wrote:
> > For the mentioned scenario, it seems to be the only feasible solution.
> >
> > On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana <
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > bagana.bharatku...@gmail.com> wrote:
> > > @anup : the time complexity will be very high ...
> O(n*M*M)...n=#characters
> > > to be checked...M=size of the matrix ...
> >
> > > On Sat, Sep 17, 2011 at 8:30 AM, Anup Ghatage 
> wrote:
> >
> > >> As WgpShashank once pointed out.
> >
> > >> Search the whole matrix for the first character instances, for each
> > >> instance, send the array, string and that char's position to a
> function that
> > >> will recursively check its direct neighbors for the next character.
> > >> Exhaustively check like that for each starting characters appearance
> till
> > >> you find the string, if any.
> >
> > >> On Fri, Sep 16, 2011 at 11:55 PM, Ankur Garg  >wrote:
> >
> > >>> In a matrix of. characters, find an string. String can be in any way
> (all
> > >>> 8 neighbours to be considered)
> > >>> like find Microsoft in below matrix.
> >
> > >>>  A
> > >>> C
> > >>> P
> > >>> *R
> > >>> *C*
> > >>> *X
> > >>> *S
> > >>> **O
> > >>> *P
> > >>> *C*
> > >>> V
> > >>> *O*
> > >>> V
> > >>> N
> > >>> *I*
> > >>> W
> > >>>  G
> > >>> *F
> > >>> **M
> > >>> *N
> > >>> Q
> > >>>  A
> > >>> *T*
> > >>> I
> > >>> T
> >
> > >>>  *Any Ideas How to Solve/Approach this problem ?*
> >
> > >>>  --
> > >>> 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.
> >
> > >> --
> > >> Anup Ghatage
> >
> > >>  --
> > >> 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.
> >
> > > --
> >
> > > **Please do not print this e-mail until urgent requirement. Go Green!!
> > > Save Papers <=> Save Trees
> > > *BharatKumar Bagana*
> > > **http://www.google.com/profiles/bagana.bharatkumar<
> http://www.google.com/profiles/bagana.bharatkumar>
> > > *
> > > Mobile +91 8056127652*
> > > 
> >
> > >  --
> > > 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.
> >
> > --
> > Anup Ghatage
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeek

Re: [algogeeks] Array ques based on correlation factor

[Piyush Grover]

=>Take a function rand() which returns value between [0, 1) uniformly or use
function rand(n) = n*rand() which return value between 0- (n-1) using
uniform probability distribution.
=>Now create a array A[0..n-1] = [0..n-1]
 now rake an array R.

k = n;
for(i = 0; i < n; i++){
 a = rand(k);
 R.push(A[a]);
 swap(A[a], A[k-1]);
 k--;
}
return(R);


Verification:

1.) Yes, R contains values between 0-n-1;

2.) Yes, R has no repeated numbers

3.) R can be filled in O(n) so yes deterministic time.

4.) Correlation factor: Selection of one number should not affect the
probability of selecting other number.

here correlation factor = 0;

for each location 0..n-1 the probability of putting any number is 1/n.

->At 0th index probability of putting a number say, x is: 1/n
->at 1st index probability of putting a number y is: (n-1)/n *  1/(n-1) =
1/n
->at 2nd index probability of putting a number z is: (n-1)/n *(n-2)/(n-1) *
1/(n-2) = 1/n

and so on. So selection of any number at any position is independent of any
number being selected. So
they have independent and uniform probability.

-Piyush

On Sat, Sep 17, 2011 at 10:42 PM, sivaviknesh s wrote:

> Write a method fill up an array of size n - and returns the array to the
> caller - with the following conditions
>
> 1. the numbers shud be between 0 to n-1
> 2. no repeated numbers
> 3. the method should have a deterministic time to fill the arrays
> 4. arrays returned from the method should have low-correlation factor
>
> ...btw what does 4 th point mean? what is a correlation factor?? Plz
> provide code and explain...
>
>
> --
> Regards,
> $iva
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Math Puzzle

[Piyush Grover]

@abhinav...

it's not about being over smart or to show someone or to prove someone
anything. It's just that
you should not take any assumptions by yourself or if you do you should
specify clearly.
If u r asked this question in an interview and you give the answer 3 without
telling your assumption, u r done!!

And if you are living in the programming world, you need to take care of all
the possible scenarios otherwise u will end up throwing exceptions and
segmentation faults.


On Thu, Sep 15, 2011 at 10:32 PM, Don  wrote:

> Right, and in every proof above, at some point there is a possible
> division by zero. Therefore the proof is not valid in cases where R or
> P or Q are zero, and there are infinitely many such cases.
> The problem states P+Q+R=0 as the only constraint. There are
> infinitely many cases which fit that constraint where the expression
> is not equal to 3.
> Don
>
> On Sep 15, 11:57 am, abhinav gupta  wrote:
> > u cnt divide a number by 0..that thing is self undrstod,,,,
> >
> > On Thu, Sep 15, 2011 at 9:49 AM, Piyush Grover <
> piyush4u.iit...@gmail.com>wrote:
> >
> >
> >
> > > Don is right
> >
> > > if R = 0, P = 1 and Q = -1 then the given expression is UNDEFINED!!!
> >
> > > On Thu, Sep 15, 2011 at 10:16 PM, abhinav gupta <
> guptaabhinav...@gmail.com
> > > > wrote:
> >
> > >> Shut up...its 3,,
> >
> > >> On Thu, Sep 15, 2011 at 9:43 AM, Don  wrote:
> >
> > >>> It might be 3, but it doesn't have to be 3.
> > >>> Don
> >
> > >>> On Sep 14, 11:56 pm, NAGARAJAN SIVARAMAN  wrote:
> > >>> > if P+Q+R= 0  then P2 /QR  + Q2/PR + R2/PQ = ??
> >
> > >>> > how to solve this??
> >
> > >>> --
> > >>> 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.
> >
> > >> --
> > >> @ |3  # ! /\/ @ \./
> >
> > >>  --
> > >> 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.
> >
> > --
> > @ |3  # ! /\/ @ \./
>
> --
> 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: Math Puzzle

[Piyush Grover]

Don is right

if R = 0, P = 1 and Q = -1 then the given expression is UNDEFINED!!!



On Thu, Sep 15, 2011 at 10:16 PM, abhinav gupta
wrote:

> Shut up...its 3,,
>
>
> On Thu, Sep 15, 2011 at 9:43 AM, Don  wrote:
>
>> It might be 3, but it doesn't have to be 3.
>> Don
>>
>> On Sep 14, 11:56 pm, NAGARAJAN SIVARAMAN  wrote:
>> > if P+Q+R= 0  then P2 /QR  + Q2/PR + R2/PQ = ??
>> >
>> > how to solve this??
>>
>> --
>> 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.
>>
>>
>
>
> --
> @ |3  # ! /\/ @ \./
>
>  --
> 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] ms question

[Piyush Grover]

A can remain same in following cases:
-> If m, n are equal in all the N iterations
-> if m, n are equal in N-2 iterations but in 1 iteration m and n both are
different in that case there should be one iteration where m and n should be
same as the previous
iteration so that they are swapped again to the same position.

In the similar fashion if you think, the pairwise similar iteration should
be there.
Now, if in all N iterations probability that m = n is: (N/N*N) *
(1/N)*...(1/N) = (1/N)^N
two of the iterations have different m and n then probability is: NC2 *
(1/N)^(N-2) * {(1 - 1/N)* 1/NC2} = NC2 * (1/N)^N * 2
similarly, four of the iterations have different m and n then probability
NC4 * (1/N)^(N-4) *{(1 - 1/N) * 1/NC2}^2 = NC4 * (1/N)^N * 2^2

-Piyush

On Mon, Sep 12, 2011 at 10:24 PM, payal gupta  wrote:

> @piyush..
> cud u plzz..xplain...n elaborate
>
> Regards,
>
> Payal Gupta
>
>
> On Mon, Sep 12, 2011 at 10:15 PM, Piyush Grover  > wrote:
>
>> Sry i was little wrong:
>>
>> nC0*(1/n)^n + nC2 *2*(1/n)^n + nC4*2^2*(1/n)^n++nCn*2^(n/2)*(1/n)^n
>> when n is even
>>
>> nC0*(1/n)^n + nC2 *2*(1/n)^n +
>> nC4*2^2*(1/n)^n++nCn-1*2^(n-1/2)*(1/n)^n   when n is odd
>>
>>
>> On Mon, Sep 12, 2011 at 10:08 PM, Piyush Grover <
>> piyush4u.iit...@gmail.com> wrote:
>>
>>> it should be:
>>>
>>> (1/n)^n * (1 + 2 + 2^2 + 2^3 +(n/2)+1 terms) = {2^(1 + n/2) -
>>> 1}*(1/n)^n   when n even
>>>
>>> (1/n)^n * (1 + 2 + 2^2 + 2^3 +(n-1/2)+1 terms) = {2^(1 + (n-1)/2)  -
>>> 1}*(1/n)^n   when n is odd
>>>
>>>
>>> -Piyush
>>>
>>>
>>> On Mon, Sep 12, 2011 at 8:01 PM, sandeep nagamalli >> > wrote:
>>>
>>>> I think it is 1 / (2N)
>>>>
>>>> (1/N) * (1/N)*(N/2) = 1/(2N)
>>>>
>>>>
>>>> On Mon, Sep 12, 2011 at 6:33 PM, Akash Mukherjee wrote:
>>>>
>>>>> this is a case, but isnt der a case of circular permutation 2??
>>>>> what say abt dis
>>>>> 0,1
>>>>> 2,3
>>>>> 4,5
>>>>> 0,1
>>>>> 2,3
>>>>> 4,5
>>>>>
>>>>> it wrks i gues??
>>>>>
>>>>>
>>>>> On Mon, Sep 12, 2011 at 12:56 PM, teja bala >>>> > wrote:
>>>>>
>>>>>>
>>>>>>
>>>>>> I think it is 1/N
>>>>>>
>>>>>>  let N=6 that means rand(6)= takes values 0-5 i.e 6 values.
>>>>>> rand(m)=6 values
>>>>>> rand(n)=6 values
>>>>>> total combinations 6*6=36 values set but among dem array will change
>>>>>> only for
>>>>>> (0,0)(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)=6values of N
>>>>>>
>>>>>> So 6/36=1/6
>>>>>>
>>>>>> If we generalize it 1/N
>>>>>>
>>>>>> correct me if i'm wrong?
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>> For more options, visit this group at
>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>
>>>>>
>>>>>  --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Thanks&Regards:
>>>> -sandeep
>>>>
>>>>
>>>>  --
>>>> 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] ms question

[Piyush Grover]

Sry i was little wrong:

nC0*(1/n)^n + nC2 *2*(1/n)^n + nC4*2^2*(1/n)^n++nCn*2^(n/2)*(1/n)^n
when n is even

nC0*(1/n)^n + nC2 *2*(1/n)^n +
nC4*2^2*(1/n)^n++nCn-1*2^(n-1/2)*(1/n)^n   when n is odd

On Mon, Sep 12, 2011 at 10:08 PM, Piyush Grover
wrote:

> it should be:
>
> (1/n)^n * (1 + 2 + 2^2 + 2^3 +(n/2)+1 terms) = {2^(1 + n/2) -
> 1}*(1/n)^n   when n even
>
> (1/n)^n * (1 + 2 + 2^2 + 2^3 +(n-1/2)+1 terms) = {2^(1 + (n-1)/2)  -
> 1}*(1/n)^n   when n is odd
>
>
> -Piyush
>
>
> On Mon, Sep 12, 2011 at 8:01 PM, sandeep nagamalli 
> wrote:
>
>> I think it is 1 / (2N)
>>
>> (1/N) * (1/N)*(N/2) = 1/(2N)
>>
>>
>> On Mon, Sep 12, 2011 at 6:33 PM, Akash Mukherjee wrote:
>>
>>> this is a case, but isnt der a case of circular permutation 2??
>>> what say abt dis
>>> 0,1
>>> 2,3
>>> 4,5
>>> 0,1
>>> 2,3
>>> 4,5
>>>
>>> it wrks i gues??
>>>
>>>
>>> On Mon, Sep 12, 2011 at 12:56 PM, teja bala 
>>> wrote:
>>>
>>>>
>>>>
>>>> I think it is 1/N
>>>>
>>>>  let N=6 that means rand(6)= takes values 0-5 i.e 6 values.
>>>> rand(m)=6 values
>>>> rand(n)=6 values
>>>> total combinations 6*6=36 values set but among dem array will change
>>>> only for
>>>> (0,0)(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)=6values of N
>>>>
>>>> So 6/36=1/6
>>>>
>>>> If we generalize it 1/N
>>>>
>>>> correct me if i'm wrong?
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Thanks&Regards:
>> -sandeep
>>
>>
>>  --
>> 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] ms question

[Piyush Grover]

it should be:

(1/n)^n * (1 + 2 + 2^2 + 2^3 +(n/2)+1 terms) = {2^(1 + n/2) - 1}*(1/n)^n
  when n even

(1/n)^n * (1 + 2 + 2^2 + 2^3 +(n-1/2)+1 terms) = {2^(1 + (n-1)/2)  -
1}*(1/n)^n   when n is odd


-Piyush

On Mon, Sep 12, 2011 at 8:01 PM, sandeep nagamalli wrote:

> I think it is 1 / (2N)
>
> (1/N) * (1/N)*(N/2) = 1/(2N)
>
>
> On Mon, Sep 12, 2011 at 6:33 PM, Akash Mukherjee wrote:
>
>> this is a case, but isnt der a case of circular permutation 2??
>> what say abt dis
>> 0,1
>> 2,3
>> 4,5
>> 0,1
>> 2,3
>> 4,5
>>
>> it wrks i gues??
>>
>>
>> On Mon, Sep 12, 2011 at 12:56 PM, teja bala wrote:
>>
>>>
>>>
>>> I think it is 1/N
>>>
>>>  let N=6 that means rand(6)= takes values 0-5 i.e 6 values.
>>> rand(m)=6 values
>>> rand(n)=6 values
>>> total combinations 6*6=36 values set but among dem array will change only
>>> for
>>> (0,0)(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)=6values of N
>>>
>>> So 6/36=1/6
>>>
>>> If we generalize it 1/N
>>>
>>> correct me if i'm wrong?
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Thanks&Regards:
> -sandeep
>
>
>  --
> 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] What would be the ans.

[Piyush Grover]

it would be close to zero but not exactly zero.

On Sat, Sep 10, 2011 at 6:28 PM, Ishan Aggarwal <
ishan.aggarwal.1...@gmail.com> wrote:

> How u calculated this??
>
>
> On Sat, Sep 10, 2011 at 6:19 PM, Neha Singh wrote:
>
>> The correct ans is :
>> for right angled triangle :  0
>> for acute angled triangle : 1/2
>> for obtuse angled triangle : 1/2
>>
>> --
>> 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.
>>
>
>
>
> --
> Kind Regards
> Ishan Aggarwal
> [image: Aricent Group]
> Presidency Tower-A, M.G.Road,Sector-14
> Gurgaon,Haryana.122015 INDIA
> Phone : +91-9654602663
> ishan2.aggar...@aricent.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] What would be the ans.

[Piyush Grover]

no...it's close to zero but we can't compute it in terms of pi, R or so.

We need to get number of points on the perimeter which is not possible with
the standard method.

For the right-triangle. choose one random point and if second points is
diametric to the first point then
any third point on the circle will make it right triangle.
or any two points amongst the three are diametric then it will form a right
triangle.
So...P = 3C2/nC3

now n-> infinite

How to solve this??



On Sat, Sep 10, 2011 at 5:22 PM, Ishan Aggarwal <
ishan.aggarwal.1...@gmail.com> wrote:

> According to me, it should be 1/3 for each of the three options...
>
>
>
> On Sat, Sep 10, 2011 at 4:48 PM, Piyush Grover 
> wrote:
>
>> Sorry guys.. I was wrong, radius also matters here...
>>
>> still investigating
>>
>>
>> On Sat, Sep 10, 2011 at 3:56 PM, sarath prasath 
>> wrote:
>>
>>> @Piyush Grover:
>>> please explain ur answer
>>>
>>>
>>> On Sat, Sep 10, 2011 at 3:30 PM, Piyush Grover <
>>> piyush4u.iit...@gmail.com> wrote:
>>>
>>>> I got..
>>>>
>>>> 1.) 2/pi
>>>>
>>>> 2.) & 3.)  0.5 - (1/pi)
>>>>
>>>>
>>>> On Sat, Sep 10, 2011 at 2:47 PM, Ishan Aggarwal <
>>>> ishan.aggarwal.1...@gmail.com> wrote:
>>>>
>>>>> three points are randomly chosen on a circle.what the probability that
>>>>> 1.triangle formed is right angled triangle.
>>>>> 2.triangle formed is acute angled triangle.
>>>>> 3.triangle formed is obtuse angled triangle.
>>>>>
>>>>>
>>>>> --
>>>>> Kind Regards
>>>>> Ishan Aggarwal
>>>>> Phone : +91-9654602663
>>>>>
>>>>>
>>>>>  --
>>>>> 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.
>>
>
>
>
> --
> Kind Regards
> Ishan Aggarwal
> [image: Aricent Group]
> Presidency Tower-A, M.G.Road,Sector-14
> Gurgaon,Haryana.122015 INDIA
> Phone : +91-9654602663
> ishan2.aggar...@aricent.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] What would be the ans.

[Piyush Grover]

Sorry guys.. I was wrong, radius also matters here...

still investigating

On Sat, Sep 10, 2011 at 3:56 PM, sarath prasath wrote:

> @Piyush Grover:
> please explain ur answer
>
>
> On Sat, Sep 10, 2011 at 3:30 PM, Piyush Grover 
> wrote:
>
>> I got..
>>
>> 1.) 2/pi
>>
>> 2.) & 3.)  0.5 - (1/pi)
>>
>>
>> On Sat, Sep 10, 2011 at 2:47 PM, Ishan Aggarwal <
>> ishan.aggarwal.1...@gmail.com> wrote:
>>
>>> three points are randomly chosen on a circle.what the probability that
>>> 1.triangle formed is right angled triangle.
>>> 2.triangle formed is acute angled triangle.
>>> 3.triangle formed is obtuse angled triangle.
>>>
>>>
>>> --
>>> Kind Regards
>>> Ishan Aggarwal
>>> Phone : +91-9654602663
>>>
>>>
>>>  --
>>> 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] What would be the ans.

[Piyush Grover]

I got..

1.) 2/pi

2.) & 3.)  0.5 - (1/pi)

On Sat, Sep 10, 2011 at 2:47 PM, Ishan Aggarwal <
ishan.aggarwal.1...@gmail.com> wrote:

> three points are randomly chosen on a circle.what the probability that
> 1.triangle formed is right angled triangle.
> 2.triangle formed is acute angled triangle.
> 3.triangle formed is obtuse angled triangle.
>
>
> --
> Kind Regards
> Ishan Aggarwal
> Phone : +91-9654602663
>
>
>  --
> 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: worst case complexity

[Piyush Grover]

O(n^4)

Just think...
  for(i = 0; i < n; i++)
 for(j = 0; j < i; j++)

 has Time Complexity O(n^2)

then how come for(i = 0; i < n; i++)
  for(j=0; jwrote:

> i==>n
> j==>i*i= n*n
> k==>j=i*i=n*n   so total i*j*k=n^5
>
> --
> 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/-/jv1X4YzDp_sJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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]

[Piyush Grover]

pseudo algo:

=>array idx[0...k-1]  indicates the current pointer position in the ith
stream(initialized to 0).
=>heap tree of size k where each node stores value of the data and value of
stream which the node belongs to.

do{
   for all i = 0:k-1
  =>insert idx[i] value of ith stream to the heap

   =>take the root element of the heap and put it in the output stream.
   =>idx[m]++ where m is the stream value stored at the root.

} while(true);



On Sat, Sep 10, 2011 at 12:15 AM, aditya kumar  wrote:

> Given k sorted streams where each stream could possibly be infinite in
> length, describe an efficient algorithm to merge the k streams into a new
> stream (also in sorted order).
>
> --
> 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] sorting

[Piyush Grover]

It depends on the use cases.

If you have less elements of order of( say 100) then even insertion sort can
be a better choice. It's in-place sorting algo and can
perform sorting as it receives the elements like a stream.

If you have large number of elements and all the elements can't be
accommodated in the system memory together than merge sort is the only
best choice.

If you  have large number of elements and can be accommodated  in the memory
together then on an average quicksort is what you should look at.



On Thu, Sep 8, 2011 at 11:22 PM, praveen raj  wrote:

> Merge sort
> Quicksort--number of comparisons and exchanges lesser than heapsort...if
> worst case not occurs...
>
>
>  --
> 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] answer these interesting questions

[Piyush Grover]

4) a and b

On Thu, Sep 8, 2011 at 12:08 AM, Piyush Grover wrote:

> 1.)a
> 2.)b
> 3.)b
> 4)b
>
>
> On Wed, Sep 7, 2011 at 11:08 PM, Mani Bharathi wrote:
>
>> “Kya-Kya” is an island inhabitants of which always answer any question
>> with two
>> answers , one of which is true and the other is false .
>>
>> 1.You are walking on a road and came to a park . You ask the inhabitants
>> Ram , Laxman and Lila , “which road will
>> take me to the village ?”Ram says “I never speak to strangers . I am new
>> to these parts .”Laxman says,”I am married
>> to Lila . Take the left road .”Lila says “I am married to Ram . He is not
>> new in these place .”Which of the following is
>> true ?(a)Left road takes you to the village(b)Right road takes you to the
>> village(c)Lila is married to Laxman.(d)none.
>>
>> 2.You find that your boat is stolen . You question three inhabitants of
>> the island and reply as follows . John saya “I
>> didn’t do it . Mathew did not do it .”Mathew says “I did not do it .
>> Krishna did not do it .”Krishna says “I did not do
>> it . I do not know who did it .” Who stole your boat ?
>> (a)John(b)Mathew(c)Krishna(d)All three (e)none.
>>
>> 3.You want to speak to the chief of the village . You question three
>> inhabitants Amar , Bobby and Charles . Only
>> Bobby is wearing a red shirt . Amar says “I am not Bobby’s son .The chief
>> wears a red shirt.”Bobby says “I am
>> Amar’s father . Charles is the chief.”Charles says “The chief is one among
>> us . I am the chief .”Who is the chief?
>> (a)Amar(b)Bobby(c)Charles(d)None.
>>
>> 4.There is only one pilot in the island.You interview three men:Koik,lony
>> and Mirna.You also notice that Koik is
>> wearing a cap.Mirna says “Lony’s father is the pilot.Lony is not the
>> priest’s son.”Koik says “I am the pilot.On this
>> island only priests can wear cap.”Lony says “I am the priest’s son.Koik is
>> not the priest .”Which of the following is
>> true?(a)Lony is not Koik’s son(b)Koik is the pilot(c)Mirna is the
>> pilot(d)Lony is the priest.
>>
>> --
>> 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/-/QsepdSoM9esJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] answer these interesting questions

[Piyush Grover]

1.)a
2.)b
3.)b
4)b


On Wed, Sep 7, 2011 at 11:08 PM, Mani Bharathi wrote:

> “Kya-Kya” is an island inhabitants of which always answer any question with
> two
> answers , one of which is true and the other is false .
>
> 1.You are walking on a road and came to a park . You ask the inhabitants
> Ram , Laxman and Lila , “which road will
> take me to the village ?”Ram says “I never speak to strangers . I am new to
> these parts .”Laxman says,”I am married
> to Lila . Take the left road .”Lila says “I am married to Ram . He is not
> new in these place .”Which of the following is
> true ?(a)Left road takes you to the village(b)Right road takes you to the
> village(c)Lila is married to Laxman.(d)none.
>
> 2.You find that your boat is stolen . You question three inhabitants of the
> island and reply as follows . John saya “I
> didn’t do it . Mathew did not do it .”Mathew says “I did not do it .
> Krishna did not do it .”Krishna says “I did not do
> it . I do not know who did it .” Who stole your boat ?
> (a)John(b)Mathew(c)Krishna(d)All three (e)none.
>
> 3.You want to speak to the chief of the village . You question three
> inhabitants Amar , Bobby and Charles . Only
> Bobby is wearing a red shirt . Amar says “I am not Bobby’s son .The chief
> wears a red shirt.”Bobby says “I am
> Amar’s father . Charles is the chief.”Charles says “The chief is one among
> us . I am the chief .”Who is the chief?
> (a)Amar(b)Bobby(c)Charles(d)None.
>
> 4.There is only one pilot in the island.You interview three men:Koik,lony
> and Mirna.You also notice that Koik is
> wearing a cap.Mirna says “Lony’s father is the pilot.Lony is not the
> priest’s son.”Koik says “I am the pilot.On this
> island only priests can wear cap.”Lony says “I am the priest’s son.Koik is
> not the priest .”Which of the following is
> true?(a)Lony is not Koik’s son(b)Koik is the pilot(c)Mirna is the
> pilot(d)Lony is the priest.
>
> --
> 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/-/QsepdSoM9esJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Element in Array Repeated Even Number of Times

[Piyush Grover]

i don't think it's of O(n)

for even it's actually easy. Take the xor of all the elements you will left
with the element which appears odd number of times. O(n)
but for the odd case, we need to use extra space. Use hash map to keep the
count of each number and
take the odd one out, i mean the even one.


On Wed, Sep 7, 2011 at 11:06 PM, Rahul Thankachan wrote:

>
>
> On Sep 7, 12:43 pm, Sandy  wrote:
> > You have an array in which every number is repeated odd number of times
> > except one.  Write a function to find that one element in O(n) time.
> >
> > --
> >
> > *Sandeep Kumar,*
> >  ( Mobile+91-9866507368begin_of_the_skype_highlighting
> +91-9866507368
> >
> > *“I believe in smart work, Believe Me”*
>
>
> sry i made the logic for the opp for even instead..u just need to
> change sm values...u will get it :):) its simple..
>
> --
> 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] Objective Question

[Piyush Grover]

Option a) i didn't understand properly, please elaborate!!

Option b) certainly yes.

Option c) No (remember, the size of the table is subjective)

Option d) yes (use index on the column used in the where clause)



On Wed, Sep 7, 2011 at 8:58 PM, Mani Bharathi wrote:

> when is index of a table used?
>
> a)when table is less range of values
> b)when table is used frequently
> c) when the table is small
> d)when we use join statement with select and where clause.
>
>  --
> 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/-/vtHvd8sE1AUJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Please provide Code to Find kth Smallest or kth Largest element in unsorted array in liner time ?

[Piyush Grover]

this can be done using heap tree data structure.

-create a max heap tree of first k elements (for finding kth min)
 -keep on adding elements in the heap
if the root element is greater than the current element, remove root element
and insert the current element in the tree
once done with n elements
the root element will give the kth min element.
Time complexity: O(nlogk)
This method is very much effective for k << n (when k is a constant)

Same can be done for kth max.

On Tue, Sep 6, 2011 at 9:00 PM, Shravan Kumar  wrote:

>
> http://jonah.cs.elon.edu/sduvall2/courses/csc331/2006spring/Lectures/Order_statistics.ppt
>
>
> On Tue, Sep 6, 2011 at 7:53 PM, yamini gupta 
> wrote:
>
>> partition the array using quick sort
>> and find the kth smallest or largest number
>>
>>
>> On Sep 6, 12:20 am, learner  wrote:
>> > @Dave,All So Can Anyone Provide The Working Code in Linear Time for
>> > the same ?
>> >
>> > Thanks
>> >
>> > On Sep 5, 6:41 pm, Dave  wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > @Sachin: Correct: in one quicksort pivoting pass, the array is
>> > > rearranged so that the pivot element is put in the correct spot, with
>> > > larger elements on the right and smaller ones on the left. Now, if the
>> > > pivot, a[p], is at location k, i.e. p = k, then you are done. If not,
>> > > do another quicksort on the correct side of p; i.e., either on a[0] to
>> > > a[p-1] or on a[p+1] to a[n-1], depending on whether k is less than p
>> > > or greater than p.
>> >
>> > > Dave
>> >
>> > > On Sep 5, 1:27 am, sachin goyal  wrote:
>> >
>> > > > PLEASE TELL ME HOW WE CAN USE QUICK SORT TO FIND THE ELEMENT
>> > > > BECAUSE IN QUICK SORT ONE ELEMENT IN SHIFT IN ITS RIGHT POSITION ALL
>> LEFTS
>> > > > ARE SMALLER AND ALL RIGHT ARE BIG
>> >
>> > > > On Mon, Sep 5, 2011 at  POSIT11:55 AM, sachin goyal
>> > > > wrote:
>> >
>> > > > > PLEASE TELL HOW
>> >
>> > > > > On Sun, Sep 4, 2011 at 7:23 PM, sarath prasath <
>> prasathsar...@gmail.com>wrote:
>> >
>> > > > >> another sol which i learned from my friend is
>> > > > >> think of heap sort...
>> >
>> > > > >> On Sun, Sep 4, 2011 at 6:28 PM, learner <
>> nimish7andr...@gmail.com> wrote:
>> >
>> > > > >>> something I Know using quick sort randomization function we can
>> find
>> > > > >>> kt smallest/largest in unsorted array , but i am not able to
>> write
>> > > > >>> code , please help me in this and provide the code for the
>> same.?
>> >
>> > > > >>> Thanks
>> > > > >>> Nimish K.
>> > > > >>> 1st Year
>> > > > >>> IITR
>> >
>> > > > >>> --
>> > > > >>> 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.-Hidequoted text -
>> >
>> > > > - Show quoted text -
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

[Piyush Grover]

it's a subjective question.

If you have 100GB of main memory and 2  GB of virtual memory and you are
running very light weight programs then
nothing will happen. The system memory has enough space to take care of all
the applications but if your system is heavily loaded with
processes then it would cause the issues of improper swapping of the
instructions under execution.For more details, go through it:

http://faq.programmerworld.net/ms_windows/virtual-memory.html

On Tue, Sep 6, 2011 at 6:27 PM, Aman Kumar  wrote:

> Hii
>
> what happen if " size of main memory is greater than size of virtual
> memory"?
>
> --
> 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] MS question

[Piyush Grover]

Here's the pseudo code. I hope it should work.


d =  (d[0]d[1])
m =  (m[0]m[1])
y =   (y[0]y[1]y[2]y[3])
dd = d;
mm = m;
yy = y;

while(1){
if (strcmp(concat(dd,mm), reverse(yy))
   return(dd,mm,yy)
else if(isValidDateMonth(yy[3]yy[2], yy[1]yy[0] ,yy){
   if(yy[3]yy[2] > d && yy[1]yy[0] >= m)
return(yy[3]yy[2], yy[1]yy[0], yy);
   else if(yy[1]yy[0] > m)
return(yy[3]yy[2], yy[1]yy[0], yy);
 }else if( !(01< yy[1]yy[0] <= 12) ){
 t = (int) (yy + 1000)/1000 ;
 yy[0] = t;
 yy[1] = 0;
yy[2] = 0;
yy[3] = 1;
return(10, strcat(0, t), yy);
}else{
numdays = getDays(yy[1]yy[0], yy);
if(yy[3]yy[2] > numDays)
   t = (yy+10)/10
   t *= 10;
   yy = t+1;
   mm = yy[1]yy[0];
   dd = yy[3]yy[2];
   }
}


isValidDateMonth(d, m, y){
if(m belongsTo(jan, mar, may, jul, aug, oct, dec) && 0 < d <= 31)
return true;
else if(m belongsTo(apr, jun, sep, nov) && 0 < d <=30)
return true;

else if(m belongsTo(feb)){
   if(0 < d <= 28)
   return true;
   else if(d == 29 && isLeapYear(y))
   return true
   else return false;
 }else
  return false;
}

getDays(m, y){

if(m belongsTo(jan, mar, may, jul, aug, oct, dec))
return 31;
else if(m belongsTo(apr, jun, sep, nov))
return 30;

else if(m belongsTo(feb)){
   if(isLeapYear(y))
   return 29;
   else return 28;
}


}
On Mon, Sep 5, 2011 at 11:50 PM, Piyush Grover wrote:

> One thing i would like to know is
>
> 01/02/2011 needs to be considered or 1/02/2011.
>
> thnx
>
>
> On Mon, Sep 5, 2011 at 11:48 PM, Neha Singh wrote:
>
>> @yogesh: its stiil not correct. There r many test cases where ur solution
>> will fail
>>
>> --
>> 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] MS question

[Piyush Grover]

One thing i would like to know is

01/02/2011 needs to be considered or 1/02/2011.

thnx

On Mon, Sep 5, 2011 at 11:48 PM, Neha Singh wrote:

> @yogesh: its stiil not correct. There r many test cases where ur solution
> will fail
>
> --
> 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 Max Sum Value Pairs

[Piyush Grover]

@Dave..:-O well catch...


On Sat, Sep 3, 2011 at 9:00 PM, Dave  wrote:

> @Piyush: Try your code with
>
> n = 10
> a[10] = {11,22,33,44,55,66,77,88,99,110}
> b[10] = {10,20,30,40,50,60,70,80,90,100}
>
> Your code gets
>
> (110, 100) = 210
> (110, 90) = 200
> (99, 100) = 199
> (110, 80) = 190
> (88, 100) = 188
> (110, 70) = 180
> (77, 100) = 177
> (110, 60) = 170
> (66, 100) = 166
> (110, 50) = 160
>
> but it should get
>
> (110, 100) = 210
> (110, 90) = 200
> (99, 100) = 199
> (110, 80) = 190
> (99, 90) = 189
> (88, 100) = 188
> (110, 70) = 180
> (99, 80) = 179
> (88, 90) = 178
> (77, 100) = 177
>
> It fails because, after choosing the first four pairs, it does not
> consider all three candidates, (110, 70) = 180, (99, 90) = 189, and
> (88, 100) = 188. It only looks at the first and last of these. Later
> on, it fails to consider (99, 80) = 179 and (88, 90) = 178.
>
> After you have chosen the maximum pair, every unused pair that is the
> last unused pair in both its row and column of the (implicit) n by n
> matrix of pairwise sums is a candidate. When you have chosen n-1
> pairs, there can be O(sqrt(n)) candidates for the last choice. You are
> considering only two of them.
>
> Dave
>
> On Sep 2, 3:09 pm, Piyush Grover  wrote:
> > if I have understood the question correctly then:
> >
> > a[n-1] + b[i] > a[j] + b[i] for all 0 <= j <  n-1
> > and a[j] + b[n-1] > a[j] + b[i] for all 0 <= i < n-1
> > therefore,
> >
> > i = j =n-1;
> > count = 1;
> > S[0] <-- (a[n-1], b[n-1])
> > p = a[n-1] + b[n-2];
> > q = a[n-2] + b[n-1]
> >
> > while(count < n){
> >
> > if(p > q){
> >  j--;
> >  S[count++] <-- (a[n-1], b[j]);
> > }else{
> > i--;
> > S[count++]  <-- (a[i], b[n-1]);
> > }
> >
> > p = a[n-1] + b[j-1];
> > q = a[i-1] + b[n-1];
> >
> > }
> >
> > Time complexity: O(n)  :  http://ideone.com/FXfVj
> >
> > On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank  >wrote:
> >
> >
> >
> > > @Dave Correct , Missed to Provide the Correct Time Complexity in Worst
> Case
> > > it Will be O(N^2) , as we need to find out n  such maximum pair , will
> think
> > > about O(N0) Algo, if able to do it, will post the Algo here
> >
> > > Thanks
> > > Shashank Mani
> > > Computer Science
> > > Birla Institute of Technology,Mesra
> >
> > >  --
> > > 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/-/a14Pj22tbJgJ.
> >
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

Re: [algogeeks] character count in array

[Piyush Grover]

use hashing u'll get O(1) space..
@rahul...why not??

On Sat, Sep 3, 2011 at 7:13 PM, priya ramesh  wrote:

> use hashing
>
> --
> 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 Max Sum Value Pairs

[Piyush Grover]

Since A(n) and B(n) are sorted so in the pair (a[i], b[j]) either i = n-1 or
j = n-1 or both.
1.) so the first element is (a[n-1], b[n-1])

2.) now, we have two numbers to compare p = a[n-1]+ b[n-2]  and q =
a[n-2]+b[n-1]

3.) if p>q then p = a[n-1]+b[n-3]
else q = a[n-3] + b[n-1]
and repeat in the similar fashion

The point to note is, either a's index is n-1 or b's index is n-1.

On Sat, Sep 3, 2011 at 10:18 AM, Siddhartha Banerjee <
thefourrup...@gmail.com> wrote:

> yeah piyush's solution seems correct to me... if current amx is from
> a[i],b[j], then next maximum can only be either of a[i-1],b[j] or
> a[i],b[j-1] continue!!!
>
>  --
> 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 Max Sum Value Pairs

[Piyush Grover]

if I have understood the question correctly then:

a[n-1] + b[i] > a[j] + b[i] for all 0 <= j <  n-1
and a[j] + b[n-1] > a[j] + b[i] for all 0 <= i < n-1
therefore,

i = j =n-1;
count = 1;
S[0] <-- (a[n-1], b[n-1])
p = a[n-1] + b[n-2];
q = a[n-2] + b[n-1]

while(count < n){

if(p > q){
 j--;
 S[count++] <-- (a[n-1], b[j]);
}else{
i--;
S[count++]  <-- (a[i], b[n-1]);
}

p = a[n-1] + b[j-1];
q = a[i-1] + b[n-1];

}
Time complexity: O(n)  :  http://ideone.com/FXfVj


On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank wrote:

> @Dave Correct , Missed to Provide the Correct Time Complexity in Worst Case
> it Will be O(N^2) , as we need to find out n  such maximum pair , will think
> about O(N0) Algo, if able to do it, will post the Algo here
>
> Thanks
> Shashank Mani
> Computer Science
> Birla Institute of Technology,Mesra
>
>  --
> 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/-/a14Pj22tbJgJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] SEEK advice very urgent

[Piyush Grover]

@Raj

I did two months summer internship there in tokyo. I did internship in
scotland also and what I can say comparing the two is
I got royale treatment in Japan. People are more keen about indians and
Indian culture but in UK no one bother for
you and the same I heard from friends who worked in the US.

@shady

Obviously, if two options are there Japan and the US then US is overall the
best option to choose considering
all the matters but Japan is not that behind in terms of living which is
mainly I guess the concern is for Raj.
Apart from that, the crime rate is almost zero in Japan as compare to the US
where you can't roam outside
in the night. But yeah, it totally depends on individual to individual which
to choose but what I look at is,
the current options.

@Raj

I can share the experience with you but it may be different for your case
because I spent only two months there
but what I can say is I enjoyed a lot and I wanted to spend more time there.
One thing you will have to consider
is that whether there's any bond or not. In the beginning a little problem
would definitely be there.


On Thu, Sep 1, 2011 at 3:52 PM, Neha Sharan  wrote:

>  how many students were selected from your college? they took written xam
> today in my college.
>
> On Thu, Sep 1, 2011 at 2:56 PM, shady  wrote:
>
>> plus japan is not that much good for indians as US."""' lmao, who told
>> you this ?
>> btw, which institute ?
>>
>> On Thu, Sep 1, 2011 at 12:37 PM, raj kumar wrote:
>>
>>> Hi friends,
>>>
>>> I have cleared the prior examination of Works application a japenese
>>> company which is offering a package of $7pannum in tokyo ,ther's
>>> high probability of getting selected in interview but as i hav read
>>> tha cost of living in tokyo is too high plus japan is not that much
>>> good for indians as US.So please  give your valuable advice what
>>> should i do take this offer or reject by remainig silent in the
>>> interview, also if  this company  selects me i will not be able to sit
>>> in any ohter company bcoz of the placement policies of my college ,
>>> please help  ...
>>> if you have any relative in japan kindly ask them please
>>>
>>> thanks
>>>
>>> --
>>> 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] SEEK advice very urgent

[Piyush Grover]

@Raj

>From my personal experience I can just say, being an Indian you will get
more respect in Japan rather in the US.
The problem you may face is the language and the food. If you are non veg,
well n good but if you are veg
you will have to cook it by yourself, there are indian curry restaurants but
li'l expensive and going there on a
regular basis will make you feel bored.
Accommodation is little expensive but the kind of package you are getting
you don't need to worry.

The technology and all, you must be aware of. I don't think if it's worth
mentioning here.

You don't need to think much, just go ahead. All the best


On Thu, Sep 1, 2011 at 1:09 PM, vaibhav shukla wrote:

> if there is no bond then u must go... after all its money and technology
> for which japan is good..
> gud luck
>
>
> On Thu, Sep 1, 2011 at 12:39 PM, rahul sharma wrote:
>
>> salary is good...u can gobe with in technology with japannn..gud
>> luck
>>
>>
>>  On Thu, Sep 1, 2011 at 12:37 PM, raj kumar wrote:
>>
>>> Hi friends,
>>>
>>> I have cleared the prior examination of Works application a japenese
>>> company which is offering a package of $7pannum in tokyo ,ther's
>>> high probability of getting selected in interview but as i hav read
>>> tha cost of living in tokyo is too high plus japan is not that much
>>> good for indians as US.So please  give your valuable advice what
>>> should i do take this offer or reject by remainig silent in the
>>> interview, also if  this company  selects me i will not be able to sit
>>> in any ohter company bcoz of the placement policies of my college ,
>>> please help  ...
>>> if you have any relative in japan kindly ask them please
>>>
>>> thanks
>>>
>>> --
>>> 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.
>>
>
>
>
> --
>   best wishes!!
> Vaibhav
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: microsoft interview

[Piyush Grover]

What's wrong with this??

for( i = 0 ; i < n ; ++i )
   for( j = 0 ; j < m ; ++j )
   if( a[i][j] != 0 )
   a[i][0] = a[0][j] = 1;
for( i = 0 ; i < n ; ++i )
   for( j = 0 ; j < m ; ++j )
   if( a[i][0] + a[0][j] != 0 )
   a[i][j] = 1;

On Thu, Sep 1, 2011 at 5:45 AM, Dave  wrote:

> @Replying to my own posting: Propagating a[0][0] as in my most recent
> post isn't correct. Gene is correct to have two flags that indicate
> whether the first row and/or the first column are to be filled with
> 1s.
>
> Dave
>
> On Aug 31, 7:01 pm, Dave  wrote:
> > @Icy: I forgot about a[0][0]. So I need to add a few lines at the end
> > of my code, so that it becomes:
> >
> > for( i = 1 ; i < n ; ++i )
> > for( j = 1 ; j < m ; ++j )
> > if( a[i][j] != 0 )
> > a[i][0] = a[0][j] = 1;
> > for( i = 1 ; i < n ; ++i )
> > for( j = 1 ; j < m ; ++j )
> > if( a[i][0] + a[0][j] != 0 )
> > a[i][j] = 1;
> > // the following added to propogate a[0][0], if necessary.
> > if( a[0][0] != 0 )
> > {
> > for( i = 1 ; i < n ; ++i )
> > a[i][0] = 1;
> > for( j = 1 ; j < m ; ++j )
> > a[0][j] = 1;
> >
> > }
> >
> > Dave
> >
> > On Aug 31, 5:12 pm, "icy`"  wrote:
> >
> >
> >
> > > Dave has a nice idea but I cant get it to work =/
> > > [[1, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 0]]   original matrix
> >
> > > [[1, 0, 1, 1], [1, 1, 1, 1], [0, 0, 1, 1]]   dave's
> > > [[1, 1, 1, 1], [1, 1, 1, 1], [1, 0, 1, 1]]   expected
> >
> > > Maybe I converted it wrong.   My method was basically the same as
> > > Anup's --
> > > 1st pass fill rows and convert 1's to 2's.
> > > 2nd pass check for 2's and fill those columns.
> >
> > > But complexity seems to be n*m*m  + n*m*n =  nm^2 + mn^2
> > > which is about   O(n^2 m^2) ?=/
> >
> > > I would like to get Dave's to work =P
> >
> > > On Aug 31, 1:47 pm, siva viknesh  wrote:
> >
> > > > @dave...additionally u ve to do this...checking the 1st row nd 1st
> > > > column...
> >
> > > >  if(a[0][0])
> > > >set both first row and first column;
> > > > else
> > > >for(i=1;i > > >   if(a[0][i])
> > > >   set first row;
> > > >   else
> > > >   set first column;
> >
> > > > On Aug 31, 10:34 pm, siva viknesh  wrote:
> >
> > > > > dave s algo is nice :)
> >
> > > > > On Aug 31, 10:09 pm, Dave  wrote:
> >
> > > > > > @Ashima: Scan all but the first row and the first column. If
> there is
> > > > > > a 1 in a row, set the first element of that row to 1. If there is
> a 1
> > > > > > in a column, set the first element of that column to zero. Now,
> set
> > > > > > any element in all but the first row and the first column of the
> > > > > > matrix that has a 1 it the first element of its row or a 1 in its
> > > > > > first element of its colunn to 1.
> >
> > > > > > Dave
> >
> > > > > > On Aug 31, 12:02 pm, "Ashima ."  wrote:
> >
> > > > > > > @dave wats d logic behind ur code
> >
> > > > > > > Ashima
> > > > > > > M.Sc.(Tech)Information Systems
> > > > > > > 4th year
> > > > > > > BITS Pilani
> > > > > > > Rajasthan
> >
> > > > > > > On Wed, Aug 31, 2011 at 9:05 AM, Dave 
> wrote:
> > > > > > > > @Manish:
> >
> > > > > > > > for( i = 1 ; i < n ; ++i )
> > > > > > > >for( j = 1 ; j < m ; ++j )
> > > > > > > >if( a[i][j] != 0 )
> > > > > > > >a[i][0] = a[0][j] = 1;
> > > > > > > > for( i = 1 ; i < n ; ++i )
> > > > > > > >for( j = 1 ; j < m ; ++j )
> > > > > > > >if( a[i][0] + a[0][j] != 0 )
> > > > > > > >a[i][j] = 1;
> >
> > > > > > > > Dave
> >
> > > > > > > > On Aug 31, 8:40 am, manish kapur 
> wrote:
> > > > > > > > > Input is a matrix of size n x m of 0s and 1s.
> >
> > > > > > > > > eg:
> > > > > > > > > 1 0 0 1
> > > > > > > > > 0 0 1 0
> > > > > > > > > 0 0 0 0
> >
> > > > > > > > > If a location has 1; make all the elements of that row and
> column = 1. eg
> >
> > > > > > > > > 1 1 1 1
> > > > > > > > > 1 1 1 1
> > > > > > > > > 1 0 1 1
> >
> > > > > > > > > Solution should be with Time complexity = O(n*m) and O(1)
> extra space
> >
> > > > > > > > --
> > > > > > > > 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.-Hidequotedtext-
> >
> > > > > > > - Show quoted text -- Hide quoted text -
> >
> > > - Show quoted text -- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group 

Re: [algogeeks] graph

[Piyush Grover]

loop within a loop, what exactly that means??
Nee to consider the planarity or two loops sharing common edge/s??


On Wed, Aug 31, 2011 at 8:46 PM, MAC  wrote:

> Q  The question asked in interview of a startup : suppose you have a graph
> as shown bellow : please see the attachment . The red dots are graph
> vertexes ( you can see 1 vertex alone , aloof )
>  so you can see there are 2 cycles one inside another . How will you find
> such a scenario in a graph i.e. a cycle within a cycle.
>
> When i couldn't answer he asked how will you find strongly conected
> components of a graph (since it was follow up it MIGHT be related to
> solution but thought its good to share )
>
>
> any thoughts on these 2 questions
> --
> thanks
> --mac
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] loop in link list

[Piyush Grover]

This is fine but adding a twist to it.
Find number of nodes which are not in the loop.

On Wed, Aug 31, 2011 at 6:27 PM, rahul sharma wrote:

> int loop(void *head1,void *head2)
> {
> //head1 and head2 initialized to start;
> while(head1!=NULL && head2!=NULL)
> {
> head1=head1->next;
> head2=head2->next->next;
> if(head1==head2)
> return 1;tehre is loop;
> }
> return 0;//no loop
> }
>
>
>
> hi guys is it corect for finding the loop...if any test case that wont
> works here plz tell...
>
> --
> 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 written test ques

[Piyush Grover]

#include 
#include 

typedef struct node{
struct node *next;
char *str;
}node;

node *M;

void swap(char *a, char *b){
  char t = *a;
  *a = *b;
  *b = t;
}

void add(char *str){

   if(M == NULL){
  M = (node *)malloc(sizeof(node));
  M->str = (char *)malloc(sizeof(char)*(strlen(str)+1));
  strcpy(M->str, str);
  M->next = NULL;
   }else{
 node *t = M;
 while(t->next != NULL){
t = t->next;
 }
 node *tmp = (node*)malloc(sizeof(node));
 tmp->str = (char *)malloc(sizeof(char)*(strlen(str)+1));
  strcpy(tmp->str, str);
  tmp->next = NULL;
 t->next = tmp;
   }
}

void print(node *t){
   while(t != NULL){
  printf("%s", t->str);
  if(t->next != NULL)
 printf("->");
  t = t->next;
   }

}
void permute(char *str, int idx){
   char *word = str;

   if(strlen(word)-1 == idx){
  add(word);

   }else{
  int i;
  for(i = idx; i < strlen(word); i++){
 swap(&word[idx], &word[i]);
 permute(word, idx+1);
 swap(&word[i], &word[idx]);
  }
   }
}
main(){
   char str[10] = "123";
   int i =0;
   permute(str, 0);
   node *tmp = M;
   print(tmp);
}

On Tue, Aug 30, 2011 at 10:51 PM, Anup Ghatage  wrote:

> So, in short, find all permutations for a given string and create a linked
> list from them?
>
> --
> Anup Ghatage
>
>  --
> 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] affect of change

[Piyush Grover]

I think, it should be C & D;
a = i++ => a=i; i = i+1;
a = ++i; => i = i+1; a = i;

in similar fashion, D gets affected.

@ Raj...how come??

On Tue, Aug 30, 2011 at 8:11 PM, raj kumar  wrote:

> code becomes more efficient
>
> --
> 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: Custom Random Generator

[Piyush Grover]

@Prabhat

CustRand(n){

sum  = n*(n+1)/2;

a = rand(sum);
for(i = 1; i <= n; i++){
 h = i*(i+1)/2;
 l = i*(i-1)/2;
 if(a <= h && a > l)
 return i;
}

}


Take an example of say 4
so sum = 10

and a = 
therefore, if 0 < a <= 1 return 1 (only 1 case possible)
if 1 < a <= 3 return 2 (only 2 cases are possible)
if 3 < a <= 6 return 3 (only 3 cases are possible)
if 6 < a <= 10 return 4 (only 4 cases are possible)


On Tue, Aug 30, 2011 at 3:17 AM, Don  wrote:

> Here is how to do it with a single call to rand and no looping.
>
> int custRand(int n)
> {
>int a = rand(n*n+n);
>int b = a / n;
>a %= n;
>    return (b > a) ? n+a-b+1 : n-a+b;
> }
>
> On Aug 29, 10:48 am, Piyush Grover  wrote:
> > Given a function rand(n) which returns a random value between 1...n
> assuming
> > equal probability.
> > Write a function CustRand(n) using rand(n) which returns a value between
> > 1...n such that
> > the probability of occurrence of each number is proportional to its
> value.
> >
> > I have a solution but wondering if I can get better than this or some
> other
> > approaches:
> >
> > CustRand(n){
> >
> > sum  = n*(n+1)/2;
> >
> > a = rand(sum);
> > for(i = 1; i <= n; i++){
> >  h = i*(i+1)/2;
> >  l = i*(i-1)/2;
> >  if(a <= h && a > l)
> >  return i;
> > }
> >
> > }
>
> --
> 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 all the subsets whose sum <= k

[Piyush Grover]

http://mathoverflow.net/questions/57371/find-all-maximal-subsets-of-a-set-of-integers-whose-sum-does-not-exceed-a-number
actual question is this.

On Sat, Aug 27, 2011 at 9:56 AM, rahul sharma wrote:

> yeah i wen first post answer i said it is for finding sum=k;
> n just add one more condition in loop for finding  i.e. if(sub+a[i] return sub,a[i];
>
> is it fine nw?
>
> On Sat, Aug 27, 2011 at 7:55 AM, raj kumar wrote:
>
>> It's not knapsack in knapsack we find max or min subset here we have to
>> find all subsets <=k not just one which is min or max , so I guess we have
>> to form all subsets and check their sum hence the algoritm will be 0(2^n)
>> where n is number of elements in the set ,
>>
>> se correct me if i am wrong or a better solution exists
>>
>>
>> thanks
>>
>>  --
>> 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: Custom Random Generator

[Piyush Grover]

Total # of cases when a - b = 0; 5 return 5
Total # of cases when a-b = 1; 4   return 4
Total # of cases when a-b = 2; 3   return 3

Sorry, it is misleading...it should be

Total # of cases when a - b = 0; 5 return 5 is probable 5 times
Total # of cases when a-b = 1; 4   return 4 is probable 4 times
Total # of cases when a-b = 2; 3   return 3 is probable 3 times and so on...

On Mon, Aug 29, 2011 at 11:17 PM, Don  wrote:

> No, a+b-1 would return values outside of the desired range.
> Don
>
> On Aug 29, 12:26 pm, nishaanth  wrote:
> > @Don...Nice solution.. But the return statement should be a+b-1
> >
> >
> >
> > On Mon, Aug 29, 2011 at 10:33 PM, Don  wrote:
> > > If you draw the nxn grid and assign a value to each diagonal:
> >
> > > (For n = 5)
> >
> > >  --b
> > > |  12345
> > > |  2345
> > > |  345
> > > |  45
> > > |  5
> > > a
> >
> > > You want the result to be the orthogonal distance from the diagonal.
> > > That is what the formula computes.
> > > Don
> >
> > > On Aug 29, 11:28 am, Piyush Grover  wrote:
> > > > I understand what you are doing in the loop but return statement is
> not
> > > > clear to me. Can you explain.
> >
> > > > On Mon, Aug 29, 2011 at 9:48 PM, Don  wrote:
> > > > > int custRand(int n)
> > > > > {
> > > > >int a,b;
> > > > >do
> > > > >{
> > > > >a = rand(n);
> > > > >b = rand(n);
> > > > >} while(a < b);
> > > > >return n - a + b;
> > > > > }
> >
> > > > > On Aug 29, 10:48 am, Piyush Grover 
> wrote:
> > > > > > Given a function rand(n) which returns a random value between
> 1...n
> > > > > assuming
> > > > > > equal probability.
> > > > > > Write a function CustRand(n) using rand(n) which returns a value
> > > between
> > > > > > 1...n such that
> > > > > > the probability of occurrence of each number is proportional to
> its
> > > > > value.
> >
> > > > > > I have a solution but wondering if I can get better than this or
> some
> > > > > other
> > > > > > approaches:
> >
> > > > > > CustRand(n){
> >
> > > > > > sum  = n*(n+1)/2;
> >
> > > > > > a = rand(sum);
> > > > > > for(i = 1; i <= n; i++){
> > > > > >  h = i*(i+1)/2;
> > > > > >  l = i*(i-1)/2;
> > > > > >  if(a <= h && a > l)
> > > > > >  return i;
> > > > > > }
> >
> > > > > > }
> >
> > > > > --
> > > > > 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.
> >
> > --
> > S.Nishaanth,
> > Computer Science and engineering,
> > IIT Madras.
>
> --
> 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: Custom Random Generator

[Piyush Grover]

No...if a = b = 5 then return 9 doesn't make any sense.

n - (a-b) is very much fine.
for n = 5
Total # of cases when a - b = 0; 5 return 5
Total # of cases when a-b = 1; 4   return 4
Total # of cases when a-b = 2; 3   return 3
and so on.



On Mon, Aug 29, 2011 at 10:56 PM, nishaanth  wrote:

> @Don...Nice solution.. But the return statement should be a+b-1
>
>
> On Mon, Aug 29, 2011 at 10:33 PM, Don  wrote:
>
>> If you draw the nxn grid and assign a value to each diagonal:
>>
>> (For n = 5)
>>
>>  --b
>> |  12345
>> |  2345
>> |  345
>> |  45
>> |  5
>> a
>>
>> You want the result to be the orthogonal distance from the diagonal.
>> That is what the formula computes.
>> Don
>>
>> On Aug 29, 11:28 am, Piyush Grover  wrote:
>> > I understand what you are doing in the loop but return statement is not
>> > clear to me. Can you explain.
>> >
>> > On Mon, Aug 29, 2011 at 9:48 PM, Don  wrote:
>> > > int custRand(int n)
>> > > {
>> > >int a,b;
>> > >    do
>> > >{
>> > >a = rand(n);
>> > >b = rand(n);
>> > >} while(a < b);
>> > >return n - a + b;
>> > > }
>> >
>> > > On Aug 29, 10:48 am, Piyush Grover  wrote:
>> > > > Given a function rand(n) which returns a random value between 1...n
>> > > assuming
>> > > > equal probability.
>> > > > Write a function CustRand(n) using rand(n) which returns a value
>> between
>> > > > 1...n such that
>> > > > the probability of occurrence of each number is proportional to its
>> > > value.
>> >
>> > > > I have a solution but wondering if I can get better than this or
>> some
>> > > other
>> > > > approaches:
>> >
>> > > > CustRand(n){
>> >
>> > > > sum  = n*(n+1)/2;
>> >
>> > > > a = rand(sum);
>> > > > for(i = 1; i <= n; i++){
>> > > >  h = i*(i+1)/2;
>> > > >  l = i*(i-1)/2;
>> > > >  if(a <= h && a > l)
>> > > >  return i;
>> > > > }
>> >
>> > > > }
>> >
>> > > --
>> > > 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.
>>
>>
>
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
>
> --
> 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: Custom Random Generator

[Piyush Grover]

I understand what you are doing in the loop but return statement is not
clear to me. Can you explain.

On Mon, Aug 29, 2011 at 9:48 PM, Don  wrote:

> int custRand(int n)
> {
>int a,b;
>do
>{
>a = rand(n);
>b = rand(n);
>} while(a < b);
>return n - a + b;
> }
>
> On Aug 29, 10:48 am, Piyush Grover  wrote:
> > Given a function rand(n) which returns a random value between 1...n
> assuming
> > equal probability.
> > Write a function CustRand(n) using rand(n) which returns a value between
> > 1...n such that
> > the probability of occurrence of each number is proportional to its
> value.
> >
> > I have a solution but wondering if I can get better than this or some
> other
> > approaches:
> >
> > CustRand(n){
> >
> > sum  = n*(n+1)/2;
> >
> > a = rand(sum);
> > for(i = 1; i <= n; i++){
> >  h = i*(i+1)/2;
> >  l = i*(i-1)/2;
> >  if(a <= h && a > l)
> >  return i;
> > }
> >
> > }
>
> --
> 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] Custom Random Generator

[Piyush Grover]

Given a function rand(n) which returns a random value between 1...n assuming
equal probability.
Write a function CustRand(n) using rand(n) which returns a value between
1...n such that
the probability of occurrence of each number is proportional to its value.

I have a solution but wondering if I can get better than this or some other
approaches:

CustRand(n){

sum  = n*(n+1)/2;

a = rand(sum);
for(i = 1; i <= n; i++){
 h = i*(i+1)/2;
 l = i*(i-1)/2;
 if(a <= h && a > l)
 return i;
}

}

-- 
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: Some bit manipulation help

[Piyush Grover]

Nice one @Dave

On Sun, Aug 28, 2011 at 6:29 PM, Dave  wrote:

> @Nikhil: See http://groups.google.com/group/algogeeks/msg/2a9e07ee8ab71366
>
> Dave
>
> On Aug 28, 3:56 am, Nikhil Gupta  wrote:
> > Here is a small piece of program which counts the number of bits set in a
> > number. I found it online somewhere.
> > InputOutput00(000)52(101)73(111)
> >
> >   *int* CountBits (*unsigned* *int* x )
> >   {
> >   *static* *unsigned* *int* mask[] *=* { 0x,
> >   0x,
> >   0x0F0F0F0F,
> >   0x00FF00FF,
> >   0x  } ;
> >   *int* i ;
> >   *int* shift ; /* Number of positions to shift to right*/
> >  *for* ( i *=*0, shift *=*1; i *<* 5; i *++*, shift **=* 2)
> >   x *=* (x *&* mask[i ])*+* ( ( x *>>* shift) *&*
> mask[i]);
> >   *return* x;
> >   }
> >
> > Can anyone explain how this is working?
> >
> > --
> > Nikhil Gupta
> > Senior Co-ordinator, Publicity
> > CSI, NSIT Students' Branch
> > NSIT, New Delhi, India
>
> --
> 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: math puzzle

[Piyush Grover]

3x+4y = 60
it's a straight line equation whose x intercept is 20 and y intercept is 15.
Draw it in first quadrant
(as x, y are positive integers)
now x = (60 - 4y)/3 = 4(15-y)/3
now for y = 1, 2...15 you need to check whether (15-y) is divisible by 3 or
not. It's simple y = 3, 6, 9, 12

-Piyush

On Sun, Aug 28, 2011 at 6:38 PM, Dave  wrote:

> @Sivaviknesh: The smallest values of x and y are 1. The largest value
> of y is (60 - 3) / 4 = 14. Solve for x: x = (60 - 4y) / 3. Since x is
> an integer, 60 - 4y must be a multiple of 3. Since 60 - 3y is a
> multiple of 3, (60 - 4y) - (60 - 3y) = y must be a multiple of 3.
> Thus, y = 3, 6, 9, 12. Then you can solve for the corresponding values
> of x.
>
> Dave
>
> On Aug 28, 7:46 am, sivaviknesh s  wrote:
> > *Find the number of solutions for 3x+4y=60, if x and y are positive
> > integers.*
> >
> > Is there any standard method for solving these type of ques ..or only
> trial
> > and error ???
> >
> > --
> > Regards,
> > $iva
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: c program

[Piyush Grover]

yeah you can do that by opening the file and printing it but as far as I
know, interviewer adds the constraint of not using the file method.

On Sun, Aug 28, 2011 at 12:35 PM, rahul sharma wrote:

> this logic is ok...but we have pre defined everything in char f...if i
> add one or two more statements then it will require corresponding
> change in char *f...can i open the same file with f open n prin t it
> out?
>
> On Aug 28, 11:31 am, Piyush Grover  wrote:
> > char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";
> >
> > f is a global pointer to the char array which contains the string
> > "char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c"
> >
> > Now in main function you are printing this string with arguments
> 34,f,34,10.
> > ASCII value of " is 34.
> > ->So in f, the first %c is replaced by ".
> > ->The next %s is replaced by string f.
> > ->the second %c is replaced by " and
> > ->last %c is replaced by backspace. The last %c is actually I feel not
> > required. So the code can be:
> >
> >
> char*f="char*f=%c%s%c;main(){printf(f,34,f,34);}";main(){printf(f,34,f,34);
> }
> >
> > I hope it helps. Try to do it manually on paper. You would be able to
> > understand it.
> >
> > -Piyush
> >
> > On Sun, Aug 28, 2011 at 11:46 AM, rahul sharma  >wrote:
> >
> >
> >
> >
> >
> >
> >
> > > plz expalin char*f=""
> >
> > > On Aug 28, 11:12 am, Piyush Grover  wrote:
> > > > it's a quine problem.
> >
> > > > char*f="char*f=%c%s%c;
> > > > main(){
> > > > printf(f,34,f,34,10);}%c";
> >
> > > > main()
> > > > {
> > > > printf(f,34,f,34,10);
> >
> > > > }
> >
> > > > I have used whitespaces to make it understand.
> >
> > > > On Sun, Aug 28, 2011 at 11:39 AM, rahul sharma <
> rahul23111...@gmail.com
> > > >wrote:
> >
> > > > > program whose output is the program itself???
> >
> > > > > --
> > > > > 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: c program

[Piyush Grover]

char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";

f is a global pointer to the char array which contains the string
"char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c"

Now in main function you are printing this string with arguments 34,f,34,10.
ASCII value of " is 34.
->So in f, the first %c is replaced by ".
->The next %s is replaced by string f.
->the second %c is replaced by " and
->last %c is replaced by backspace. The last %c is actually I feel not
required. So the code can be:


char*f="char*f=%c%s%c;main(){printf(f,34,f,34);}";main(){printf(f,34,f,34);}

I hope it helps. Try to do it manually on paper. You would be able to
understand it.

-Piyush

On Sun, Aug 28, 2011 at 11:46 AM, rahul sharma wrote:

> plz expalin char*f=""
>
>
> On Aug 28, 11:12 am, Piyush Grover  wrote:
> > it's a quine problem.
> >
> > char*f="char*f=%c%s%c;
> > main(){
> > printf(f,34,f,34,10);}%c";
> >
> > main()
> > {
> > printf(f,34,f,34,10);
> >
> > }
> >
> > I have used whitespaces to make it understand.
> >
> > On Sun, Aug 28, 2011 at 11:39 AM, rahul sharma  >wrote:
> >
> >
> >
> >
> >
> >
> >
> > > program whose output is the program itself???
> >
> > > --
> > > 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] c program

[Piyush Grover]

it's a quine problem.

char*f="char*f=%c%s%c;
main(){
printf(f,34,f,34,10);
}%c";
main()
{
printf(f,34,f,34,10);
}

I have used whitespaces to make it understand.

On Sun, Aug 28, 2011 at 11:39 AM, rahul sharma wrote:

> program whose output is the program itself???
>
> --
> 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 ques :Online round

[Piyush Grover]

pardon 1 small mistake
instead of
if(i == 0 || i == n)
   return (lower, upper);

it should be

if(i == lower || i == upper)
   return (lower, upper);

On Sat, Aug 27, 2011 at 8:31 PM, Piyush Grover wrote:

> satisfy the point on lines, for point(x,y) to lie in between the two, the
> f(x,y) value would have different sign.
> This can be done using the binary search approach. Here is the pseudo code:
> f(x,y) = Ax + By - C
> (x0, y0)
> initial Call: SearchLines(f, n/2, 0, n);
> SearchLines(f, i, lower, upper){
>
> if(i == 0 || i == n)
>return (lower, upper);
>  if (f [i] (x0, y0)  < 0){
>lower = i;
>mid = (i + upper)/2;
>SearchLines(f, mid, lower, upper);
> }else if(f [i] (x0, y0)  > 0){
> upper = i;
> mid = (i+lower)/2;
> SearchLines(f, mid, lower, upper);
>
> }else{
>if(f [i+1] (x0,y0) < abs(f[i-1] (x0, y0)) )
>   return(i, i+1)
>else return(i-1, i);
>
>
> }
>
> }
>
> On Sat, Aug 27, 2011 at 5:59 PM, Piyush Grover 
> wrote:
>
>> I don't understand your point if y[i] < y[i+1]
>> how come the slope is positive?
>> It's just that the i'th line will lie under line i+1th line.
>>
>>
>>
>> On Sat, Aug 27, 2011 at 5:11 PM, monish001 wrote:
>>
>>> If I correctly understood the question, It says:
>>> 1. 0<= x[i] <=1 for all i and for all x of line i.
>>> 2. y[i]>>
>>> If line i is f(x,y): A[i]x + B[i]y -C[i], Use the following concept:
>>> 1. Find 1 line closest to the given point such that f(x,y) is of same
>>> sign for both (0,0) and given point.
>>> 2. Find other line closest to the given point such that f(x,y) is of
>>> opposite signs for both (0,0) and given point.
>>>
>>> To check which line is closest, use the formula which finds the
>>> (perpendicular) distance between the line and the point.
>>> I am not sure about the correctness of the following formula:
>>> If distance of x,y from ax+by=c is d.
>>>
>>> d = sqrt(2)*( (a*a + b*b - c) / (a-b) )
>>>
>>>
>>> -Monish
>>> On Aug 26, 6:19 am, Ankur Garg  wrote:
>>> > You are given n no. of lines in form of Ax + By = C, basically you are
>>> given
>>> > A[i], b[i] and C[i] for line "i".
>>> > Lines are given in a way such that 0 <= x[i] <= 1 and y[i] < y[i+1] for
>>> same
>>> > X.
>>> > Also, one point (x,y) is given too. Find out the two closest lines to
>>> the
>>> > point such that the point is between them.
>>> > Given: n - no. of lines
>>> > a[i] b[i] c[i] - i th line.
>>> > X Y - Point
>>> > Output
>>> > A[i] B[i] C[i]
>>> > A[j] B[j] C[j]
>>> > such that the point X,Y is between them.
>>>
>>> --
>>> 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 ques :Online round

[Piyush Grover]

satisfy the point on lines, for point(x,y) to lie in between the two, the
f(x,y) value would have different sign.
This can be done using the binary search approach. Here is the pseudo code:
f(x,y) = Ax + By - C
(x0, y0)
initial Call: SearchLines(f, n/2, 0, n);
SearchLines(f, i, lower, upper){

if(i == 0 || i == n)
   return (lower, upper);
 if (f [i] (x0, y0)  < 0){
   lower = i;
   mid = (i + upper)/2;
   SearchLines(f, mid, lower, upper);
}else if(f [i] (x0, y0)  > 0){
upper = i;
mid = (i+lower)/2;
SearchLines(f, mid, lower, upper);

}else{
   if(f [i+1] (x0,y0) < abs(f[i-1] (x0, y0)) )
  return(i, i+1)
   else return(i-1, i);

}

}

On Sat, Aug 27, 2011 at 5:59 PM, Piyush Grover wrote:

> I don't understand your point if y[i] < y[i+1]
> how come the slope is positive?
> It's just that the i'th line will lie under line i+1th line.
>
>
>
> On Sat, Aug 27, 2011 at 5:11 PM, monish001 wrote:
>
>> If I correctly understood the question, It says:
>> 1. 0<= x[i] <=1 for all i and for all x of line i.
>> 2. y[i]>
>> If line i is f(x,y): A[i]x + B[i]y -C[i], Use the following concept:
>> 1. Find 1 line closest to the given point such that f(x,y) is of same
>> sign for both (0,0) and given point.
>> 2. Find other line closest to the given point such that f(x,y) is of
>> opposite signs for both (0,0) and given point.
>>
>> To check which line is closest, use the formula which finds the
>> (perpendicular) distance between the line and the point.
>> I am not sure about the correctness of the following formula:
>> If distance of x,y from ax+by=c is d.
>>
>> d = sqrt(2)*( (a*a + b*b - c) / (a-b) )
>>
>>
>> -Monish
>> On Aug 26, 6:19 am, Ankur Garg  wrote:
>> > You are given n no. of lines in form of Ax + By = C, basically you are
>> given
>> > A[i], b[i] and C[i] for line "i".
>> > Lines are given in a way such that 0 <= x[i] <= 1 and y[i] < y[i+1] for
>> same
>> > X.
>> > Also, one point (x,y) is given too. Find out the two closest lines to
>> the
>> > point such that the point is between them.
>> > Given: n - no. of lines
>> > a[i] b[i] c[i] - i th line.
>> > X Y - Point
>> > Output
>> > A[i] B[i] C[i]
>> > A[j] B[j] C[j]
>> > such that the point X,Y is between them.
>>
>> --
>> 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 ques :Online round

[Piyush Grover]

I don't understand your point if y[i] < y[i+1]
how come the slope is positive?
It's just that the i'th line will lie under line i+1th line.


On Sat, Aug 27, 2011 at 5:11 PM, monish001  wrote:

> If I correctly understood the question, It says:
> 1. 0<= x[i] <=1 for all i and for all x of line i.
> 2. y[i]
> If line i is f(x,y): A[i]x + B[i]y -C[i], Use the following concept:
> 1. Find 1 line closest to the given point such that f(x,y) is of same
> sign for both (0,0) and given point.
> 2. Find other line closest to the given point such that f(x,y) is of
> opposite signs for both (0,0) and given point.
>
> To check which line is closest, use the formula which finds the
> (perpendicular) distance between the line and the point.
> I am not sure about the correctness of the following formula:
> If distance of x,y from ax+by=c is d.
>
> d = sqrt(2)*( (a*a + b*b - c) / (a-b) )
>
>
> -Monish
> On Aug 26, 6:19 am, Ankur Garg  wrote:
> > You are given n no. of lines in form of Ax + By = C, basically you are
> given
> > A[i], b[i] and C[i] for line "i".
> > Lines are given in a way such that 0 <= x[i] <= 1 and y[i] < y[i+1] for
> same
> > X.
> > Also, one point (x,y) is given too. Find out the two closest lines to the
> > point such that the point is between them.
> > Given: n - no. of lines
> > a[i] b[i] c[i] - i th line.
> > X Y - Point
> > Output
> > A[i] B[i] C[i]
> > A[j] B[j] C[j]
> > such that the point X,Y is between them.
>
> --
> 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: puzzle

[Piyush Grover]

Cut the rope in 50mtrs and 100mtrs length.

Make a small loop(of negligible length at one end of the 50 mtrs rope)

Tie the other end of the rope at the top and from the loop end side pass the
100mtrs rope
such that you have both the ends of 100mtrs rope in your end.

now get down at 100mtrs peg point(~50 + 50 = 100 mtrs).

Pull the 100 mtrs rope and tie it at the peg at 100mtrs height.

Get down to the bottom.


On Fri, Aug 26, 2011 at 7:29 PM, Himanshu Srivastava <
himanshusri...@gmail.com> wrote:

> lol :P
>
>
> On Wed, Aug 10, 2011 at 11:35 PM, $hr! k@nth  wrote:
>
>> Tie the rope at the top of the tower
>> Climb down with the help of the rope up to 100 mt peg possItion
>> Tie the rope to that peg, Climb up to the top of the tower with that rope.
>> Now release the rope at the top and hold it. It ll take you down.:P
>>
>>
>> On Wed, Aug 10, 2011 at 7:49 PM, varun pahwa wrote:
>>
>>> make two ropes 50m and 100 meter. make a loop kind of thing with that now
>>> you have two 50 mtr ropes so get down to 100 mtr point and tie loop rope in
>>> downward now cut the loop at 100 mtr you have 100 mtr rope then move down
>>> with the help of that. i hope i am clear.
>>>
>>>
>>> On Mon, Aug 8, 2011 at 1:52 PM, Shachindra A C wrote:
>>>
 tie the rope to the peg and hold the rope at a little less than 100m
 point. Then jump.


 On Mon, Aug 8, 2011 at 1:19 PM, Himanshu Srivastava <
 himanshusri...@gmail.com> wrote:

> @Dave oh i thought some logical concept willl be applied in that
> case...it is ok!!!
> thanks:)
>
>
> On Fri, Aug 5, 2011 at 1:47 AM, Dave  wrote:
>
>> @Himanshu: That is easy for any boy scout. :-) Tie the rope at the top
>> of the tower. Then tie a sheepshank knot of a comfortable length in
>> the rope and cut the middle strand inside the knot. Climb down the
>> rope to the peg and tie the other end of the rope onto the peg. Then,
>> while standing on or hanging from the peg, shake the upper rope to
>> release the sheepshank knot. The upper end will fall down and you can
>> climb the rest of the way down.
>>
>> Dave
>>
>>
>> On Aug 4, 1:50 pm, Himanshu Srivastava 
>> wrote:
>> > suppose u tie the rope at 200mt height and now climb down to 100m
>> > heightthen u tie the rope at that point then how will you open
>> the rope
>> > at point above 200mt where u have tied it earlier
>> >
>> >
>> >
>> > On Thu, Aug 4, 2011 at 11:15 PM, mohit verma 
>> wrote:
>> > > can't we tie the rope where we are standing (at height of 200
>> meter)?
>> >
>> > > On Thu, Aug 4, 2011 at 10:26 PM, neeraja marathe <
>> > > neeraja.marath...@gmail.com> wrote:
>> >
>> > >> this was the puzzle asked to me in NVIDIA interview:
>> > >> you are standing on top of a tower of ht 200 mt. .At 100 mt. ht .
>> from
>> > >> bottom of tower there is a peg where u can tie a rope. You have a
>> rope
>> > >> of length 150 mt. with you and using this rope you have to get
>> down
>> > >> the tower. you can not jump or there is nobody to help you. how
>> will u
>> > >> get down the tower??
>> >
>> > >> --
>> > >> 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.
>> >
>> > > --
>> > > 
>> > > *MOHIT VERMA*
>> >
>> > >  --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text
>> -
>> >
>> > - Show quoted text -
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, v

Re: [algogeeks] Re: Find all the subsets whose sum <= k

[Piyush Grover]

it's similar to knapsack but not the same. In knapsack, types of items are
limited and we play on the quantity of each item.
Here each element will come once in the subset.

On Fri, Aug 26, 2011 at 11:49 PM, Don  wrote:

> @rahul
> Your code will only find pairs which sum to k. The problem is to find
> a subset of as many elements in the array as required to sum as close
> as possible to k.
> It is a well-known problem and after years of study, no polynomial
> solution is known. There are reasonably fast solutions for small
> inputs, but the best anyone has done is a pseudo-polynomial-time
> algorithm using dynamic programming. Thus it is weakly NP-complete. As
> n gets large, the time required increases exponentially.
> Search the web for "Knapsack problem" to learn more.
> Don
>
> On Aug 26, 1:04 pm, rahul sharma  wrote:
> > yes it will
> > return in c return 1 value at tym...
> > ijust given the code snipetjust modify it..store trhm in some
> > other array like thebut it will
> >
> > On Aug 26, 11:02 pm, Piyush Grover  wrote:
> >
> > > @rahul...I'm unsure if your algo returns all the subsets.
> >
> > > On Fri, Aug 26, 2011 at 11:24 PM, rahul sharma <
> rahul23111...@gmail.com>wrote:
> >
> > > > yeah can be done in poly tym also...but we dnt knw whether we have
> > > > unsorted arryit is possible in sorted array.
> >
> > > > On Aug 26, 10:52 pm, Don  wrote:
> > > > > This is the knapsack problem.
> > > > > Find a polynomial-time solution and you will be a hero.
> > > > > Don
> >
> > > > > On Aug 26, 12:43 pm, Piyush Grover 
> wrote:
> >
> > > > > > Here is a problem:
> >
> > > > > > Given an array of size n. Find all the MAXIMAL subsets whose sum
> is <=
> > > > K.
> > > > > > The solution is not a concern, the optimization is required.
> >
> > > > > > -piyush
> >
> > > > --
> > > > 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] apti!

[Piyush Grover]

it's basic unitary method problem:

x men do work in 10 days
1 man will do-in 10*x days
x-10 men do it in 10*x/(x-10) = (10+10)

Solve it and x = 20
 it can't be 130

On Fri, Aug 26, 2011 at 11:53 PM, gmagog...@gmail.com
wrote:

> @Rahul
>
> Assume the productivity of each man is the same
>
> let original number of man be x
>
> The total workload= x*10*p
> also workload = (x-10)(10+10)*p
>
> solve it
> so x=20
>
> Yanan Cao
>
>
>
> On Fri, Aug 26, 2011 at 1:21 PM, Rahul Verma wrote:
>
>> @yanan how it is 20.
>>
>> Rahul Verma
>>
>> --
>> 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/-/uIONcvrf6kUJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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 all the subsets whose sum <= k

[Piyush Grover]

@rahul...I'm unsure if your algo returns all the subsets.

On Fri, Aug 26, 2011 at 11:24 PM, rahul sharma wrote:

> yeah can be done in poly tym also...but we dnt knw whether we have
> unsorted arryit is possible in sorted array.
>
> On Aug 26, 10:52 pm, Don  wrote:
> > This is the knapsack problem.
> > Find a polynomial-time solution and you will be a hero.
> > Don
> >
> > On Aug 26, 12:43 pm, Piyush Grover  wrote:
> >
> >
> >
> >
> >
> >
> >
> > > Here is a problem:
> >
> > > Given an array of size n. Find all the MAXIMAL subsets whose sum is <=
> K.
> > > The solution is not a concern, the optimization is required.
> >
> > > -piyush
>
> --
> 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] Find all the subsets whose sum <= k

[Piyush Grover]

Here is a problem:

Given an array of size n. Find all the MAXIMAL subsets whose sum is <= K.
The solution is not a concern, the optimization is required.

-piyush

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