Problem: Given a character stream as an array, compress the characters in place appending the number of continuous characters by the numerical value and then the character. The array is terminated by a 0x00 character.

Solution: Another classic interview problem which tests multiple skills in a single problem, namely,
  • Conversion from integer to ascii - the number returned is a integral value which needs to be converted to ascii and then put in place in stream
  • Skills with pointers (not the real pointers) when operating on an array

The following JAVA code illustrates how to work up the given problem. It makes use of an itoa() method that was explained before here.
package com.sangupta.keepwalking;

public class CharacterArrayCompression {

	public static void main(String[] args) {
		String stream = "aaaaaaaaaaaaaaaaaaaaabbbbbbssssskkkkjkkdkksdkkkdeeeekkllsssiii";
		char[] characters = stream.toCharArray();
		compress(characters);
		System.out.println(characters);
	}

	private static void compress(char[] characters) {
		if(characters == null || characters.length <= 1) {
			// do nothing if we are not provided with any data
			// or if we have a single character
			return;
		}
		
		char current = characters[0];
		int count = 1;
		int destination = 0;
		for(int index = 1; index < characters.length; index++) {
			char found = characters[index];
			if(current == found) {
				count++;
			} else {
				// compress and store the value
				if(count > 1) {
					char[] value = IntegerToAscii.itoa(count);
					for(int j = 0; j < value.length; j++) {
						char temp = value[j];
						if(temp != '\0') {
							characters[destination++] = temp;
						}
					}
				}
				characters[destination++] = current;
				
				// reset to the new occurence of character
				current = found;
				count = 1;
			}
		}
		
		for(int index = destination; index < characters.length; index++) {
			characters[index] = '\0';
		}
	}

}

Happy Coding!

written by Sandeep Gupta

Thursday, July 14, 2011 at 8:00 AM

Yesterday a very dear friend of mine, Rajat Ahuja suggested me to add a Facebook Like or a Google +1 button to the blog so that sharing becomes easy. As this was something I had turned off a while back, bringing it in was not so tough. Hence, from just now all over my blog the following 3 buttons will appear along with the usual ReTweet button,
  • Facebook Like button
  • Google Buzz button
  • Google +1 button

I might turn off the Google Buzz button, again, due to my personal aversion to its color combination :)

Thanks a lot, Rajat for suggestion.

written by Sandeep Gupta

Wednesday, July 13, 2011 at 3:34 PM

Problem: Given a character stream as an array, encode the characters in place replacing given set of characters by their 3-character equivalent. The array is terminated by a 0x00 character. If the array cannot be fully encoded, the array should not be modified.

