http://123maza.com/25/data759/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send
@above:
Any Undirected Graph trivially has a cycle!
Consider any two adjacent vertex A and B, I can go from A to B and then from
B to A (since they are connected by an undirected edge).
Hence, any Undirected Graph trivially has a cycle.
Any contradictory views? please let me know :)
Thank
use a hash map
On Mon, Jun 14, 2010 at 12:14 AM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:
give an algo to find a unique number in an array
for eg a[]={1,3,4,1,4,5,6,1,5}
here 3 is the unique number as it occur only once... moreover array
contains only 1 unique number
--
With
This C code will create a new mirror copy tree.
mynode *copy(mynode *root)
{
mynode *temp;
if(root==NULL)return(NULL);
temp = (mynode *) malloc(sizeof(mynode));
temp-value = root-value;
temp-left = copy(root-right);
temp-right = copy(root-left);
return(temp);
}
On 13 June 2010 17:07, BALARUKESH
Why not just pop all elements from stack ( O(n) ) and insert it in a self
balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and
inorder traversal ( O(n) )and push elements in stack again.
Time = O(nlog(n) + n)
Space=O(n) (for storing the tree)
Anurag Sharma
On Sun, Jun 13,
Are all the numbers within some given range?
If so then keep a count of all and later find out the non repeating one.
otherwise, make a balanced BST and insert every element in it and increment
the counter of the node if already present in the tree and then do inorder
traversal to find out the
Here is an implementation for BST and search an element in BST in O(logn )
time
On Sun, Jun 13, 2010 at 8:04 PM, Lekha lek...@gmail.com wrote:
Inorder traversal till u reach the kth element(If it is sorted in
descending order, otherwise go till (n-k)th element)..
On Sun, Jun 13, 2010 at
Even your own stack will give TLE :)
Try solving this question with binary solution of tower of hanoi and you
will definately pass the time limit.
--
Regards
Jitendra Kushwaha
MNNIT, Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
Uninitialized global variables are stored in .bss section of the process
memory and initialised global variables are stored in .data section of the
memory. In the linking stage, they get the actually physical address. But
since x and y are local variables they are just stored in stack while
On Mon, Jun 14, 2010 at 8:35 AM, sharad kumar sharad20073...@gmail.comwrote:
@rohit..i m not able to find this ques in this group so plzz help
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
how can we print the reconstructed configuration of the towers after k
steps in towers of hanoi problem in O(1) 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
I think there should be additional constraint added that atmost 1 disk can
be placed in ground. Otherwise one can place all disks on ground and put
them in order in the last peg :D
Anurag Sharma
On Mon, Jun 14, 2010 at 2:01 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
give the algorithm
xor all the elements. Similar elements would become 0. Remaining would be
unique element.
On Mon, Jun 14, 2010 at 12:14 AM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:
give an algo to find a unique number in an array
for eg a[]={1,3,4,1,4,5,6,1,5}
here 3 is the unique number as it occur
Use iterative version :http://en.wikipedia.org/wiki/Tower_of_Hanoi
Anurag Sharma
On Mon, Jun 14, 2010 at 12:36 AM, ANUJ KUMAR kumar.anuj...@gmail.comwrote:
http://www.spoj.pl/problems/HAN01/
i implemented it using stack but am getting tle someone please help
--
You received this message
Using Segment tree below is the implementation.
http://codepad.org/5jVxLmsA
On Sat, Jun 12, 2010 at 6:14 AM, Jitendra Kushwaha jitendra.th...@gmail.com
wrote:
This is direct question of segment tree. read the topcoder's tutorial for
segment tree
--
Regards
Jitendra Kushwaha
MNNIT,
I second this opinion. Lets keep discussion limited to algorithms only.
On Mon, Jun 14, 2010 at 5:47 AM, Roshan Mathews rmath...@gmail.com wrote:
On Sun, Jun 13, 2010 at 18:36, souravsain souravs...@gmail.com wrote:
Lets keep discussions in t his group limited to Algos and problems
neutral
reverse in order traversal till u reach kth node. reverse inorder means
first visit right child then print data nd then left.
On 14 June 2010 08:34, Lekha lek...@gmail.com wrote:
Inorder traversal till u reach the kth element(If it is sorted in
descending order, otherwise go till (n-k)th
@jalaj
endian specific.
Anurag Sharma
On Sun, Jun 13, 2010 at 11:54 PM, Modeling Expert
cs.modelingexp...@gmail.com wrote:
@jalaj
Yes , this is endian ness specific. On windows/x86 linux which are
little endian, ch[0] would be lower 8 bits. On solaris/power pc which
are big endian this
@rohit..i m not able to find this ques in this g
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
Using segment tree: it does using O(logn) complexity
just check it out:
http://codepad.org/5jVxLmsA
On Sat, Jun 12, 2010 at 2:10 AM, Modeling Expert
cs.modelingexp...@gmail.com wrote:
My previous post went unfinished :((
anyway this is summary of algo . (as N is very large , sorting could
be
@lekha u dont noe total elements in bst...for finding that 1 more traversal
is required...can it be done in 1 pass only
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
Seems correct to me :)
Anurag Sharma
On Sun, Jun 13, 2010 at 11:23 PM, amit amitjaspal...@gmail.com wrote:
Can anyone tell what is Stack Space required for Quick Sort and Merge
Sort.And how in each case it can be modified.
Correct me if I am wrong on this.
Space Complexity of Merge Sort (
why a.c gets closed. well comma operator has left to right associativity.
for eg
a=(2,3,4) ;
here is a=4 after the statement is executed so similarly why not here. y c.c
is not closed here?
On 13 June 2010 22:16, souravsain souravs...@gmail.com wrote:
For Problem 3 see section 4.2 Using feof()
Create a recurrence and then the algorithm.
On Mon, Jun 14, 2010 at 2:31 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
give the algorithm for toi if... the a disk can be placed on top the disk
just larger then it and on the ground..
--
With Regards,
Jalaj Jaiswal
+919026283397
@ vadivel,yes i mean the former has got unused space in which the latter
can occupy
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
i meant make an array of indexes.. index[]={0,1...,n-1}
now sort the original array and move the elements of index array
accordingly..
now follow modelling expert's algo nd while taking largest-smallest check if
the index of largest in index array index of smallest in index array.
On 13 June
@sharad: Do you have some article that explains cycle detection in
bfs? Will be of help if you can share that or book or so which
explains cycle detection via bfs.
@amit: Both in directed and undirected graphs you can find a cycle in
O(|v|) time using a dfs. See Algorithm Design Manual Second
use XOR
On Mon, Jun 14, 2010 at 1:49 PM, kunzmilan kunzmi...@atlas.cz wrote:
Write the array as a vector string S, eg
(1,0,0,0...)
(0,0,1,0...)
(0,0,0,1...)
etc.
Find the quadratic form S^T.S. On its diagonal, occurences of all
numbers are counted.
kunzmilan
On 13 čvn, 20:44, jalaj
range of numbers is not given..so cannot find maxnum without sorting..which
is nlogn
On Tue, Jun 15, 2010 at 12:21 AM, asit lipu...@gmail.com wrote:
Let's assume array contains only +ve numbers and maximum number is
MAXNUM
Take an array arr[MAXNUM]
for(i=1; i=MAXNUM; i++)
arr[i]=0;
http://codepad.org/ricAcQtu
On Sun, Jun 13, 2010 at 9:13 PM, Anand anandut2...@gmail.com wrote:
Here is an implementation for BST and search an element in BST in O(logn )
time
On Sun, Jun 13, 2010 at 8:04 PM, Lekha lek...@gmail.com wrote:
Inorder traversal till u reach the kth element(If
@saurav: your code will always print 2 irrespective of the system's
endianness!
correct thing to do is:
printf(%d, *(char *) (0x0002))
--Sundeep.
On Mon, Jun 14, 2010 at 3:02 AM, Minotauraus anike...@gmail.com wrote:
How about a pointer? :D
On Jun 13, 5:56 am, debajyotisarma
Dis'd do :-D
int klargest_recur(int k,List* head)
{
if(!head || !k) return -1;
int rsize = 0;
if(head-right) rsize = size(head-right);
if(k == rsize + 1) return head-data;
if(k = rsize) return klargest_recur(k, head-right);
else return klargest_recur(k - rsize - 1,
#includemalloc.h
char *f()
{char *s=malloc(8);
strcpy(s,goodbye);
}
main()
{
*f()='A';
printf(%c,*f()); }
find o/p n explain it
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
Given n points in the space. Now given a new point you have to find
the nearest neigbour to it from initial n points
This can be done in O(n), a trivial solution.
This can also be accomplished in O(logn) by space partioning. here is
a link:
CopyBits(x,p,n,y)
write c code to copy n LSBs from y to x starting LSB at 'p'th
position using bitwi se.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from
Using Hashing
space : O(n)
time : O(n)
Using sorting
space : O(1)
time : O(nlogn)
special case: (all elements are of the range of the array then using count
sort)
space : O(1)
time : O(n)
any better solutions???
--
Regards
Jitendra Kushwaha
MNNIT, Allahabad
--
You
Which book are you studying for OS ?
--
You received this message because you are subscribed to the Google Groups
Algorithm 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
@ souravsain
Don't understand your solution.
if u type convert to char how u can say that msb is in higher memory address?
i think (char) will alway give the value of the lsb.
How u r checking endian ness?
normal endian ness check program
main()
{
int i=1;
char *p=(char*)i;
if(*p==1)
printf(Small
Given N points how can we find a triangle formed using any of the
three points with maximum area?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group,
Using XOR, you can do in one pass, does it have any problem ?
Like, element = element XOR array[i], for each i = 1,2, ..., N. What
'element' contains at the end will be the unique element.
Thanks,
Sathaiah
On Mon, Jun 14, 2010 at 1:49 PM, kunzmilan kunzmi...@atlas.cz wrote:
Write the array
XOR all the elements of array, the remaining value is the required unique
number.
(XORing two same numbers results in zero)
--
Thanks Regards,
Priyanka Chatterjee
Third Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
I have this code snippet:
This code snippet defines a boundary coordinates on the screen wrt to the
center(of the screen).
if( x x_center )
x_border = x_center - x_shift;
else
x_border = x_center + x_shift;
if( y y_center )
y_border = y_center - y_shift;
use hash table , and if you find for a number , a entry already
exists , mark it unwanted !
in the end , hash table entries are unique numbers .
@kunzmilan : could you explain a bit more, couldn't get full idea of
what you wrote
-Manish
On Jun 14, 1:19 pm, kunzmilan kunzmi...@atlas.cz wrote:
@jalaj jaiswal
given array contain 3,6 both r unique.
Is this the exact question?
if array is 6,3,4,1,4,5,6,1,5 than we can solve using xor properties.
int a,b=5;
a=b^b; //value of a is 0 convert in binery form and do u will get
a=0^a;//value of a is a itselt
Program:
@vivek : was that a joke?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Mon, Jun 14, 2010 at 11:40 AM, souravsain souravs...@gmail.com wrote:
@sharad: Do
On Mon, Jun 14, 2010 at 5:13 AM, Sundeep Singh singh.sund...@gmail.comwrote:
@saurav: your code will always print 2 irrespective of the system's
endianness!
correct thing to do is:
printf(%d, *(char *) (0x0002))
--Sundeep.
... dereferencing a very low address pointer, are you sure?
XOR has the following problem...
assume array is 2,3,3,2,1,2
here the unique element is 1 but using XOR we get
2^3^3^2^1^2=3
XOR works only when all the elements except the unique element occur even
number of times.
--
You received this message because you are subscribed to the Google
Dear Anuj,
Its easy to do.
lets take an example
say we have 4 disks. We will require 2^4-1 = 15 steps to solve it.
Now suppose we are at 6th step..
write it binary form using 4 bits(since we have 4 disks) 0110
now from left 0 means 4th disk is on initial peg
second bit 1 means disk 3 is on left
Suppose points are given in the form (a1, b1) (a2, b2). (an, bn).
- find the point furthest away from the origin by maximizing a^2 +
b^2 [ will take O(n) time]
- Find the point at maximum distance from this point. Use distance
formula. Sqrt( (a2-a1)^2 + (b2-b1)^2) [will take O(n) time]
-
Write a pseudo code 4 that..using c/c++...
how can we find the depth(height) of 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,
Don't understand the question.
explain differently.
On 6/14/10, siddharth srivastava akssps...@gmail.com wrote:
I have this code snippet:
This code snippet defines a boundary coordinates on the screen wrt to the
center(of the screen).
if( x x_center )
x_border = x_center -
@Sathaiah :
offcourse XOR have problem . All tha other numbers are not repeated even
nuber of times so its not necessary that they cut out to give 0
for eg a[]={1,3,4,1,4,5,6,1,5,6}
XOR will give output as 1^3 which is not done
If every other element is repeated even times then XOR is OK
@jalaj
Hi All,
char s[]={'a', 'b', 'c', 'd'};
printf(%d\n, strlen(s));
o/p is 8
can anybody plz explain why 8 ?
Mohit
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
Guys, XOR operation you are suggesting wont work, as a number can be
repeated more than 2 times or may not be even number of times. Check the
example given by him:-
*a[]={1,3,4,1,4,5,6,1,5}*
Here 1 is repeated 3 times, and which certainly is not the unique element
but will leave its affect on XOR
@Sharad
assuming p(n-1)
o/p=
x [ ~ { (~((~0)n)) (p-n+1) } ] | [ y [~((~0)n)]]
Mohit
On Tue, Jun 15, 2010 at 2:10 PM, sharad sharad20073...@gmail.com wrote:
CopyBits(x,p,n,y)
write c code to copy n LSBs from y to x starting LSB at 'p'th
position using bitwi se.
--
You
@divya
u r correct that in a=(2,3,4) 4 gets in a
but if u remove parenthesis then u get 2 in a
here although parenthesis is there bt that is for function call i.e f(1,2,3)
but effectively its written 1,2,3
so a.c get closed
i hope i m clear...plzzz correct me if i m wrong sumwhere
--
You
XORing the numbers can not give the correct result, this will give correct
result if repeation is in even times otherwise it will give incorrect
result.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
did you forget to return any value from function f() ?
Anurag Sharma
On Mon, Jun 14, 2010 at 7:19 PM, sharad sharad20073...@gmail.com wrote:
#includemalloc.h
char *f()
{char *s=malloc(8);
strcpy(s,goodbye);
}
main()
{
*f()='A';
printf(%d,12424);
will give the efficient solution
if it print 1 then little indian otherwise big endian.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this
Priyanka,
will XOR work for
{1,1,1,3,3,4,5}
Thanks
Sri
On Mon, Jun 14, 2010 at 7:02 PM, Priyanka Chatterjee
dona.1...@gmail.com wrote:
XOR all the elements of array, the remaining value is the required unique
number.
(XORing two same numbers results in zero)
--
Thanks Regards,
just check the signs of the i, j components of vector from the centre of
screen to (x,y)
pseudo code:-
getQuadrant(x,y){
string Q[]={1st,4th,2nd, 3rd};
vx=(x=midx)?0:1
vy=(y=midy)?0:1
return Q[(vx1)|vy]
}
Anurag Sharma
On Mon, Jun 14, 2010 at 5:55 PM, siddharth srivastava
Xor works only if a number is repeated is repeated even number of times. It
will not work in other case.
On Mon, Jun 14, 2010 at 7:02 PM, Priyanka Chatterjee dona.1...@gmail.comwrote:
XOR all the elements of array, the remaining value is the required unique
number.
(XORing two same numbers
But what about the Stack Space Used while doing Merge and Quick Sort?
On Mon, Jun 14, 2010 at 9:30 AM, Anurag Sharma anuragvic...@gmail.comwrote:
Seems correct to me :)
Anurag Sharma
On Sun, Jun 13, 2010 at 11:23 PM, amit amitjaspal...@gmail.com wrote:
Can anyone tell what is Stack
plzzz comment on this question
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
@debajyoti sharma
your method works only if a number is repeated even number of times ...try
for this int array[]={6,3,4,1,4,5,6,1,1,5};... so xor method fails... or can
dere be any modofication in it ??
On Mon, Jun 14, 2010 at 6:18 PM, Debajyoti Sarma
sarma.debajy...@gmail.comwrote:
@jalaj
can only think of O(N^3) brute force solution - any better ideas? :)
On 14 June 2010 16:57, amit amitjaspal...@gmail.com wrote:
Given N points how can we find a triangle formed using any of the
three points with maximum area?
--
You received this message because you are subscribed to the
@BALARUKESH
i think the problem is to maximize the diffrence j-i according to condition
and in your solution j can be less than i.
This problem can be solved by sorting the array first, then taking
diffrence.
this solution is done in O(nlogn).
--
You received this message because you are
Just to point out :
how many times have you all repeated this --
Xor works only -- even number of times. It will not
work...
Why don't you all read some earlier posts before posting. :P
--
Rohit Saraf
Second Year
here's a recursive solution
int depth(Node n){
if (n==NULL)
return 0;
else
return 1 + max( depth( n.right ) , depth( n.left ) );
}
calling depth(root) will yield the height of the tree
On 6/15/10, ajay kumar ajaykr@gmail.com wrote:
Write a pseudo code 4 that..using
ya i forgot that...considering that plz explain o/p
i.e
#includemalloc.h
char *f()
{char *s=malloc(8);
strcpy(s,goodbye);
return s;
}
main()
{
*f()='A';
printf(%c,*f());
}
--
You received this message because you are subscribed to the Google
you didn't put an '\0' at the end of the string
strlen looks for a '\0' in the string and here it happened to be 8
bytes after the starting position of s
On 6/15/10, mohit ranjan shoonya.mo...@gmail.com wrote:
Hi All,
char s[]={'a', 'b', 'c', 'd'};
printf(%d\n, strlen(s));
o/p is 8
can
how to implement doubly linked list using only one pointer ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
sort all arrays
for each number in A , A[k]
find two numbers in B and C such that their sum is -A[k]
this can be done in O(n) time:
set i at the beginning of B and j at the end of C
while in or j=0
if ( B[i] + C[j] == -A[k] ) return true
if ( B[i] + C[j] -A[k] ) increase i
else decrease
@ajay:recursively count the number of nodes then use formula h=log2(number
of nodes)
On Wed, Jun 16, 2010 at 5:39 AM, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
here's a recursive solution
int depth(Node n){
if (n==NULL)
return 0;
else
return 1 + max(
height of current node = max(height of left child, height of right child) +1
Hope now you get that? :)
Anurag Sharma
On Tue, Jun 15, 2010 at 5:31 PM, ajay kumar ajaykr@gmail.com wrote:
Write a pseudo code 4 that..using c/c++...
how can we find the depth(height) of BST ?
u have to use XOR linked list
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
76 matches
Mail list logo