Code Kata – Reverse words in a string

Dave Thomas creates a website called Code Kata, Who encourage developers improve their skills by keep practicing coding, trying to find better solutions for some questions.

Today I met an interesting question: How to reverse words in a string?
For example, given a string "The quick brown fox jumped over the lazy dog", reversed string needs to be “dog lazy the over jumped fox brown quick The”. The thing is you can not use extra memory to do it, you had better manipulate the reverse logic in the original text string.

To solve this question, I remembered I read a good book several years ago, it is called Programming Pearls ,written by John Bentley.

In chapter 2, section “The power of Primitive”, the author gives the solution of transform an array vector, which is clean, elegant and efficient. I used this solution to solve this problem.
The algorithm has two steps:
1. First reverse the entire string by character
For example: "The quick brown fox jumped over the lazy dog" becomes
“god yzal eht revo depmuj xof nworb kciuq ehT”
2. Then reverse each word by character
For example: “god yzal eht revo depmuj xof nworb kciuq ehT” becomes
“dog lazy the over jumped fox brown quick The”

You see it is pretty easy, right? No need extra memeory, no need substring.This is the power of the algorithm.

Here I post the java version of the solution, you can easily implement this algorithm in C or other language.

public class StringRerverse {

private int wordStartIndex;
private int wordEndIndex;
private StringBuffer sBuffer;

String reverse(String string)
{

this.sBuffer = new StringBuffer(string);

sBuffer.reverse();

int size = sBuffer.length();
int pos = 0;

while(pos < size)
{
if(findNextWord(pos) == true)
{
reverseWord(sBuffer,wordStartIndex,wordEndIndex);
pos = wordEndIndex+1;
}
else
{
break;
}
}


return sBuffer.toString();

}
boolean findNextWord(int startFrom)
{
int start = startFrom;

while (start< sBuffer.length()-1 && sBuffer.charAt(start) == ' ')
{
start++;
}
if(start == sBuffer.length() -1 )
{
return false;
}

wordStartIndex = start;

int end = start+1;
while(end < sBuffer.length()-1 && sBuffer.charAt(end) != ' ' )
{
end++;
}
if(end == sBuffer.length() -1 )
{
wordEndIndex = end;
}
else
{
wordEndIndex= end-1;
}
return true;
}

void reverseWord(StringBuffer sBuffer,int wordStartIndex, int wordEndIndex)
{
int length = wordEndIndex - wordStartIndex + 1;
for(int j = 0; j<length/2; j++)
{

int startIndex = wordStartIndex + j;
int endIndex = wordEndIndex - j;
char c = sBuffer.charAt(startIndex);
sBuffer.setCharAt(startIndex, sBuffer.charAt(endIndex));
sBuffer.setCharAt(endIndex, c);
}
}



public static void main(String[] args)
{
StringRerverse reverse = new StringRerverse();

String string = new String("The quick brown fox jumped over the lazy dog");
String reverseString = reverse.reverse(string);
System.out.println("reversed String: "+reverseString);

}
}

From Good to Great Developer

Last week I watch a presentation called “From good to great developer“ from www.infoq.com.
Here is the link : http://www.infoq.com/presentations/Good-to-Great-Developer-Chris-Hedgate

Chris Hedgate made a really great presentation. He pointed out that good developer writes code quickly but hard to maintain; but great developer has long term goal and try to write clean code and make it easier to maintain.

He also gave the advices how to become a great developer. I really like the 4-stage learning model he introduced: unconscious incompetence, conscious incompetence, conscious competence and unconscious competence. The learner in different stage will take different actions: inspiration, training, practice and reflection.


Talking about becoming a great developer, which is the same idea coming from Agile. It means craftsmanship, professionalism, discipline, and mastery. I think every serious developer should have a goal to become a great developer or master programmer, just like kong-fu master or samurai. It is a whole life’s practice.

Being a great developer is not an easy job. You need to understand the agile principles, understand design patterns, have disciplines and patience to write clean codes and keep refactoring; you have to constantly reflect yourself; you need to keep learning new technologies. And you need to help other people and try to motivate and inspire them. This is raising the bar, it is hard, but this is the only way to create a remarkable career for you, the only way to give you a passion, and the only way to transcend yourself.

Here I add some other videos which share the same philosophy:

1. Craftsmanship and Ethics, by Robert Martin:
http://www.infoq.com/presentations/craftmanship-ethics

2. Developing Expertise: Herding Racehorses, Racing Sheep, by Dave Thomas
http://www.infoq.com/presentations/Developing-Expertise-Dave-Thomas

Dave Thomas is the author of “Pragmatic Programmer, from journeyman to master”. This video talks about the Dreyfus model, which is 5-stage learning model. The details about it is in the Book “Pragmatic learning and thinking” by Andy Hunt.

