Reversing a string should be linear time.
void reverse(char *str)
{
int i = 0;
int j = strlen(str)-1;
while(i j)
swap(str[i++], str[--j]);
}
On Nov 27, 12:47 am, shady sinv...@gmail.com wrote:
what is the time complexity of this?
str_reverse(str){
if(isempty(str)) return
i guess it should be swap(str[i++], str[j--]); because we
already subtracted 1
On Tue, Nov 27, 2012 at 8:58 PM, Don dondod...@gmail.com wrote:
swap(str[i++], str[--j]);
--
code:-
http://ideone.com/yMQSK
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
Queues are basically linked lists with head and tail pointers. It is
possible to reverse the list by change of pointers in O(n) time n O(1)
space.
PS: Not considering queue ADT with enqueue dequeue operations.
On Wednesday, 20 June 2012 18:34:46 UTC+5:30, Navin Kumar wrote:
How to reverse a
void Reverse(std::queueint pQ)
{
if(pQ.empty())
return;
int item=pQ.front();
pQ.pop();
Reverse(pQ);
pQ.push(item);
}
Regards
On Wed, Jun 20, 2012 at 9:41 PM, enchantress elaenjoy...@gmail.com wrote:
Queues are basically linked lists with head and tail pointers. It is
possible to reverse the
Just a query :
If the queue is implemented as an array, then is it not possible to swap
the elements from the last and first position onwards until you reach
middle point. Wont this use O(1) space and O(n/2) time.
On Wed, Jun 20, 2012 at 1:56 PM, Hassan Monfared hmonfa...@gmail.comwrote:
using recursion,
reverse(queue,front,rear) {
if( front rear ) {
swap( queue[front], queue[rear] );
reverse( queue, front+1, rear-1);
}
}
On Wed, Jun 20, 2012 at 11:53 PM, Sreeprasad Govindankutty
sreeprasad...@gmail.com wrote:
Just a query :
If the queue is implemented as an
Abhishek Sharma : swap is not allowed because you can push at only one
side of queue.
it's not dequeue.
On Wed, Jun 20, 2012 at 11:21 PM, Abhishek Sharma abhi120...@gmail.comwrote:
using recursion,
reverse(queue,front,rear) {
if( front rear ) {
swap( queue[front], queue[rear] );
awesome question :D :D
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
@atul
true... :P:P:P:P
and definately linux will develop within a year after release of
windows95...:P
On Jan 30, 11:20 am, Karthikeyan V.B kartmu...@gmail.com wrote:
hi,
can anyone tell me how i can convert exe back to c source?
--
You received this message because you
In general it is not possible to go from a lower-level language to a
higher-level language. There have been some attempts to do this, but
they have not been very successful. Some debuggers do embed source
information into the executable, and that might be helpful in
recovering the original source.
if this would have been possible . we can get all software for free.
On Wed, Feb 1, 2012 at 12:36 AM, Don dondod...@gmail.com wrote:
In general it is not possible to go from a lower-level language to a
higher-level language. There have been some attempts to do this, but
they have not been
@atul: can you explain what this is doing?
for(i=0;in;i++)
{
pre=reverse(root-children[i],NULL);
if(pre)
{
pre-children[i]=root;
}
}
when u do tree reversal I see that child points to
@Arun : yup ...rite...
so i guess this will work..once pointer has been updated for parent node.
there is no need of other point from children[i+1] to n. so adding one
more loop at the end.
for(i=0;in;i++)
{
pre=reverse(root-children[i],NULL);
if(pre)
@all just a small bug found after discussing with one of the friend , i
forgot to put the for loop , in 2nd if condition .
Thanks
Shashank
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
A better representation for a n-ary tree would be
struct node{
int data;
node* left;
node* sibling;
}
Like in a binary tree the second ptr points to its right child . Here it
points to its sibling.This one saves space and also We know in each level
we have how many nodes
@Shashank,
I
How abt representing the tree as a graph. If you represent it in
adjacency mattix or as a map of edges e.g. Edge{from}{to}=edge weight,
which could be a constant in this case. all you need to is to reverse
the pairs.
Order of complexity is o(e) and you can reach to leaf nodes and push
them in a
@Ankur : didnt understand , how you want to represent n-ary using this
structure.
struct node{
int data;
node* left;
node* sibling;
}
if root has 5 children then how will root point to its children using 2
pointers( left ,sibiling)
On Wed, Dec 21, 2011 at 3:13 PM, Ankur Garg
@shashank:
yeah here is the algo , please me know if you find any bug:-
node *Reverse(node *root,node *pre)
{
flag=0;
for i=0 to n
if (root-children[i]!=NULL)
{
flag=1;
}
end for
if( ! flag)
{
i guess there is one more if i am not wrong;
if(n==null)
{
n=n.children[++j];
return null;
}
here when n==NULLyou are doing n.children[++j].will give
segmentation fault.
On Wed, Dec 21, 2011 at 7:05 PM, WgpShashank
adding one more check :- this one is updated
node *Reverse(node *root,node *pre)
{
flag=0;
for i=0 to n
if (root-children[i]!=NULL)
{
flag=1;
break;
}
end for
if( ! flag)
{
add
adding break to first loop...just to avoid unnecessary iterations.
if (root-children[i]!=NULL)
{
flag=1;
break;
}
end for
On Wed, Dec 21, 2011 at 10:59 PM, atul anand atul.87fri...@gmail.comwrote:
@shashank:
yeah here is the
here is my code
ListNode list=new LinkeListNode();
public ListNode reverseTreeandReturnListContainingAllLeafNOdes(Node n)
{
int i=0;
static int j=0;
if(n==null)
{
n=n.children[++j];
return null;
}
just a thought . to reverse the given tree is like finding
inorder successor of the nodes.
and every time we find a leaf node add it to the linked list.
On Tue, Dec 20, 2011 at 11:23 PM, WgpShashank shashank7andr...@gmail.comwrote:
here is my code
ListNode list=new LinkeListNode();
Hey Shashank
Unfortunately I cudnt understand the problem
What do u mean by reversing the tree here :(..
On Tue, Dec 20, 2011 at 11:23 PM, WgpShashank shashank7andr...@gmail.comwrote:
here is my code
ListNode list=new LinkeListNode();
public ListNode
@ankur : for the given tree above instead of parent pointing to its child ,
it would be child pointing to its parent after reversing
i guess thats wat he is trying to say.
On Tue, Dec 20, 2011 at 11:38 PM, Ankur Garg ankurga...@gmail.com wrote:
Hey Shashank
Unfortunately I cudnt
@Atul
Even i thought so..but then the definition of leaf node is that its a node
which doesnt have any children...then the answer is root of the original
tree so I got confused here :(
On Wed, Dec 21, 2011 at 12:20 AM, atul anand atul.87fri...@gmail.comwrote:
@ankur : for the given tree
How do you represent the N-ary tree? If you represent child nodes as a
list, reversing this child node list at each node will solve the
problem right? I may be wrong.
On Dec 20, 10:50 am, atul anand atul.87fri...@gmail.com wrote:
@ankur : for the given tree above instead of parent pointing to
@rahul : i dont think so , i guess what u are telling will be like creating
mirror image of the tree.
On Wed, Dec 21, 2011 at 6:23 AM, rahul rahul...@gmail.com wrote:
How do you represent the N-ary tree? If you represent child nodes as a
list, reversing this child node list at each node will
@Ankur , we need to reverse the pointer for each node so that points to
their parents. thats what reversal a n-Ary tree means
hope it help . have a look at my code , its just thought i approached using
preorder traversal , but not getting correct answer , seems like missing
something
@all Reversing the N-ary tree means reversing the pointer nodes pointing to
, as i shown above , children back points to their parents ..
here is is structure of N-Ary Tree we can think of
Class Node
{
String label;
ListNode children;
}
you can try in any language C/C++/java etc.
Thanks
@atul,, yeah , but can you write some proper psuedo code/ Algorithm then we
can discus more about test cases.
Thanks
Shashank
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
Nodes of these XOR lists look like
typedef struct {
PTRS_AS_INT next_xor_prev;
DATA data;
} NODE;
You need 2 pointers to adjacent nodes to traverse. If p and q are
these pointers, then to advance to the next node,
tmp = p;
p = q ^ p-next_xor_prev; // not correct C; add casts to make it
count no of 0s,1s and 2s.fill first 0s followed by 1s den 2s :)
On Thu, Aug 25, 2011 at 11:37 PM, icy` vipe...@gmail.com wrote:
not enough information, imo. Tell me more about the given string...
is the string made up of consecutive integers/characters ? Are there
always the same number of
int reverse(int n)
{
int i=9*( abs(n/10 - n%10) );
return i;
}
On Wed, Aug 24, 2011 at 9:56 PM, Dave dave_and_da...@juno.com wrote:
@Anika: So you want to reverse the digits of the decimal
representation of a number. Extracting decimal digits requires
division and modulus by 10.
On Thu, Aug 25, 2011 at 7:58 PM, amit kannaujiya
amitkannaujiyan...@gmail.com wrote:
int reverse(int n)
{
int i=9*( abs(n/10 - n%10) );
i=i+n;
return i;
}
On Wed, Aug 24, 2011 at 9:56 PM, Dave dave_and_da...@juno.com wrote:
@Anika: So you want to reverse the digits of the
@Amit: This gives, e.g., reverse(26) as 36 rather than 62.
Dave
On Aug 25, 9:28 am, amit kannaujiya amitkannaujiyan...@gmail.com
wrote:
int reverse(int n)
{
int i=9*( abs(n/10 - n%10) );
return i;
}
On Wed, Aug 24, 2011 at 9:56 PM, Dave dave_and_da...@juno.com wrote:
@Anika: So
not enough information, imo. Tell me more about the given string...
is the string made up of consecutive integers/characters ? Are there
always the same number of each character type? And the goal is to
braid , like the hairstyle, as much as possible (if the previous
answer is no, all braids
@Anika: So you want to reverse the digits of the decimal
representation of a number. Extracting decimal digits requires
division and modulus by 10. Normally this is done by division, but as
a different recent thread has shown, division can be accomplished by
bit operations, comparisons, and
What exactly do you mean by reverse a number?
Please define what that means and give an example.
Don
On Aug 11, 12:13 pm, Rajeshwar Patra rajeshwarpa...@gmail.com wrote:
how can we reverse a number using bitwise operators?
--
*Rajeshwar Patra,*
*MCA final year,*
*Nit Durgapur*
--
You
first create a temp char array with size equal to dat of the string
length.scan each word(char by char until end is white space is
reached)...then start filling the new array from last by subtracting the
original string length with each word lengthcrct me if i'm wrong..
//BE COOL// kavi
m nt getting correct output for this program can any1 tell me wats the error
#includeiostream.h
#includeconio.h
#includestring.h
void main()
{
char a[]=Hello daughter;
couta\n;
int l,i,j,k,c;
int temp;
l=strlen(a);
for(i=0;il/2;i++)
{
temp=a[i];
a[i]=a[l-i-1];
a[l-i-1]=temp;
}
Heya,
Someone please explain dinesh's approach with an example.
I am not able to get the answer. Doing some mistake.
--
AP
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To
explanation for dinesh's algo.
let the sting is:arr[]=my name is kamakshi
first reverse the whole string by swapping characters from beginning and end
strlen(arr)=19;
now process till 19/2=9
swap(arr[0].arr[strlen-1])
now swap (arr[1],arr[strlen-2]);
this way u will reverse the string in place.
I am looking for a solution with no 'tail' node available/static types
used etc.
Also with algorithms given without above two conditions, i don't see
they doing the right thing for me. Maybe i need to check more.
Have you guys tried to see if this is working for you?
On Jul 17, 4:42 pm, bharath
@Navneet:
Its not possible to solve this without a single tail pointer. I have come
across this question saying it requires a single pointer and that pointer is
the tail pointer. So along with head you need a tail pointer or a global
pointer. Otherwise cannot keep track of header for reversed
To do it in O(1) for N bits, you need a table lookup. But for 32 bits, the
table is 16 Gb. A compromise is to build a table of 256 entries to reverse
the bits in a byte (it's easy to write a program to do this). Then the
result is something like
unsigned reverse_bits(unsigned x)
{
static
#includestdio.h
typedef struct ll
{
int data;
struct ll *link;
}node;
node *nw,*next,*prev=NULL,*head,*temp,*head1;
void print(node *temp)
{
while(temp!=NULL)
{
printf(%d\n,temp-data);
temp=temp-link;
}
}
void print_reverse(node *temp)
{
if(temp!=NULL)
{
any type of replace would need at least one extra memory space.
recursion is the worst, depends how you implement recursion. one
iteration might depends on another, which depends one other, and so
on.. each iteration hold its own stack
On Sep 23, 1:59 pm, Albert alberttheb...@gmail.com
I agree with Nishant.
For inplace replacement we need to swap two place for that we need
index, which is not possible without additional variables.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
please let me know solution using extra memory.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
@albert
why r u asking for a non optimal solution??
On Sat, Sep 25, 2010 at 11:24 PM, albert theboss alberttheb...@gmail.comwrote:
please let me know solution using extra memory.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
Here is another approach. Remove the first character. Reverse the
rest of the string recursively. Append the character at the end.
Others have given solutions along these lines, but they have various
mistakes. Here's one that I believe is correct. As pointed out
already, this is not a good
use it like this
char* strrev(char *)
strrev(str)
void strrev(char *str)
{
xstrrev(str , 0, strlen(str)); // code posted by Nishant
}
:-)
On Sep 23, 11:35 pm, albert theboss alberttheb...@gmail.com wrote:
Ur function prototype is not similar to one i posted before
check it
char * strRev(char* string)
{
static int ptr;
if(ptr == lengthOf(string)/2 || ptr == lengthOf(string/2)+1)
{
return string;
}
ptr++;
strRev(swap(string, ptr-1, lengthOf(string)-ptr-2));
}
where swap returns a string with the chars at the two
@nishanth :
could u give me any solutions without global variable or static
variable
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send
@albert
i think you know the solution and u r just testing others.so post the
solution and stop this discussion..
On Sat, Sep 25, 2010 at 12:48 AM, albert theboss alberttheb...@gmail.comwrote:
@nishanth :
could u give me any solutions without global variable or static
variable
sorry i dont know the solution.
i just expecting such answer
--
You received this message because you are subscribed to the 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 dont think that without giving 1st and last index, this is possible.i
m using i and j as 1st and last index respectively
On Sat, Sep 25, 2010 at 1:00 AM, albert theboss alberttheb...@gmail.comwrote:
sorry i dont know the solution.
i just expecting such answer
--
You
On Mar 21, 7:40 am, hijkl [EMAIL PROTECTED] wrote:
. How to reverse all the bits in a unsigned integer? an signed
integer (you have to keep the sign of the integer)?
For an unsigned int, the following algorithm can be used (I believe
you can find in in the Hacker's Delight book by H.Warren)
It would make a nice homework question in an undergraduate data
structures course, and there might be some applications where it
performs marginally better than the standard approach, which is a
single pointer to a single array. To grow the array, allocate new
memory twice as large as the
61 matches
Mail list logo