Do-It-Yourself (OpenGyan) - Write a (your own) shell

This is one of the exercises we give to students in our workshop on Linux programming. Many of the participants understand the concept behind the shell and use basic process management system calls (fork, exec, wait and exit) to write a miniature shell on their own. Given time (and effort), i think one can write their own shell. Here is the requirement for a brand new shell (feel free to assume/add more requirements). As an additional effort, try to find the features that are missing in existing shells and implement those in your new shell.

Write a mini-shell with a following features

1. The shell should receive command from the user and execute it. If the user just gives the command, you have search the command in all of directories defined in the environment variable PATH. If you are not able to find the command, you have print "no luck, seems like your program is toasted". If the user specifies the path along with the program, it is enough if you just load and execute it.
2. You should store the last command that is execute and its exit status.
3. You should implement a facility to run the program in background.
4. You should remember last “N” commands and print it upon user request.
5. You should name your shell and it should appear as the prompt.
6. When you type "quit", you must quit from your shell with a greeting.

Hope you find this interesting. Happy Shelling....

Puzzle - Mega Substring

Scenario #1

Given two strings - string1 and string2,  write a program to find whether string2 is a part of string1 (substring of string1). The above puzzle may seem to be very simple as it is. If this sound silly, read on.

Scenario #2

Assume that you have to write above substring program to compare the contents of two files whose sizes put together is more than the size of your RAM + SWAP partition (let us say 10GB of contents). If you feel like you can solve this with bit of try, move on to the next scenario.

Scenario #3:

What if I want to exploit the number of cores? Will it be better if I have few threads to do the job. If i choose to go with multi-threaded way, what are the special conditions that i should take care of?

Watch out this place for answer (probably this weekend - 20/Nov/2011)

Software Design Puzzle #8 - Manufacturing Soaps

Assume that you are an expert in manufacturing many varieties of soaps - bath soaps, detergent soaps and all soaps in the earth. You have a magic recipes of soap making right from procuring raw materials till manufacturing soaps and shipping to stores. There are many processes involved in soap making and there are various flavors for each process. And some of the processes are optional and specific types of soaps. For example, you know that you to have add a lot of scents for bath/toilet soap and lot of whitening material for detergent soaps. 

The puzzle is to design the soap manufacturing with lot of processes/steps and all these processes/steps are sequential meaning that one process cannot start until the previous processes are complete. For instance, the process of shipping cannot happen until you make soap and you cannot make soaps until you form soap base and you cannot start soap base without raw materials.

Can you design soap manufacturing process where one step depends on so many previous steps. To induce your thinking, let us assume that you have the following processes/steps

• Buy raw materials (can be different based on the soaps)
• Mix raw materials
• Form soap base
• Make soaps
• Package soaps
• Ship It

You are free to add more steps but the key is to come up with a process that can be changed dynamically based on soap types that are going to be invented in future :-)

Software Design Puzzle #7.2 - Thread Pools & Tasks

Please refer to previous two posts on the same problem - Implementing Thread Pools and Tasks. Here is the link for your convenience.

• Software Design Puzzle #7 - Thread Pools & Tasks
• Software Design Puzzle #7.1 - Thread Pools & Tasks

Yesterday, i added a requirement that i want to have a priority for tasks (a problem on data structures and algorithms). Today, i thought about another feature that gives a lot of flexibility (real OO design). In the above examples, we didn't talk much about the threads in thread pools. Can we try to make threads in thread pool dynamic entity - based on the need, the number of threads in thread pool should grow or shrink. Here are my next set of questions.

1. What are the design decisions that i should take so as to make thread pool dynamic.
2. How can i make threads, tasks, thread pool at the topmost level of abstraction and yet get many different concrete implementations.
3. How can i ensure that the code I am going to develop after two years (due to new requirements) doesn't affect my code now (seal the code from modification for new requirements)
4. How can i bring in hierarchy, levels of abstraction and modularity for better design?
5. Do i have any design patterns?

Software Design Puzzle #7.1 - Thread Pools & Tasks

Refer to the previous post, Software Design Puzzle #7 - Thread Pools & Tasks. This post is an addendum to the previous post.

I m going to add one more enhancement to the thread pool design. The enhancement is to come up with a priority queue for tasks. Each task will have certain priority, an integer that increases as priority increases. At any given time, the task with highest priority has to be selected and run by threads in thread pool.

Can you refactor your design?

Software Design Puzzle #7 - Thread Pools & Tasks

We know what is thread. The thread is an independent execution path or entity in a process. When you want to exploit multi-core (increased processing) or do some blocking operations, the thread is the default destination (increased interactivity, heavy input/output operations). In any programming language that supports multi-threading, you run the code that can be run as independent execution path as thread with each having its own context. The infrastructure that is needed to run threads in parallel like stack, program counter, registers are tightly coupled with the code that runs. Due to this tight coupling, each time you need an independent path (let us call it as task), you create a thread (the infrastructure) which has its own overheads. Is it possible to change code of the thread?

Obviously the next step is to separate out the infrastructure and the task which is achieved using thread pools. Here is the next problem.

Write a simple thread pool in Java with following requirements

1. Have a fixed but configurable number of threads in thread pool. At any point of time, you can run up to N threads.
2. Have a task queue (or a suitable data structure). This can be much bigger than number of threads. The tasks wait in the queue for their turn.
3. The thread should consume tasks from the task queue and execute it. It can be any task (but you have to ensure some fairness). The role of the thread is to run task without bothering too much on what it does and how it does.

Software Design Puzzle #6 - Design A Dictionary

Think about a dictionary now and kind of things that you will do with a dictionary. Normally a dictionary will have simple operations of add, delete, edit and search words. Being a software dictionary, won't it be good that it suggests you list of words based on the words you type.

For example, when you type "sim", it should display first "N" closest match with the prefix supplied. I don't need to emphasize that the first word should be the exact match (if any) and then followed by list of words that matches closely.

Assume that you have many data store in which the words are stored (database, XML file, txt file, CSV file etc). It is enough to perform the search/auto-suggestion on the data in local database. If the user is willing, the user can also hear the word through audio and for doing that you have to contact a remote web service that gives a audio file for a specific word. You can also assume that there exists a audio file for every word in the database.

Can you design the application, come up with set of classes, assign responsibilities to the classes and a brief architectural diagram too.

Put your design patterns knowledge in action :-)

Testing is Fun and Brain Intensive - Why

Why testing is fun and Why testing has to be brain intensive

Before answering it, let us do this exercise.

Let us take one of the primitive types - "int" in Java and an arithmetic operation addition (imagine that you are testing Java compiler that will be used by developers/testers worldwide). What are things that you would do to verify the correctness of addition for "int". For now, let us focus only on integer addition alone. List down the things that you will learn (meaning that you should know) for completing the task. This exercise will help us to know "why testing is fun, why it has to be brain intensive and why it is equally rewarding".

To help you with some code, this is how addition looks like and you got to test + (which is in red font)

int a = 10, b = 255, c;

c = a + b;

How will you proceed?