?
Solved

Reverse the order of words

Posted on 2004-11-17
13
Medium Priority
?
2,561 Views
Last Modified: 2008-01-09
Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it
0
Comment
Question by:skvenkee
  • 3
  • 2
  • 2
  • +5
13 Comments
 
LVL 48

Expert Comment

by:Mikal613
ID: 12605588
can it be in vb6?
0
 
LVL 9

Expert Comment

by:Rodney Helsens
ID: 12605688
this sounds like homework
0
 
LVL 48

Expert Comment

by:Mikal613
ID: 12605731
really?
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:skvenkee
ID: 12605839
This is not a homework. I am trying to get solutions for as many algorithms as possible for the interview. I do have a solution with me. I just want the algorithm and not a program.

My algorithms is:

1. Start from the end of the array and keep decrementing until you see a <space>
2. Then start another loop that then, stores the characters from that index to the next space
3. Continue this until you reach the start.


The efficiency of this algorithm is O(nk) where n is the total number of characters in the sentence and K is the length of the biggest word in the sentence.

Does anyone know a better (efficient ) algorithm than this.

It will also be helpful if anyone have a link or file containing solutions to these type of algorithms.

Thanks.
0
 
LVL 48

Expert Comment

by:Mikal613
ID: 12605879
well you split with the spaces and just start from the bottom of the array
0
 
LVL 24

Expert Comment

by:fridom
ID: 12605903
very simple:
import List

reverse_sentence sentence =
    List.unwords (List.reverse (List.words sentence))


Main> reverse_sentence "this is a sentence"
"sentence a is this"

Feel free to find out the language used

Regards
Friedrich
0
 
LVL 3

Expert Comment

by:MaximKammerer
ID: 12606369
Hi skvenkee,

IMO the efficency of your algorithm is O(n); n being the array lengh. AFAIK in an O(something) description, constant factors are ignored.

Two questions:
- Target array == source array or different?
- What kind of efficency (memory, processing or code size)?

Best regards,
Maxim
0
 

Author Comment

by:skvenkee
ID: 12606907
I refer to efficiency as the execution time of the algorithm.
It will be great if the target array is same as the source array
0
 
LVL 1

Expert Comment

by:darcone
ID: 12608241
Here is a simple algorithm that should perform pretty well:

char c;
            
for(int i = 0; i < word.length/2; i++) {
                  
  c = word[i];
  word[i] = word[word.length - 1 - i];
  word[word.length - 1 - i] = c;
}

word is a character array.

Hope this helps!
0
 
LVL 1

Expert Comment

by:darcone
ID: 12608251
Oh sorry.. nervmind that post :-/ That was reversing characters, not words
0
 
LVL 3

Expert Comment

by:MaximKammerer
ID: 12610083
Hi svenkee,

I can't see how your original algorithm description can be much improved while using two seperate arrays.
You don't need a second loop, just remember the space, continue counting down 'til the next space and do a memcopy of the chars in between. I think there is not much room for improvement in this - you _do_ have to look at every character to make sure where the spaces are.

(Just brainstorming):
If your target is not to produce another char[], but could be a different structure you could replace all the spaces with \0 while counting up and just put all the pointers to first letters into a stack / list / array (expensive resizing?) -> voilá, you'll get a sorted structure of words. You can walk it up or down and get the order you want. Main advantage: You don't have to do memcopys.

At the moment I don't see any reasonably performing method of re-using the same array. I think you'd need a maximum word size and even then you would have to use twice as many memcopys. This only would be useful if the array is huge in size and the words remain very small compared to the size of the array. Then the algorithm could look somewhat like this:

0) bufferL and bufferR have a size of 2*MaxWordSize
1) Coming from left, read words sorted into bufferL until PosLeft > Length - PosRight (initially Length==PosRight -> 1 word read at 1st iteration)
2) Write bufferR to Array at PosRight (initially empty / 0 -> nothing done at 1st iteration)
3) Coming from right, read words sorted into bufferR until Length-PosRight > PosLeft
4) Write bufferL to Array at Length-PosLeft
5) Repeat  at 1) until PosRight <= PosLeft

Best regards,
Maxim
0
 
LVL 3

Accepted Solution

by:
baboo_ earned 800 total points
ID: 12615627
svenkee:

Best solution, I think, is this:

1) Reverse the whole array - O(n)

"Punch me in the face"

         becomes

"ecaf eht ni em hcnup"


2) Reverse each word in place
       a) Read until you reach the end of the word - O(n) in total
       b) Then swap first and last letters, working your way in to the middle - O(n/2) worst case

for a grand total of O( n + n + n/2 ) = O((5/2)n), which is better than O(nk) whenever the longest string is longer than 2.5 characters.


Aaaand, here's the site you're looking for:

http://www.techinterview.org/index.html


BTW, Maxim: when you're comparing two algorithms where one asymptotically increases, then you're right - constants can be left off, as they are asymptotically insignificant.  For example, if you were comparing O( 5n ) versus O( n^2 ), you would be correct to say that the 5 doesn't matter.  But for algorithms that are in the same complexity category (like these two), there's nothing wrong with leaving in constant multipliers and the like, since it allows you to differentiate algorithmic complexity with higher granularity.

baboo_
0
 

Expert Comment

by:nee_nee
ID: 12822632
I wanted to do something like this but instead I wanted to read a file, search for states that are 2 char length and make the country for them United States.  Can anyone assist me with this?
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

The SignAloud Glove is capable of translating American Sign Language signs into text and audio.
If you are a mobile app developer and especially develop hybrid mobile apps then these 4 mistakes you must avoid for hybrid app development to be the more genuine app developer.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…
Screencast - Getting to Know the Pipeline

807 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question