[algogeeks] Fwd: Graph problem - cut vertex
how to find all cut vertexes in a given graph ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Array problem
given an array of size n...
create an array of size n such that ai where ai is the element in the
new array at index location i is equal to sum of all elements in
original array which are smaller than element at posn i...
e.g
ar[]={3,5,1,6,7,8};
ar1[]={0,3,0,9,15,22};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Maximum height/depth of tree
Quoting from wikipedia: The *depth* (or *height*) of a tree is the length of the path from the root to the deepest node in the tree. However notice *length *is not defined and is left on the intuition.So *both answers 2 and 3 are correct if we follow the above definition.* However the next line on wiki entry says *A (rooted) tree with only one node (the root) has a depth of zero. **So this line suggests the height should be 2. *But in either case I don't think any sane computer scientist/programmer will worry about whether the answer should be 2 or 3.After all the answer differs by a constant factor.All depends on how you want to implement it.Somewhat similar question can be whether 0 is a positive number? Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Mar 11, 2012 at 12:44 PM, rahul sharma rahul23111...@gmail.comwrote: but according to the o/p it should be 3i also concerned from the data structure and algo book it is also giving same answer.so the height/depth is the number of nodes in largest pathis it rigt??? On Sun, Mar 11, 2012 at 12:10 PM, Sonia Keys soniak...@gmail.com wrote: Correct is always whatever the specification says. You may think something else is more conventional, or something else may seem right to you, but none of that matters if there are clear instructions otherwise. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xmJbzvy_X6sJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding majority element(which is ocuuring more than n/2 imes in array)
@rahul, the voting algorithm may not give the majorty element in the array if the majorty element occurs =n/2 times. but the problem clearly says that majorty element that appears more than n/2 times. in such cases, the voting algo always gives the corret majorty element, if exists. On Sun, Mar 11, 2012 at 12:55 PM, rahul sharma rahul23111...@gmail.comwrote: can be done easily with hashing..btu takes extra space. cant we simplify just by one step. On Sun, Mar 11, 2012 at 12:46 PM, rahul sharma rahul23111...@gmail.comwrote: *refered from:-http://www.geeksforgeeks.org/archives/503 basically want to know that whether voting algo is corret??? *2,2,2,3,3,4,4 in this case it is giving majority element as 4 but it should be 3???plz explain. * METHOD 3 (Using Moore’s Voting Algorithm)* This is a two step process. 1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only. 2. Check if the element obtained from above step is majority element. *1. Finding a Candidate:* The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. findCandidate(a[], size) 1. Initialize index and count of majority element maj_index = 0, count = 1 2. Loop for i = 1 to size – 1 (a)If a[maj_index] == a[i] count++ (b)Else count--; (c)If count == 0 maj_index = i; count = 1 3. Return a[maj_index] Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1. First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element. Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2. Example: A[] = 2, 2, 3, 5, 2, 2, 6 Initialize: maj_index = 0, count = 1 – candidate ‘2? 2, 2, 3, 5, 2, 2, 6 Same as a[maj_index] = count = 2 2, 2, 3, 5, 2, 2, 6 Different from a[maj_index] = count = 1 2, 2, 3, 5, 2, 2, 6 Different from a[maj_index] = count = 0 Since count = 0, change candidate for majority element to 5 = maj_index = 3, count = 1 2, 2, 3, 5, 2, 2, 6 Different from a[maj_index] = count = 0 Since count = 0, change candidate for majority element to 2 = maj_index = 4 2, 2, 3, 5, 2, 2, 6 Same as a[maj_index] = count = 2 2, 2, 3, 5, 2, 2, 6 Different from a[maj_index] = count = 1 Finally candidate for majority element is 2. First step uses Moore’s Voting Algorithm to get a candidate for majority element. 2.* Check if the element obtained in step 1 is majority* printMajority (a[], size) 1. Find the candidate for majority 2. If candidate is majority. i.e., appears more than n/2 times. Print the candidate 3. Else Print NONE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array problem
By Augmented BST-
TC-O(n)
On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote:
given an array of size n...
create an array of size n such that ai where ai is the element in the
new array at index location i is equal to sum of all elements in
original array which are smaller than element at posn i...
e.g
ar[]={3,5,1,6,7,8};
ar1[]={0,3,0,9,15,22};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array problem
u r right payal but
can u expln o(n) time complexity..
On Sun, Mar 11, 2012 at 6:10 PM, payal gupta gpt.pa...@gmail.com wrote:
By Augmented BST-
TC-O(n)
On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote:
given an array of size n...
create an array of size n such that ai where ai is the element in the
new array at index location i is equal to sum of all elements in
original array which are smaller than element at posn i...
e.g
ar[]={3,5,1,6,7,8};
ar1[]={0,3,0,9,15,22};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Sanjiv Yadav
MobNo.- 8050142693
Email Id- sanjiv2009...@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.
[algogeeks] Jyotirmoy Sundi wants to chat
--- Jyotirmoy Sundi wants to stay in better touch using some of Google's coolest new products. If you already have Gmail or Google Talk, visit: http://mail.google.com/mail/b-65354814fc-14728963ae-RbTaQCJLZNdtXMp5RN--omrdSpc You'll need to click this link to be able to chat with Jyotirmoy Sundi. To get Gmail - a free email account from Google with over 2,800 megabytes of storage - and chat with Jyotirmoy Sundi, visit: http://mail.google.com/mail/a-65354814fc-14728963ae-RbTaQCJLZNdtXMp5RN--omrdSpc Gmail offers: - Instant messaging right inside Gmail - Powerful spam protection - Built-in search for finding your messages and a helpful way of organizing emails into conversations - No pop-up ads or untargeted banners - just text ads and related information that are relevant to the content of your messages All this, and its yours for free. But wait, there's more! By opening a Gmail account, you also get access to Google Talk, Google's instant messaging service: http://www.google.com/talk/ Google Talk offers: - Web-based chat that you can use anywhere, without a download - A contact list that's synchronized with your Gmail account - Free, high quality PC-to-PC voice calls when you download the Google Talk client We're working hard to add new features and make improvements, so we might also ask for your comments and suggestions periodically. We appreciate your help in making our products even better! Thanks, The Google Team To learn more about Gmail and Google Talk, visit: http://mail.google.com/mail/help/about.html http://www.google.com/talk/about.html (If clicking the URLs in this message does not work, copy and paste them into the address bar of your browser). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Hi
Hi Has anyone here given a VMWare interview. Could someone tell me about it. Thanks -- U -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Graph problem - find all cut vertex
how to find all cut vertexes in a given graph ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 problem
we can use self balancing BST for this problem to yield the complexity O(nlogn) ..where every node will contain the sum of the node values on it left sub tree .. you can check this post..its pretty similar (Method 2) http://www.geeksforgeeks.org/archives/17235 On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor pkjee2...@gmail.com wrote: This can be done very easily with the help of a Binary Indexed Tree,and it is very short to code as well.Simply process the numbers in order,and for each number output the cumulative frequency of the index of the number you are processing. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 problem
@payal : what will be be the structure of the augmented tree , i add 2 to
the given input. so input become.
ar[]={3,5,1,6,7,8,2};
On Sun, Mar 11, 2012 at 11:07 PM, payal gupta gpt.pa...@gmail.com wrote:
the algo vich i thought of is as follows-
struct node{
int data;
struct node *left,*right;
int lsum; //for storing the leftsum
int k;// for storing the storing the reqd sum which is leftsum + sum
of the elements traversed till now on the path
};
Algo for insertion of nodes in bst-
1. add the new node with data as the value ,lsum set to 0 and k set to 0
2.continue adding further nodes and update the value of 'k' by the data to
be added whenever value is added to theleft subtree of the node
3. on adding the node to the right of the root set the value of leftsum to
be summation of rootvalue+k of the nodes considered during traversal
(3,0,0)
\
(5,3+0,0)
(3,0,1)
/\
(1,0,0)(5,3+0,0)
(3,0,1)
/ \
(1,0,0) (5,3+0,0)
\
(6,1+5+3,0)
(3,0,1)
/ \
(1,0,0) (5,3+0,0)
\
(6,1+5+3,0)
\
(7,1+5+3+6,0)
(3,0,1)
/ \
(1,0,0) (5,3+0,0)
\
(6,1+5+3,0)
\
(7,1+3+5+6,0)
\
(8,3+1+5+6+7,0)
where the node-(data,leftsum,k)
On Sun, Mar 11, 2012 at 7:06 PM, sanjiv yadav sanjiv2009...@gmail.comwrote:
u r right payal but
can u expln o(n) time complexity..
On Sun, Mar 11, 2012 at 6:10 PM, payal gupta gpt.pa...@gmail.com wrote:
By Augmented BST-
TC-O(n)
On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli
gpgaurav.n...@gmail.comwrote:
given an array of size n...
create an array of size n such that ai where ai is the element in the
new array at index location i is equal to sum of all elements in
original array which are smaller than element at posn i...
e.g
ar[]={3,5,1,6,7,8};
ar1[]={0,3,0,9,15,22};
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Sanjiv Yadav
MobNo.- 8050142693
Email Id- sanjiv2009...@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array problem
@piyush : i dont think so BIT would work over here , we are not just reporting cumulative sum tilll index i. On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor pkjee2...@gmail.com wrote: This can be done very easily with the help of a Binary Indexed Tree,and it is very short to code as well.Simply process the numbers in order,and for each number output the cumulative frequency of the index of the number you are processing. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array problem
@atul anand- It will still work as follows--- (3,0) / \(5,0+3) (1,0) \(6,0+3+5) \(2,0+1)\(7,0+3+5+6) \(8,0+3+5+6+7) here, my logic is that if number is grater than its parent,then add the parent in the current sum,else keep it as such. check it and made correction in my logic if i m wrong. On Mon, Mar 12, 2012 at 10:33 AM, atul anand atul.87fri...@gmail.comwrote: @piyush : i dont think so BIT would work over here , we are not just reporting cumulative sum tilll index i. On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor pkjee2...@gmail.comwrote: This can be done very easily with the help of a Binary Indexed Tree,and it is very short to code as well.Simply process the numbers in order,and for each number output the cumulative frequency of the index of the number you are processing. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Sanjiv Yadav MobNo.- 8050142693 Email Id- sanjiv2009...@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.
Re: [algogeeks] Array problem
@sanjiv : wont work for this test case :-
{1,5,3,6,2,7,8};
On Mon, Mar 12, 2012 at 10:54 AM, sanjiv yadav sanjiv2009...@gmail.comwrote:
@atul anand- It will still work as follows---
(3,0)
/ \(5,0+3)
(1,0) \(6,0+3+5)
\(2,0+1)\(7,0+3+5+6)
\(8,0+3+5+6+7)
here, my logic is that if number is grater than its parent,then add the
parent in the current sum,else keep it as such.
check it and made correction in my logic if i m wrong.
On Mon, Mar 12, 2012 at 10:33 AM, atul anand atul.87fri...@gmail.comwrote:
@piyush : i dont think so BIT would work over here , we are not just
reporting cumulative sum tilll index i.
On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor pkjee2...@gmail.comwrote:
This can be done very easily with the help of a Binary Indexed Tree,and
it is very short to code as well.Simply process the numbers in order,and
for each number output the cumulative frequency of the index of the number
you are processing.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Sanjiv Yadav
MobNo.- 8050142693
Email Id- sanjiv2009...@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