3. I Come to Bury Agile, Not to Praise It, by Alistar CockBurn
http://www.infoq.com/presentations/cockburn-bury-not-praise-agile
This video talks about a Shu-Ha-Ri, a 3-stage learning model, I first learned Shu-Ha-Ri from his book “Agile Software Development”

4. Deliberate Practice in Software Development, by Marry Poppendieck,
http://www.infoq.com/presentations/poppendieck-deliberate-practice-in-software-development
Marry Poppendieck is regarded the first person who apply Toyota’s Lean technology into software development, this video she provide the 10-year rule theory, emphasizes the craftsmanship and clean code.

5. Productive Programmer: On the Lam from the Furniture Police, by Neal Ford
http://library.theserverside.com/detail/RES/1242309506_447.html?asrc=vcatssc_sitepost_05_14_09
The author of “Productive programmer”, he talked about the principles in his book, the book of “Peopleware” and “pragmatic learning and thinking”

6. Transcendence and Passing Through the Gate, by Dave West
http://www.infoq.com/presentations/transcendence-gate-dave-west

This video is really interesting, it talks about agile, but he use the concept of Zen. He mentioned the famous 10 Bulls pictures which describe 10 different stages of a human being to describe the agile development.

Learning from the Book Of Five Rings

Miamoto Musashi was a very famous Japanese saumari, who wrote a book called The book of Five Rings. I first heard of him by Alistir CockBurn’s book – Agile Software Devleopment.

The good thing is Alistair pointed out what we can learn from his book into our software development. Here is what Alistair pointed out:

• Do not develop an attachment to any one weapon or anyone school of fighting.
Use the rang of them without getting stuck in anyone.
• Practice and observe reflectively.
Practice hard, win big (pointed out by Jeff Sutherland, the SCRUM creator)
• Win
Pay more attention to winning than to looking good,
“Do not do anything useless”

Here I also would like to copy what his rules for learning the art ( from page 41):
1. Think of what is right and true.
2. Practice and cultivate the science.
3. Become acquainted with the arts.
4. Know the principles of the crafts.
5. Understand the harm and benefit in everything.
6. Learn to see everything accurately.
7. Become aware of what is not obvious.
8. Be careful even in small matters.
9. Do not do anything useless.

The interesting thing is that in the book, Mushasi use carpentry as a metaphor for mastering his science of martial art. (from page 9, Likening the Science of Martial Arts to Carpentry). It seems every word can be used to software development, used as principles of mastering programmer's skills.

In future I will post more about this book.

My vision of a good software developing team

We need to do things in the right way. In Chinese, “way” means “TAO”. If we follow the TAO of the software development, then we can deliver the great product in a short time.

Following are my vision for a good software developing team, and what the TAO should be:

- Follow good design
We need follow good OO design principles, and good design patterns. A good design is a foundation of a software product, and a good design is the DNA of a good product.

- Build Quality in
We need to balance between long-term benefits with short term benefits
Our software should be: flexibility, maintainability, and readability.

- Write clean code, constantly keep refactoring, continuously improving design
I like Uncle Bob’s saying” If code is messy, so does the product”.
Bad code slows down the productivity
Only one way to go fast is going well, writing clean code.

- Design for maintenance
The only way to develop maintainable code is to design the maintainability at design phase

- Deliver DRY project
DRY means “Don’t Repeat Yourself”.
Here I would like to mention the definition of what does mean a project is Done:
1. Deliver the product to our customer
2. Developers improve their skills;
3. Team gain knowledge;
4. The design and code is easier for future project
I think all these 4 things together means a project is done, but currently we only focus on No. 1, which cause on the problem in future: since the code is not reusable, we have to rebuild the entire app, or we have to duplicate all the old code, which either by fixing duplicating bugs or by spending long time to fix the issues by adding new codes. Finally we spend more time and money by reinventing the wheels.

- Test Driven Development
We need are not only use JUnit, but also to make sure our design is easier for unit test, our framework is easier to using unit test.

- Build automation
Our build automation should support everywhere, server side code, client side code, and test code.
Everything we need should be checked in the repository, including dependent libraries, config files, property files, database script, build tools, etc.

- Use static analysis tools
Currently there a lots of open source static analysis tools. For example they can find the potential bugs; tell you how complex of your code, how messy your code is, and tell you the coverage of your test code, etc. which will help us improving our code quality greatly

- Foster knowledge sharing and internal training
We need to build an environment which can foster knowledge management in our company, which is called ‘ba’ in “Lean technology”. We need to use Wiki, internal forum, internal training to share the knowledge for all the developers.
Knowledge management is very important

- Following the Agile
We need not only do the agile practices, but need also fully understand the agile principles and its values.
And each team needs to use different agile methods.
Developer needs to follow XP;
Manager team needs to follow Scrum
The whole company needs to follow Lean technology

