[algogeeks] Re: Amazon: sort array
@Jitendra
I have run the code with input given by you and found that it works
well.
Please have a look at http://codepad.org/iMBTwAL7
Appriciate the effort taken by you to analyze the solution and do let
me know if you still do not agree with the code.
Regards,
Sourav
On Jul 8, 9:03 pm, Jitendra Kushwaha jitendra.th...@gmail.com wrote:
@souravsain
Consider your algo for the case
int arr[] = {10,20,30,40,50,23,27};
everytime when you increment the j you are missing on element i.e j-1 for
further comparison
--
Regards
Jitendra Kushwaha
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon: sort array
@Jitendra
Sorry for the previous post. There is a problem in my approach. I
overlooked that.
Working on it.. :(
On Jul 8, 9:03 pm, Jitendra Kushwaha jitendra.th...@gmail.com wrote:
@souravsain
Consider your algo for the case
int arr[] = {10,20,30,40,50,23,27};
everytime when you increment the j you are missing on element i.e j-1 for
further comparison
--
Regards
Jitendra Kushwaha
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Approximate String Matching Algorithm
@ashgoel Thanks for the reply. Any web link or book / chapter from which I can read more about the nearest word finding approach using trie you mentioned? Thanks in advance. Sourav On Jul 4, 11:12 am, ashgoel ashg...@gmail.com wrote: bloom filters are used for approx matches, however, if you want the nearest word finding, and a dictionary is available, may be a trie, then till there is a match move, into the trie down, however if there is a mismatch, calculate the levenstein distan with the rest of the characters in the pattern and the down strings within the trie and list down the lowst distance words On Jul 4, 8:40 am, souravsain souravs...@gmail.com wrote: Hi All I am looking for an algorithm for approximate string matching problem. This is a common known problem and I do have one from Steven S Skiena in his book Algorithm Design Manual [Chapter 8]. Link / guide to any other good algorithm will be of great help.[Please don't send results of google search. Looking for some source where member has read and used / liked it] For those who are not familiar to this problem, it gives me a list of possible words from known dictionary of words, if I type type a word with some spelling mistake. Like I type peple and it should give me people,peble,purple etc. Thanks, Sourav- 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.
[algogeeks] Re: Amazon: sort array
@all
Please find my O(n) time and O(1) space implementation for this
problem.
Summary of approach: let i be start for first sorted part and j be
start of next sorted part. move i as long as a[i] is less than a[j] as
that means things are sorted.
if a[i] a[j], swap them and increment i. Increment j if it is no
more start of a sprted part. So j always points to start of a sorted
part of array. As long as i equals j, we are done.
Here is the implementation
# include stdio.h
void sort(int* array, int SIZE, int i, int j)
{
while(ij)
{
if(array[i] = array[j])
i++;
if(array[j] array[i])
{
int temp = array[j];
array[j]=array[i];
array[i]=temp;
i++;
if(j (SIZE-1) (array[j] array[j+1]) )
j++;
}
}
}
void my_print(int * array, int SIZE)
{
printf(\n);
for(int i = 0; i SIZE ; i++)
printf(%d, ,array[i]);
printf(\n);
}
int main()
{
int array1[8] = {1,3,6,7,4,5,6,8};
int array2[10] = {1,2,3,5,6,7,4,8,9,10};
sort(array1,8,0,4);
sort(array2,10,0,6);
my_print(array1,8);
my_print(array2,10);
return 0;
}
Sourav
On Jul 5, 2:15 pm, harit agarwal agarwalha...@gmail.com wrote:
inplace merging requires worst case O(nlogn)
check pdf
merge-algorithms-screen.pdf
238KViewDownload
--
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: cycle in Linked List generalised
@Amit You should me able to find waether there is a loop or not in a LL with any value of m and n. But if you have to find where the loop is, then you have to chose m and n such that gcd(m,n)=1, as Dave said. Consier the example below 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-24-25-26 and 26 points to 3. With this and m=4 and n=8. You will be able to detect loop but not the location where loop is (at node 3) as the to pointers will keep jumping by 4 and 8 steps and gcd94,8)!=1 Let me know your views. On Jul 7, 2:34 pm, jaladhi dave jaladhi.k.d...@gmail.com wrote: There are more efficient ways of doing this. Refer wikihttp://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm On Wed, Jul 7, 2010 at 9:16 AM, Dave dave_and_da...@juno.com wrote: @Anand. You've described one way to do it, and maybe the most efficient way, but not the only way. Dave On Jul 6, 8:42 pm, Anand anandut2...@gmail.com wrote: you increment slow pointer by 1 and fast pointer by 2 to find a loop in Linked list. On Mon, Jul 5, 2010 at 9:02 PM, amit amitjaspal...@gmail.com wrote: Consider the general fast and slow pointer strategy to detect loop in a LL. Now , Suppose we move the slowPtr 'm' nodes at a time and move the fastPtr 'n' nodes at a time. What are the constraints on 'm' and 'n' so that we that we are able to find whether the list is circular or not? -- 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.- 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.
[algogeeks] Re: microsoft.
@sharad When you say you want first repeating element, do u mean first in the sense in which numbers are layed out in the array (i mean moving from left to right in the array, the first element, =K, that is repeating) or the first smallest element that is repeating? for example in the given example 2,4,3,6,7,1,2,5,1,2 which has 10 elements, if your answer 2 or 1? Sourav On Jul 7, 4:52 pm, Satya satya...@gmail.com wrote: Use selection algorithm, a variation of quicksort algorithm which is in place.http://en.wikipedia.org/wiki/Selection_algorithm . Satya On Wed, Jul 7, 2010 at 1:45 PM, sharad kumar sharad20073...@gmail.comwrote: ya i want inplace 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.- 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.
[algogeeks] Re: google favourite ques
Some additions below: On Jul 4, 1:30 am, Amit Jaspal amitjaspal...@gmail.com wrote: Thanks Ashish for this wonderful postI must say many of my doubts regarding networking were cleared And I will highly appreciate if any one can add on to this wonderful post by ashish.. On Sat, Jul 3, 2010 at 10:42 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: ur browser is a application which uese aplication layer protocol which is HTTP But to formulate packet it needs to find out port and mac address and ip-address to which it wanst to sentd this request so that it can pass these information to lower layer protocol like TCP and IP so, now it sends a DNS query to find out the host name then it gets the IP address. as it is http requets application knows that host will be listening at port 80 all web-servers listens at 80 this layer only now it will send data to session layer which will create a new session. and all further communication to this server willl hapspen through this session. presentation data wont do much other than rerraning the data data comes to Transport layer for sendnig the packet it needs to know the destination port and destination mac-address. it have information of port which is 80. but n o idea abt mac-address. so it willl form a Arp query. as it know ip address it will broadcast this packet as nobody on your netwrok will have this mac-address. and touter will know that this is in some other network. so router in your network will respone with his mac-address. now tranport layer will form segment using these information (TCP protocol ) and will send it to network layer netwrok layer will find out the data size and will break the data into multiple datagrams if data that needs to be sent is large as maximum ethernet size allowed is 1546 bytes it will have squence number for packets so that destination can arrange the data in correct order as it already have infromation about , it has to do nothing much other than forming datagrma There is more for network layer to do. All routing algorithms like shortest path routing, distance vector routing, broadcast routing etc are impkemented here. If your macine is a part of a lan then the network layer in that machine may not have the routing table. All it may do it establish a connection (connection oriented) to the router in your lan (your IPS provider's router). That router has all the routing table and knows which is the best path to send packets in the internet. Here the network layer uses IP protocol which is connection less. So routing tables are dynamic and packets may follow different directions. now datagram is ready. it will forward this frame to link layer link-layer will use either 802.1q (most probably) or FDDI or tokeRing it depends on your link communication if it is optical link it will use some other protocol if it is wireless 8802.11q i guess anyways it will send this packet to link layer which wil send the packet your router will get the packet router has rounit gtabel Here again, router does not use routing table to decide on packets sent by data link layer. Routing table is used by network layer. from which it will found out which link to forward liek this it will finally will reach to router to which detination host is attached On Sat, Jul 3, 2010 at 9:58 AM, Thirupathi reddy Thumma thirupathi.thu...@gmail.com wrote: hai friends sharad was generated an intrested question,iam also intrested to know this,plz any one can analyze xplan us, thank u THIRUPATHI REDDY M.Sc-MATHEMATICS,M.Tech(CSE) ASST PROF IN MATHEM ATICS AURORA,S ENG COLLEGE,HYD On Sat, Jul 3, 2010 at 8:54 AM, sharad kumar sharad20073...@gmail.comwrote: explain in detail what happens in all d 7 layers of osi model when u type www.google.comin ur browser -- 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
[algogeeks] Re: malloc implementations
@Amit, You can find that in The ANCI C - PROGRAMING LANGUAGE by Kernighan and Ritchie, chapter Chapter 8 - The UNIX System Interface, section 8.7 Example - A Storage Allocator Regards, Sourav On Jul 5, 5:52 pm, amit amitjaspal...@gmail.com wrote: Hi, can anybody tell me how is malloc implementedany links to tutorials for this will be highly apperciated. -- 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: Amazon: sort array
@Anand
Also you cannot conclude that k will be middle. There is no mention of
half. Its that only kn. So you can also have something lke
[9,1,2,3,4,5,6] = [9] [1,2,3,4,5,6]
[8,9,10,11,3,4,7,15,17] = [8,9,10,11] [3,4,7,15,17]
and so on
Sourav
On Jul 3, 1:32 am, Anand anandut2...@gmail.com wrote:
This is an example of bitonic sequence if we reverse the bottom half of the
array.
Sequence is called Bitonics if the sequence of number first
increases(ascending order) and then decrease(descending order).
1. We need to reverse the bottom half the array to make it bitonic.
2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
In the below code, I have implemented sorting n/w to sort any kind of array
but for bitonic sequence we only bitonic merge function call which take
O(n).
Refer section Sorting network from Corman for more details
http://codepad.org/ZhYEBqMw
On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ ankibha...@gmail.comwrote:
Given an array of n elements and an integer k where kn. Elemnts
{a[0].a[k] and a[k+1].a[n] are already sorted. Give an
algorithm to sort in O(n) time and O(1) space.
--
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon: sort array
@Anand
Please explain how you concluded that the array will first
continuously increase and then continuously decrease? Why can it not
be 2 continuous increase like [1,2,3,4,5,3,4,8] where [1,2,3,4,5] and
[3,4,8] are a[1] to a[k] and a[k+1] to a[N] respectively? Whill your
method work still?
@Ankur, Correct me if my interpretation of the question is wrong.
Sourav
On Jul 3, 1:32 am, Anand anandut2...@gmail.com wrote:
This is an example of bitonic sequence if we reverse the bottom half of the
array.
Sequence is called Bitonics if the sequence of number first
increases(ascending order) and then decrease(descending order).
1. We need to reverse the bottom half the array to make it bitonic.
2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
In the below code, I have implemented sorting n/w to sort any kind of array
but for bitonic sequence we only bitonic merge function call which take
O(n).
Refer section Sorting network from Corman for more details
http://codepad.org/ZhYEBqMw
On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ ankibha...@gmail.comwrote:
Given an array of n elements and an integer k where kn. Elemnts
{a[0].a[k] and a[k+1].a[n] are already sorted. Give an
algorithm to sort in O(n) time and O(1) space.
--
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: most viewed pages
@divya The answer to this question is perhaps in another question u asked You are provided with a stream of integers, design a data structure to store the number of occurrences of each integer If you have such a data structure with no. of occurances of each integer (web page for this question), that the one with max occurance if your answer here. see the smae link as provided earlier for discussion on this. On Jul 3, 12:12 pm, divya sweetdivya@gmail.com wrote: Design an algorithm to calculate the most user viewed pages. -- 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: algo for counting integers in a stream
@divya This is a widely known issue and lot of work has been done on it. See http://www.americanscientist.org/issues/pub/the-britney-spears-problem/1 for a discussion on this and more. On Jul 3, 10:03 am, divya sweetdivya@gmail.com wrote: You are provided with a stream of integers, design a data structure to store the number of occurrences of each integer. If the set of integers is known, then the problem becomes simple. If the set of integers is known: Have a hash of the known set of integers. Parse the input stream, hash it to get the key and increase its corresponding value. how to do efficiently if the set is not known? -- 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: b tree
I am assuming that nodes of this tree contain numbers and we want to get the median of these numbers. Also is this B-Tree a search tree - are the 3 numbers in each node (each node has 4 chidren and hence 3 values) sorted? Regards, Sourav Sain On Jun 26, 8:27 am, sharad kumar sharad20073...@gmail.com wrote: Find the median in B-tree of order 4? Note that as the tree has order 4, it is not a binary tree. -- 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 higher element
@Raj
You need to examine the nature of the array from end. If form end you
move forward and you find elements are decreasing [10,12,14,16] then
for each element, the previous is next higher. So keep pushing them on
a stack. If you find an increase [say 11,10,12,14,16], then pop from
stack till tap(stack) is greater than current element. This approach
will be max 2n (invstigate that).
Here is the algo
NextHigher[last] = Nothing;//NextHIgher will have the solution and
last = input array's size.
while(--last=1) //am asuming 1 based array and starting from last but
one of array as last elment will always be Nothing.
{
if(array[las]top(stack))
{
NextHigher[last]=top(stack);
push(stack,array[last];
}
if(array[last]=top(s))
{
while(array[last]=top(stack) !empty(stack)) //This loop
will still keep time complexity 0(n) as there cannot be
pop(stack);//more than n times of pop.
if(empty(stack))
NextHigher[last]=Nothing;
else
NextHigher[last]=top(stack);
push(stack,array[last]);
}
}
Thanks,
Sourav Sain
On Jun 25, 10:37 am, chitta koushik koushik.infin...@gmail.com
wrote:
It works for the input given by you. Check the below code:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class NextHigherElement {
public static void main(String args[]){
List Integer input = new ArrayListInteger();
StackInteger s = new StackInteger();
input.add(4);
input.add(1);
input.add(3);
input.add(5);
input.add(6);
input.add(3);
input.add(2);
s.push(input.get(0));
for(int i=1;iinput.size();i++){
while( !s.isEmpty() (input.get(i) s.peek()) )
{
System.out.println(s.pop()+**+input.get(i));}
s.push(input.get(i));}
while(!s.isEmpty()){
System.out.println(s.pop()+**+nothing);
}
}
}
--Koushik C
On Thu, Jun 24, 2010 at 10:46 PM, Raj N rajn...@gmail.com wrote:
@Chitta: Hey this doesn't work in all cases. For eg: 4 1 3 5 6
Output:
4-5
1-3
3-5
5-6
6-null
But according to ur logic u push 4 then, u push 1 as it is 4, do u
conclude that 4 doesn't have next higher element ?
On Thu, Jun 24, 2010 at 4:04 PM, chitta koushik
koushik.infin...@gmail.com wrote:
push the elements into stack , when the element to be pushed is greater
than the 'top' element.. pop the elements and write then
eg : if array is 1 2 3 4 5 8 6
insert 1
-
stack : 1
insert 2 ( as 2 top i.e 1)
-
output 1 - 2
stack : 2
insert 3 ( as 3 top i.e 2)
-
output 1-2, 2-3
stack 3
.
.
.
insert 8 ( as 8 top i.e 5)
--
output 1-2, 2-3,3-4,4-5
stack 8
insert 6
---
output 1-2, 2-3,3-4,4-5,5-8
stack 8,6
final output : 1-2, 2-3,3-4,4-5,5-8,8- -1 , 6 - -1
On Wed, Jun 23, 2010 at 10:48 PM, Raj N rajn...@gmail.com wrote:
@Kumar: The next higher of 5 will be 7 as it comes first in the array.
On Wed, Jun 23, 2010 at 5:28 PM, Kumar Vishal kumar...@gmail.comwrote:
hi the number should be just next higher element or any higher element
like
if my arr is like
arr= 2 5 1 3 7 6
the next higher element for 5
should be what (7 or 6 ) because 6 is more closer to 7 but 7 comes
first in arr
On Wed, Jun 23, 2010 at 11:18 AM, Raj N rajn...@gmail.com wrote:
Design a data structure to find the next higher element for each
element in an array.
For e.g. if array is 1 2 3 4 5 8 6
o/p should be
(element) (next higher element)
1 2
2 3
3 4
4 5
5 8
8 nothing
6 nothing
The array need not be sorted.
Constraints-O(n) time complexity
--
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.
--
Kumar Vishal
StAy HunGrY , StAy fOOlisH
Contact No:- 09560193839
--
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
[algogeeks] Re: Cycle in Undirected and Directed Graphs
@sharad: Do you have some article that explains cycle detection in bfs? Will be of help if you can share that or book or so which explains cycle detection via bfs. @amit: Both in directed and undirected graphs you can find a cycle in O(|v|) time using a dfs. See Algorithm Design Manual Second Edition, chapter 5 by Stiev. S. Skiena. Its a very good explanation. On Jun 14, 6:19 am, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: In any directed graph just check if dfs has a back edge. For undirected, check if there is a nontree edge -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 -- 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: Problem with Virtual Function
Guys
Lets keep discussions in t his group limited to Algos and problems
neutral to any language.
@akshay: Request you to post these C++ language specific questions to
those language specific groups. This will not only help this group
remain confined to its core purpose but will help you get better
insights to ur problem by language specific geeks there. For C++ I
would recommend you to try the group
http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en.
Regards,
Sourav
On Jun 13, 5:08 pm, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com
wrote:
In the first post the problem was that m_speed is not public also u should
access m_speed using Scope resolution operator as m_speed is not a member of
B.
class A
{
public:
virtual int speed()=0;
int m_speed;};
class B:public A
{
public:
int speed()
{
return A::m_speed;}
};
For ur second question...
int main()
{
A *aptr=new B;
coutaptr-speed();
return 0;
}
I hope ur not clear with the concept of virtual functions... This example
will help you. If not post back ur questions...
--
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: bits
@divya
Lets keep discussions in t his group limited to Algos and problems
neutral to any language.
Request you to post these C++ / C language specific questions to those
language specific groups. This will not only help this group remain
confined to its core purpose but will help you get better insights to
ur problem by language specific geeks there. For C++ I would recommend
you to try the group
http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en.
Regards,
Sourav
On Jun 13, 2:29 pm, divya sweetdivya@gmail.com wrote:
tell the o/p of following with explanations
1. #includestdio.h
int main()
{
struct value
{
int bit1:1;
int bit3:4;
int bit4:4;
}bit;
printf(%d\n,sizeof(bit));
return 0;
}
2.
#includestdio.h
int main()
{
struct value
{
int bit1: 1;
int bit3: 4;
int bit4: 4;} bit={1,2,2};
printf(%d %d %d\n,bit.bit1,bit.bit3,bit.bit4);
return 0;
}
3 can bit field be used in union??
--
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: union- c
Guys
Lets keep discussions in t his group limited to Algos and problems
neutral to any language.
@divya: Request you to post these C++ language specific questions to
those language specific groups. This will not only help this group
remain confined to its core purpose but will help you get better
insights to ur problem by language specific geeks there. For C++ I
would recommend you to try the group
http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en.
Regards,
Sourav
On Jun 13, 4:10 pm, divya jain sweetdivya@gmail.com wrote:
wat i meant is
the ans of this questn is
10.00 0.00 3 1080263967
now my questn is y u.f_e is printing 0.00 and similarly y u.l_e is
giving this value...
On 13 June 2010 15:08, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
If you are not able to print the long int and that's the prob, you can use
%ld instead of %d
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
On Sun, Jun 13, 2010 at 1:49 PM, divya jain sweetdivya@gmail.comwrote:
its an o/p questn..
conversion wen ur variable is long..nd u r printing using %f...i dont know
how to perform conversion from float to int long nd vice versa..
pl help
On 13 June 2010 12:12, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
what is this for...
and which conversion are you talking abt?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
On Sat, Jun 12, 2010 at 11:20 PM, divya sweetdivya@gmail.comwrote:
#include stdio.h
main()
{
union {
long l_e;
float f_e;
} u;
long l_v;
float f_v;
l_v = u.l_e = 10;
printf(%f , (float)l_v);
printf(%f , u.f_e);
f_v = u.f_e = 3.555;
printf(%d , (long)f_v);
printf(%d , u.l_e);
}
hw to do the conversion here..
--
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.
--
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.- 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.
[algogeeks] Re: file handing
Guys Lets keep discussions in t his group limited to Algos and problems neutral to any language. @divya: Request you to post these C++ language specific questions to those language specific groups. This will not only help this group remain confined to its core purpose but will help you get better insights to ur problem by language specific geeks there. For C++ I would recommend you to try the group http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en. Regards, Sourav On Jun 13, 5:32 pm, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: For the 1st qn.. the o/p will print the code in the file and then print an infinite sequence of empty spaces. the reason is... In C EOF is defined to hold a value -1 which when assigned to unsigned becomes 255. So it goes in an unending loop even after encountering the end of file. In second qn.. the file myfile.c will be closed. In third qn... It is not eof(fp) it is feof(fp) . There is no function eof defined in stdio.h. Use the correct function for files -- 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: bits
and @rohit you will get better insight into the topic by more expert
people by posting the question in right forum. I guess thats a win-win
situation for one who has the question as he is get to know more and
for people you are interested in going through C++ questions as they
will read views from many more experts :)
On Jun 13, 7:31 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
@Souravsain : Is there any serious problem in this. Anyone can just add a
[C++] in the subject and uninterested people can make filters in gmail :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14
On Sun, Jun 13, 2010 at 6:35 PM, souravsain souravs...@gmail.com wrote:
@divya
Lets keep discussions in t his group limited to Algos and problems
neutral to any language.
Request you to post these C++ / C language specific questions to those
language specific groups. This will not only help this group remain
confined to its core purpose but will help you get better insights to
ur problem by language specific geeks there. For C++ I would recommend
you to try the group
http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en.
Regards,
Sourav
On Jun 13, 2:29 pm, divya sweetdivya@gmail.com wrote:
tell the o/p of following with explanations
1. #includestdio.h
int main()
{
struct value
{
int bit1:1;
int bit3:4;
int bit4:4;
}bit;
printf(%d\n,sizeof(bit));
return 0;
}
2.
#includestdio.h
int main()
{
struct value
{
int bit1: 1;
int bit3: 4;
int bit4: 4;} bit={1,2,2};
printf(%d %d %d\n,bit.bit1,bit.bit3,bit.bit4);
return 0;
}
3 can bit field be used in union??
--
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.- 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.
[algogeeks] Re: bits
@rohit: This is not about any serious problem, its about asking ur
self why then make different types of groups. You can also talk about
art and music by adding [art] or [music] in subject or talk about any
topic on earth. The question u need to ask is then why have different
groups. This will answer ur question.
On Jun 13, 7:31 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
@Souravsain : Is there any serious problem in this. Anyone can just add a
[C++] in the subject and uninterested people can make filters in gmail :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14
On Sun, Jun 13, 2010 at 6:35 PM, souravsain souravs...@gmail.com wrote:
@divya
Lets keep discussions in t his group limited to Algos and problems
neutral to any language.
Request you to post these C++ / C language specific questions to those
language specific groups. This will not only help this group remain
confined to its core purpose but will help you get better insights to
ur problem by language specific geeks there. For C++ I would recommend
you to try the group
http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en.
Regards,
Sourav
On Jun 13, 2:29 pm, divya sweetdivya@gmail.com wrote:
tell the o/p of following with explanations
1. #includestdio.h
int main()
{
struct value
{
int bit1:1;
int bit3:4;
int bit4:4;
}bit;
printf(%d\n,sizeof(bit));
return 0;
}
2.
#includestdio.h
int main()
{
struct value
{
int bit1: 1;
int bit3: 4;
int bit4: 4;} bit={1,2,2};
printf(%d %d %d\n,bit.bit1,bit.bit3,bit.bit4);
return 0;
}
3 can bit field be used in union??
--
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.- 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.
[algogeeks] Re: Endian-ness check
Printf(%d,(char)2); If this print 2 then lsb is 2, else if 0 then msb is 2 On Jun 13, 5:56 pm, debajyotisarma sarma.debajy...@gmail.com wrote: Is it possible to check endianness of a system in C without creating variable? i.e. Program should not contain any variable. -- 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: sleep
@sharad process A has gone to sleep asking kernel to wake it only if resource which it needs is available. So this process is sleeping. I think it is not possible for a process to interrupt another process. Lets understand it by these examples. Two processes can communicate, bit not interrupt. Communication is different from interrupts. If process A says Are u there? to process B, process B may say Yes or process B may not reply. It is process A's responcibility to handle all cases like got reply from B, did not get reply from B, wait indefinetly or return saying error. For interrupts lets understand it this way. Process A says I want to write this value to a file. Kernel may decide to write this to the actual file in the disk. This means disk device driver (this will be some routine in kernal code) will called by kernal to write the value to the file. For this time, process A may be put to sleep by kernel (but not necessarily. If process A is the only process running and it has more thread then some other thread of A may execute now). If put to sleep, Kernel will run another process B which may be, say a music audio for example. When the disk device driver routine will have completed the writing to file, it will give its retrun valur (remember its a routine / function for kernal) to kernal. The kernal will then interrupt the sleeping process A as your job is done. But this it can not do at any time. It has to find a proper instance during the running of process B which the kernel can do so. Because to do so, the kernal has do do a context switch. There are more issues to this. For example if kernel is executing some system call, called by B, it may not immediately do the context switch. In system calls the kernal may be manipulating some of its internal data structures like in call to malloc etc. So it will do the context switch only acter this data structure manipulation is over. On Jun 11, 3:28 pm, sharad kumar sharad20073...@gmail.com wrote: @souravsain means that process has slept and asked kernel to wake it only if its resource which it need,it got so at that time can any process interrupt it or not -- 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: Array Problem
Problme is not clear. Quesrtions: 1. Is the array all of positive numbers if yes then sort the array in ascending order. Now for every j, ji and i,j =n, A[j]A[i] and so A[j]-A[i] 0. Now if we want max(j-i) such that A[j]-A[i]0, it has to be j=n, the last element of A and i=1, the first element of A Time Complexity = O(nlogn) for sorting. 2. Is array consisting of +ve and -ve numbers? Again sort in ascending order(nlogn). We know A[j] is max of all elements. If A[j] = 0, then no solution exists. Else if A[j] +ve then again j=n, the last element of A and i=0 the first element is answer. Sourav Sain On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- 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: max sum
int FindMaxSum(int array[],int i)
{
if(iSize) //Size is array size, considered as global variable in
my solution
return 0;
int Sum1 = FindMaxSum(array,i+2);//cannot chose i+1 as that will
make it adjacent
int Sum2 = FindMaxSum(array,i+3);//at any place I cannot chose i
+1, so I chose i+2 above
//But chosing i+2 will mean cannot chose i+3 and I will miss that
route. So again call
//FindMaxSum with i+3;
if(Sum1Sum2) return Sum1+array[i];
else return Sum2+array[i];
}
This FindMaxSum must be called by some function like
F()
{
int Sum1 = FindMaxSum(array,0);//0 = first element of array
int Sum2 = FindMaxSum(array,1);
//Larger of Sum1 and Sum2 will be the answer.
}
This is a brute force approach and many calculations are done
repetedly. Dynamic Programing will improve the performance.
On Jun 11, 8:41 pm, divya sweetdivya@gmail.com wrote:
Given an array all of whose elements are positive numbers, find the
maximum sum of a subsequence with the constraint that no 2 numbers in
the sequence should be adjacent in the array.
Eg.
i) 3 2 7 10 should return 13 (sum of 3 and 10)
ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
--
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: os
Originally semaphore is a concept given by Dijkstra who says it is
something that can have two operations P and V both atomic. In an OS
(for example Unix) we have kernal objects called semaphore which
have the same two atomic oprerations. It is used to control
communication between 2 things (it can be 2 thread, 2 processes) as
you have rightly mentioned. You can 'wait' for a semaphore. Someone
else (thread/process) can broadcast a message that it has freed a
semaphore. So emphasis is on communication.
Mutex is more for controlling access to some resource. I do not know
how many threads will access an object, say a linked list. What I only
know is that the linked list should not be manipulated simultaneously
by 2 or more threads. So my focus is on makeing sure than the shared
object 'linked list' is in good shape. So a Mutex is in itself an
object which sort of guards the resoure. So the mutex says If a thread
wants to access / change the linked list, first lock me, then do ur
changes and unlock me.
Having said this, Binary semaphore is one which can change value
between 2 states (enerally 1 and 0) and most interestingly, we
implement a mutex object by having a binary semaphore inside the Mutex
object.
class Mutex
{
private BinSem MySem;
lock()
{
if MySem is 0 then lock or wait
}
unlock()
{
if MySem is 1 broadcast all am releasing and release.
}
}
On Jun 10, 8:56 pm, sharad kumar sharad20073...@gmail.com wrote:
@sharad but when it is binary semaphore then only one process is accessing
the resource,rest all are blockedwhich means that only that process who
locked bin. sem will unlock it .plzzz correct me if i m wrong
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to 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: sleep
This needs a bit clarification. Interrupts and priority are different. Priority of a process determines who often it gets CPU slot for execution. Interrupt is an external (hardware or software) event raised which may results in temporary context switch from the running process to handle the interrupt. So it uninterruptible priority is not clear. Please elaborate a bit more. On Jun 10, 8:50 pm, sharad sharad20073...@gmail.com wrote: Can process which is sleeping at uninterruptible priority be interrupted by higher priority process -- 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: ds
Guys We can solve this in O(n) time like this: Let me say total elements in array is 2N such that 1 to N are a's and N +1 to 2N (which I will again refer to as 1 to N) are b's Observation: If an element is on first 1 to N (an 'a') and has index i then in the final array its position index (in the final 2N array) will be i+(i-1) [current index + no. of positions lying to the left]. If an element is on the second 1 to N (the b's series) and has index j then in the final array of 2N, its index will be 2j. With this observation we start with the last element of first series, the a's and find its final position in result array. Place the element in final position. Take the element which is lying there and find this elements new position and go on. Example: start with temp=a6 (the last element of furst series) a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,b5,b6 temp=a6, final position of a6 = 6+(6-1) = 11. Put a6 in eleventh position and take the element at 11th position into temp: So now a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,a6,b6 and temp = b5. Final position of b5 = 2*5 = 10. Put b5 at 10th position and take previous element in temp. So now a1,a2,a3,a4,a5,a6,b1,b2,b3,b5,a6,b6 and temp = b4. Final position of b4 = 2*4 = 8. Put b4 at 8th position and take previous element at 8th in temp. So now a1,a2,a3,a4,a5,a6,b1,b4,b3,b5,a6,b6 and temp = b2, going this way we will have next position of b2 = 2*2=4 a1,a2,a3,b2,a5,a6,b1,b4,b3,b5,a6,b6 and temp = a4: next position of a4 = 4 + (4-1) = 7 a1,a2,a3,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=b1: next position of b1 = 1*2=2 a1,b1,a3,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=a2:next position of a2 = 2+(2-1)=3 a1,b1,a2,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=a3:next position of a3 = 3+(3-1)=5 a1,b1,a2,b2,a3,a6,b4,b4,b3,b5,a6,b6 and temp=a5:next position of a5 = 5+(5-1)=9 a1,b1,a2,b2,a3,a6,b4,b4,a5,b5,a6,b6 and temp=b3:next position of b3 = 3*2=6 a1,b1,a2,b2,a3,b3,b4,b4,a5,b5,a6,b6 and temp=a6:next position of a6 = 6 + (6-1)=11 But now we find a6 already present at 11. Hence arranged in O(n) time and constant space of 1 temp variable Thanks, Sourav Sain On Jun 9, 8:54 pm, Anurag Sharma anuragvic...@gmail.com wrote: Its not O(n) time. Anurag Sharma On Wed, Jun 9, 2010 at 5:46 PM, Jitendra Kushwaha jitendra.th...@gmail.comwrote: here is a sel explainatory algo given: abcd1234 abc1d234 ab1c2d34 a1b2c3d4 here is the link for the code :http://codepad.org/SZnufGc6 -- Regards Jitendra Kushwaha 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.- 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.
[algogeeks] Re: isomorphic trees
As per @Algoose's explanation, this can be found using the algorithm
to comapre if 2 binary trees are equal (quite often asked and found in
net). In this we generally go recursive and say
T1 is equal to T2
if T1=T2
and same holds for T1-Left, T2-Left (recursive call on left tree)
and same holds for T1-Right, T2-Right (recursive call on right tree).
We can use the same and change the calls as
if T1=T2
and same holds for T1-Left, T2-Right (recursive call on left tree)
and same holds for T1-Right, T2-Left (recursive call on right tree).
Sain
On Jun 9, 10:45 pm, saurabh gupta sgup...@gmail.com wrote:
is-isomorphic(t1, t2) {
t1ld = t1-left-data
t2ld = t2-left-data
//.
//base case for null or replace by sentinels and check
if( t1ld == t2ld t1rd == t2rd)
return is-isomorphic(t1ld, t2ld) return is-isomorphic(t1rd, t2rd)
if (t1ld == t2rd t1rd == t2ld)
return is-isomorphic(t1ld, t2rd) return is-isomorphic(t1rd, t2ld)
return false;
}
On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.com wrote:
@vadivel and anand
{ 1,2,3 } is *isomorphic* to { 1,3,2 }
{ 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 }
{ 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 }
so its nt necessary that right and left will interchange. it may or may
not. if all right and left are interchanged then it is mirror tree. i think
ur code is for mirror tree and not isomorphic tree..
--
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.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.- 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.
[algogeeks] Re: array question
@Anand: Your solution will take huge space and can easily be made to
run out of memory!
If arr5[] = {12,12,6,6,635}, you will run into n^3 space complexity.
For arr[5]={12,12,6,6,390625} it will be n^6.
Sain
On Jun 7, 3:27 am, Anand anandut2...@gmail.com wrote:
Here is my approch which runs in O(n).
http://codepad.org/d3pzYQtW
http://codepad.org/d3pzYQtW
On Sun, Jun 6, 2010 at 7:47 AM, divya jain sweetdivya@gmail.com wrote:
output willl be 12 12 5 6 6
On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote:
@divya: Does your problem require the output to be sorted also? What
will be the output required if inout is 12,5,6,12,6? Will it be
12,12,6,6,5 or 12,12,5,6,6,?
Sain
On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote:
Given an array with some repeating numbers. Like 12,6,5,12,6
output: 12,12,6,6,5
12 shud come before 6 since it is earlier in list. So cant use a
dictionary
--
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.- 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.
[algogeeks] Re: array question
@sharad: Your code seems will seem to give output 12,3,4 and not
12,3,3,3,4. It semes from the original description of the problem that
you also need to keep count of frequency of occurance of items in the
map.
Secondly, you have iterated through the map and got the elemenst in
same order as you had inserted. This is specific to the map in
programing language and may not be a feature available in all
languages. Conceptually map is a dictionary of name,value pair which
enables O(1) insertion, deletion and O(1) access. Traversal in the
order of insertion may not be always available. Let me know what you
feel.
Sain
On Jun 6, 4:39 pm, sharad kumar aryansmit3...@gmail.com wrote:
#includeiostream
#includemap
#includeiterator
using namespace std;
int main()
{
int arr[5]={12,3,4,3,3};
mapint,intmp;
int i=0;
for(i=0;i5;++i)
{
if(!(mp[arr[i]]))
mp[arr[i]]=i;
else
continue;
}
mapint,int::iterator it;
for(it=mp.begin();it!=mp.end();++it)
coutit-secondendl;
cin.sync();
cin.get();
return 0;
}
On Sun, Jun 6, 2010 at 3:14 PM, divya jain sweetdivya@gmail.com wrote:
@sharad
while storing each element in hash by your approach u ll check if its
already there in hash. so the complexity here will be O(n2). correct me if i
m wrong. isnt there ny better algo..?
On 6 June 2010 06:28, sharad kumar aryansmit3...@gmail.com wrote:
@dhivya:keep storing the first occurance element index in hash map and
then start insertin eleement based on index position
On Sun, Jun 6, 2010 at 12:31 AM, divya sweetdivya@gmail.com wrote:
Given an array with some repeating numbers. Like 12,6,5,12,6
output: 12,12,6,6,5
12 shud come before 6 since it is earlier in list. So cant use a
dictionary.
--
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.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
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.
--
yezhu malai vaasa venkataramana Govinda Govinda- 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.
[algogeeks] Re: ds
In order to make it inplace, time complexity has gone to n^2.
Rearrange(array,int N) //So array size is 2N
{
int i = 1;//points to index array[1] which has a2 since a1 is already
at the correct place;
int j = N;//array[0] to array[N-1] is a1 to aN. so j is index of b1
//it is assumed that N is
for(;j 2N;j++)
{
int bValue = array[j];
//right shift all elements from j to i (moving right to left)
for(int k = j; ki ; k--)
{
array[k]=array[k-1];
}
//k now is equal to i but a2 has shifted to array[2] from
array[1];
array[k] = bValue;
i = i+2;//No need to consider array[i+1] as that element (a2 in
first iteration is at its proper place
}
}
Space Complexity: Inplace
Time Complexity:
to move b1 : a2 to aN i.e., N-1 right shifts
to move b2 : a3 to aN i.e., N-2 right shifts
...
to move b(N-1): aN moved right: 1 right shift
so total shifts=1+2+3+.N-1
hence time complexity = n^2
Let me know if you have comments or improvements.
Sain
On Jun 6, 7:28 pm, sharad kumar sharad20073...@gmail.com wrote:
this is ques by adobe and they want inplace 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array question
@divya:go through the elements and keep inserting them in a BST. While inserting if elements already exists in BST, increase its frequency (Node of BST has element a nd frequency). Also if elemengs is newly inserted then also place it in a seperate array. So this array (say Array M) will become something like 12,5,6. This array will give order of first occurance of numbers. This whole process will take nlogn (BST creation assuming worst case that all elements are uinque in the input array). Once done, scan through each element in array M, find its corrosponding element in BST (logn) which will give the frequency. Fill those many indexes in input array with array M[i]. If all elements are uinque, this will also take nlogn. Else if input array has m distince elements, which will require us to look into BST for m times. hence entire process has time compelxity: O(nlogn + nlogn)= O(2nlogn) Space complexity: O(2n) [1 for BST and 1 for array M, worst case when all elements are unique in inpur array). Let me know your comments if any or any better appraoch as this once may have improvements. On Jun 6, 7:47 pm, divya jain sweetdivya@gmail.com wrote: output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote: @divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary -- 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.- 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.
[algogeeks] Re: Puzzle
Take a Nut, try putting it to all bolts (this is Comparing Nut with Bolt). If Nut goes not go and fit into bolt, keep the bolt on left, if Nut fits loose, keep the bolt on right and keep the bolt and nut which match, at centre. This is pivot of quicksort. All bolts to left of this central Nut+bolt are smaller and all towards right are large than central Nut + bolt. This will take N comparision. Then take second Nut. try fitting to central bolt. It will not fit. But we will be able to make a decision weather to move left or right. if this Nut is tight on bolt, try smaller bolts on left, else try larger bolts on right. This will take n/2 comparisions and we will find exact bolt fitting this 2nd nut. This process will again divide either left or right bolts into 2 part. and go on. This shold take NlogN time to complete the whole matching process as in case of quick sort. let me know your comments or improvements. Sain On Jun 6, 7:05 pm, sharad sharad20073...@gmail.com wrote: There are N nuts and N bolts, all unique pairs od Nut and Bolt You cant compare Nut with Nut. You cant compare Bolt with Bolt You CAN compare Nut with Bolt Now how would you figure out matching pairs of nut and bolt from the given N nut and Bolt. The basic soln is O(N^2). Give O(NlogN 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- 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.