Solution: This is a classic interview problem. There are two aspects to this problem,
  • Calculating whether the array would be able to contain the entirely encoded string. This can be easily achieved by calculating the length of the string, the number of encodable characters and the size of the array. If the free space in the array is equal to the additional capacity that would be needed by the encodable characters
  • Encode the string from tail than from head. This is a must so that one does not override the characters ahead, when an encodable character is written encoded in the string.

    A simple JAVA implementation is shown below.
    /**
     * Copyright (C) 2010-2011, Sandeep Gupta
     * http://www.sangupta.com
     * 
     * The file is licensed under the the Apache License, Version 2.0
     * (the "License"); you may not use this file except in compliance with
     * the License.  You may obtain a copy of the License at
     * 
     * http://www.apache.org/licenses/LICENSE-2.0
     * 
     * Unless required by applicable law or agreed to in writing, software
     * distributed under the License is distributed on an "AS IS" BASIS,
     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     * 
     * See the License for the specific language governing permissions and
     * limitations under the License.
     * 
     */
    
    package com.sangupta.keepwalking;
    
    import java.util.Arrays;
    
    /**
     * Class to encode a given character stream (defined as char[] array). The character array is the only
     * memory space one has. In case encoding is not possible, the array should be left untouched. The array
     * will be terminated by a null to indicate string termination.
     * 
     * Each encodable character is 3 characters in length. Thus, additional space required would be 2 characters
     * per each encodable character.
     * 
     * @author sangupta
     * @since 12 July 2011
     */
    public class CharacterStreamEncoder {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		char[] stream = new char[12];
    		Arrays.fill(stream, '\0');
    		stream[0] = 's';
    		stream[1] = 'a';
    		stream[2] = 'n';
    		stream[3] = 'd';
    		stream[4] = ' ';
    		stream[5] = ' ';
    		stream[6] = 'p';
    		
    		boolean result = encode(stream);
    		if(result) {
    			System.out.println(stream);
    		} else {
    			System.out.println("String was not modified.");
    		}
    	}
    	
    	public static boolean encode(char[] stream) {
    		final int streamLength = stream.length;
    		System.out.println("Total length: " + streamLength);
    		
    		// first we need to check if we can encode the string or not
    		// in the given only space
    		// so we read each character and count the total number of encodable
    		// characters and also the length of the string.
    		int encodable = 0;
    		int length = 0;
    		for(int index = 0; index < stream.length; index++) {
    			char temp = stream[index];
    			if(temp == '\0') {
    				break;
    			} else {
    				length++;
    				if(isEncodable(temp)) {
    					encodable++;
    				}
    			}
    		}
    		
    		System.out.println("Length of string: " + length);
    		System.out.println("Encodable: " + encodable);
    		
    		if(encodable == 0) {
    			return true;
    		}
    			
    		// now check for the balance length
    		int balance = streamLength - length;
    		if(encodable *2 >= balance) {
    			// not sufficient space in stream to encode
    			return false;
    		}
    		
    		// now we start from the end of the stream to encode
    		// so that we do not override the characters before
    		// as we already know the number of encodable characters
    		// we know where the last character would be written
    		int destination = length + encodable * 2 - 1;
    		int source = length;
    		
    		for(int index = source; index > 0; index--) {
    			char character = stream[index - 1];
    			char[] encoded = encode(character);
    			if(encoded.length == 1) {
    				stream[destination--] = encoded[0];
    			} else {
    				// we need to set the 3 character bytes properly
    				stream[destination--] = encoded[2];
    				stream[destination--] = encoded[1];
    				stream[destination--] = encoded[0];
    			}
    		}
    		
    		return true;
    	}
    
    	private static boolean isEncodable(char character) {
    		switch(character) {
    			case ' ':
    				return true;
    				
    		}
    		
    		return false;
    	}
    	
    	private static char[] encode(char character) {
    		switch(character) {
    			case ' ':
    				return new char[] { '%', '2', '0' };
    		}
    		
    		return new char[] { character };
    	}
    
    }
    

written by Sandeep Gupta

at 8:19 AM

As far as I know, Java never updated the syntax for defining integral constants since JDK 1.2, which seems like ages before. To end that drought, Java 7 defines enhanced syntax for the following,
  • Numeric constants expressed as binary
  • Suffix to denote type as short or byte
  • Improved readability by use of underscores in integer constants

The above enhancements do not impact a seasoned developer much, nor they provide something out-of-this-world. The only benefit you get is improved readability and vanishing of minor hiccups when coding.

Binary Values

Before Java 7, in order to parse binary values one would write,
int value = Integer.parseInt("10101010", 2);
This in addition to some extra code, also has performance impact besides making the value as a runtime constant than compile time constant. Thankfully, Java 7 introduces the concept of 0b on the same lines as 0x for hexa-decimal values. Thus, the above code fragment in Java 7 would become,
int value = 0b10101010;
The value is now a compile time constant and also, has no performance hit.

Short and Byte values

Java had several integral types such as short and byte, but no syntactical way to code the values directly in, as all numerical constant were treated as integers. Type-casting led to annoyance and discomfort during code and might also have led to limit-over-runs. With Java 7, assigning values for these integral types becomes easy as,
byte b = 245y;
and,
short s = 65535s;
The above values just provide some syntactical sugar when coding and improves readability.

Underscores in values

A long binary, hexa-decimal or integral value becomes hard to read by human mind. If the number of digits increase figuring out the exact extant of the value at times gets difficult. Java 7 adds some real beauty for such use-cases by adding support to add underscores to integral values for improved readability. Thus a value of 2 GB, 2147483648 now may be expressed as,
long twoGigabytes = 2_147_483_648L;
In my honest opinion, this is definitely a boon for mathematical and statistical developers who really had tough time understanding someone's else code... err.. defined constants.

Hope this helps me, more than anyone else in remembering the new sugars! Happy Coding!

written by Sandeep Gupta

