[algogeeks] Re: Amazon Intrerview
yes..DFS seems a good solution..then look until u get a Z..here is a piece of code.. static ArrayListInteger buffer; void findSum(TreeNode head, Node nodeZ,ArrayListInteger buffer) { if (head == null || head == nodeZ) return; buffer.add(head.data); ArrayListInteger c1 = (ArrayListInteger) buffer.clone(); ArrayListInteger c2 = (ArrayListInteger) buffer.clone(); findSum(head.left, nodeZ, c1); findSum(head.right, nodeZ, c2); } then look thu the arraylist to check see if the Y is there..Hope this helps..correct me if I'm wrong.. On Jan 8, 12:12 am, nishaanth nishaant...@gmail.com wrote: 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.
[algogeeks] Re: Amazon Intrerview
small correction in my post.. yes..DFS seems a good solution..then look until u get a Z..here is a piece of code.. void findSum(TreeNode head, Node nodeZ,ArrayListInteger buffer) { if (head == null || head == nodeZ) return; buffer.add(head.data); ArrayListInteger c1 = (ArrayListInteger) buffer.clone(); ArrayListInteger c2 = (ArrayListInteger) buffer.clone(); findSum(head.left, nodeZ, c1); findSum(head.right, nodeZ, c2); } then look thu the arraylist to check see if the Y is there..Hope this helps..correct me if I'm wrong.. On Jan 8, 12:12 am, nishaanth nishaant...@gmail.com wrote: 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.
[algogeeks] Re: Amazon Intrerview
my solution will not work..it works only if X Y or on the same side of subtree..like suppose if path is left node,root,right node..then the LCS will do..i think first we need to find whether both X Y r on the both side of subtree or different sides..depending on tht we need to find the path and Y..sorry for multiple posts.. On Jan 8, 3:18 am, Newbie grajesh...@gmail.com wrote: small correction in my post.. yes..DFS seems a good solution..then look until u get a Z..here is a piece of code.. void findSum(TreeNode head, Node nodeZ,ArrayListInteger buffer) { if (head == null || head == nodeZ) return; buffer.add(head.data); ArrayListInteger c1 = (ArrayListInteger) buffer.clone(); ArrayListInteger c2 = (ArrayListInteger) buffer.clone(); findSum(head.left, nodeZ, c1); findSum(head.right, nodeZ, c2); } then look thu the arraylist to check see if the Y is there..Hope this helps..correct me if I'm wrong.. On Jan 8, 12:12 am, nishaanth nishaant...@gmail.com wrote: 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.
[algogeeks] Re: Problem from ACM ICPC 2010
Just got AC for this problem. Here is simple solution: 1. Calculate degree for each vertex. If there is a degree 2, then answer is No. You may use hash_map or map here. 2. So at this step we don't have any verticies with 3 and more edges, only = 2 are allowed. Though, we should check if there is circle (cycle). If such exists and it doesn't have ALL vertices (it size is equal to n, so all children are connected next to each other), then answer is No, otherwise Yes. Used bfs for this. Good luck. -- 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: Adobe - Coding
RLE run length encoding is another solution because counting sort eats space whilw with RLE we can do it in time complexity O(n) Space Complexity O(1) Correct me if i am wrong ...i m talking about possibility not exactness. 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 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] Adobe Again..-Jig Saw
Jig saw puzzle. What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function? Thanks Shashank -- 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] Serialization in BT
Design an algorithm and write code to serialize a binary tree. Regards SHahsank -- 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] Serialization in BT
store inorder and preoder traversal of tree in arrays.. On Sat, Jan 8, 2011 at 5:49 PM, bittu shashank7andr...@gmail.com wrote: Design an algorithm and write code to serialize a binary tree. Regards SHahsank -- 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.
Re: [algogeeks] Re: Google Interview Question
@bittu I would like to discuss one thing regarding your approach , How you managed to put forward your 1st statement that is of Synchronization . On Fri, Jan 7, 2011 at 1:18 PM, Pedro Rezende web...@gmail.com wrote: Hi all! And what could be the best way to test / debug issues like these? 2011/1/7 vaibhav agrawal agrvaib...@gmail.com @Douglas, nicely put!!! On Fri, Jan 7, 2011 at 8:37 PM, Douglas Diniz dgdi...@gmail.com wrote: Some examples, supposing you do always the same thing: 1-) You have a program that use some random number, and based on the number the program do different things, and this different things crash the program at different places. 2-) you have a program that connect with a external server. Depending on the links status you could crash in different places. 3-) You have a program that talk with another program (or external server) through a protocol, and the protocol could do different things even if you do the same thing several times. 4-) Your program has timeouts that could expire based on the system usage, crashing the program in different places. 5-) Your program read some system variable and do different things. 6-) etc On Fri, Jan 7, 2011 at 12:09 PM, juver++ avpostni...@gmail.com wrote: The application is single threaded :) -- 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. -- 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 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 - Coding
@bittu , I think RLE , would be of no use ; as inp:AAABBRRGH out :3A2B2R1G1H so to reach the top 5 counts , there will be of no use . as stated earlier by others , HASH TABLE will be the one of best solution for this . maintain hash table in O(n) and then sort it .for top 5 counts. Please mend me if I am wrong somewhere as I am also in a learning phase. On Sat, Jan 8, 2011 at 7:08 AM, bittu shashank7andr...@gmail.com wrote: RLE run length encoding is another solution because counting sort eats space whilw with RLE we can do it in time complexity O(n) Space Complexity O(1) Correct me if i am wrong ...i m talking about possibility not exactness. 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 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. -- Lalit Kishore Sharma IIIT Allahabad (Amethi Capmus) 5th Sem -- 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] Serialization in BT
Another option is to serialize it in XML-like manner. -- 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.
[algogeeks] Re: Problem from ACM ICPC 2010
Hi.. thanks for your response. The number of kids: 3 = K = 10^9 I cant declare an array: long long A[10]; and how does dfs or bfs finds the components of the graph? because i have to verify if there is a cycle in all the components. -- 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 from ACM ICPC 2010
Use mapint, vectorint whichs maps vertex and all its neighbors. You should use bfs only to find if there is cycle (with a shape of circle). setint is useful to keep track of visited vertices. -- 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 from ACM ICPC 2010
Also, you may use hash_set and hash_map if such exists in your language. -- 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
Here is simple example: x = 2, z = 3, y = 1. Your code cannot reach node 1 while doing dfs from x. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] binary
Given a (decimal - e.g.3.72) number that is passed in as a string, print the binary rep¬resentation.If the number can not be represented accurately in binary, print “ERROR -- 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: codechef jan challenge
cam somebody provide hint in solving this problem ?? I am stuck :( . -- 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: codechef jan challenge
I don't think you should ask help for the problem of the *running *contest. -- 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: codechef jan challenge
oops it is running -- 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] binary
Her is the code...u need to add the if block for -ve numbers. 1 public static String printBinary(String n) { 2 int intPart = Integer.parseInt(n.substring(0, n.indexOf(‘.’))); 3 double decPart = Double.parseDouble( 4 n.substring(n.indexOf(‘.’), n.length())); 5 String int_string = “”; 6 while (intPart 0) { 7 int r = intPart % 2; 8 intPart = 1; 9 int_string = r + int_string; 10 } 11 StringBuffer dec_string = new StringBuffer(); 12 while (decPart 0) { 13 if (dec_string.length() 32) return “ERROR”; 14 if (decPart == 1) { 15 dec_string.append((int)decPart); 16 break; 17 } 18 double r = decPart * 2; 19 if (r = 1) { 20 dec_string.append(1); 21 decPart = r - 1; 22 } else { 23 dec_string.append(0); 24 decPart = r; 25 } 26 } 27 return int_string + “.” + dec_string.toString(); 28 } -Original Message- From: algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] On Behalf Of snehal jain Sent: Saturday, January 08, 2011 2:40 PM To: Algorithm Geeks Subject: [algogeeks] binary Given a (decimal - e.g.3.72) number that is passed in as a string, print the binary rep¬resentation.If the number can not be represented accurately in binary, print “ERROR -- 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. -- 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 Question
http://coders-stop.blogspot.com/2010/12/most-used-data.html On Jan 7, 5:24 pm, bittu shashank7andr...@gmail.com wrote: You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. 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 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 Intrerview
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Problem from ACM ICPC 2010
In the 3rd test case, how come the answer is Yes. 1,2 and 3 are forming a cycle. On Jan 8, 1:19 pm, juver++ avpostni...@gmail.com wrote: Also, you may use hash_set and hash_map if such exists in your language. -- 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] floating point
#includestdio.h int main() { float a=275.7; if(275.7a) printf(Hi); else printf(Hello); return 0; } #includestdio.h int main() { float a=75.7; if(75.7a) printf(Hi); else printf(Hello); return 0; } why the above two programs give different output? -- 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 from ACM ICPC 2010
I wondered that too...seems kid 3 gets too many wishes On Jan 8, 8:21 pm, bhawana goel bhawan...@gmail.com wrote: In the 3rd test case, how come the answer is Yes. 1,2 and 3 are forming a cycle. On Jan 8, 1:19 pm, juver++ avpostni...@gmail.com wrote: Also, you may use hash_set and hash_map if such exists in your language. -- 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: floating point
I guess it has to do with how float/double is stored on your computer. Always use an error tolerance when it comes to floating-point numbers comparison. By the way, on my machine it outputs the same thing(Hello) e.g. #define epsilon 10e-6 if(275.7-aepsilon) printf(HI); else printf(Hello); On Jan 8, 9:24 pm, priya mehta priya.mehta...@gmail.com wrote: #includestdio.h int main() { float a=275.7; if(275.7a) printf(Hi); else printf(Hello); return 0; } #includestdio.h int main() { float a=75.7; if(75.7a) printf(Hi); else printf(Hello); return 0; } why the above two programs give different output? -- 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: floating point
i know the EPS stuff. ok so it is machine dependent what output we get. On Sun, Jan 9, 2011 at 9:08 AM, Jammy xujiayiy...@gmail.com wrote: I guess it has to do with how float/double is stored on your computer. Always use an error tolerance when it comes to floating-point numbers comparison. By the way, on my machine it outputs the same thing(Hello) e.g. #define epsilon 10e-6 if(275.7-aepsilon) printf(HI); else printf(Hello); On Jan 8, 9:24 pm, priya mehta priya.mehta...@gmail.com wrote: #includestdio.h int main() { float a=275.7; if(275.7a) printf(Hi); else printf(Hello); return 0; } #includestdio.h int main() { float a=75.7; if(75.7a) printf(Hi); else printf(Hello); return 0; } why the above two programs give different output? -- 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: floating point
The 275.7 and 75.7 are doubles. The assignment statements round the double constant to float precision. Then you compare the unrounded double to the rounded float. If you had used 275.7e0 and 75.7e0 in the if statements, the results would have been Hello in both cases. Or to put it differently, 275.7 != 275.7e0 (not surprising) and 75.7 ! = 75.7e0 (ditto), but one double is greater than the float because the double is rounded down to form the float and the other is less than the float because the double is rounded up to form the float. Dave On Jan 8, 8:24 pm, priya mehta priya.mehta...@gmail.com wrote: #includestdio.h int main() { float a=275.7; if(275.7a) printf(Hi); else printf(Hello); return 0; } #includestdio.h int main() { float a=75.7; if(75.7a) printf(Hi); else printf(Hello); return 0; } why the above two programs give different output? -- 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: floating point
why is 1 double rounded down and the other double rounded up is it compiler dependent? On Sun, Jan 9, 2011 at 9:29 AM, Dave dave_and_da...@juno.com wrote: The 275.7 and 75.7 are doubles. The assignment statements round the double constant to float precision. Then you compare the unrounded double to the rounded float. If you had used 275.7e0 and 75.7e0 in the if statements, the results would have been Hello in both cases. Or to put it differently, 275.7 != 275.7e0 (not surprising) and 75.7 ! = 75.7e0 (ditto), but one double is greater than the float because the double is rounded down to form the float and the other is less than the float because the double is rounded up to form the float. Dave On Jan 8, 8:24 pm, priya mehta priya.mehta...@gmail.com wrote: #includestdio.h int main() { float a=275.7; if(275.7a) printf(Hi); else printf(Hello); return 0; } #includestdio.h int main() { float a=75.7; if(75.7a) printf(Hi); else printf(Hello); return 0; } why the above two programs give different output? -- 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.
Re: [algogeeks] floating point
On Sunday 09 January 2011 04:24:40 priya mehta wrote: #includestdio.h int main() { float a=275.7; if(275.7a) printf(Hi); else printf(Hello); return 0; } #includestdio.h int main() { float a=75.7; if(75.7a) printf(Hi); else printf(Hello); return 0; } why the above two programs give different output? If you add a printf(%f\n, a) after each variable initialization, you'll get: - for 275.7 - 275.700012 - for 75.7 - 75.67 The C compiler treats real constants as 'double'-s which is why you get 'Hello' for first and 'Hi' for the second. If the 'if' from the second program becomes: if ((float)75.7 a) [...] then you'll get a 'Hello'. Floating point, single precision, is not always a good choice: http://en.wikipedia.org/wiki/Single_precision You might want to use 'double' to keep future surprises out of the way. -- Mihai Donțu -- 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: floating point
@Priya: Most modern processors have arithmetic that conforms to the IEEE Floating Point Standard. Double constants have 53 bits of precision, while floats have 24 bits. Rounding depends on the bit to the right of the 24th bit from the left. If that bit is a 1, the number is rounded up, while 0 rounds down. I should point out that with many language implementations, there is a mechanism to control the rounding. While round to nearest is the default, it also may be possible to round up, round down, or round to zero. Dave On Jan 8, 10:01 pm, priya mehta priya.mehta...@gmail.com wrote: why is 1 double rounded down and the other double rounded up is it compiler dependent? On Sun, Jan 9, 2011 at 9:29 AM, Dave dave_and_da...@juno.com wrote: The 275.7 and 75.7 are doubles. The assignment statements round the double constant to float precision. Then you compare the unrounded double to the rounded float. If you had used 275.7e0 and 75.7e0 in the if statements, the results would have been Hello in both cases. Or to put it differently, 275.7 != 275.7e0 (not surprising) and 75.7 ! = 75.7e0 (ditto), but one double is greater than the float because the double is rounded down to form the float and the other is less than the float because the double is rounded up to form the float. Dave On Jan 8, 8:24 pm, priya mehta priya.mehta...@gmail.com wrote: #includestdio.h int main() { float a=275.7; if(275.7a) printf(Hi); else printf(Hello); return 0; } #includestdio.h int main() { float a=75.7; if(75.7a) printf(Hi); else printf(Hello); return 0; } why the above two programs give different output? -- 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.
Re: [algogeeks] Serialization in BT
we can make a doubly linked list of the 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] post and pre increment operators
int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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] post and pre increment operators
@priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.comwrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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.
Re: [algogeeks] post and pre increment operators
small correction printf evaluation starts from right to left. On Sun, Jan 9, 2011 at 10:59 AM, kartheek muthyala kartheek0...@gmail.comwrote: @priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.comwrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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] BT
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] post and pre increment operators
ok i got that On Sun, Jan 9, 2011 at 11:01 AM, kartheek muthyala kartheek0...@gmail.comwrote: small correction printf evaluation starts from right to left. On Sun, Jan 9, 2011 at 10:59 AM, kartheek muthyala kartheek0...@gmail.com wrote: @priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.comwrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] post and pre increment operators
Yeah you might be knowing how the expression evaluators work using stack right. printf also uses the same approach On Sun, Jan 9, 2011 at 11:06 AM, priya mehta priya.mehta...@gmail.comwrote: @kartheek so does it use stack for that? On Sun, Jan 9, 2011 at 11:03 AM, priya mehta priya.mehta...@gmail.comwrote: ok i got that On Sun, Jan 9, 2011 at 11:01 AM, kartheek muthyala kartheek0...@gmail.com wrote: small correction printf evaluation starts from right to left. On Sun, Jan 9, 2011 at 10:59 AM, kartheek muthyala kartheek0...@gmail.com wrote: @priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.comwrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] post and pre increment operators
ok but the output of int a=10,b; b=a++ + ++a; printf(%d,%d,%d,%d,b,a++,a,++a); is 22 13 14 14 howz that then? On Sun, Jan 9, 2011 at 11:11 AM, kartheek muthyala kartheek0...@gmail.comwrote: Yeah you might be knowing how the expression evaluators work using stack right. printf also uses the same approach On Sun, Jan 9, 2011 at 11:06 AM, priya mehta priya.mehta...@gmail.comwrote: @kartheek so does it use stack for that? On Sun, Jan 9, 2011 at 11:03 AM, priya mehta priya.mehta...@gmail.comwrote: ok i got that On Sun, Jan 9, 2011 at 11:01 AM, kartheek muthyala kartheek0...@gmail.com wrote: small correction printf evaluation starts from right to left. On Sun, Jan 9, 2011 at 10:59 AM, kartheek muthyala kartheek0...@gmail.com wrote: @priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.com wrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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. -- 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: post and pre increment operators
Evaluation of printf is from right to left !!!, Regards Sundi On Jan 9, 10:08 am, priya mehta priya.mehta...@gmail.com wrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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: post and pre increment operators
Evaluation of b=a++ + ++a; is also from right to left, so b = 22; but i am getting the o/p as 22,13,13,13 On Jan 9, 10:59 am, Sundi sundi...@gmail.com wrote: Evaluation of printf is from right to left !!!, Regards Sundi On Jan 9, 10:08 am, priya mehta priya.mehta...@gmail.com wrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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
http://www.ideone.com/mxvmt please see On Sun, Jan 9, 2011 at 11:34 AM, Sundi sundi...@gmail.com wrote: Evaluation of b=a++ + ++a; is also from right to left, so b = 22; but i am getting the o/p as 22,13,13,13 On Jan 9, 10:59 am, Sundi sundi...@gmail.com wrote: Evaluation of printf is from right to left !!!, Regards Sundi On Jan 9, 10:08 am, priya mehta priya.mehta...@gmail.com wrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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.
Re: [algogeeks] Re: post and pre increment operators
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: post and pre increment operators
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: post and pre increment operators
When you invoke the ++ operator (either pre- or post-increment) twice in the same statement, you invoke undefined behavior. How your compiler decides to resolve that is completely compiler-dependent. There is undefined behaviour because the same variable is modified more than once between consecutive sequence points, i.e., the sequence point just before the call of printf, and then the sequence point just after the evaluation of the arguments to printf. -- 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
it would be more accurate to call that behaviour (as in order of evaluation of arguments) unspecified rather than undefined. It is compiler dependent whether it takes from right to left or the other way round. -- 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: floating point
to add to @Dave's reply. He explained it elaborately in thishttp://groups.google.com/group/algogeeks/browse_thread/thread/20af6e098297d413thread Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the scripture of this age. On Sun, Jan 9, 2011 at 9:56 AM, Dave dave_and_da...@juno.com wrote: @Priya: Most modern processors have arithmetic that conforms to the IEEE Floating Point Standard. Double constants have 53 bits of precision, while floats have 24 bits. Rounding depends on the bit to the right of the 24th bit from the left. If that bit is a 1, the number is rounded up, while 0 rounds down. I should point out that with many language implementations, there is a mechanism to control the rounding. While round to nearest is the default, it also may be possible to round up, round down, or round to zero. Dave On Jan 8, 10:01 pm, priya mehta priya.mehta...@gmail.com wrote: why is 1 double rounded down and the other double rounded up is it compiler dependent? On Sun, Jan 9, 2011 at 9:29 AM, Dave dave_and_da...@juno.com wrote: The 275.7 and 75.7 are doubles. The assignment statements round the double constant to float precision. Then you compare the unrounded double to the rounded float. If you had used 275.7e0 and 75.7e0 in the if statements, the results would have been Hello in both cases. Or to put it differently, 275.7 != 275.7e0 (not surprising) and 75.7 ! = 75.7e0 (ditto), but one double is greater than the float because the double is rounded down to form the float and the other is less than the float because the double is rounded up to form the float. Dave On Jan 8, 8:24 pm, priya mehta priya.mehta...@gmail.com wrote: #includestdio.h int main() { float a=275.7; if(275.7a) printf(Hi); else printf(Hello); return 0; } #includestdio.h int main() { float a=75.7; if(75.7a) printf(Hi); else printf(Hello); return 0; } why the above two programs give different output? -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Intrerview
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: post and pre increment operators
@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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] tic tac toe
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] post and pre increment operators
b=(11++)+ (++10)=11+11=22 a=12 in printf the control goes to right first , i.e. ++a , so ++a =(++12), (a becomes 13 but ++a is not printed) then control moves to a but as the next expression pushed in stack is of the same variable so control moves to a++. without printing a a++= 13++, (now a becomes 14) , the control moves now to a=14, the control moves to ++a now as the value of a is changed ++a=14 (it evaluates a from all expressions and then prints) the expressions are popped from stack ( right to left) and printed left to right . as a++=13,a= 14, ++a=14 I hope now things get clearer to you On 9 January 2011 11:16, priya mehta priya.mehta...@gmail.com wrote: ok but the output of int a=10,b; b=a++ + ++a; printf(%d,%d,%d,%d,b,a++,a,++a); is 22 13 14 14 howz that then? On Sun, Jan 9, 2011 at 11:11 AM, kartheek muthyala kartheek0...@gmail.com wrote: Yeah you might be knowing how the expression evaluators work using stack right. printf also uses the same approach On Sun, Jan 9, 2011 at 11:06 AM, priya mehta priya.mehta...@gmail.comwrote: @kartheek so does it use stack for that? On Sun, Jan 9, 2011 at 11:03 AM, priya mehta priya.mehta...@gmail.comwrote: ok i got that On Sun, Jan 9, 2011 at 11:01 AM, kartheek muthyala kartheek0...@gmail.com wrote: small correction printf evaluation starts from right to left. On Sun, Jan 9, 2011 at 10:59 AM, kartheek muthyala kartheek0...@gmail.com wrote: @priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.com wrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind this? -- 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. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] BT
One approach would be to convert both the trees to well formed flat-tree representation and then reduce the problem to a substring matching one (can use KMP/Boyer-Moore/Rabin-Karp for it). eg. 1 2 3 4 5 is flattened to (using postorder traversal) (1 (2 4 .) (3 . 5)) Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the scripture of this age. On Sun, Jan 9, 2011 at 12:10 PM, nishaanth nishaant...@gmail.com wrote: 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.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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@Juvier, @yq Zhang In your approach, when you are asked pop_front() you keep popping from one stack and pushing them to another and then from the other pop the top element. What happens is this top element happens to have been the Min element?Example stack1 {(2,2),(4,2),(3,2),(6,2)} (a,b) = ( element, min) then you are asked pop_front(), you push to another stach like below stck2: {(6,2),(3,2),(4,2),(2,2)}. Then you remove (2,2)! Ok. But all elements in your stack2 still say 2 is the min element. But 2 is no more in the queue (or for that matter in the stacks we are using). On Jan 4, 9:07 am, yq Zhang zhangyunq...@gmail.com wrote: @sourav, As Juvier++ pointed out, it's an **amortized** O(n) algorithm. That's because each element can be at most popped twice. Thanks Yq On Mon, Jan 3, 2011 at 11:20 AM, sourav souravs...@gmail.com wrote: @yq Zhang, To pop if you are going to pop all from first stack and push into the second stack, then does your operation remain constant time? Please note that we need constant time implementation for the 3 functions pop_front, push_rear and get_min(). Goint by your approach, not all of them are constant time. Thanks, Sourav On Jan 3, 9:44 pm, yq Zhang zhangyunq...@gmail.com wrote: Push into one stack. When pop first pop all from the first stack and push into the second stack. Then pop from the second stack On Jan 3, 2011 7:42 AM, MOHIT mohit...@gmail.com wrote: if only two stack are used but how pop_front is get? suppose if element comes in order 12 15 4 3 7 20 then in min queue 1. 12 (12) 2. 12 12 (12,15) 3. 12 12 4 (12,15,4) 4.12 12 4 3 (12,15,4,3) 5.12 12 4 3 3 (12,15,4,3,7) 6.12 12 4 3 3 3 (12,15,4,3,20) we can get min in constant by pop of stack but how pop front will work using two stack only in constant 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.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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
When you push into stack2, you have to recompute the min value. So after you push into stack2, it will be: (6,6),(3,3),(4,3),(2,2) On Thu, Jan 6, 2011 at 6:34 PM, sourav souravs...@gmail.com wrote: @Juvier, @yq Zhang In your approach, when you are asked pop_front() you keep popping from one stack and pushing them to another and then from the other pop the top element. What happens is this top element happens to have been the Min element?Example stack1 {(2,2),(4,2),(3,2),(6,2)} (a,b) = ( element, min) then you are asked pop_front(), you push to another stach like below stck2: {(6,2),(3,2),(4,2),(2,2)}. Then you remove (2,2)! Ok. But all elements in your stack2 still say 2 is the min element. But 2 is no more in the queue (or for that matter in the stacks we are using). On Jan 4, 9:07 am, yq Zhang zhangyunq...@gmail.com wrote: @sourav, As Juvier++ pointed out, it's an **amortized** O(n) algorithm. That's because each element can be at most popped twice. Thanks Yq On Mon, Jan 3, 2011 at 11:20 AM, sourav souravs...@gmail.com wrote: @yq Zhang, To pop if you are going to pop all from first stack and push into the second stack, then does your operation remain constant time? Please note that we need constant time implementation for the 3 functions pop_front, push_rear and get_min(). Goint by your approach, not all of them are constant time. Thanks, Sourav On Jan 3, 9:44 pm, yq Zhang zhangyunq...@gmail.com wrote: Push into one stack. When pop first pop all from the first stack and push into the second stack. Then pop from the second stack On Jan 3, 2011 7:42 AM, MOHIT mohit...@gmail.com wrote: if only two stack are used but how pop_front is get? suppose if element comes in order 12 15 4 3 7 20 then in min queue 1. 12 (12) 2. 12 12 (12,15) 3. 12 12 4 (12,15,4) 4.12 12 4 3 (12,15,4,3) 5.12 12 4 3 3 (12,15,4,3,7) 6.12 12 4 3 3 3 (12,15,4,3,20) we can get min in constant by pop of stack but how pop front will work using two stack only in constant 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.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.