- Training developer to be professionalism
We need our developers have the concept of:
Professionalism, craftsmanship, discipline, ethics, etc.

Next I want to discuss more about the gap between the manager and developer. I think there is a role we are missing – “coach”. I think a good coach will be a bridge connecting developers and managers, his role is filling the gap.
I would like to make a metaphor: thinking our software team as a sports team- whether basketball team or a hokey team. In a sports team a coach plays a very important role:
- Design the wining strategy for the team
- Instruct each player not only what to do but also how to do;
- start timeout when he found the issue during the game, either by substituting a new player or set up a new strategy;
- Training players and improve their skills;
- Motivate players and find their potentials;



So my suggestion is we need a coach or several coaches in our development team.

Be prepared to leave

I was totally motivated by the book -The passionate programmer. Now I am trying to copy the author’s idea and write an essay using his style, the name is called “Be prepared to leave”.

Usually people start to update their resume when they want to find a new job, then they realize their problems: they found it is hard to review what they did in the past few years; they realize their skills might be outdated; they don’t know where to go, just randomly submit their resumes. Every thing seems to be by accident, not deliberately.

So how can we plan our career deliberately? My answer is be prepared to leave. If you have this mind set, you have a positive attitude of doing your daily jobs. Suppose you are going to leave or be fired, then it force you to update your resume regularly, to update your resume, it forces you to review yourself constantly:

• For every project you finished, you ask yourself: how did I finish it, what kind of skills I used, how can I add a good achievement in my resume? How can I improve it? How can I use the current new technology into my project, so that I can improve my work and also I can add it into my resume? If you summarize and review your work constantly, you will find you have many good points to put into your resume.

• Find your blind spots. Since you are going to leave, you need to take chance trying to learn what you don’t know. Think it proactively, when you find your blind spot, then try to fix it as soon as possible. When you find you have a challenge to do some job, then it is probably a blind spot for you, and it is a good opportunity for you to get improved. For example you found it is very painful for you to deploy or build a project, because it needs you manually do many different steps and easy to make error. So why not improve the build script and improve the build automation process? If you have this attitude, you will find every job is interesting, even it is a maintain job.

• Research the market regularly, try to find the skills the market need and what skills you need to improve and learn; try to find the company you want to go and find out what kind of technologies they are using, then try to learn it, try to use them into your current project.

In summary when you have a “be prepared to leave” attitude, you will not find your daily job is boring any more, you will find many opportunities to improve yourself. Sooner or later your skills and thoughts will go to next level, and you will be easily got a good new job when chances come.

IPhone development: memory management rules

Right now I am learning the IPhone development using objective-C, I have to admit that I am a new beginner of objective-C, even if I have lots of experience of C/C++ development, the syntax of object-C confuse me a lot.

Right now I run into a problem: when should we release the object? Here is the example:

YellowViewController *yellowController =
[ [YellowViewController alloc] initWithNibName:@"YellowView"
bundle:nil];
self.yellowViewController = yellowController;
[yellowController release];

It seems an idiom for objective-c memory management, since I’ve seen lots of source code did in the similar way. I was really confused, since I treated the objective-c object as a c++ pointer. In the above example, yellowController and self.yellowViewController are pointers, they are pointing to the same memory address, if we release yellowController, then how about self.yellowViewController? Will it become an invalid object because it is pointing to the memory address which was released already?


Through me research, then I understand the memory management rule of objective-c. It uses reference counting method to manage the memory:
- When create an object using alloc, the reference count will be 1;
- When release method is called, decreases reference counter by 1;
- When copy or retain method is called, increases the reference counter by 1;

Then I have a question: how about the assignment operation? What does it exactly do? Will it increase the reference counter or will it copy the whole object data to the variable self.yellowViewController?

Finally I realize that the key is in the definition of the instance variable self.yellowViewController:
It’s definition is like this:
@property (retain, nonatomic) YellowViewController *yellowViewController;

Which means we do the assignment operation to the class variable self.yellowViewController, the retain method will be called, which means the reference counter will be increased by 1.

We can use the following methods to check the reference counter:
NSLog([NSString stringWithFormat:@"%u", [yellowController retainCount]]);
self. yellowViewController = yellowController;
NSLog([NSString stringWithFormat:@"%u", [yellowController retainCount]]);

In summary, here is the simple rules for object-c memory management:

Retention Count rules: (copy from here)
1. Within a given block, the use of -copy, -alloc and -retain should equal the use of -release and -autorelease.
2. Objects created using convenience constructors (e.g. NSString's stringWithString) are considered autoreleased.
3. Implement a -dealloc method to release the instance variables you own

Some good references:
1. Very simple rules for memory management in Cocoa
2. Learn Objective-C
3. Forum thread: newbie memory management question ("release")