Reversing A String - The worse way, The better way

A common programming interview question is to reverse a string. A common first approach is to copy the contents of the string into a temporary string in reverse order, and then copy the temporary string over the original string. Do this in an interview, and you'll be informed that while your solution is correct, it can be much better. Doing it in this fashion is very inefficient, but it is still nonetheless a good place to start. As always, solve the problem first, then optimize. The naive solution would look something like this:



At this point, the interviewer is going to ask you to perform the reversing "in-place" meaning "do it all in one pass of the string, no double-pass copying shenanigans!"

So, how do we accomplish this? A basic swap should immediately come to mind. You need to swap pairs of characters in the string as you iterate over it until no more pairs exist. But, how to know when you've reached that point? Sure, you could keep track of indices of the string that have been swapped, but at that point you're diverging toward the inefficiency of the first solution because you'd have to do a lookup in the index table each time you attempted a swap, and that gets slower as your string becomes larger. So, storing indices is out. What else can we do? Well, let's see if there is an algorithm behind this.

Given the string "abc", what can we deduct about which pairs should be swapped?

'a' and 'c' get swapped, leaving us with 'b'. Clearly, we see there is nothing else to swap with, but how would we know this internally, from a source code level? The key lies in the positions of the characters in relation to the end of the string. We never want to swap 2 characters unless the location of the second character is > the location of the first character. Using our string "abc", 'a' is located at position 0 and 'c' at position 2. 'b' is located at position 1, but the character at position 2 has already been swapped.

To compute this mathematically, you do this:

firstIndex = 0
secondIndex = length of the string - 1
while secondIndex > firstIndex:
swap
increment firstIndex
decrement secondIndex
loop

Putting this into C, we have the following, efficient reverse algorithm:



And here is the output, using both versions consecutively on the same string (reverses it, then reverses it again):

$ ./reverse
original: abc
reverse: cba
reverse2: abc

Hopefully this has been helpful to you. Remember, the most obvious solution is most likely not the most efficient.

10 Great Features In Netbeans IDE 6.1

Netbeans is an excellent IDE from Sun Microsystems. It is written in Java and runs on all major platforms. With the latest 6.1 release, Netbeans has really stepped up its game and can now compete with some of the market leaders for integrated development environments. For more information about Netbeans, visit http://www.netbeans.org

Below is a list of 10 really helpful (...and cool) features in Netbeans 6.1. My examples are illustrated using a C++ project, but almost all of them apply across the board to the other languages that Netbeans 6.1 supports: http://www.netbeans.org/features/index.html


1. Code Bookmarks - This feature allows you to bookmark individual lines of code for easy browsing later.




2. Build Platform - When working with a C/C++ project, you can select which platform you'd like to build the executable for.




3. Code Completion - If you've used Visual Studio, then you've seen this type of thing before. While coding, you can pause (or use Ctrl+Space) and a code completion dialog will pop-up. This works for standard library items as well as items specific to user-created classes.




4. Code Formatting - Netbeans 6.1 gives you the ability to customize every possible code formatting option you can think of. Each case is separated into a group, and then each item in that group is a check-box. Changes are reflected in real-time via a preview pane to the right which is populated with example code. Once you make changes to these settings, Netbeans automatically accounts for them while you're coding. Very cool.




5. Single File Compile - Tired of building your entire project when all you want to do is make sure that the file you've just changed compiles cleanly? Netbeans 6.1 offers the "Compile File" option to do just that.




6. Diff - Diff is a very powerful tool for tracking changes between 2 different versions of a file. It isn't source control, it's simply a tool to contrast 2 versions of the same file, and it's commonly used when writing software patches. Netbeans 6.1 gives you the ability to run a Diff on a file right inside of the IDE.




7. Favorites - Netbeans 6.1 allows you to add files from your project to a list of Favorites. This is extremely helpful in large code bases.




8. Symbol Tracking - While viewing a source file, simply right-click on a symbol and you have the option to track various things such as the definition/declaration of the symbol, its source/header file, all occurrences of the symbol in the current file/entire project, and more. Again, very helpful in large code bases.




9. Include Directories - When developing a C/C++ project, Netbeans 6.1 makes it easy to add additional include directories to it's search path.




10. Local History - This is one of the coolest features I've seen in a while. Just think source control, except it's stored internally and it's graphical.




Hopefully this list has gotten you excited about Netbeans 6.1. If not, read it again! :)

