Explain the JDBC Architecture - 2 tier and 3 tier both
JDBC APIs support both the architectures - 2-tier and 3-tier models for accessing a relational database.
JDBC for a 2-tier architecture
In such an architecture, the Java application (or Applet) communicates directly with the data source (or database). The database may reside on the same machine or may be on another machine to which the clinet machine needs to be connected through a network. In the latter case it will be a clinet-server configuration and the server will hold the database. The client will send the statements to the database residing on the server and the result will be communicated back to the client.
In this architecture, the client machine will typically be a Java application and the server machine will have a Relational Database installed on it.
JDBC for a 3-tier architecture
In such an architecture, the client machine will send the database access statements to the middleware, which will then send the statements to the database residing on the third tier of the archirecture, which is normally referred to as the back end. The statements will be processed there and the result be returned back to the client through the middle tier. This approach will have all the advantages associated with the 3-tier architecture, such as better maintainability, easier deployment, scalability, etc.
This scenario will typically have a Java Applet or a Web Browser as the clinet tier, an Application Server as the Middle-tier, and a Relational DBMS as the Back-end.
Saturday, May 31, 2008
Explain the JDBC Architecture - 2 tier and 3 tier both
What's a database transaction?
What's a database transaction?
A database allows multiple users to use it concurrently and hence while a user is making some changes to data in the DB, some other user might be accessing the same data concurrently. This can lead to inconsistent data and hence such a situation should be managed with proper care. Most of the DBMSs use the concept of transactions to handle such a situation, which helps them to maintain data consistency as well as data concurrency.
A transaction is a basically a set of one or more SQL stataments, which will either execute as an atomic unit or will simply rollback and will leave the database as it was prior to the start of execution of the set of SQL statements of the transaction. If all the statements of the transaction gets executed as a stomic unit then the transaction ends with 'commit' statement which makes the changes to the database permanent,otherwise the changes are rolled back using the 'rollback' statement and the database returns to the state it was before the start of the transaction.
The database management system must have the capability to allow access to only one transaction to update a data item at a time otherwise the atomicity of the transaction will be violated and consequently the data will become inconsistent. The DBMSs use the concept of 'locks' to ensure this. A lock is a database object used to ensure that only one transaction gets access to manipulate a data item at a time. Every transaction requires to obtain the lock associated with the data item it intends to change and only after acquiring that lock it can proceed with the changes it needs to make on that data item.
For example: a table lock will not allow that table to be dropped unless an uncommitted transaction on that table gets committed/rolled-back. Similarly a row lock will prevent that row to be modified (or even accessed in required) while another transaction is still modifying that row. The row will become accessible to any other transaction when the transaction accessing it either gets committed or rolled-back.
What is a Relational Database? What're Integrity Rules?
Relational Database
It's a database which stores and manages the information in tables, which are composed of rows and columns. The name 'Relational' came from that fact that the tables in such a database are nothing but a collection of similar type of information stored in form of rows. This is the reason why a table is also referred to as a relation in such a DB.
Integrity Rules
These are the rules which a relational database follows in order to stay accurate and accessible. These rules govern which operations can be performed on the data and on the structure of the database. There are three integrity rules defined for a relational databse,which are:-
- Distinct Rows in a Table - this rule says that all the rows of a table should be distinct to avoid in ambiguity while accessing the rows of that table. Most of the modern database management systems can be configured to avoid duplicate rows.
- Entity Integrity (A Primary Key or part of it can not be null) - this rule says that 'null' is special value in a relational database and it doesn't mean blank or zero. It means the unavailability of data and hence a 'null' primary key would not be a complete identifier. This integrity rule is also termed as entity integirty.
- Referential Integrity - this rule says that if a foreign key is defined on a table then a value matching that foreign key value must exist as th e primary key of a row in some other table.
Role of JDBC in Java? What are JDBC components?
Role of JDBC in Java
JDBC is probably used to achieve the following three tasks in Java:-
- Connect to data source - it helps the Java program to establish a connection to a data source, such as a database.
- Sending/Executing SQL statements - once the connection gets established then JDBC can be used to prepare, send, and execute SQL queries or Update statements on the data source, the connection is established to.
- Retrieving results and processing them - finally the JDBC APIs can be used to retrieve the results of the fired SQL statements and helps them getting processed to be used in the Java application.
Example:
//Connecting to the data source
Connection con = DriverManager.getConnection("url", "userid","password");
//preparing SQL statement
Statement stmt = con.createStatement();
//sending/executing SQL queries and retrieving the result
ResultSet rs = stmt.executeQuery("SELECT ...");
//processing the result
while (rs.next()) {
...
}
Components of JDBC
- JDBC API - The JDBC 4.0 APIs come in two packages: java.sql and javax.sql and these packages contain all the APIs which provide programmatic access to a relational database (like Oracle, SQL Server, MySQL, etc.) from Java.
- JDBC Driver Manager - There are two ways of connecting to a database - One, by using the DriverManager class (the traditional way of establishing connection to a database from Java) and Two, by using a Data Source. This method requires javax.naming and javax.sql packages to find a DataSource object registered with JNDI, and to establish connection using that DataSource object. This is the recommended approach of establishing connection to a database from Java.
- JDBC Test Suite - this test suite will of course not be exhaustive, but they do contain almost all the standard test cases required to test the many JDBC features. You may only need to add the application specific test cases.
- JDBC-ODBC Bridge - as the name suggests this enables JDBC access via ODBC drivers. Though this is normally used only for development and testing purposes and not for production use.
Why Prepared Statements are faster? Are they compiled?
Question: Why Prepared Statements are faster? Are they compiled?
Answers: Prepared Statements are faster not because they are compiled (in fact they are not compiled), instead the reason for them being faster is that they are bound to the underlying JDBC Driver. Whenever you create a prepared statement, all the columns involved in that SQL statement get bound to the JDBc driver and hence the binding overhead gets eliminated while execution which in turn makes the prepared statements faster. We use Connection.prepareStatement() to create a prepared statement.
Difference between Client-side & Server-side DB cursors?
Question: Difference between client side and server side DB cursors?
Answer: There is nothing like client side DB cursor. What you may think of a clinet side DB cursor is actually the current row of either the ResultSet in case of JDBC or the Result in case of ODBC. DB cursor is only a server side entity and it resides and runs only on the server. Read about DB Cursors in this article - Life Cycle of Cursors, Implicit vs Explicit, Static vs Dynamic >>
Friday, May 30, 2008
Oracle Database - How to tune for better performance?
Oracle Database - How to tune for better performance?
Why to tune?
Simply to improve performace of the overall system by enabling the best possible resource utilization. The resource here includes all the resources involved including Software, Hardware, and Human Resources. Thankfully the Oracle Databse can be tuned to a great extent and it's probably one of the biggest responsibilities of a DBA to ensure whether the DB is well tuned or not.
When to tune?
Whenever the DBA discovers that the DB is not well tuned :-) There can be a veriety of
reasons why the DB may not look like to be well tuned. Few of them might be:-
- The system is not running at a pace matching with what your business requires
- The system is too slow to respond to the users and thereby wasting the precious human time
- The hardware are probably not being utilized properly and hence hardware cost is rising
How to tune it?
There are so many areas where the DBA can concentrate on for tuning the Oracle DB. Few of these areas are quire dependent on each other, so it's DBA's responsibility to ensure that focusing on one area doesn't produce some side effects to any other tunes area. So, it's important to focus on these areas in a proper order. For example, you can't jump on to SQL Tuning before having a fixed Database Design for the obvious reason that it's pretty difficult (if at all possible) to have a refined SQL statement without having a refined database schema. Some of the areas to focus are:-
- Design of the Database - the design of the database if of utmost importance and the DBA should be very sure that the current design is what he can think of as the best possible considering so many factors including normalization (or selective denormalization to improve performance), access paths, replication, etc.
- SQL Tuning - probably the second most important area to focus on. There are a variety of ways how the performance of a SQL query can be improved and the DBA should not leave even a single stone unturned :-) Poor SQL statements can cause lot of performance problems during peak hours.
- Memory Tuning - it's important to allocate sufficient memory to the various memory structures of the Oracle Instance. These memory structures are Shared Pool, Buffer Cache, Redo Log Buffer, Large Pool, etc.
- Input/Output Tuning - Disk I/O is probably the most time consuming stuff involved in the entire operation of the DB, so the DBA must consider all the possible scenarios involving Disk I/O and try reduce them to minimum possible.
- Connection Tuning - DB locks and latches must be reduced to the minimum and for the least time possible.
- OS Tuning - finally the DBA might focus on the underlying OS and see if it's in the right shape to ensure the proper execution of the Oracle DB installed on the system.
Thursday, May 29, 2008
Archives from the Category Frameworks - 1
Archived Articles from the Category Frameworks
- How does Constructor Injection work? Impl of CI using Pico
- Spring: Beans, Container, Config Metadata, IoC Instantiation
- Spring IoC: Inversion of Control. DI: Dependency Injection.
- AspectJ, Aspect Oriented Programming (AOP), Spring AOP
All types of database files used in Oracle DB
All types of database files used in Oracle DB
The physical structure of the Oracle DB consists of three file types, which are:-
- Datafiles - as the name suggests, these type of files store the data on disk.These files are almost always written only by the Mandatory Background process named DBWR (Database Writer). There are only a few exceptions when these files are written by some other system processes. From the logical structure of Oracle DB, we can visualize that Datafiles reside in the logical container of the tables and indexes. This container is called 'Tablespaces'.
- Control files - these are binary files and they store information about the database, such as name of the database. The control files contain so vital information that the Oracle DB won't start if these files are not available. Probably that's the reason why Oracle allows to maintain duplicate copies of control files. This process is called multiplexing of control files and it'll always be a good idea to keep duplicate copies on separate disks for obvious reasons.
- Redo Log files - these files are used to record all the changes made to the Oracle DB. These files comes very handy in situation like DB crash. Suppose you have scheduled periodic backup every 15 days and if the disk crashes on say 14th day then it may be quite difficult to recover the data in absence of these redo log files. Redo log files will be of so much help in this case that you will simply need to restart the database to recover all the lost data. These Redo Log files are online log files and Oracle DB requires at least two online Redo Log files. When one is full it switches to the other. You can have multiplexed Redo Log files as well and for that'll be handy if these online Redo Log files themsevles get corrupted.
In addition to these three types of files, Oracle DB uses many other types of files as well and each of these files have their own special uses. Some of these file types are:-
- Parameter file - this file is also called init.ora in Oracle DB. It contains the configuration details which are used for during startup of the database. Some of the information contained by this file is: the location of the Control files, the size of RAM the Oracle DB would be using, location of the trace files, etc. As you can easily understand that without these information, the database won't start. Oracle DB supports two types of parameter files: One, Manual parameter file which is also known as PFILE and Two, server side parameter file aka SPFILE.
- Trace files - Oracle DB creates these files in many cases including session failure, disk crash, etc. It can be created by issuing commands by users of Oracle DB as well.
- Networking configuration files - tnsnames.ora and listener.ora fall in this category of files. As the name suggests, these files are used to store the configuration details of the different network components used by the underlying Oracle DB.
- Oracle Binary files - these binary files contain the instructions to run the Oracle DB.
Library Cache vs Data Dictionary Cache in Oracle
Library Cache
This part of the Shared Pool memory structure is used for storing the recently executed SQL and PL/SQL statements and hence these statements if encountered again will be shared which will subsequently boost the performance of the database.
This memory structure is managed by a LRU (Least Recently Used) algorithm and this memory structure is also composed of two structures. One, Shared SQL area - for storing the most recently executed SQL statements and Two, Shared PL/SQL area - for storing the most recently executed PL/SQL statements.
Data Dictionary Cache
This part of the Shared Pool memory structure is used for storing the most recently used data definitions in the Oracle DB. These data definitions may include information about: database files, tables, indexes, privileges, users, etc.
Caching these inforamtion in memory improves the performance especially for queries and updates using DML. During the parsing phase, the server process scans this memory structure to resolve the database object names and validate access.
Library Cache vs Data Dictionary Cache
Thus we see that Library Cache is used to store the recently executed SQL and PL/SQL statements, which eliminates the need for parsing and compiling the statements again if used subsequently and hence improves performance. Whereas, the Data Dictionary Cache is used to store the information which improves the validation phase of the execution of those SQL and PL/SQL statements. So, both the memory structures can be visualized as being complimentary to each other.
SGA Memory Structure of the Oracle DB - Explained
SGA Memory Structure of the Oracle DB
SGA (System Global Area) is the fundamental component of an Oracle Instance and is one of two memory areas of an Oracle Server. This memory area contains several memory structures each of which is designated to a specific task required by the Oracle DB during its execution. SGA is dynamic and the allocation is done in granuels. The maximum size of the SGA is stored in the parameter named SGA_MAX_SIZE. The primary memory structures contained by SGA are:-
- Shared Pool - this memory structure is used to store most recently executed SQL or PL/SQL statements and most recently used data definitions. For storing these two different types of data, this memory structure is divided into two sub-structures which are Library Cache and Data Dictionary Cache. Library Cache is used to store the most recently executed SQL or PL/SQL statements whereas the Data Dictionary Cache is used to store the most recently executed data definitions. The maximum size of the Shared Pool is stored in the parameter named SHARED_POOL_SIZE.
- Database Buffer Cache - this memory structure is used to store the blocks of data recently obtained from the datafiles and it improves the performace to a great extent while fetching or updating the recent data. The size of this cache is stored in the parameter named DB_BLOCK_SIZE.
- Redo Log Buffer - this memory structure is used to store all the changes made to the database and it's primarily used for the data recovery purposes. The size of this memory structure is stored in the parameter named 'LOG_BUFFER'.
In addition, there are other memory structures as well including those which are used for lock and latch management, statistical data, etc.
SGA can support two other optional memory structures as well, but it needs to be configured for that. These additional memory structures are:-
- Large Pool - This memory structure is used to reduce the burden of the Shared Pool memory structure. This memory structure can be used as the Session memory for the Shared Server and as the temporary storage for the I/O involved in the server processes. This memory structure can also be used for the backup and restore operations or RMAN. This memory structure doesn't use LRU (Least Recently Used) list. The size of this memory structure is stored in the parameter named 'LARGE_POOL_SIZE'.
- Java Pool - As the name suggests, this optional memory structure is used Java is installed and used on the Oracle Server. Size of this memory structure is stored in the parameter named 'JAVA_POOL_SIZE'.
Oracle Server Architecture - Main Components
Oracle Server Architecture - Primary Components
Well... most of the components themselves comprise of so many other logical components. Let's start with the major components first and the we'll dive deep into the details of the sub-components of each of these components.
Oracle Server - what's it?
It's a DBMS that facilitates a comprehensive management of information. It provides an open and integrated approach towards information management.
Components of Oracle Server
It is made up of two main components:-
- Oracle Instance: this is not the actual database, but you can not access the actual DB directly and you need to use this component to access the DB. It can have only one DB open and connected to it. This component is responsible for facilitating all the memory and process structures, which are used for the smooth and expected execution of the Oracle DB. The memory structure consists of two memory areas: One, SGA (System Global Area) and Two, PGA (Program Global Area). SGA is the fundamental component of an Oracle Instance and is allocated at the time of Instance startup, whereas the other memory area, PGA is allocated when the server process is started. PGA is basically the memory area reserved for every user process which connects to the underlying Oracle DB. It is allocated at the time of process creation and gets de-allocated when the process terminates. User processes are the processes which are started at a time when an user tries to establish connection with the Oracle Server. Server processes are the processes are used to connect to the Oracle Instance in response to a user process requesting for the connection and it establishes the session as well. Background processes are the processes which are used for doing periodic and routine activities. They get started when the Oracle Instance is started and they keep running in the background since then. The background processes include five mandatory processes and many other optional background processes. Mandatory Background Processes are: PMON (Process Monitor), SMON (System Monitor), CKPT (Checkpoint), LGWR (Log Writer), and DBWR (Database Writer). Details of these mandatory background processes and other optional processes will make this article too big, so I'll post them separately.
- Oracle Database: as the name suggests, it's the actual DB which stores the data. Putting it differently, Oracle DB is a collection of data and this data is treated as a unit. The physical structure of Oracle DB includes three types of files which are Datafiles, Control Files, and Redo Log files. The logical structure of an Oracle DB can be seen as a hierarchy, which includes Tablespaces, Segments, Extents, and Blocks. Tablespace is right at the top of the hierarchy and it consists of segments, which are themseves made of extents. These extents are made up of sevaral blocks and these blocks are finally used for storing the information.
What's the Role of the Future interface in Java?
Future interface
public interface Future
You can use Future in that case also where you simply want to either check if a task is complete or not or to simply cancel an ongoing task, but you don't want to return any significant result. Use Future to declare the type and return 'null' as the result in such a case.
Methods of the Future
- boolean cancel(boolean mayInterruptIfRunning) - this method cancels the task if it's still under progress and returns 'true' in case it successfully cancels it. 'false' is returned if the task has alraedy completed or if the attempt of this method to cancel the task fails due to some other reasons. If the task has not started when the cancel method is called the the task should never run. The parameter mayInterruptIfRunning is used to determine if the thread executing this task should be interrupted or not. If it's true then the thread is interrupted otherwise the taks in progress are allowed to complete and the attempt to cancel the task fails.
- boolean isCancelled() - it returns 'true' if the task got cancelled before its completion
- boolean isDone() - it returns 'true' in case the task got completed either due to normal completion or due to exception or due to cancellation of the task using the cancel() method.
- V get() - if the task has completed, it returns the result, otherwise waits for thr task to get completed first and then returns the result. This method may throw three exception:- One, CancellationException - in case the task was cancelled using cancel() method; Two, ExecutionException - if an exception occured during the execution of the task; Three, InterruptedException - if the thread executing the task was interrupted while it was in the waiting state.
- V get(long timeout, TimeUnit timeUnit) - As the parameters suggest this variant of get will wait for the specified time only and if the task gets completed before the expiry of the timeout then it returns the result if the computation otherwise returns TimeoutException. It may throw the other three exceptions as well similar to the other variant of get() method.
start() method vs run() method in Java
start method
public void start() - this method is responsible for causing the thread (it's called upon) to begin execution. The name may seem to be a misnomer here as this method only causes and not actually starts the execution. It just schedules the thread and when the CPU Scheduler picks this thread for excution then the JVM calls the run() method to actually start the execution of the thread.
This method will obviously result into two concurrent threads - one, from which this method is called and two, the new thread which executes the run() method of the new Thread instance.
A thread will throw IllegalStateException in case you try to call the start() method on an already started thread instance. That means, a thread can not be started more than once. As per the Java specifications a thread may not be restarted after completing its execution. You'll be required to create and start the execution of a new thread in that case.
run method
public void run() - this is the only method of the Runnable interface and the classes which intend to execute their code in a separate thread of execution first implement the Runnable interface and subsequently define this method and put all the code expected to be executed in the separate thread inside the scope of this run method.
The other way, such classes can follow for the same is by extending the Thread class and in that case also they should oevrride the run method of the Thread class and put all the code supposed to be executed in the new thread inside the scope of the overriden run method.
Difference between start() and run() methods
start() methods only schedules the thread for execution and not actually begins the execution of the thread. The execution of the thread is started when the JVM calls the run() method of the thread once the CPU Scheduler picks this scheduled thread for execution.
Threads and Daemon Threads in Java.
Threads
A thread represents an execution environment. It's quite similar to a process with the difference that threads within the same process share much of the same state including the address space and other open I/O resources of the process. The Java Virtual Machine allows multithreading which means that more than one thread can continue to execute concurrently in the same process.
Threads are used to execute a task and based on the importance of the task we can assign priority to the thread executing it. Obviously the threads having a higher priority will be given preference over those threads which are having a relatively lower priority.
Daemon Threads
There may be cases when you may like to have certain periodic and routine tasks running as background threads. You can set any thread as daemon thread for that purpose by using the setDaemon() method. This ensures that this thread will be killed and discarded only when all other threads of the application have already exited. The Java Interpreter thread continues to run until all the non-daemon threads running in that JVM have exited. If it finds that the only active threads are daemon thraeds, then the Java Interpreter thread exits. Example of creating a daemon thread in Java:-
public class BackgroundThread extends Thread{
BackgroundThread(){
setDaemon(true); //setting the thread as a daemon thread
start(); //scheduling the thread for execution
}
public void run() {
//the code which is required to be run under this thread
}
}
When does a thread stop its execution?
On start up of a JVM, only a single non-daemon thread exists. This thread eventually calls the main() method of a designated class. All the threads running in a JVM keep on executing until one of the following two cases occur:-
- The security manager has approved the exit operation - this happens when the exit method of the class Runtime has been called and the underlying security manager is okay with the call.
- The non-daemon thread has died in the JVM - this happens when the non-daemon thread has either returned from its run method after completing the designated task or throws an exception which is not handled in the run method and hence propagates beyond that method.
Callable interface vs Runnable interface in Java
Callable interface
Runnable interface
public interface Runnable - this interface is implemented by those classes whose instances are supposed to be executed in a different thread. This interface has only one method 'run', which takes no arguments and obviously all the classes implementing this interface need to define this method.
This interface is implemented by the Thread class as well and it's a common protocol for all the objects who wish to execute in a different thread. It's one of the ways of creating threads in Java. The other way to create a thread is by subclassing the Thread class. A class implementing Runnable interface can simply pass itself to create a Thread instance and can run thereafter. This eliminates the need of subclassing the Thread class for the purpose of executing the code in a separate thread.
As long as we don't wish to override other methods of the Thread class, it may be a better idea to implement the Runnable interface to enable multithreading capabilities to a class than enabling the same by extending the Thread class.
Callable vs Runnable
Though both the interfaces are implemented by the classes who wish to execute in a different thread of execution, but there are few differences between the two interface which are:-
- A Callable<V> instance returns a result of type V, whereas a Runnable instance doesn't
- A Callable<V> instance may throw checked exceptions, whereas a Runnable instance can't
The designers of Java felt a need of extending the capabilities of the Runnable interface, but they didn't want to affect the uses of the Runnable interface and probably that was the reason why they went for having a separate interface named Callable in Java 1.5 than changing the already existing Runnable interface which has been a part of Java since Java 1.0.
Wednesday, May 28, 2008
How do you modify the Manifest File of a JAR?
Question: How do you modify the Manifest File of a JAR?
Answer: Let's discuss first why would we need to modify a Manifest File? Well... there can be various reason. One being the change of Entry Point of a stand-alone application. The Main-Class header of the Manifest file contains the Class Name whose main() method wil be used to start the execution. If you want to specify any other Class as the Entry Point, you may need to modify the Manifest File. Similarly, the Manifest File may be modified to add any other special purpose headers with appropriate values.
How to modify it?
We can only merge other info to the already existing manifest file of a JAR. 'jar' tool automatically creates one default manifest file and we can add any extra info to the contents of the default manifest file. Subsequently, if we want to add even more info then also we need to follow the same procedure and that extra info will be added to the contents of the existing manifest file.
For adding any extra info we need to create a text file having the details in a proper format. Once the text file is ready then we can use the 'jar' tool with 'm' option to add that info to the contents of the already existing manifest file. Proper format means the data you have in the text file should form the contents of a valid manifest file and every line of the text file must end with a new line or a carriage return.
Caution: don't forget to add a new line after the last line of the text file as well otherwise that line may not be parsed properly.
Command for adding some info right at the time of creating the JAR file can be like this:-
jar cfm JArFileName.jar ManifestAdditionTextFile.txt InputFilesOfTheJAR
Here option 'c' means 'create a new JAR', option 'f' means 'the output should go to a file and not to the standard output', and option 'm' means 'merge info to the already existing (in this case default) manifest file'.
The order of options 'm' and 'f' must be in the same order as you provide the corresponding arguments to the command. 'c' option doesn't require any argument and normally comes as the first one.
What does 'e' option do with 'jar' command in Java?
Question: What does the option 'e' do with 'jar' command in Java?
Answer: This option is used to set an entry point to a stand-alone application bundled as a JAR file. This option was introduced in Java 6.0 and it either creates or overrides the Main-Class attribute value set in the manifest file of the JAR (which is also used for the same purpose). We can use this option either while creating the JAR or while updating it and it saves the effort of either editing or creating the manifest file.
Example: Creating a JAR file and setting the entry point:-
Option 'c' is for create and 'f' indicates that the output of the command will go to a file instead of going to the standard output.
jar cfe JarFileName.jar PackageName.EntryPointClass PackageName/EntryPointClass.class
Running the stand-alone application using the entry point:
java -jar JarFileName.jar
The execution will start with the main() method of the class named EntryPointClass as we set the entry point of the stand-alone application as this class.
Similarly, we can set the entry point while updating a JAR file using the 'u' option for update and then we can simply run the JAR file as we do in the above case:-
jar ufe JarFileName.jar PackageName.EntryPointClass PackageName/EntryPointClass.classJava -jar JarFileName.jar
Puzzle: 15 pirates, 100 Coins - how to distribute?
Puzzle: There are fifteen pirates all ranked by their years of service i.e., Pirate 15 is having 15 years of service, Pirate 14 is having 14 years of service, and so on. They find 100 gold coins. To divide these coins they agree on the condition which says "The most senior pirate will propose a way of distributing the coins, and then all the pirates (including the one who proposed) will vote and if he gets at least 50% votes then everyone will accept that proposal otherwise he'll be forced to leave the place without any coin. The next senior most will follow the same... and so on until a proposal gets approved."
Considering that all the pirates are able enough to see which proposal will ensure them the maximum gain. Their prefernces will be in the order to stay alive first, maximize the number of gold coins, and if at all there are equal outcomes in two situations then to have fewer number of pirates left with them.
After thinking for a while, the most senior pirate proposes a solution, which maximizes his share of gold coins, and others also accept that as none could think of any better alternative. What plan did the most senior pirate suggest?
Solution: The key here is to think about the pirates who the most senior pirate needs to take care of while proposing a plan. Okay... what will be the least number of pirates left to divide the gold coins among themselves? The least number will 1 when all other pirates get their plans dumped and hence leave the place. Now, if there is only 1 pirate left then he'll obviously get his own vote which will ensure 100% vote for him and he'll take home all the 100 coins.
Similarly, if there are only 2 pirates left then pirate 2 will be the most senior among them and he'll 50% vote by his own vote only and hence will take home all 100 coins. So, in this case pirate 1 won't get any coins.
If there are 3 pirates then the pirate 3 being the most senior may offer only 1 gold coin to pirate 1 to ensure his vote and will safely take home the rest 99 coins. Pirate 1 knows that if he dumps the plan proposed by pirate 3 then pirate 3 will leave the place and pirate 2 being the senior most will take home all 100 coins. So, pirate 1 will have no ther choice but to accept the plan prposed by pirate 3 in this case.
If there are 4 pirates then pirate 4 being the senior most pirate requires one more vote to ensure 50%. He knows that in case there are only 3 pirates left then pirate 2 gets 0 coins, so he'll offer 1 gold coin to pirate 2 and pirate 2 will have no other option but to accept it. Pirate 4 will take home 99 coins.
If there are 5 pirates then pirate 5 being the senior most requires 2 votes except his own vote to ensure 50%+. So, he will offer 1 coin to pirate 3 and 1 coin to pirate 1, which pirate 3 and pirate 1 will have to accept because in absence of pirate 5, pirate 4 will become the senior most and in that case pirate 1 and pirate 3 will get nothing. So, pirate 5 will take home 98 gold coins.
Similarly, if there are 15 pirates then pirate 15 being the most senior requires 7 other votes except his own vote to ensure 50%+ and hence he'll offer 1 coin each to all the pirates who won't get anything in absence of pirate 15. These pirates will be pirate 13, pirate 11, pirate 9, pirate 7, pirate 5, pirate 3 and pirate 1. All these seven pirates will accept the plan proposed by pirate 15 because they know that if he leaves and pirate 14 becomes the senior most then they'll go home with 0 coins :-)
Significance of the Manifest File in a JAR?
Question: Significance of the Manifest File in a JAR?
Answer: The Manifest File in a JAR contains meta-information (information about other information) about the other contents of it.
One common usage of Manifest File is to specify the entry point of a stand-alone application bundled as a JAR. The Main-Class header is used to specify the class whose main method will be called to start the execution if the JAR file is run by the command "java -jar JarFileName.jar".
Other uses of Manifest File is to provide information about Dependencies of the JAR file on other JAR files, Version of the JAR file, Security Information, etc.
This file exists in the META-INF directory of the JAR with the filename "MANIFEST.mf".
How to invoke an Applet packaged as a JAR?
Question: How do you invoke an Applet packaged as a JAR?
Answer: By including archive attribute to the 'applet' element in the HTML code, which invokes the Applet. This attribute will have the value as the JAR file name containing the Applet class. (...archive="nameOfTheJARFile.jar"...)
Probability of seeing a car in 5 minutes - Puzzle
Puzzle: If the probability of observing a car on a highway in 20 minutes time is 609/625 then what is the probability of observing a car in 5 minutes time on the same highway (considering all the factors involved to be uniform)?
Solution: Probability of seeing a car in 20 minutes = 609/625
=> Probability of not seeing a car in 20 minutes = 1 - 609/625 = 16/625
=> (Probability of not seeing a car in 5 minutes)^4 = 16/625
=> Probability of not seeing a car in 5 minutes = (16/625)^(1/4)
=> Probability of not seeing a car in 5 minutes = 2/5
Hence, the Probability of seeing a car in 5 minutes = 1 - 2/5 = 3/5
Archives from the Category Tips/Hacks - 1
Archived Articles from the Category - Tips/Hacks
- Creating documents straight out of your emails in GMail using Labs
- Free 2/3 - Col XML Templates. How to apply a new Skin in Blogger?
- Inserting Google AdSense Ad code in Body, Sidebar, etc. in Blogger?
Tuesday, May 27, 2008
Externalizable in Java? What is it used for?
Externalizable in Java
It's an interface which subclasses the java.io.Serializable marker interface. This interface contains two methods:
- void writeExternal(ObjectOutput out)
- void readExternal(ObjectInput in)
This interface is implemented by a class to handle the responsibility of saving and restoring the contents of its instances to (or from) streams by itself, which it does by implementing the above two methods. Only the identity of the class which implements Externalizable interface is saved in the serialization stream. The control is entirely delegated to the class to handle the saving and restoring all of its contents. It needs to take care of the saving/restoring the state of its super types as well.
Every object which requires to be stored is first tested whether it's Externalizable or not. If yes, then the writeExternal() method is called to do the task of saving of contents otherwise the state of the object is saved using ObjectOutputStream (using writeObject() of this class). If the class is not even Serializable (in case the class doesn't even implement java.io.Serialzable interface) then we get NotSerialzableException. Similarly, an Externalizable instance is restored by first using the public no-argument constructor and then by calling the readExternal() method. If the class is not Externalizable, but it's Serializable then the restore is done by ObjectInputStream (readObject() method of this class).
writeExternal method
This method saves the contents of objects either by calling the methods of the DataOutput interface for primitive data types or by calling the writeObject() method of the ObjectOutput interface for all kind of objects (including arrays). This method throws IOException if it encounters any problem while writing the contents to the output stream.
readExternal method
This method restores the contents of objects either by calling the methods of the DataInput interface for primitive data types or by calling the readObject() method of the ObjectInput interface for all kind of objects (including arrays). This method throws either IOException in case it encounters any I/O error while reading from the input stream OR ClassNotFoundException in case the class for the object being restored is not found.
Read Next: You may like to go through the article - Serializability in Java >>, if you have not already gone through. Proceed next to the article - Security risks with Externalizable interface & its inapplicability >>
InvalidClassException and serialVersionUID in Java
InvalidClassException and serialVersionUID in Java
When you implement java.io.Serializable interface to make a class serializable, the compiler looks for a static, final field named "serialVersionUID" of type long. If the class doesn't have this field declared explicitly then the compiler will create one such field and assign it with a value which comes out of a implementation dependent computation of serialVersionUID. This computation depends upon various aspects of the class and it follows the Object Serialization Specifications given by Sun. But, the value is not guaranteed to be the same across all compiler implementations.
This value is used for checking the compatibility of the classes with respect to serialization and this is done while de-serializing a saved object. The Serialization Runtime verifies that the serialVersionUID of the sender class (which was used for saving the state of the object on the stream) and that of the receiver class (the class which is being used to restore the object, possibly at some other system) both are exactly same. If the receiver system has loaded the class having some other serialVersionUID than that of the class used while serialization process then we get an InvalidClassException.
Caution: It's highly recommended that you explicitly declare and initialize the static, final field of type long and named 'serialVersionUID' in all your classes you want to make Serializable instead of relying on the default computation of the value for this field. This computation is extremely sensitive and may vary from one compiler implementation to another and hence you may turn up getting the InvalidClassException even for the same class just because you used different compiler implementations on the sender and the receiver ends of the serialization process.
In most of the cases you would be using 'private' access specifier only for this field as the declaration normally applies only to the class declaring it and we don't really need to either inherit this field in the subclasses OR to access it from outside. So, there is hardly any reason why we shouldn't keep it 'private'.
How do you avoid InvalidClassException for arrays?
Question: Arrays are objects in Java. How do you ensure that you don't get InvalidClassException due to potentially different serialVersionUID across different Java Compiler implementations?
Answer: Java specifications ensure that for us. Nothing specific required for arrays in this regard. Okay... the next question which may come to our mind is:- why the requirement of matching the serialVersionUID is waived for Arrays in Java? The underlying reason for this waiver is that even though Arrays are treated as objects in Java, we don't really have a Class which we can change for adding this new field explicitly, so we can not declare and initialize serialVersionUID field the way we do for any other class we ensure uniform serialization for. Array classes will continue to have only the default computed value for serialVersionUID. And hence the waiver is probably the only solution to avoid a potential InvalidClassException across different Java Compiler implementations.
What is Serializability in Java? How does it work?
Serializability in Java
It's a mechanism in Java to ensure that the objects of classes implementing java.io.Serializable interface will have the capability of storing their states on a persistent storage that can be loaded back into the memory with the same state whenever needed.
The Serializable interface is only a marker interface and has no methods or fields in it. It just serves the purpose of notifying the JVM about the Class implementing it that the Class may require to save its state on a persistent medium and subsequently may need to restore the same saved state in the memory when needed. The compiler handles it either by identifying serialVersionUID field in the class or by adding one to the class (the next post talks in detail about serialVersionUID) and presence of this field notifies the Runtime Environment to treat the instance creation appropriately.
The subclasses of a Serializable class are automatically Serializable, and if you want to Serialize sub classes of non-serialized classes then you need to ensure that the super class has a no-argument constructor. Reason being, on marking the sub class as a Serialized class, it tries to save and restore the state of public, protected, and package (of course only if accessible) fields of the super class also. The sub class can do this only if the super class has a no-argument constructor. Otherwise, you'll get a runtime exception.
While De-Serialization also the state of the public, protected, and package (only if accessible) fields of the non-serialized super classes are restored using the no-argument constructor of the super class. The state of the fields of the serialized sub-class is restored from the stream.
Custom handling of objects while Serialization/Deserialization
In addition to the default serialization or deserialization of objects, Java also supports special handling of the serialization (or deserialization) of objects. You just need to implement the following three special methods in that case and do whatever way you want the save/restore of the objects to go. These special methods are:-
- private void writeObject(java.io.ObjectOutputStream out) throws IOExceptionprivate
- private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundExceptionprivate
- private void readObjectNoData() throws ObjectStreamException
writeObject method
As the name suggests, this method is used for writing the state of the object to the output stream passed as its parameter. Usually the defaultWriteObject() method (or methods from the DataOutput interface for primitive types) of the ObjectOutputStream class is used to write non-static and non-transient fields of the current class to the output stream. The defaultWriteObject() method can be called from within a writeObject method only, otherwise it throws NotActiveException. Some I/O error while writing the date to the stream will cause the IOException to be thrown by this method.
readObject method
This method reads the data saved by the writeObject method and restores the state of the object. This method normally calls readDefaultObject() method (or methods from DataInput interface for primitive types) of the ObjectInputStream class to restore the non-static and non-transient fields of the object.
An interesting scenario: Suppose you have a class having 4 non-static and non-transient fields namely fld1, fld2, fld3, and fld4. Now you create an instance and save the state of the object on a persistent medium using writeObject method. Down the line the class evolves and you need to add two new non-static, non-transient fields namely fld5, fld6. What will happen, if you try to restore the previously saved state of the object with an object reference of the new version of the Class?
Well... nothing serious. Actually the readDefaultObject() method reads the data and the field name from the stream and assigns the corresponding named field of the current object. So, in our case fld1, fld2, fld3, and fld4 will get restored from the stream and the other two fields fld5 and fld6 will continue having default values.
readObjectNoData method
Suppose you have a class named Class1 and you have saved the state of an object of this class on a persistent medium. You send that saved state to some other application, which has a different version of the same class 'Class1'. Say the recipient application is having a version where Class1 extends another class named 'Class2'. Now, if you try to restore the saved state shipped to the recipient application, you need to use readObjectNoData method and not the readObject method. Reason being, the recipient application will try to look for the state of the superclass of Class1, which is Class2 and obviously it won't find that in the saved state. This may happen in that case also where the saved state of the object gets tempered. readObjectNoData method simply initializes the state of the superclass in any of the above two scenarios.
Read Next - What is Externalizable interface in Java? Once done with this artcile you may like to compare the two interfaces and see the differences between the two. This may help you understanding when to use which one of the two interfaces? What are the potential problems and security risks with using these interfaces? ... The artcile - Serializability vs Externalizability in Java covers these topics.
Monday, May 26, 2008
Train, Tunnel, and Man. How faster is the train running?
Puzzle: A man has entered into a tunnel and has crossed only 1/4 of it while it hears a whistle from a train behind him. He turns and runs towards the train with the same speed and he could barely get out of tunnel before the train (running with a constant speed) could hit him at the entrance of the tunnel. Had he moved in the same direction with the same speed then also he could have crossed the tunnel before the train could have hit him at the exit of the tunnel. Assume that the speed of the man is uniform, he takes zero time to turn back, and instantly gets his speed while turning back. How faster is the train moving as compared to the man?
Solution: Let the speed of the train be X and that of the man be Y. Let the length of the tunnel be T and the distance of the train from the entrance of the tunnel at the time the man turned back is E.
Now, we can easily form two euqations with the given data. One, The man covered T/4 distance and the train covered E distance in the same time, hence
E/X = (T/4)/Y
=> X/Y = E/(T/4)
=> X/Y = 4E/T ..... (i)
Two, The man could have covered 3T/4 distance and the train could have covered E + T in the same time, hence
(E+T)/X = (3T/4)/Y
=> X/Y = (E+T)/(3T/4)
=> X/Y = 4(E+T)/3T ..... (ii)
Comparing (i) & (ii), we get
4E/T = 4(E+T)/3T
=> E = (E+T)/3
=> 3E = E + T
=> T = 2E
putting this value in equation (i), we get
X/Y = 4E/2E
=> X/Y = 2
That means the train is running twice as fast as the man.
Extension Mechanism in Java. What, How, etc.
Extensions in Java
Extension are nothing but a set of packages or classes or related resources all bundled into a Java Archive (JAR) file and stored at (or referenced from) a specified location. You can have two types of extensions in Java based on whether you store the JAR at a specified location OR reference the JAR from a specified location. These are:
- Installed Extension: If you store the JAR file in a particular directory (inside the current Java Runtime Environment), which is especially meant to store Java extensions then such extensions are named installed extensions.
- Download Extenssion: If you specify the JAR file from the manifest file of another JAR file (accessible to the application) then in this case the extensions are named download extensions.
Installed Extensions
The special directory used to keep the installed extensions is jdk<version>/jre/lib/ext. These installed extensions become part of the Core API of the underlying Java platform, so they will be visible and hence available in all the processes running in the current Java Runtime Environment, so do take care of the directory structure of the classes in the JAR file before bundling them. It should be similar to what we have for the other standard APIs in Java.
Java 6 goes one step further and allows you to store the installed extensions at an independent location and all the JREs installed on a particular system can share the same extensions. Prior to Java 6, the extensions were looked only in ../jre/lib/ext directory, but from Java 6 they will be looked in a series of directories staring with this directory. So, the first directory of that series will always be .../jre/lib/ext and maybe you can have the independent location as the second entry. Currently this independent location is independent only to the JREs installed on a system, but fixed for a particular Operating System. Like, this directory should be SystemRoot\Sun\Java\lib\ext for MS Windows OS, /usr/jdk/packages/lib/ext for Solaris OS, and /usr/java/packages/lib/ext for Linux OS.
Download Extensions
In this case the extension JAR files are referenced from the manifest file of any other JAR of the current JRE. The JAR file referring to the download extension need to be itself an extension. It can be a normal JAR file somehow reachable to the application (i.e., the directory having this JAR file should be there somewhere in the CLASSPATH). There are two ways of referring to an external JAR file in a manifest file: One, by using a Class-Path header and Two, by using an Extension-List header. A maximum of one of each of the headers is allowed in a manifest file. But, one header can refer any number of extension JARs.
The difference between the two ways is that the download extensions referred by a Class-Path header are downloaded only for the lifetime of the application which downloads them. For example, a Web Browser running an Applet may require certain functionalities to be shipped via download extensions for the smooth execution of the Applet in the browser window. The advantage of using this approach is that you don't need to install anything on the clinet machine. The clinet machine should be capable of running a Web Browser. That's it. The disadvantage is also quite clear - you download it every time you need. Download extentions referred by an Extension-List header cause the extensions to be downloaded the first time they are needed and they are directly installed in the .../jre/lib/ext directory of the underlying JRE that time only. So, they become similar to an installed extension afterwards. This is the advantage that you need to download them only once, but the disadvantage is that the deployment of Extension-List header based download extentions is complex as compared to Class-Path header based download extensions.
Sunday, May 25, 2008
Properties and System Properties in Java
One of our visitors, Ran Vijay posted the following two questions:-
- What are System Properties in Java?
- What is the difference between loading a JDBC Driver using System Properties and loading it using Class.forName()?
Let's first discuss Properties in Java and then we'll move on to System Properties and finally to the second question, which is regarding loading of JDBC Drivers.
Properties in Java
In Java, Properties are actually configuration values which are managed as the traditional key-value pairs. Both the Key and the Value in every pair will be String values only. As the name suggests, the Key will be used to retrieve the corresponding Value and hence it must be unique in a properties file. These files are plain text files and by convention we give them ".properties" extension. To manage properties in Java, we need to create instance of java.util.Properties class. This class contains all the methods required to manage and access the properties file. The properties files are used quite frequently in Java applications for storing and managing the configuration value which your application may require during various phases of its execution. For Example, you may have a property named "DBURL" and you can simply use the value associated with this key to fetch the Database URL you would like to use at run time. The advantage of using this approach is that if you want to change the DBURL then you don't need to touch the code now. The all you need is to go and change the Value associated with the "DBURL" Key in the properties file being accessed in your application. This will make your application far more flexible and maintainable. If a user (say a tester) doesn't know Java then it'll be difficult for him/her to change the URL in the Java code, but changing the value in a text-file will be easy for everyone and hence such an approach will enhance the usability of your application as well.
getProperty(String key) and getProperty(String key, String defaultValueifkeyNotFound) are the methods used to read the properties. Similarly, setProperty(String key, String value) is the method to add another Key-Value pair to the Properties object.
Caution: Access to a properties file requires approval from the current security manager of the running application. So, you may not like to put any such code inside an applet as the browser, your code will run into, may not have enough priviledges to access a file on the local disk. Moreover, it's hard to assume that the property you require in your applet will be there in the properties file (or even a file with that name will exist) on the local disk.
System Properties in Java
The way we use custom proprties file to maintain the configuration details of our application, the Java platform also uses a Properties object to maintain the configuration details of the current runtime environment. This object is called System Properties and it stores hell lot of Key-Value pairs for different properties the Java runtime environment uses to maintain the execution environment. Some of these properties store the Current User, Version of the Java Runtime Env, Path Separator character, OS Name, OS Version, User's Working Directory, User's Home Directory, JDBC Drivers, etc. Many of these System Properties are standard, but few additional platform dependent System Properties may also exist.
Reading/Writing to the System Properties
Reading is pretty simple. You just need to use 'System.getProperty()' method. This method has two variants. One, which requires only one String argument. Two, which requires two String arguments. For the one which requires only one argument, you need to give the name of the System Property you're trying to get the value of. This method returns 'null' if the property with that name doesn't exist. The second variant of this method requires you to specify the second String argument as the value you would like to be returned (instead of 'null') in case a property with the name given as the first argument doesn't exist.
Writing to the System Properties is not quite similar to what we use to write to a normal Properties onject. We use 'System.setProperties()' method, which requires a Propereties object. You need to set this object with all the required Key-value pairs. Beware, it replaces the entire set of system properties with those represented by the passed properties object. The changes made by this method will last only for the current run time environment and the Java run time system re-initializes the system properties each time it starts up. If you want to make the changes permanent then you need to write the value to some file before shutting down the application and load and set the System Properties each time the application starts up.
Caution: Read/Write access to the System Properties is also governed by the current Security Manager of the running application, so you may be denied the access in various situation - most common of them being 'accessing them in Applets'.
Difference between loading the JDBC Drivers through System Properties and through Class.forName()?
Well... no real difference in the functioning of the drivers. It's just the time of loading and instantiating the drivers that gets different in these two cases. In case of loading the drivers through System Properties, they get loaded and instantiated during the start up of the Java Runtime Environment itself while loading them through Class.forName() will cause the loading and instantiating of the driver during the execution of this Java statement. You may like to read the article 'Role of DriverManager Class and Driver Interface in Java' for more details.
Saturday, May 24, 2008
Why Java does not have Clear Screen functionality?
Why Java does not have Clear Screen functionality?
Clear Screen functionality has not been implemented in Java as it's simply not possible without sacrificing Platform Independence. So, how to handle a situation asking this? Well... Java has not been designed to develop applications requiring a direct console based interaction. You may think of using Swing or AWT based GUI instead. It's not impossible to have such a functionality in Java, but certainly not portable and hence not preferrable. We do have few platform dependent workarounds to achieve it in Java and the best among the lot still remains the same - using JNI.
In Java, we don't have the concept of a typical console as we have in C/C++. Instead all I/O in Java is stream-based. I don't think Clear Screen can be implemented for a stream as the steam may point to a file, a printer (it will be a really challenging scenario, isn't it?), or may be to a console on certain platforms. Since, you never know what this stream would be pointing to at run time, you can't assume it to be a console in all the cases and hence can not have that functionality. Clear Screen will obviously make sense only for clearing the console and not for a file (logs etc.).
System.out.println() is far more easier to implement in all environments maintaining platform independence as irrespective of what the stream points to at runtime, it can always be written on. This holds true for C/C++ as well. And probably this is the reason why 'printf()' works fine in all environments in case of C/C++ (Now in Java also ... Java 5.0 onwards) and not 'clrscr()'.
C++ also has the concept of Streams similar to that in Java and I think Clear Screen function is not a part of any class based on streams. It's a separate method altogether and it has a specific implementation only for those environments which have the concept of Console. For different platforms we may need to look for different vendor specific extension to have that functionality even in case of C/C++. For instance, Turbo C/C++ has the function 'clrscr()' in the vendor specific header file 'conio.h'. We don't have that header file available for Linux platform.
Similar explanation can be given for other platform dependent tasks such as 'accepting input without ENTER being pressed - a functionality getch() provides in C/C++', 'applying font color, background color, etc. on the console', and so on. Such tasks have not been implemented consistently across all platforms even in C/C++, so forget about Java. The goals of Java will probably never allow such tasks to be implemented not at least by using standard library functions. You got to use platform-dependent vendor specific packages to achive them unless of course, all the environments start following the same standards for console and other related stuff.
I thank Lavnish (one of our regular visitors) for raising this point in response to the post on 'Limitations of Java Language'. He runs a blog and writes frequently on Java. You can find his post on the Clear Screen functionality here. I hope our visitors will continue chipping in with their valuable comments and making this place better and better for us.
Update from Java 6.0
Java 6.0 has gone C/C++ way to facilitate better interaction with character-based console devices by using standard library functions. It seems that it wasn't possible for them to have such features for traditional Java Streams and hence they created a new Java Class named java.io.Console. This Class is mainly for reading from and writing to the Console and not for clearing it (as of now).
The Sun Java Doc of this class clearly says that the class contains methods to access the character-based console device, if any, associated with the current JVM. We can obviously see a compromise with Platform Independence here as the code written using this Class can never be guaranteed to behave uniformly across all platforms and hence not portable. System.console() method simply returns 'null' on the platforms which doesn't have an associated Console with the underlying JVM.
On the platforms where it finds a Console, it probably uses JNI internally to get the task done. We always have such solutions provided by third party vendors and the only good thing about the addition of this new class is probably that it's now a part of the standard library and it might be having little more efficient code than the code supplied by the third party vendors.
BTW, the center of our discussion 'Clear Screen functionality' is still not there in this class. Let's see if at all they provide that also in the newer releases of Java.
The bottom line remains the same - we would probably never have any such functionality without compromising Platform Independence and in most of the cases the APIs would probably be using JNI only. A true Java solution to this problem still remains a topic of research.
Friday, May 23, 2008
Rope Bridge, Torch, Four People - Puzzle
Puzzle: Four people need to cross a rope bridge, which is strong enough to support only two people at a time. First person takes 1 minute to cross the bridge, Second person takes 2 minutes, Third person takes 5 minutes, and the Fourth person takes 10 minutes to cross the bridge. They have a torch which has battery left only for 17 minutes and the bridge can not be crossed without light. How will they manage to cross the bridge?
Solution: Let's say the four people as P, Q, R, and S. Based on the info we have, let's consider P takes 1 minute, Q takes 2 minutes, R takes 5 minutes, and S takes 10 minutes to cross the bridge.
Now, they can manage to cross the bridge in time if they follow the below steps:-
- Step #1: P and Q cross the river. Total time taken so far = 2 minutes
- Step #2: Q comes back. Total time taken so far = 2 + 2 = 4 minutes
- Step #3: R and S cross the river. Total time takes so far = 4 + 10 = 14 minutes
- Step #4: P comes back (he's at the other end). Total time so far = 14 + 1 = 15 minutes
- Step #5: P & Q cross the river. Total time taken so far = 15 + 2 = 17 minutes
We can have another valid solution similar to the above in case P comes back instead of Q in Step #2:-
- Step #1: P and Q cross the river. Total time = 2 minutes
- Step #2: P comes back. Total time = 2 + 1 = 3 minutes
- Step #3: R and S cross the river. Total time = 3 + 10 = 13 minutes
- Step #4: Q comes back. Total time = 13 + 2 = 15 minutes
- Step #5: P and Q cross the river. Total time = 15 + 2 = 17 minutes
Adobe - Reverse the order of words in a char seq
Question: Write an efficient algorithm to Reverse the order of words in a given array of character which form a sequence of words.
Note: Memory-based question, suppodely a part of 'Engineering' section of the written test for a Dev position at Adobe.
Solution: Find below one possible algorithm to solve this problem:-
- Allocate memory for another array of same size
- Iterate through the array and find words (by finding white spaces)
- Put the word reversed (order of characters reversed) in the new array
- Put the white spaces as well (you won't reverse them as they are same either way)
- Continue and complete the iteration for all the words in the array
- Copy the new array reversed into the original array and you're done!
Example: Suppose you have one array "int char float" in the beginning. The expected result should be "float char int" in this case. Let's dry run the above algorithm for this test array and see if it gets us the expected result.
NewArray = " " (a array of 14 characters, currently all blank)
Iteration starts here
First word found: "int", so NewArray = "tni "
Second word found: "char", so NewArray = "tni rahc "
Third word found: "float", so NewArray = "tni rahc taolf"
Iteration ends here
Now reverse of the NewArray = "float char int"
Adobe - C code for allocating a 2D (or 3D) array
Question: Write C code to dynamically allocate and free memory for a 2D (or 3D) array.
Note: Memory-based question, suppodely a part of 'C Programming' section of the written test for a Dev position at Adobe.
Solution: Here, I'm taking the case of a 2D array only. Allocation of a 3D array will also be quite similar. Let number of rows be ROW and number of columns be COL. There are at least three ways of doing the allocation, which are:-
Method #1: Store the elements of the array as a set of ROW, each of which holds COL integers. An array of ROW integer pointers, each of which will point to the corresponding row having COL integers each. Array is accessed as arr[i][j]. The allocation may be Non-Contiguous in this case.
Find above the C-code for allocating and freeing a 2D array following this method. Click the image to enlarge it.
Method #2: Store the elements of the array as a 1D array of ROW*COL integers with an array of ROW integer pointers which refer to the appropriate places in the previously allocated 1D array for the arr[i][j] type of access. In this case the allocation will always be Contiguous.
Find above the C-code for allocating and freeing a 2D array following this method. Click the image to enlarge it.
Method #3: This method is just a variant of the second method. In this case we allocate memory for 1D of ROW*COL integers and access the elements as arr[COL * i + j], instead of arr[i][j]. The allocation is always Contiguous in this case as well.
Find above the C-code for allocating and freeing a 2D array following this method. Click the image to enlarge it.