[algogeeks] Re: Amazon Intrerview

2011-01-08 Thread Newbie
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

2011-01-08 Thread Newbie
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

2011-01-08 Thread Newbie
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

2011-01-08 Thread juver++
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

2011-01-08 Thread bittu
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

2011-01-08 Thread bittu
 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

2011-01-08 Thread bittu
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

2011-01-08 Thread snehal jain
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

2011-01-08 Thread LALIT SHARMA
@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

2011-01-08 Thread LALIT SHARMA
@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

2011-01-08 Thread juver++
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

2011-01-08 Thread nishaanth
@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

2011-01-08 Thread rgap
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

2011-01-08 Thread juver++
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

2011-01-08 Thread juver++
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

2011-01-08 Thread juver++


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

2011-01-08 Thread snehal jain
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

2011-01-08 Thread Rahul Singal
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

2011-01-08 Thread juver++
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

2011-01-08 Thread Rahul Singal
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

2011-01-08 Thread Rajesh Gadipuuri
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

2011-01-08 Thread Aviral Gupta
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

2011-01-08 Thread Gene
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

2011-01-08 Thread bhawana goel
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

2011-01-08 Thread priya mehta
#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

2011-01-08 Thread Jammy
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

2011-01-08 Thread Jammy
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

2011-01-08 Thread priya mehta
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

2011-01-08 Thread Dave
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

2011-01-08 Thread priya mehta
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

2011-01-08 Thread Mihai Donțu
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

2011-01-08 Thread Dave
@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

2011-01-08 Thread Harshal
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

2011-01-08 Thread priya mehta
 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

2011-01-08 Thread kartheek muthyala
@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

2011-01-08 Thread kartheek muthyala
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

2011-01-08 Thread Harshal
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

2011-01-08 Thread priya mehta
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

2011-01-08 Thread kartheek muthyala
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

2011-01-08 Thread priya mehta
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

2011-01-08 Thread Sundi
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

2011-01-08 Thread Sundi
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

2011-01-08 Thread priya mehta
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

2011-01-08 Thread Harshal
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

2011-01-08 Thread priya mehta
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

2011-01-08 Thread Harshal
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

2011-01-08 Thread Harshal
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

2011-01-08 Thread nishaanth
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

2011-01-08 Thread nishaanth
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

2011-01-08 Thread nishaanth
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

2011-01-08 Thread nishaanth
@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

2011-01-08 Thread Avi Dullu
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

2011-01-08 Thread Algoose chase
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

2011-01-08 Thread Priyanka Chatterjee
@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

2011-01-08 Thread divya
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

2011-01-08 Thread Priyanka Chatterjee
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

2011-01-08 Thread Avi Dullu
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.

2011-01-08 Thread sourav
@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.

2011-01-08 Thread yq Zhang
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.