This review was submitted for the Sun Microsystems Student Reviews Contest. You can get more information about this contest here: http://www.sun.com/products-n-solutions/reviews/studentzone/contest.jsp

Netbeans: Why It Matters

The topic comes up all the time: "Which IDE to you use?"

It doesn't matter which programming language is being discussed or the scope of the project, developers always want to know what the "other guy" is using. I tend to do all of my development in C/C++ and it probably comes as no surprise to others using Netbeans for C/C++ the shock and resistance I receive when I tell people this.

I'm a Linux guy. Up until last year, I had never written a lick of code under any platform other than Linux. When I was eventually "forced" to write some C++ under Windows, I felt like a foreign exchange student with no sponsor. I had absolutely no idea what was going on. I almost started to believe I didn't know how to program anymore. Where was gcc? How do I run this thing? How in the hell do I use Visual Studio? In walks Netbeans, the one thing I can always count on in my software development. That is, aside from the knowledge I've already garnered.

The fact that Netbeans offers a full-fledged IDE that runs on multiple platforms is enough in itself. The fact that it has support for every language you could ever want (or need) to write code in is nearly unprecedented. The fact that it does all of this better than any IDE I've ever seen is teetering on goofy. The fact that it's open source is down right nuts.

I, like many developers, am forced to write code in a number of different languages for a number of different platforms. It's frustrating enough having to remember the nuances of all of these different languages. You do something one way in Java, another in C++, a new way in Ruby... but that's not the worst part. Chances are, unless you are really just using an editor as opposed to an IDE, you have to write this code with a different development tool. Isn't the idea behind an IDE to make the whole development process easier? What's easy about juggling different programming languages along with different development environments? In walks Netbeans.

Netbeans provides developers with a consistent look and feel across all of its supported languages. This allows developers to use Netbeans for all of their tasks without missing a beat. There is no learning curve. If you've written Java code in Netbeans, congratulations, you can now use Netbeans to develop software in any other language. I think people overlook the benefits of this, mainly because it's not a very common luxury. The old school of thought between developers, namely C/C++ developers, is that you use a text editor on Linux, and Visual Studio on Windows. For a lot of people, that's a deal breaker. I can't say I blame them: Visual Studio is usually a nightmare to use for anyone coming from the purist environment that is Linux/UNIX C/C++ development. In walks Netbeans. You're a Linux C/C++ developer coming over to Windows for a project? No sweat, just install Netbeans, install the C/C++ development tools (compiler, make system, etc...), and get right back to work. The effect this has on productivity is astounding. Not only can you get right to work, but all the experience you gain while working on this project under Windows can be directly translated back to Linux, or whatever your native environment is because the IDE's interface is the same, because the IDE is the same!

I talk a lot about C/C++. Guilty. Every other language is on a "need to use" basis with me. However, I've done a lot of work in Java, some work in Ruby, and recently my first ever experience with JavaScript. Let's focus on JavaScript since that's a pretty old school language. The JavaScript project I was working on involved some proprietary Microsoft technologies. Given that, I was basically forced to use Visual Studio. Luckily the new version isn't so bad, but I still wasn't pleased. I was out of my element, and I had to worry about more than just the code I was writing. That's a bad thing. In walks Netbeans. In the 6.1 Beta, JavaScript support was added. Eurkea! I said. The nature of the project was such that I could write the JavaScript code separate from those other proprietary technologies I mentioned, so I installed the beta and got to work. Not only was the learning curve involved with Visual Studio cut out of the mix, but the fact that I had the reference documentation built in to Netbeans was instrumental in my rapid development iterations with this project having never written any JavaScript in my life!

The IDE war will never be settled. Maybe that's for the best, to each his own. However, the bottom line is Netbeans makes you a better developer. It helps you do your job, and it helps you do your job well. The fact that it covers the major elements of all of the languages it supports is second to none. Break your code down by classes? Done. Attach an in-depth profiler? Cake. Debugger? You betcha'. Source control? Look ma', no hands.

If you've never tried Netbeans, I strongly encourage you to do so. It's alright, you don't have to tell anyone that you're using Netbeans. You can lock yourself away, keep all the lights off, cover your face if you must, but just try it. Once you put all the hype aside, you'll realize just how invaluable a tool like Netbeans is. And then you'll wonder why you weren't using it years ago.

--

This blog entry was submitted for the Netbeans 6.1 Beta Blogging Contest. For more entries, check out the contest page here: http://www.netbeans.org/competition/blog-contest.html