Re: [algogeeks] branching factor when BFS and DFS of a graph is same
yes branching factor should be 1. it can be not equal to 1 only for the penultimate node. by penultimate node i mean whose children are the leaves of the tree. rest all cases it should be 1. On Tue, Sep 13, 2011 at 9:24 AM, siddharam suresh siddharam@gmail.comwrote: cant say if there more than one leaf element still both the algo give same result Thank you, Sid. On Tue, Sep 13, 2011 at 7:52 AM, Sundi sundi...@gmail.com wrote: if the dfs and bfs of a graph is same, does it mean that if the branching factor of a graph is one? abcd example: both dfs abd bfs are same here -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] MICROSOFT WRITTEN QUESTION-2010
convert the binary search tree into a sorted linked list. After flattening construct the tree out of it. And please don't use capital letters unnecessarily. It reflects bad on you. On Sun, Sep 11, 2011 at 7:29 AM, teja bala pawanjalsa.t...@gmail.comwrote: MERGE 2 BINARY SEARCH TREES? HOW TO DO IT?(POST AN EFFICIENT ALGORITHM) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Max sub matrix problem
@Neha.. This problem can be solved by DP. Create an auxiliary matrix C[][] . C[i][j] would give the maximum size sub matrix with C[i][j] as the right bottom entry. now the DP eqn is if M[i][j] == 1 C[i][j] = min(c[i-1][j],c[i][j-1],c[i-1][j-1])+1 else c[i][j] = 0 Now take the maximum c[i][j] entry in the matrix. Hope it helps. On Mon, Sep 12, 2011 at 10:07 AM, tech coder techcoderonw...@gmail.comwrote: this is possible in o(n^2) with n^2 addidtional space . On Sun, Sep 11, 2011 at 11:33 AM, Neha Singh neha.ndelhi.1...@gmail.comwrote: @victor: Can u provide the algo ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Custom Random Generator
@Don...Nice solution.. But the return statement should be a+b-1
On Mon, Aug 29, 2011 at 10:33 PM, Don dondod...@gmail.com 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 piyush4u.iit...@gmail.com 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 dondod...@gmail.com 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 piyush4u.iit...@gmail.com 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.
Re: [algogeeks] Re: MS Question
ya why not hashing ? On Thu, Aug 25, 2011 at 3:31 PM, SANDEEP CHUGH sandeep.aa...@gmail.comwrote: wat abt doing wid hashing? On Thu, Aug 25, 2011 at 3:55 PM, vikas vikas.rastogi2...@gmail.comwrote: yep, trie needs to be built On Aug 24, 10:49 pm, Ankur Garg ankurga...@gmail.com wrote: It means when u call that func u get the next word in the document Regards Ankur On Wed, Aug 24, 2011 at 6:59 PM, vikas vikas.rastogi2...@gmail.com wrote: what do you mean by a function for finding the next word is given ? On Aug 22, 1:56 am, Ankur Garg ankurga...@gmail.com wrote: Question-- Given a document containing some words ...and a function for finding the next word is given .design a code which efficiently search the word and find occurrence of it in given document . -which data structure will be used? -write algorithm for implementing complexity? Guys any Ideas here .. I think tries can be used but can anyone explain/suggest/discuss proper implementation /technique to solve this problem Regards Ankur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- 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.
Re: [algogeeks] MS test
1. c 2. b 3. 0.1 cannot be represented but how about 1.32 ? 4. a 5. Can anyone point how the loop will be terminated ? 6. b On Mon, Aug 8, 2011 at 3:18 PM, DeVaNsH gUpTa devanshgupta...@gmail.comwrote: 4. a The solution is given by aditya, but it asked for additional processors, so ans is 5. -- Thanks and Regards *Devansh Gupta* *B.Tech Third Year* *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. -- 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.
Re: [algogeeks] Duplicates in a string
Store the frequency of all the letters in an array in one scan(like counting sort). In the next pass remove the duplicates and appropriately shift . takes 2 O(n) passes i guess On Fri, Aug 5, 2011 at 4:50 PM, priya v pria@gmail.com wrote: Remove duplicate alphabets from a string and compress it in the same string. For example, MISSISSIPPI becomes MISP. O (n2) is not acceptable. For this problem is it a good idea to sort the array using a sorting technique with efficiency O(nlogn) and remove the duplicates? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: Duplicates in a string
@deepikayour solution is not O(n) i guess...
@Sachinthe question says compress the *same* string. By 'printing' i
dont know what you mean
On Fri, Aug 5, 2011 at 5:17 PM, deepikaanand swinyanand...@gmail.comwrote:
static int array[256];
removedupli(char s[],int n)
{
array[s[0]]=1;
for(i=1;in;i++)
{
if(array[s[i]]==0)
array[s[i]]=1;
else
{
for(pos=i;in;i++)
s[pos]=s[pos+1];
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.
--
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.
Re: [algogeeks] probablity
5/6 On Fri, Aug 5, 2011 at 5:55 PM, Rahul Jain rahuljai...@gmail.com wrote: i agree with puneet. 1/2 On Fri, Aug 5, 2011 at 9:18 PM, Puneet Goyal puneetgoya...@gmail.comwrote: 1/2 you got the blue pen so it is for sure that is one of the first two packets, so you are left with a black pen and a blue pen and you have to find the probability of finding a blue pen among them On Fri, Aug 5, 2011 at 9:14 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: I was given 3 packets, with 2 pens each. 1st Packet has 2 blue pens. 2nd Packet has 1 blue pen,1 black pen. 3rd Packet has 2 black pens. I took any one packet and pulled out one pen. It turned out to be a blue one. What is the probability that the next pen from the same packet will also be a blue one? -- Regards, Kamakshi kamakshi...@gmail.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. -- --- Puneet Goyal Student of B. Tech. III Year (Software Engineering) Delhi Technological University, Delhi --- -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] array pointer
1 On Fri, Aug 5, 2011 at 5:47 PM, mohit goyal mohitgoya...@gmail.com wrote: n=x, is correct or n = x[0][0] is correct On 8/5/11, Arshad Alam alam3...@gmail.com wrote: we can equate base address of double dimension array to a pointer variable, tell me which one is correct. if n is a pointer variable and x[5][5] is double dimension array 1. n=x; 2. n=x[0][0]; 3. both -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Laugh as much as you breathe and love as long as you live. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] simple doubt
i think both are erroneous.
first statement i think you are trying to change the array address
which is not possible.
second statementarr doesn't make any sense i guess arr gives the
address but arr is not allowed
On Fri, Aug 5, 2011 at 4:19 PM, Vijay Khandar vijaykhand...@gmail.comwrote:
but u initialized **dp means .
ex-dp=p and p=arr then its correct so dp contains addr of p which
inturns contains addrof arr now **dp is correct initialization.
On Fri, Aug 5, 2011 at 7:45 PM, Arun Vishwanathan
aaron.nar...@gmail.comwrote:
i see but is not arr a pointer to first array element and so arr contain
address of that pointer ?
On Fri, Aug 5, 2011 at 4:06 PM, Vijay Khandar vijaykhand...@gmail.comwrote:
I dont think so dp=arr; since **dp; dp contains the addr of another
ptr variable...
On Fri, Aug 5, 2011 at 7:27 PM, Arun Vishwanathan
aaron.nar...@gmail.com wrote:
I guess someone had posted a link earlier from which I have a basic
doubt
when u have
int arr[3]={1,0,2};
int **dp;
int (*pa)[3];
is this the right assingment for instance?
pa=arr;
dp=arr;
or have I flipped the ampersand in assigning?
Also when I do pa++ will it jump by size of int or the whole array
size it points to?
--
People often say that motivation doesn't last. Well, neither does
bathing - that's why we recommend it daily.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
People often say that motivation doesn't last. Well, neither does
bathing - that's why we recommend it daily.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
Re: [algogeeks] [brain teaser ] W Riddle 16 may
only 1... its w's that we have to count not w :P On Mon, May 16, 2011 at 11:26 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @vivek...how come only one?? I think its 8... On Mon, May 16, 2011 at 1:03 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *W Riddle * * * ** *George Washington's wife was sweeping when George Washington's wife slipped and got wet. How many w's in all? * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/05/w-riddle-16-may.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] [brain teaser ] 17march
:P On Thu, Mar 17, 2011 at 10:52 AM, kunal srivastav kunal.shrivas...@gmail.com wrote: lol On Thu, Mar 17, 2011 at 2:20 PM, Srirang Ranjalkar srira...@gmail.comwrote: @amit have you considered Lee as an answer for that question? :P Thank you, Srirang Ranjalkar -- Luck is when hard work meets opportunity On Thu, Mar 17, 2011 at 2:19 PM, amit singh amit.lu...@gmail.com wrote: Lu (hint a,e,i ,o,u) On Thu, Mar 17, 2011 at 1:58 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: *Problem Solution* * *Lee's parents have five children, the names of the first four are La, Le, Li, and Lo. What's the name of the fifth child? Update Your Answers at : Click Herehttp://dailybrainteaser.blogspot.com/2011/03/17march.html Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe 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. -- Amit Kumar Singh Software Engineer Samsung India Software Operations Banglore 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. -- thezeitgeistmovement.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. -- 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.
Re: [algogeeks] give answer
Abstract classes can have non abstract methods. Derived classes must implement the abstract methods. But Interfaces have only abstract method definitions. Implementing classes must implement all the method definitions in the interface. On Thu, Mar 10, 2011 at 11:13 PM, LALIT SHARMA lks.ru...@gmail.com wrote: google it On Thu, Mar 10, 2011 at 10:49 PM, Sudhir mishra sudhir08.mis...@gmail.com wrote: Ques: What is Abstract Classes? Ques:What is interfaces? Ques:What is difference between abstract classes and interfaces? Ques:Give an example where do you use interfaces and abstract classes? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Lalit Kishore Sharma, IIIT Allahabad (Amethi Capmus), 6th Sem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Amazon Question
@Ankit..your algm is O(n)...you should split the problem size to n/2 at
every stage...rather you are again computing both the subarrays..
Here is the correct code...
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
if(a[mid] mid )
BsearchElemEqualIndex (a, start, mid);
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf (%d, x);
system (PAUSE);
return 0;
}
On Thu, Mar 3, 2011 at 7:20 PM, jagannath prasad das jpdasi...@gmail.comwrote:
@ankit sinha:i dont think the algo u wrote is o(logn).its o(N) i guess
On Thu, Mar 3, 2011 at 7:05 PM, Ankit Sinha akki12...@gmail.com wrote:
@sukhmeet, as per the question, there is a unique value which satisfy
a[i] = i in the array and written code captures that only. Else we
need to modify if we are interested in all such values which statisfy
the said condition. And also in that case looping around bsearch will
not be a good idea.. it will be better to go for simple loop in o(n)
time as every time mid calculation is also costly. I agreed to Arpit
view point and accordingly did coding as preetika needed as per arpit
comments.
Cheers!!
Ankit
On Thu, Mar 3, 2011 at 6:53 PM, sukhmeet singh sukhmeet2...@gmail.com
wrote:
what should be the answer for this:
if A={0,1,2,4,5}
0 or 1 or 2
On Thu, Mar 3, 2011 at 6:26 PM, Ankit Sinha akki12...@gmail.com
wrote:
Hi,
Here is the code to do this using Bsearch in o(logn) time.
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
BsearchElemEqualIndex (a, start, mid);
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf (%d, x);
system (PAUSE);
return 0;
}
Cheers,
Ankit!!!
On Thu, Mar 3, 2011 at 11:04 AM, Param10k paramesh...@gmail.com
wrote:
There is a sorted array and you have to write a fn to find a number
in
the array which satisfies
A[i] = i ; where A is the array and i is the index...
- Param
http://teknotron-param.blogspot.com/
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
Re: [algogeeks] Amazon Question
Ignore the previous post..there is a small error in the code..
@Ankit..your algm is O(n)...you should split the problem size to n/2 at
every stage...rather you are again computing both the subarrays..
Here is the correct code...
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
if(a[mid] mid )
BsearchElemEqualIndex (a, start, mid);
else
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf (%d, x);
system (PAUSE);
return 0;
}
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.
Re: [algogeeks] Re: Amazon Question
@Gunjani made a mistake...u r right...but there is one more hidden
assumption that the numbers are positive integers.
On Thu, Mar 3, 2011 at 10:57 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
he already pointed out that there are no repetations..!!
On Thu, Mar 3, 2011 at 9:40 PM, Vipin Agrawal vipin.iitr@gmail.comwrote:
take an example
3 3 3 5 5 5 7 8
I think this would fail
On Mar 3, 8:22 pm, Ankit Sinha akki12...@gmail.com wrote:
It is funny but right input is as mentioned earlier to rahul. 0,2,3,8,
10, 12, 14., 15 :).. Sorry for unnecessarily flooding your mail
accounts. Please ignore previous post
thanks,
ankit!!
On Thu, Mar 3, 2011 at 8:15 PM, rajul jain rajuljain...@gmail.com
wrote:
i think he is wrong bcoz this array in not sorted one.
so solution of Ankit is right.
On Thu, Mar 3, 2011 at 7:33 PM, nishaanth nishaant...@gmail.com
wrote:
Ignore the previous post..there is a small error in the code..
@Ankit..your algm is O(n)...you should split the problem size to n/2
at
every stage...rather you are again computing both the subarrays..
Here is the correct code...
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
if(a[mid] mid )
BsearchElemEqualIndex (a, start, mid);
else
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf (%d, x);
system (PAUSE);
return 0;
}
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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
Re: [algogeeks] Missing Number in New Way Please Read Question Carefully..
Find XOR from 1 to n...takes O(n) ans = X1 Now fetch individual bits from array elements...again take xor...takes O(n) ans= X2 result is X1 xor X2 On Wed, Mar 2, 2011 at 1:44 AM, bittu shashank7andr...@gmail.com wrote: An array A[1...n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time? Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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.
Re: [algogeeks] Re: amazon
Declare it as *static.* On Wed, Feb 23, 2011 at 11:33 PM, Jammy xujiayiy...@gmail.com wrote: Are you talking about IPC? On Feb 22, 10:05 am, jaladhi dave jaladhi.k.d...@gmail.com wrote: What do you mean by data element here ? Also by file you mean the file where you wrote the code ? And above all which programming language are we talking ? You hit send button too early I guess :) On 22-Feb-2011 7:39 PM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: Is there any way by which a data element in a file is accessible by another file, where the program has multiple files. That data element should be accessible to a particular file only and inaccessible to the rest.? declaring it as an extern will make it accessible to all i think .. what cud be the answer ? -- With Regards, *Jalaj Jaiswal* (+919019947895) Software developer, Cisco Systems B.Tech IIIT 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. -- 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.
Re: [algogeeks]
how does it ignore ' , ' for x but not for y ?. Can you explain what
happens if u give , in an int.
On Sat, Feb 5, 2011 at 6:34 PM, Gajendra Dadheech gajju3...@gmail.comwrote:
x would be 20 as when we put zero in front of any number then this is taken
as octel number and value of 024 in decimal would be 20
Thanks and regards,
Gajendra Dadheech
On Sat, Feb 5, 2011 at 6:30 PM, Gajendra Dadheech gajju3...@gmail.comwrote:
20,1 this would be output
Thanks and regards,
Gajendra Dadheech
Software Engineer-I (RD)
MediaTek India Technology
Work: 120-4343900(Ext. 276)
Mobile: +91-9540646145
-
Be the change you want to see in the world -Mohandas Gandhi
On Sat, Feb 5, 2011 at 6:11 PM, vaibhav agrawal agrvaib...@gmail.comwrote:
@ankit: how x is 20?
On Sat, Feb 5, 2011 at 4:46 PM, ankit sablok ankit4...@gmail.comwrote:
x is 20 for sure and y i m guessing to be 1 comma operator and 0 used
for octal constnts
On Sat, Feb 5, 2011 at 3:01 PM, radha krishnan
radhakrishnance...@gmail.com wrote:
guess the output
main()
{
int x=(1,024),y;
y=1,024;
printf(%d %d,x,y);
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Amazon Again
nice solution..
On Sun, Jan 30, 2011 at 11:51 PM, Wei.QI qiw...@gmail.com wrote:
here is the code:
public int findStartPumpIndex(int[][] pumpDistance){
int leftGas = 0;
int start = 0;
//Find the potential start
for(int i=0; ipumpDistance.length; i++){
int addGas = pumpDistance[i][0];
int consumeGas = pumpDistance[i][1];
int left = leftGas + addGas - consumeGas;
if(left = 0){
leftGas = left;
}else {
leftGas = 0;
start = i+1;
}
}
//if we failed find a start at last, not solution
if(start = pumpDistance.length)
return -1;
//otherwise continue to go, until back to start
for(int i=0; istart; i++){
int addGas = pumpDistance[i][0];
int consumeGas = pumpDistance[i][1];
int left = leftGas + addGas - consumeGas;
if(left 0){
leftGas = left;
}else {
return -1;
}
}
return start;
}
On Sun, Jan 30, 2011 at 9:55 AM, Wei.QI qiw...@gmail.com wrote:
For any gas pump, when your car arrives, it contains 0 or more gas.
So, for each gas pump, the worst case is starting from that pump.
Then, if we starting from pump A1, passed A2 - Ak and failed at Ak+1. for
A1 to Ak, we can not pass Ak+1 starting from any of them. So we try start
from Ak+1.
This could be solved in liner time. finding a possible start pump use O(n)
and prove it use another O(n).
-weiq
On Sat, Jan 29, 2011 at 9:47 PM, nishaanth nishaant...@gmail.com wrote:
@Wei.Qi Can you clarify when your algorithm terminates and also what
is the running time of the algorithm ?
On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.comwrote:
can you prove it?
On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote:
Starting with any pump A, try to finish the circle, if at pump B that
can not reach pump B+1, it means all pumps from A to B can not finish the
circle (it will go broke at pump B), then just start with B+1. After go
through all the pumps start from some pump, we got an answer. if we go back
to pump A and later, still can not find an answer, there is no answer.
On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
I'm sure you have misstated the problem statement
just find out the total path length and return the first petrol pump
which gives you the required milage
go greedy
On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote:
There are N petrol pumps along a circular path. Every petrol pump
gives some amount of fixed petrol. Need not to be unique and in no
particular order means it is random. We have a car and we need to
find
a petrol pump which can provide so much of petrol that we can take
a
full of the circle. Mileage of car is fixed.
Distance between adjacent petrol pumps are given.
Thanks Regards
Shashank
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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
Re: [algogeeks] Re: first larger element in unsorted array...
@Balaji.nice solution..but care to explain how it is applied in the
other 2 problems you mentioned at the end(Rectangle in a histogram and
largest rectangle in the binary matrix ..)
On Mon, Jan 31, 2011 at 2:21 PM, Balaji Ramani rbalaji.psgt...@gmail.comwrote:
Hi,
This can be solved the technique to use stacks to save incomplete problems.
Push first element to stack.
While iterating over the array,
if the element is smaller than stack top, push it to stack along with
index.
if the element is larger than stack top, pop till current element
is smaller than stack top and for all the popped indices store the
current element.
time complexity: o(n)
space complexity: o(n)
The same technique is used to solved largest rectangle in a histogram
and largest rectangle with all 1s in a binary matrix.
Thanks,
Balaji.
On Mon, Jan 31, 2011 at 1:25 PM, ritu ritugarg.c...@gmail.com wrote:
for {9,7,8} it gives me {8,8,-1}...not correct
On Jan 31, 11:16 am, abhijith reddy abhijith200...@gmail.com wrote:
simple dp
void solve(int *arr,int sz)
{
int ans[sz];
ans[sz-1]=-1;
for(int i=sz-2;i=0;i--)
{
if(arr[i]arr[i+1]) ans[i]=arr[i+1];
else ans[i]=ans[i+1];
}
for(int i=0;isz;i++)
printf(%d ,ans[i]);
}
On Sun, Jan 30, 2011 at 10:00 PM, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity:O(n)
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] can i know the best way to learn programming??
solve problems from SPOJ and topcoder.it helps a lot. On Tue, Feb 1, 2011 at 1:30 AM, sandy sandeep.aa...@gmail.com wrote: plz help -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Amazon Again
@Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Minimum positive-sum subarray
@snehalno its incorrect..consider the following example -2 3 The answer to this problem is the entire array with sum 1.(not the min of positive number) On Sun, Jan 30, 2011 at 11:00 AM, snehal jain learner@gmail.com wrote: a friend of mine was asked this question in google interview.. according to me the min element in the array is the answer provided that its not zero.. as 1 element can also be a subarray. but that would solve the problem in O(n) only.. ( this is what i understood) am i missing anything..? please help.. On Sun, Jan 30, 2011 at 5:19 AM, Dan dant...@aol.com wrote: On Jan 21, 1:05 am, snehal jain learner@gmail.com wrote: In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive or negative numbers, and you are asked to find a subarray A[i : j] such that the sum of its elements is (1) strictly greater than zero, and (2) minimum. In other words, you want to find a subarray of smallest positive sum. Give an O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic Programming Algorithm. There are three considerations here: 1) Insufficient clarity in the problem statement. 2) Most people don't want to do others homework/school problems for them. 3) At very least... you need to show that you are attempting to answer the problem yourself at least a little bit. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Divide the array into groups
@snehal..i guess you are missing something in the question...divide it into 2 groups such that (there should be some other condition or criterion). On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.com wrote: my approach sort in nlogn and then while traversing the array put the elements in a group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in different group.. now we need to rearrange elements in the group so that they are according to the given array.. but that will make it O(n^2) .. anyone with better ideas? On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.comwrote: Divide a list of numbers into groups of consecutive numbers but their original order should be preserved. Example: 8,2,4,7,1,0,3,6 Two groups: 2,4,1,0,3 8,7,6 Better than O(n^2) is expected. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Divide the array into groups
so whats the required outputlist all possiblities or anything else? if
its just this one output...then it sounds trivial
On Sun, Jan 30, 2011 at 11:43 AM, snehal jain learner@gmail.com wrote:
@nishanth
divide into groups ( not necessarily 2) in as many group as possible.. such
that elements in each group is consecutive
another example to clearify
A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15)
ans
9,7,13,11,6,12,8,10
3,4,2
16,14,17,13,15
On Sun, Jan 30, 2011 at 11:32 AM, nishaanth nishaant...@gmail.com wrote:
@snehal..i guess you are missing something in the question...divide it
into 2 groups such that (there should be some other condition or
criterion).
On Sun, Jan 30, 2011 at 11:29 AM, snehal jain learner@gmail.comwrote:
my approach
sort in nlogn and then while traversing the array put the elements in a
group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in
different group.. now we need to rearrange elements in the group so that
they are according to the given array.. but that will make it O(n^2) ..
anyone with better ideas?
On Fri, Jan 21, 2011 at 1:20 PM, snehal jain learner@gmail.comwrote:
Divide a list of numbers into groups of consecutive numbers but their
original order should be preserved.
Example:
8,2,4,7,1,0,3,6
Two groups:
2,4,1,0,3 8,7,6
Better than O(n^2) is expected.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: zig zag
@above...can you please enlighten me about the second term in the dp
expression
And are you sure its O(n) ?
On Fri, Jan 28, 2011 at 7:08 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
This can be done in O(n) very easily , similar to Longest increasing
subsequence
Solution :-
dp[l]= maximum length of the zigzag sequence upto the length l
//At any position , the particular number in the array can either
extend the zigzag sequence containing the last element or it can start
one of it's own . So the recurrance becomes
dp[i]= max(dp[j]) ,and diff[A[p[j]]]^(A[i]-A[p[j]]31)!=0 , ji
find out the maximum in this array , it will get you the answer .
PS:- You can also check out the Topcoder tutorials .
On Jan 27, 7:41 pm, bittu shashank7andr...@gmail.com wrote:
well I found it as it Can be Done in O(n). but with additional space
O(n)
here program is written in Java
public class ZigZag
{
public int longestZigZag(int[] sequence)
{
if (sequence.length==1) return 1;
if (sequence.length==2) return 2;
int[] diff = new int[sequence.length-1];
for (int i=1;isequence.length;i++)
{
diff[i-1]=sequence[i]-sequence[i-1];
}
//90% Program is done here it self. by looking at the sign if
alternative number in auxiliary array we can count longest zigzag
array
int sign=sign(diff[0]);
int count=0;
if (sign!=0)
count=1;
for (int i=1;idiff.length;i++)
{
int nextsign=sign(diff[i]);
if (sign*nextsign==-1){
sign=nextsign;
count++;
}
}
return count+1;
}
public int sign(int a)
{
if (a==0) return 0;
return a/Math.abs(a);
}
public static void main(String[] args)
{
ZigZag z = new ZigZag();
System.out.println(z.longestZigZag(new int[] { 1, 7, 4, 9, 2, 5 }));
System.out.println(z.longestZigZag(new int[] { 1, 17, 5, 10, 13, 15,
10, 5, 16, 8 }));
}
}
Try for Inplace
Thanks Regards
Shashank Mani The best way to escape from a problem is 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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Doubt regarding Pointers in C......
Hi guys,
I have a small doubt regarding pointers and functions.
Consider the following prototype
void insert(bst * head, int data);
This function creates a node and inserts the data in the node. Lets say i
call this function iteratively from main.
main(){
bst* record=NULL;
insert(record, 5);
insert(record, 8);
}
I see that record is not getting modified. Now is this related to call by
value. But since we are passing pointers shouldnt the change get reflected
in main.
isnt is similar to passing an array?
Enlighten me in this regard. I am tired of segfaults :(
Regards,
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.
Re: [algogeeks] Puzzle
(91-1)/9 On Wed, Jan 26, 2011 at 11:07 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: 9 + 1 - ( 1 / 9 ) On Wed, Jan 26, 2011 at 10:29 PM, satish satish@gmail.com wrote: 19-(9/1). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Doubt regarding Pointers in C......
How can we pass pointers by value. Lets say even if it creates a copy of the
pointer.
The address stored by the pointer is the same. So when we dereference it
shouldnt it get updated(as its just a memory address)?
On Thu, Jan 27, 2011 at 5:39 PM, ritu ritugarg.c...@gmail.com wrote:
Here you are passing record pointer by value.
as you call insert(record, 5),stack frame of insert contains a copy
of record.after this value is modified by calling program,it should
be either returned explicitly to caller program or needs to be passed
by reference,so that calling program refers to it always by address.
On Jan 27, 4:17 pm, nishaanth nishaant...@gmail.com wrote:
Hi guys,
I have a small doubt regarding pointers and functions.
Consider the following prototype
void insert(bst * head, int data);
This function creates a node and inserts the data in the node. Lets say i
call this function iteratively from main.
main(){
bst* record=NULL;
insert(record, 5);
insert(record, 8);
}
I see that record is not getting modified. Now is this related to call by
value. But since we are passing pointers shouldnt the change get
reflected
in main.
isnt is similar to passing an array?
Enlighten me in this regard. I am tired of segfaults :(
Regards,
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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] zig zag
How about this dp solution? Let dp[i][j][k] be the lookup table. It is defined as the longest zigzag sequence in the range i and j. k is either 0 or 1. 0- if the sequence ends with a positive difference, i.e last element is greater than the last to one. 1- if the sequence ends with a negative difference. Now we can define the recursive formula as follows, for(k=i;kj;k++) dp[i][j][0]= max(dp[i][j][0],dp[i][k][1]+dp[k+1][j][0]) dp[i][j][1]= max(dp[i][j][1],dp[i][k][0]+dp[k+1][j][1]) correct me if i am wrong. On Fri, Jan 21, 2011 at 12:48 PM, snehal jain learner@gmail.com wrote: A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] merging 2 search trees
Find the node in T which is the maximum(which is either the root or the rightmost in the right subtree). After finding this node, just make the right child of this node point to the root of T'. Correct me if i am wrong On Fri, Jan 21, 2011 at 2:43 PM, snehal jain learner@gmail.com wrote: You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Distance in a dictionary
Its a state space search. Solve it by using any of the known search algorithms. BFS, Best first search, DFS, A* On Fri, Jan 21, 2011 at 2:00 PM, snehal jain learner@gmail.com wrote: You have a dictionary of N words each of 3 chars. Given 2 words you have to find the optimum path between the 2 words. The optimum path contains the words in the dictionary each word at a distance of 1 from the previous word. for eg source = cat , target = sun path is cat - bat - but - bun - sun given all these words are in the dictionary -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Distance in a dictionary
Ok lets define the following functions. movegen()- gives the list of next move given the state. This is basically all the 1 distance words given the current word. heuristic()- this gives the number of non-matching characters of the given word with the goal word. Start from start state and expand. Now always choose the move which gives a lesser heuristic valued state. Stop if you reach the goal. You can refer to Russel Norvig book on AI for detailed explanation. Regards, 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.
Re: [algogeeks] Re: Amazon Question
@Juver..doesnt it require the parent information ? What if the data structure has only left and right pointers. On Fri, Jan 21, 2011 at 8:41 PM, juver++ avpostni...@gmail.com wrote: This question was posted some time ago. One solution is - start from the largest element (which is the righmost one in the tree). Then apply algorithm of searchin node's predecessor. It takes O(k) time to find k-th largest/smallest number. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: probability
Simple Conditional probability formula...Ans B) On Fri, Jan 14, 2011 at 9:04 PM, Jammy xujiayiy...@gmail.com wrote: Bayes' theorem: http://en.wikipedia.org/wiki/Bayes'_theoremhttp://en.wikipedia.org/wiki/Bayes%27_theorem P(x=even|x3) = P(x3|x=even)*P(x=even)/P(x3)===B On Jan 14, 2:29 am, snehal jain learner@gmail.com wrote: An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3? (A) 0.453 (B) 0.468 (C) 0.485 (D) 0.492 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Adobe Question
Ya as Ashish said hashing is the best solution :) On Fri, Jan 14, 2011 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote: ideally, a hashMap would be preferred walk through one array and set the corresponding entry, and then through another array, if any entry found, then they are not disjoint. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Jan 14, 2011 at 3:35 PM, bittu shashank7andr...@gmail.com wrote: how to find if two arrays of size n are disjoint or not in O(n) time ?? You can use only O(n) space The elements are +ve in the range 0 to n power 100.. Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Google Question
How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: google mcqs
RAM Question ;- Ans D... Larger RAM - Larger number of frames per process - lesser number of pagefaults - increased performance. Scheduling :- Ans D..All are correct. @all those guys who say only I and III, why not II ? Preemption doesnt guarantee bounded waiting.Starvation may still happen. Correct me if i am wrong. -- 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.
Re: [algogeeks] Re: post and pre increment operators
@priya...ya thats wat i meant by interleaving of operations(non-atomic operations). you can understand the results if you can trace the register values. On Sat, Jan 8, 2011 at 10:18 PM, Priyanka Chatterjee dona.1...@gmail.comwrote: @harshal, sundi: Use some compiler to check, i checked on gcc , it gives 13,14,14 On 9 January 2011 11:44, Harshal hc4...@gmail.com wrote: hey i am also getting the output as 12,13,13,13.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] tic tac toe
someone - going by the exact words of the problem description. Just see all the 8 possible winning combinations(row,column, 2 diagonals)...if anyone combination is filled by the same player..then there is a winner. I know it sounds trivial, correct me if i am wrong. On Sat, Jan 8, 2011 at 11:16 AM, divya sweetdivya@gmail.com wrote: Design an algorithm to figure out if someone has won in a game of tic- tac-toe. give O(N) soln -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
In essence what you say boils down to DFS , isnt it ? On Sat, Jan 8, 2011 at 10:15 PM, Algoose chase harishp...@gmail.com wrote: Will this work ? Find the node x, then the node y within the sub tree rooted at x and then z within the sub tree rooted at y since they must within a unique path If any of those searches fails there are no such nodes On Sun, Jan 9, 2011 at 6:02 AM, Gene gene.ress...@gmail.com wrote: The problem never says that the tree is rooted. So LCA is not very relevant. The path between two nodes in any tree is unique. (Otherwise it has a cycle and is not a tree.) So all that's needed is to search for z starting at x (DFS or BFS will work fine). When you find the unique path, see if it contains y. This is O(n) where n is the number of nodes. The problem is more interesting if you are allowed to pre-process the tree one time in order to build a data structure to support many queries. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
so if its in another subtree, whats the problem? If z is not reachable print 'no'. On Sun, Jan 9, 2011 at 5:32 PM, juver++ avpostni...@gmail.com wrote: Your approach is failed! Read my previous post. There is a simple counterexample when doing dfs from x we cannot reach target node cause z can be placeed into another subtree, so x is not its ancestor. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
please describe the tree...give an elaborate explanation to your input On Sun, Jan 9, 2011 at 8:02 PM, juver++ avpostni...@gmail.com wrote: x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1 cannot be reached while DFS from node 2 https://lh3.googleusercontent.com/_qdJSDBXyZKE/TSi5XyCrEzI/ARg/PB7anNiPA2c/graph.png -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
@Juver++ Its its not reachable then print answer as 'no'.. whats the problem.. can you elaborate a bit ? I didnt get where it fails. On Sat, Jan 8, 2011 at 1:30 AM, juver++ avpostni...@gmail.com wrote: z can be unreachable while doing DFS from node x, cause their common ancestor locates on the upper level. So this solution failed. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: post and pre increment operators
output should be 22,13,13,13 right ? On Sat, Jan 8, 2011 at 10:22 PM, priya mehta priya.mehta...@gmail.comwrote: http://www.ideone.com/mxvmt please see please see the link it has the program with output On Sun, Jan 9, 2011 at 11:44 AM, Harshal hc4...@gmail.com wrote: hey i am also getting the output as 12,13,13,13.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BT
Do an inorder walk on T1 till you get the root of T2. Then do a simultaneous walks on both the trees till T2(smaller tree) is fully explored. If at any point you discover dissimilar nodes. print 'no' else print 'yes' One more issue is if duplicates are allowed, then we cant print 'no' with just one failure, repeat till you explore the bigger tree fully. Correct me if i am wrong. On Sat, Jan 8, 2011 at 9:31 PM, Harshal hc4...@gmail.com wrote: Given two binary trees T1 and T2 which store character data, duplicates allowed. You have to devise an algorithm to decide whether the T2 is a subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes. -- Harshal Choudhary, III Year B.Tech Undergraduate, Computer Science and Engineering, National Institute of Technology Surathkal, Karnataka India. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: post and pre increment operators
which order of execution will anyways give 22,13,14,14? The only way to explain is interleaving of each of the operations(i.e operations are not atomic). On Sat, Jan 8, 2011 at 10:34 PM, nishaanth nishaant...@gmail.com wrote: output should be 22,13,13,13 right ? On Sat, Jan 8, 2011 at 10:22 PM, priya mehta priya.mehta...@gmail.comwrote: http://www.ideone.com/mxvmt please see please see the link it has the program with output On Sun, Jan 9, 2011 at 11:44 AM, Harshal hc4...@gmail.com wrote: hey i am also getting the output as 12,13,13,13.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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. -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
@Gene...BFS wont work i guess. Because even if y is in the path it may not be in the queue. DFS is a bit intuitive i guess On Sat, Jan 8, 2011 at 4:32 PM, Gene gene.ress...@gmail.com wrote: The problem never says that the tree is rooted. So LCA is not very relevant. The path between two nodes in any tree is unique. (Otherwise it has a cycle and is not a tree.) So all that's needed is to search for z starting at x (DFS or BFS will work fine). When you find the unique path, see if it contains y. This is O(n) where n is the number of nodes. The problem is more interesting if you are allowed to pre-process the tree one time in order to build a data structure to support many queries. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Adobe Interview
@anand...A small correction, in that longest increasing subsequence algorithm we also should make sure that the first two dimensions are also proper. Because sorting two dimensions based on area doesnt mean they fit. On Sat, Jan 8, 2011 at 4:40 AM, Anand anandut2...@gmail.com wrote: This is absolutely longest increasing sub-sequence problem. Since rotation is not possible. For the given L and B values calculate the base area L * B for all the given values and sort it. From this sorted array calculate the longest increasing sub-sequence of H. The Out put sequence gives the answer. On Fri, Jan 7, 2011 at 11:46 AM, Decipher ankurseth...@gmail.com wrote: I think this is a modification of longest increasing subsequence problem . First , sort by length then find the longest increasing subsequence by width. Now, in this solution find longest increasing subsequence by height . This would be the answer to this question. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
How about this solution, Do a DFS on the graph with x as the start node. If you get z , just see if y is in the stack, if its there then it is in the path,else it is not. correct me if i am wrong. On Fri, Jan 7, 2011 at 7:51 PM, juver++ avpostni...@gmail.com wrote: Heh, problem clearly stated that there a general binary tree, not BST. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Single linked list questions.
for 2nd question. Let m1,m2 be the length of sll1 and sll2.. now we know that after the merge no of nodes are same in both the slls. So take the difference , k= m1 - m2 skip k nodes frm the longer lists, then increment both sll1 and sll2 till you find a match. The matched node is the required answer. On Thu, Jan 6, 2011 at 11:14 PM, Tushar Bindal tushicom...@gmail.comwrote: I agree But my doubt is that whether we have to find that they just have their last node as common or they can have many nodes common(which I was calling intersecting) On Thu, Jan 6, 2011 at 11:07 PM, Naveen Kumar naveenkumarve...@gmail.comwrote: How can two list just intersect, each node can have one pointer to the next. So, if they intersect they will definitely be merging. On Thu, Jan 6, 2011 at 11:01 PM, Tushar Bindal tushicom...@gmail.comwrote: Is it necessary that the two lists are merging at their ends?? Do we have to find whether they merge at the end into same lists or wheter they are just intersecting?? On Thu, Jan 6, 2011 at 10:04 PM, Aditya adit.sh...@gmail.com wrote: There are two aspects here for second question. 1. to find if the common node exist (ie the lists are merging) with out the limitation of length available. 2. To find the merging node. On 1/6/2011 8:49 PM, Naveen Kumar wrote: @ Vishal, I think question says that its merging at a point. But anyway can you tell me how to detect cycle in this case. On Thu, Jan 6, 2011 at 7:57 PM, vishal raja vishal.ge...@gmail.comwrote: @aditya, Who said it's a Y shaped structure, It can very well has a cycle. Assume the case when the last node is not pointing to NULL but to a node in the list. On Thu, Jan 6, 2011 at 7:45 PM, ADITYA KUMAR aditya...@gmail.comwrote: @vishal saurabh is right its merging at only one point its a Y-shaped structure On Thu, Jan 6, 2011 at 7:29 PM, vishal raja vishal.ge...@gmail.comwrote: @sourabh, In addition to your solution, If there is any cycle(loop) exist in the link list your algo will fail. To solve this problem first detect this cycle if there is any and count the element in the cycle, and then you can do the mathematics. On Thu, Jan 6, 2011 at 6:51 PM, sourabh jakhar sourabhjak...@gmail.com wrote: for second question calculate the difference in length of two linked list. and than shift the head of longest linked list to the calculated difference. while the head of shorest is at the first node of that linked list. Than iterate both to see if info is equal and that is the merging point. complexity-o(n). hope this help On Thu, Jan 6, 2011 at 6:48 PM, juver++ avpostni...@gmail.comwrote: Yes, but recursion stack's size is limited instead of iterative version. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen
Re: [algogeeks] Re: Single linked list questions.
@Sanchit..sorry i didnt see the replies :P On Thu, Jan 6, 2011 at 11:32 PM, sanchit mittal sm14it...@gmail.com wrote: Problem hav been solved u all giving same answers..! On Thu, Jan 6, 2011 at 11:30 PM, nishaanth nishaant...@gmail.com wrote: for 2nd question. Let m1,m2 be the length of sll1 and sll2.. now we know that after the merge no of nodes are same in both the slls. So take the difference , k= m1 - m2 skip k nodes frm the longer lists, then increment both sll1 and sll2 till you find a match. The matched node is the required answer. On Thu, Jan 6, 2011 at 11:14 PM, Tushar Bindal tushicom...@gmail.comwrote: I agree But my doubt is that whether we have to find that they just have their last node as common or they can have many nodes common(which I was calling intersecting) On Thu, Jan 6, 2011 at 11:07 PM, Naveen Kumar naveenkumarve...@gmail.com wrote: How can two list just intersect, each node can have one pointer to the next. So, if they intersect they will definitely be merging. On Thu, Jan 6, 2011 at 11:01 PM, Tushar Bindal tushicom...@gmail.comwrote: Is it necessary that the two lists are merging at their ends?? Do we have to find whether they merge at the end into same lists or wheter they are just intersecting?? On Thu, Jan 6, 2011 at 10:04 PM, Aditya adit.sh...@gmail.com wrote: There are two aspects here for second question. 1. to find if the common node exist (ie the lists are merging) with out the limitation of length available. 2. To find the merging node. On 1/6/2011 8:49 PM, Naveen Kumar wrote: @ Vishal, I think question says that its merging at a point. But anyway can you tell me how to detect cycle in this case. On Thu, Jan 6, 2011 at 7:57 PM, vishal raja vishal.ge...@gmail.comwrote: @aditya, Who said it's a Y shaped structure, It can very well has a cycle. Assume the case when the last node is not pointing to NULL but to a node in the list. On Thu, Jan 6, 2011 at 7:45 PM, ADITYA KUMAR aditya...@gmail.comwrote: @vishal saurabh is right its merging at only one point its a Y-shaped structure On Thu, Jan 6, 2011 at 7:29 PM, vishal raja vishal.ge...@gmail.com wrote: @sourabh, In addition to your solution, If there is any cycle(loop) exist in the link list your algo will fail. To solve this problem first detect this cycle if there is any and count the element in the cycle, and then you can do the mathematics. On Thu, Jan 6, 2011 at 6:51 PM, sourabh jakhar sourabhjak...@gmail.com wrote: for second question calculate the difference in length of two linked list. and than shift the head of longest linked list to the calculated difference. while the head of shorest is at the first node of that linked list. Than iterate both to see if info is equal and that is the merging point. complexity-o(n). hope this help On Thu, Jan 6, 2011 at 6:48 PM, juver++ avpostni...@gmail.comwrote: Yes, but recursion stack's size is limited instead of iterative version. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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
Re: [algogeeks] Re: Dynamic prog.
https://www.spoj.pl/problems/LISA/
this problem is similar to what you have mentioned. I have attached my dp
solution to this problem.
The lines of the algo is similar to matrix chain multiplication.
Regards,
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
#includeiostream
#includecstring
#includeclimits
using namespace std;
struct res
{
int max,min;
}m[101][101];
main()
{
int i,t,l,j,length,q,q1,k;
char str[200];
cint;
while(t--)
{
cinstr;
length=strlen(str);
for(i=0;i=length-1;i++)
m[i][i].max=m[i][i].min=str[i]-48;
for(i=0;i=length-3;i++)
{
if(str[i+1]=='+')
m[i][i+2].max=m[i][i+2].min=str[i]+str[i+2]-96;
else
m[i][i+2].max=m[i][i+2].min=(str[i]-48)*(str[i+2]-48);
}
for(l=4;llength;l+=2)
{
for(i=0;i=length-l-1;i++)
{
j=i+l;
m[i][j].max=INT_MIN;
m[i][j].min=INT_MAX;
for(k=i;k=j-2;k+=2)
{
if(str[k+1]=='+')
{
q=m[i][k].max+m[k+2][j].max;
q1=m[i][k].min+m[k+2][j].min;
}
else
{
q=m[i][k].max*m[k+2][j].max;
q1=m[i][k].min*m[k+2][j].min;
}
m[i][j].max=std::max(m[i][j].max,q);
m[i][j].min=std::min(m[i][j].min,q1);
}
}
}
coutm[0][length-1].max m[0][length-1].minendl;
}
}
Re: [algogeeks] Spoj problem-pigbank
#includeiostream
#includeclimits
using namespace std;
int m[1];
struct coin
{
int value;
int weight;
}s1[1000];
main()
{
int t,w0,w1,n,temp,temp1,i,j,w;
cint;
while(t--)
{
cinw0w1;
w=w1-w0;
cinn;
temp1=INT_MAX;
for(i=1;i=n;i++)
{
cins1[i].values1[i].weight;
if(temp1s1[i].weight)
temp1=s1[i].weight;
}
for(i=0;itemp1;i++)
m[i]=0;
for(i=temp1;i=w;i++)
{
temp1=INT_MAX;
for(j=1;j=n;j++)
{
temp=0;
if(i-s1[j].weight=0)
{
if(m[i-s1[j].weight]0 || i==s1[j].weight)
temp=m[i-s1[j].weight]+s1[j].value;
}
if(temptemp1 temp!=0)
temp1=temp;
}
if(temp1==INT_MAX)
m[i]=0;
else
m[i]=temp1;
}
if(!m[w])
coutThis is impossible.endl;
else
{
coutThe minimum amount of money in the piggy-bank is
m[w].endl;
}
}
}
This is my code
On Sun, Dec 5, 2010 at 2:01 PM, Bharath 2009503507 CSE
bharathgo...@gmail.com wrote:
i am a beginner.pl help me with this code.i submitted a solution.it s
giving op for all given testcases.but the judge is giving me a TLE.
code:
#includeiostream
#includemap
#define inf 9
using namespace std;
mapint,int m2;
int func(mapint,int m1,int w)
{
if(m2[w]inf)
return m2[w];
mapint,int::iterator it;
int min=inf;
for(it=m1.begin();it!=m1.end();it++)
{
if((*it).second=w)
{
int x=func(m1,w-(*it).second);
if(x+(*it).first min)
min=x+(*it).first;
}
}
m2[w]=min;
return min;
}
main()
{
int t;
cint;
while(t--)
{
int w1,w2;
cinw1w2;
int w=w2-w1,no,a,b;
cinno;
mapint,int m1;
for(int i=0;ino;i++)
{
cinab;
m1.insert(pairint,int(a,b));
}
m2[0]=0;
for(int i=1;i=w;i++)
m2[i]=inf;
func(m1,w);
if(m2[w]!=inf)
coutThe minimum amount of money in the piggy-bank is
m2[w].\n;
else
coutThis is impossible.\n;
}
}
pl say hw i can improve.
thanks in advance.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find triplets in an integer array A[] which satisfy condition: a[i]^2 + a[j]^2 = a[k]^2
I have a O(n^2) solution.. Hash all the squares.0(n) Now for every pair find the sum, see if its there in the hash table.O(n^2) Total complexity : O(n^2) On Wed, Dec 1, 2010 at 11:00 PM, fenghuang fenghaungyuyi...@gmail.comwrote: yeah, you're right. thank you and is it the optimal solution about this question? On Thu, Dec 2, 2010 at 1:08 AM, Dave dave_and_da...@juno.com wrote: @Fenghuang: No. You don't have to search for b for every a, or more precisely, you don't have to search for a j for every i. Something like this should work for step 3: i = 0 j = k-1 repeat while i = j if asq[i] + asq[j] asq[k] then i = i+1 else if asq[i] + asq[j] asq[k] then j = j-1 else break end repeat if i = j then you have found an i, j, and k satisfying the desired relationship; otherwise, no such i and j exist for this k. This loop is O(n). Surround this with a loop over k and precede that loop with a sort to get Senthilnathan's algorithm. So, as he says, the whole task is O(n log n + n^2) = O(n^2). Dave On Dec 1, 10:11 am, fenghuang fenghaungyuyi...@gmail.com wrote: should it be O(n^2*lgn)? for each x in n, it's O(n), and for each a, it'sO(n), and searching b, it's O(lgn), so it's O(n*n*lgn),Thank You! On Wed, Dec 1, 2010 at 11:02 PM, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: Hi, How about the following approach? Step 1: Replace each array element with its square - O(n) Step 2: Sort the array - O(n*log(n)) Step 3: For each element x in the array Find two elements a, b in the array (if any) such that a+b = x. Since finding two such elements can be done in O(n) time in a sorted array, the complexity of this step 3 is O(n^2). While reporting the output you can take the square root and print it out. Total complexity is O(n^2). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Placement
ya indibabix.com is an awesome linkthanks mukesh... On Thu, Nov 18, 2010 at 6:31 PM, coolfrog$ dixit.coolfrog.div...@gmail.comwrote: @Mukesh indiabix.com is really a nice on for place ment... thankyou.. keep posting such linking On Wed, Nov 17, 2010 at 9:53 AM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: try website:-.www.placementpapers.com indiabix.com On 11/15/10, Bittu B bittu.bitt...@gmail.com wrote: Plz suggest some links for placement aptitude and technical For companies like Microsoft , Amdocs, Infosys, Accenture etc -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
@Praveenit is not possible..in a BST *all the nodes* on the right subtree are greater than the node :) On Sat, Oct 16, 2010 at 3:26 PM, Praveen Baskar praveen200...@gmail.comwrote: @nishaanth: wat if the left child of the right node has a negative value On Thu, Oct 14, 2010 at 11:12 AM, nishaanth nishaant...@gmail.com wrote: Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Smallest window of K[] in N[]. Best order solution
It is nothing but a common subsequence problem...isnt it ?
On Wed, Oct 13, 2010 at 3:42 PM, Mridul Malpani malpanimri...@gmail.comwrote:
@ ankit agarwal, you are right. thanx man.
On Oct 13, 11:37 am, prodigy 1abhishekshu...@gmail.com wrote:
Let I,Q be input array,query array respectively.
1. Sort query array. O(klogk)
2. Allocate an array A of size N.
3. Fill A such that A[i]= position of Q[i] in I, -1 if not present in
I. O(nlogk)
4. Allocate an array B of size k with all elements initiated to -1.
5. for(counter=0,i=0,countern,i++)
{
if(B[i]==-1)
counter++;
if(A[i]!=-1)
B[A[i]] = i
}
6. Build min-heap of B.(use an auxiliary array C to keep track of
position of last occurence of an element of Q in min-heap B.)
7. for(diff=i-B[1] ; in; i++)
if(A[i]!=-1)
B[C[A[i]] = i
//percolate up or down if needed
diff=max(diff,i-B[1]);
8. printdiff
On Oct 7, 1:20 pm, RAHUL KUJUR kujurismonu2...@gmail.com wrote:
@prodigy: how is it coming O(nlogk) can u explain???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BiasedRandom fron unbiasedRandom.
@snehal...a simple way to do it is.. create an array of lets say 1000... fill in 1000* p elements with 0 and the rem with 1 now use rand() and generate the index..and return arr[index] On Fri, Oct 8, 2010 at 8:49 PM, Dave dave_and_da...@juno.com wrote: @Snehal: If p has a finite binary representation, of say n bits, then generate a sequence of up to n unbiased random numbers, continuing the sequence as long as the ith random number agrees with the ith bit to the right of the binary point. When the ith number disagrees with the ith bit, return that ith number. If the computation continues until even the nth number matches the nth bit, then start over. Example: Suppose that the binary representation of p is 0.101101. If the first unbiased random number is 1, generate the second number. If the second number is 0, continue to the third number. If the third number is 0, return 0. If p does not have a finite binary representation, e.g., if p = 1/3 or sqrt(1/2) and you are not using a finite precision floating point representation, then the algorithm will terminate with probability 1. Dave On Oct 8, 2:44 am, snehal jain learner@gmail.com wrote: Given a unbiased function that generates 0 and 1 with equal probability write a function biasedrandom that genreates 0 with probability p and 1 with probability 1-p. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Algorithm to determine the largest number of envelopes that can be nested inside one another.
ya...finding the longest subsequence is the simplest method...and its nlogn.. It works...it similar to box stacking problem On Fri, Oct 1, 2010 at 6:00 AM, adit.sh...@gmail.com adit.sh...@gmail.comwrote: The problem here is more about finding the most optimal solution and not just solution. Rgds Adi -Original Message- From: Sathaiah Dontula Sent: 29/09/2010, 09:25 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Algorithm to determine the largest number of envelopes that can be nested inside one another. I think we can do like this, 1. Sort all the xi's in ascending order - nlog(n) 2. Then find the longest increasing sequence of yi's - nlog(n) 3. complexity will be nlog(n). Thanks, Sathaiah Dontula On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni prashant.r.k...@gmail.com wrote: i think it is similar to finding max in a list O(n) or sorting algorithm O(n log n) -- Prashant Kulkarni On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal rahulsinga...@gmail.com wrote: A possible solution i can think is create a directed graph where each vertex is a envelope and edges are from a bigger envelope to smaller envelope ( one which can fit in bigger envelope ) . Now the problem is reduce to finding longest path in the graph . Regards Rahul -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: linked lists
@Snehal...wat ligerdave says is have ptr1 for list1 and ptr2 for list2. if(ptr1-data==ptr2-data)increment both ptr1 and ptr2 else reset ptr2 to the head of list2 , increment ptr1 ptr2 position gives from where we need to concatenate. On Sat, Oct 9, 2010 at 12:21 AM, ashita dadlani ash@gmail.com wrote: I think we can use KMP string matching algorithm. On Fri, Oct 8, 2010 at 6:40 PM, shashank jain shashankg...@gmail.comwrote: there are 2 unsorted array we have to want a third array in sorted form in mininmum time complexicity answer can like be this merge the two array in 3rd array then sort the array or sort the individual array and then merge if feel first one is better can any one can help On 10/8/10, snehal jain learner@gmail.com wrote: @ligerdave m nt getting ur algo..can u explain with an example On 10/8/10, snehal jain learner@gmail.com wrote: @neeraj ur worst case complexity will be O(mn) On 10/8/10, snehal jain learner@gmail.com wrote: @tech the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with prefix of 2nd On 10/7/10, ligerdave david.c...@gmail.com wrote: use pointer. shift to left if one more leading char has been found. any unmatched char resets the pointer to first char once you went through the entire list(first one), the pointer on the second list tells you where to concatenate that gives you O(n) where n is the length of first list On Oct 7, 3:52 am, snehal jain learner@gmail.com wrote: There are two linked list, both containing a character in each node. If one linked list contain characters o x e n c and second contain characters e n c a r t a then the final linked list should contain o x e n c a r t ai.e. if the end of one list is same as the start of second then those characters should come only once. can we do it in O(n+m) where n and m are the length of list. both are singly link list. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MAX size of an array
10^5 On Wed, Oct 13, 2010 at 4:47 AM, ANUJ KUMAR kumar.anuj...@gmail.com wrote: what is the maximum size an array can have in spoj in c++? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: 2 elements with sum = x
@ashishnice soln On Mon, Oct 11, 2010 at 1:55 PM, DIPANKAR DUTTA dutta.dipanka...@gmail.comwrote: use DP On 10/10/10, ashish agarwal ashish.cooldude...@gmail.com wrote: take two pointer p and q p=a[0] and q=a[n-1]; sum=p+q; if(sumx) q--; if (sumx) p++; On Sun, Oct 10, 2010 at 6:54 PM, Rohit email.rohit.n...@gmail.com wrote: On Oct 10, 10:48 am, Shravan shravann1...@gmail.com wrote: http://ideone.com/D5W2y Good :). What if array is unsorted. What will be the best solution in terms of time complexity? Better then (nlog(n)+n). Regards Rohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- DIPANKAR DUTTA M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 email:dipan...@iitr.ernet.in email%3adipan...@iitr.ernet.in email%3adipan...@iitr.ernet.in email%253adipan...@iitr.ernet.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Duplicate in an array
@ankit and lingerdave How does hashing help here ?? i say we have to create an array size which is there range of the numbers...else it cant be solved in O(n) Hashing is not helpful here in worst case hashing may lead to a O(n2) solution as all the keys may hash into the same place eg.. 4,14,24,34,44,4 if h(n)= n mod 100 On Sun, Oct 10, 2010 at 5:51 PM, Mridul Malpani malpanimri...@gmail.comwrote: can this problem be solved in O(n) time and in O(1) space? On Oct 6, 10:41 pm, ligerdave david.c...@gmail.com wrote: @mukesh, nope, you do not need to know the range. are you thinking about array? ankit's solution is the implementation of bucket logic. On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote: @Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the numbers is not known we cannot predict whether the algo will run in linear time. Any other idea for O(n)?? Mukesh Gupta Delhi College of Engineering On Wed, Oct 6, 2010 at 4:32 PM, sourav souravs...@gmail.com wrote: @Mukesh Thanks for your attempt. But the question asks for liner or sublinear solution. Sourav On Oct 6, 3:50 pm, Mukesh Gupta mukeshgupta.2...@gmail.com wrote: Keep inserting elements in a binary search tree and break once you get the find the element in the tree. Complexity=O(n log n) On 10/5/10, sourav souravs...@gmail.com wrote: You are given an array of positive numbers in which one number is repeated. Rest all are present only once. Find the duplicate number in linear or sub linear time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mukesh Gupta Delhi College of Engineering -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Duplicate in an array
correction about that example h(n)= n mod 10 On Fri, Oct 15, 2010 at 10:23 PM, nishaanth nishaant...@gmail.com wrote: @ankit and lingerdave How does hashing help here ?? i say we have to create an array size which is there range of the numbers...else it cant be solved in O(n) Hashing is not helpful here in worst case hashing may lead to a O(n2) solution as all the keys may hash into the same place eg.. 4,14,24,34,44,4 if h(n)= n mod 100 On Sun, Oct 10, 2010 at 5:51 PM, Mridul Malpani malpanimri...@gmail.comwrote: can this problem be solved in O(n) time and in O(1) space? On Oct 6, 10:41 pm, ligerdave david.c...@gmail.com wrote: @mukesh, nope, you do not need to know the range. are you thinking about array? ankit's solution is the implementation of bucket logic. On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote: @Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the numbers is not known we cannot predict whether the algo will run in linear time. Any other idea for O(n)?? Mukesh Gupta Delhi College of Engineering On Wed, Oct 6, 2010 at 4:32 PM, sourav souravs...@gmail.com wrote: @Mukesh Thanks for your attempt. But the question asks for liner or sublinear solution. Sourav On Oct 6, 3:50 pm, Mukesh Gupta mukeshgupta.2...@gmail.com wrote: Keep inserting elements in a binary search tree and break once you get the find the element in the tree. Complexity=O(n log n) On 10/5/10, sourav souravs...@gmail.com wrote: You are given an array of positive numbers in which one number is repeated. Rest all are present only once. Find the duplicate number in linear or sub linear time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com . To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mukesh Gupta Delhi College of Engineering -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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. -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Duplicate in an array
@Harshal...it aint O(n)...initiaize all elemnts of aux to 0. This can be even o(n^2) depending on the range On Sat, Oct 16, 2010 at 12:06 AM, Harshal hc4...@gmail.com wrote: let arr is given array of size N. find the max_number in arr. O(n) form an aux array of size_max initiaize all elemnts of aux to 0. O(n) for(i=0;iN;i++)O(n) if(aux[arr[i]]0) return arr[i]; //duplicate element else aux[arr[i]]=i+1; the solution requires extra memory. pls correct me if i am wrong. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BST Question
Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: DP
http://people.csail.mit.edu/bdean/6.046/dp/ check out this lecture... -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: How will you find the subarray whose product is k in an array of negative and positive numbers
Ya as minotauraus said it can be approached like a max_subarray problem but a minor modification a[i][j] is a SET define a[i][j] as the possible product ending at i... j is used to indicate if it was extended from previous window r starting at i...0- for ext 1-for new start for every i calculate , a[i][0]= a[i-1][0](every el in the set) *a[i] , a[i-1][1] * a[i] a[i][1]=a[i] check if a[i][0] or a[i][1] is equal to k and print accordingly Here set is used becuase the windows that can be extended at i always increases by 1so its better to use a set 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Bitwise operator - Adobe
how about this
n+(8-(n7))
On Sun, Sep 26, 2010 at 4:48 AM, Dave dave_and_da...@juno.com wrote:
@Ashwath: Thanks for the correction.
Dave
On Sep 26, 1:20 am, aswath G B aswat...@gmail.com wrote:
@Dave
Slight change u have to do
#includestdio.h
main()
{
int a = 24;
int b = (a | 7)+1; //This Line U have to change. not a || 7.
printf(%d,b);
return 0;
}
tats it
btw it is nice one line easy soln...
On Sat, Sep 25, 2010 at 10:17 PM, Dave dave_and_da...@juno.com wrote:
answer = (x || 7) + 1;
Dave
On Sep 25, 6:56 am, Krunal Modi krunalam...@gmail.com wrote:
Q: Write an algorithm to compute the next multiple of 8 for a given
positive integer using bitwise operators.
Example,
(a) For the number 12, the next multiple of 8 is 16.
(b) For the number 16, the next multiple of 8 is 24.
-
I have written a code using bitwise operators...but, I am not happy
with the solutionIs there any ONE LINE solution ?
Here, is my code.
Approach: shift left till LSB is 0 (say n number of times) then, OR
with 1, finally shift right (same number of times).
#includestdio.h
int main(){
int count,m,n,ans,t;
printf(Enter any number :);
scanf(%d,n);
m=8; //multiple of 8 !!
ans=0;
while(ans=n){
t = m;
while(t){
count=0;
while(ans1){
count++;
ans = ans1;
}
ans = ans|1;
ans = anscount;
t--;
}
}
printf([%d]\n,ans);
return 0;
}- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--http://aswath78.blogspot.com- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: next multiple of 8
try x+8-(x7 ) On Sep 26, 4:47 am, Dave dave_and_da...@juno.com wrote: @Shrevan: I mistyped what I intended. Try answer = (x | 7) + 1; Dave On Sep 26, 5:51 am, Shravan shravann1...@gmail.com wrote: @Dave Your answer will be always 2 irrespective of the value of 'x'. BTW I too didn't the question. On Sep 26, 2:42 pm, Mahendran MaheM mehamind...@gmail.com wrote: sry...i dnt get the qstn clearly. On Sat, Sep 25, 2010 at 10:18 PM, Dave dave_and_da...@juno.com wrote: Simpler: answer = (x || 7) + 1 Dave On Sep 25, 10:14 am, rajess rajess1...@yahoo.com wrote: scan last(left) 4 bits .if the bits are not 1000.make them 1000.else scan from left till u find first one(1).make this bit 1.and make last(left) bits as 1000 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- MAHEM- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Adobe Question
@Dave sorry i didnt see k n (thought it was k=n) The intuition i guess would be at every powers of 2 it increases by 1 i.e 1=0 2=1 3=1+1=2 4=2+2=4 see the increase of 2 here 5=4+2=6 6=6+2=8 7=8+2=10 8=10+3=13 ..see the increase of 3 here i guess we can work on from here On Fri, Sep 24, 2010 at 9:53 AM, Krunal Modi krunalam...@gmail.com wrote: But, how was it derived ? :( What is the intuition behind ? :( :( -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Anyone know optimized solution to bytelandian gold coins problem
It is a straight forward dp problem.Use a memoized version. it is pretty
simple.
#includeiostream
#includemap
using namespace std;
map long long int,long long int p;
main()
{
long long int a,f;
long long int fun(long long int );
p.clear();
while(cina)
{
f=fun(a);
coutfendl;
}
}
long long int fun(long long int a)
{
long long int ch,q;
if(a==0)
return 0;
if(p.find(a)!=p.end())
return p[a];
else
{
ch=fun(a/2)+fun(a/3)+fun(a/4);
if(ch=a)
p[a]=ch;
else
p[a]=a;
}
return p[a];
}
--
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: do this: two numbers with min diff
i dont think there exists a o(n) solution for this
the best we can do is sort in o(nlogn) and then do a o(n) traversal
On Thu, Sep 23, 2010 at 8:48 PM, Dave dave_and_da...@juno.com wrote:
@Yellow: Change the 12 in a[1] in your test case to 35 and see what
you get.
Dave
On Sep 23, 10:09 am, Yellow Sapphire pukhraj7...@gmail.com wrote:
I hope this will work. It finds the two minimum numbers and then prints
the
difference.
#include stdio.h
#include stdlib.h
void find_two_mins(int array[], int size)
{
int i,t;
int min1=array[0], min2=array[1];
for (i=2; isize; i++){
t=array[i];
if(t=min1) {
min2=min1;
min1=t;
continue;
}
}
printf(\nMin elements are 1: %d 2: %d, min1,min2);
printf(\n Absolute difference between two minimum elements are %d,
abs(min1-min2));
}
int main()
{
//int array[10]={ 9,2,3,4,1,7,5,6,8,0};
//
int array[10]={99,12,45,33,88,9098,112,33455,678,3};
find_two_mins(array,10);
return 0;
}- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Adobe Question
@Davefor n=2 ur formulae would give 1 but the result is 3
On Thu, Sep 23, 2010 at 6:53 PM, Apoorve Mohan apoorvemo...@gmail.comwrote:
what is the data type of 'j' ?
On Thu, Sep 23, 2010 at 6:49 PM, Krunal Modi krunalam...@gmail.comwrote:
for(k=1 ; kn ; k++){
j=k;
while(j0){
j=j/2;
}
}
How many times while loop gets executed (for any n) ?
I don't want answer in terms of series (i.e, don't want any sigma, I
have that)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