Tuesday, July 12, 2011 at 4:06 PM

Most of the Java web projects (and desktop projects as well) use the well known Spring and Hibernate frameworks. I myself have been using them for over 6 years now, and must say, the benefits they have provided have been immense, both in terms of rapid application development, testing and of course, maintenance. With good amount of experience in using the both I rarely find it difficult debugging a bug, but sometimes, I have come across issues that have been both time-consuming and have thrown open unleashed areas of the frameworks. Recently, I happened to land debugging one such issue.

When running are project, which uses HibernateTemplate to simplify access to the data layer, we saw intermittent timeout issues. The intermittent failures in them self were very strange. Running from a machine with query latency of around 10 seconds, only once reproduced the issue. Running from a machine with 2.5 second latency, the issue was 25% reproducible, and from a machine with just 1 second latency (quite close to DB datacenter) never reproduced the issue.

Our application configuration was pretty simple, Spring 2.5.6 working in tandem with Hibernate 2.4, using C3P0 as the connection pool. Good stack, right?

There were two Java exceptions which were coming up randomly, as,
org.hibernate.util.JDBCExceptionReporter

No suitable driver found for jdbc:oracle:thin:@myDomain:myPort/mySchemaName
and,
org.springframework.dao.DataAccessResourceFailureException: Hibernate operation: Cannot open connection; SQL [???]; 
Io exception: The Network Adapter could not establish the connection; nested exception is,
 java.sql.SQLException: Io exception: The Network Adapter could not establish the connection
	at org.springframework.jdbc.support.SQLErrorCodeSQLExceptionTranslator.doTranslate(SQLErrorCodeSQLExceptionTranslator.java:236)
	at org.springframework.jdbc.support.AbstractFallbackSQLExceptionTranslator.translate(AbstractFallbackSQLExceptionTranslator.java:72)
	at org.springframework.orm.hibernate3.HibernateAccessor.convertJdbcAccessException(HibernateAccessor.java:424)
	at org.springframework.orm.hibernate3.HibernateAccessor.convertHibernateAccessException(HibernateAccessor.java:410)
	at org.springframework.orm.hibernate3.HibernateTemplate.doExecute(HibernateTemplate.java:424)
	at org.springframework.orm.hibernate3.HibernateTemplate.execute(HibernateTemplate.java:339)
	at java.util.concurrent.FutureTask$Sync.innerRun(FutureTask.java:303)
	at java.util.concurrent.FutureTask.run(FutureTask.java:138)
	at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:886)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:908)
	at java.lang.Thread.run(Thread.java:662)
Caused by: java.sql.SQLException: Io exception: The Network Adapter could not establish the connection
	at oracle.jdbc.driver.DatabaseError.throwSqlException(DatabaseError.java:145)
	at oracle.jdbc.driver.DatabaseError.throwSqlException(DatabaseError.java:190)
	at oracle.jdbc.driver.DatabaseError.throwSqlException(DatabaseError.java:363)
	at oracle.jdbc.driver.T4CConnection.logon(T4CConnection.java:401)
	at oracle.jdbc.driver.PhysicalConnection.(PhysicalConnection.java:441)
	at oracle.jdbc.driver.T4CConnection.(T4CConnection.java:165)
	at oracle.jdbc.driver.T4CDriverExtension.getConnection(T4CDriverExtension.java:35)
	at oracle.jdbc.driver.OracleDriver.connect(OracleDriver.java:839)
	at java.sql.DriverManager.getConnection(DriverManager.java:582)
	at java.sql.DriverManager.getConnection(DriverManager.java:154)
	at org.springframework.jdbc.datasource.DriverManagerDataSource.getConnectionFromDriverManager(DriverManagerDataSource.java:174)
	at org.springframework.jdbc.datasource.DriverManagerDataSource.getConnectionFromDriver(DriverManagerDataSource.java:165)
	at org.springframework.jdbc.datasource.AbstractDriverBasedDataSource.getConnectionFromDriver(AbstractDriverBasedDataSource.java:149)
	at org.springframework.jdbc.datasource.AbstractDriverBasedDataSource.getConnection(AbstractDriverBasedDataSource.java:119)
	at org.springframework.orm.hibernate3.LocalDataSourceConnectionProvider.getConnection(LocalDataSourceConnectionProvider.java:82)
	at org.hibernate.jdbc.ConnectionManager.openConnection(ConnectionManager.java:417)
	at org.hibernate.jdbc.ConnectionManager.getConnection(ConnectionManager.java:144)
	at org.hibernate.jdbc.AbstractBatcher.prepareQueryStatement(AbstractBatcher.java:139)
	at org.hibernate.loader.Loader.prepareQueryStatement(Loader.java:1560)
	at org.hibernate.loader.Loader.doQuery(Loader.java:661)
	at org.hibernate.loader.Loader.doQueryAndInitializeNonLazyCollections(Loader.java:224)
	at org.hibernate.loader.Loader.doList(Loader.java:2144)
	at org.hibernate.loader.Loader.listIgnoreQueryCache(Loader.java:2028)
	at org.hibernate.loader.Loader.list(Loader.java:2023)
	at org.hibernate.loader.custom.CustomLoader.list(CustomLoader.java:289)
	at org.hibernate.impl.SessionImpl.listCustomQuery(SessionImpl.java:1695)
	at org.hibernate.impl.AbstractSessionImpl.list(AbstractSessionImpl.java:142)
	at org.hibernate.impl.SQLQueryImpl.list(SQLQueryImpl.java:150)
	at org.springframework.orm.hibernate3.HibernateTemplate.doExecute(HibernateTemplate.java:419)
	... 15 more

Obviously the ERROR 1 listed above was nothing related, as the code had obtained DB connections (for sure). The ERROR 2 indicated that we were opening more connections than what the database could handle. We tried setting up a local database and tested the whole code, but the error won't reproduce. We thus concluded (only to be proven wrong later) that the database was unable to handle the load of our connections (a connection pool of 100 connections). We lowered our throttle of hitting to 50, 20, 10, and lastly 5 connections but the error still occurred on the staging and production servers. We contacted the database team and they informed that there were more than enough free handles on the database side and no alert was raised for DB going overboard the total number of allowed connections.

This made us change our mind to think that there was some connectivity issues with the stating/production machines, both being in the same datacenter. We tested heavily both the machines but found nothing that suggested a connectivity issue. Again we stood at a blank wall.

We again went back to the DB team to help us debug. As one another test, we ran our code in the DBA presence monitoring the database. The DBA informed that we were creating connections at a rapid pace, creating them, firing a query, and then disconnecting. Voila! What was that - we were using a connection pool. Was it not working?

We went back to the code and ran the profiler along with netstats. This confirmed that we were creating DB connections and then dropping for every single query. But why should that happen, when we were for sure, using C3P0 (shipped with Hibernate) for our connection pooling. After deep penetration into the code, we figured out that firing plain SQL queries using Hibernate template does not makes use of the inherent connection pool of Hibernate. This broke all our code - we were using the HibernateTemplate extensively in our application and firing native queries (why so - leaving as it calls for another detailed post) over the MySQL database.

As a quick fix, we added Apache Commons DBCP connection pooling layer over our data-source. This made our stack look something like,
DB -> Apache DBCP DataSource -> Hibernate -> C3P0 -> Spring -> Our application
.
This seemed to do the trick. Not only did the connection fetch failure vanished, we also saw improved performance gains with connection pooling (as if we didn't knew).

As they say, better late than never - we could fix the problem well before the release, burning some mid-night...err... mid-day oil. But this taught me a lesson,
Always profile your application for connections before releasing.
.
Hope this helps someone out there having a similar problem. You do, try this and if it gets resolved, drop in a comment.

written by Sandeep Gupta

Monday, July 11, 2011 at 12:14 PM

They say,
Change is the only constant.
How true this is, we realize as we keep walking down the lane of our life.

Today, happens to be one such change. Today, I have started migrating all code from various repositories that held my code, such as Source Forge, Google Code and other locally hosted ones, to their new home - Github.

This is one single consolidation effort where in I want all my code to be available publicly, be of good quality and above all - clean up my systems. Keeping their backups have already become nightmare for me. I anticipate this to take around 2 weeks, so keep watching for more posts under the label, myjerry.

Stay tuned, for more blog posts on how to reuse all this shit of code ;)

Keep Walking!

written by Sandeep Gupta

Wednesday, July 6, 2011 at 8:14 PM