How to write a Program?

Minesweeper

2008-05-11T20:26:00.000-07:00

If you are designing a minesweeper game, you would need to mark each block with how many mines are adjacent to it.

Write a program that places mines in a square grid. And marks each block with the number of mines adjacent to it.

Palindromes - Solution

2008-05-09T23:19:00.001-07:00

There are multiple ways to solve this trivial problem.
For a beginner, there is one catch in this problem. How to make it case insensitive? Basically, we can do so by changing the string to all upper or all lowercase letters and then check for palindromes.

There maybe any number of ways to approach this problem. I'll list down the 2 ways that usually people apply.

1. Reverse the string and check if the strings are the same

There are quite a few things to learn here.
i> There are library functions available to check if a character is uppercase or lowercase. There are also functions to convert a character from uppercase to lowercase and visa-versa. You can find these functions is ctype.h header file.
ii> Note that we did not compare the reverse of the string with str using the '==' operator. Can you guess why? Basically, because the '==' operator returns true only if the two strings share the same memory location. So we use the 'compare' method in the 'string' class.

2. Compare the 1st against the last character, 2nd against the 2nd last character and so on till we reach the middle.
This one is simple. Here is the code.

Click on the images for code clarity.

Problem 9 - Palindromes

2008-05-09T20:55:00.000-07:00

Write a program to find if a string is a palindrome.
Make it case insensitive.

Eg. "MADAM" - returns true
"ROB" - returns false
"Madam" - returns true
"mADaM" - returns true
"WhaWha"- returns false

Day 8 - Solution

2008-05-09T07:36:00.000-07:00

The first way is to go by a Brute Force string matching technique.
I guess its useless to give the algorithm if you are giving the source code anyways.

So here is the program.

Now lets try to do the same using the built in features of the 'string' class. Remember, our strings are not (char *) any more, they are objects of the 'string' class. Check out how our whole function that we wrote above, is replaced with a single statement.

Prog:

Note: Click on the image for clarity in reading.

Day 8 - Substring

2008-05-06T22:58:00.000-07:00

You are given two strings - haystack and needle.
You have to find the position of the first occurrence of needle in haystack.
Write a function that takes haystack and needle as input and returns the position of the first occurrence of needle or -1 if needle is not found in haystack.

Eg.

haystack = "Once upon a time, there lived a little boy named Jingle!"
needle = "up"
Return Value = 5

If needle = "fox"
Return Value = -1

Day 7 - Solution

2008-05-06T11:52:00.001-07:00

In a hurry today.
Please see the code!

click on the image for clarity.

Day 7 - Who Won?

2008-05-05T22:12:00.000-07:00

You are given an array of strings containing a 3 letter country name followed by a hyphen (-) and A 3 digit number. These strings represent the number of points earned by the students of the respective country in a programming competition.
NOTE: There are only 3 countries participating, India, China and USA. The 3 letter code for the countries are IND, CHI and USA respectively.

Write a function that calculates the total number of points scored by the students of IND, CHI and USA and returns a string in the same format with the country code followed by a hyphen followed by the total points scored by the country which has the highest points.

eg
INPUT -> ["IND-32","CHI-33","USA-29","USA-30","IND-12","CHI-34"]
OUTPUT -> "CHI-67"

NOTE: It is guaranteed that the sum of the scores won't be equal.

Day 6 - Solution

2008-05-05T06:20:00.000-07:00

The problem here is to break the string into corresponding numbers.

There are 2 general ways of going about it.

1. Using String Streams.
String Streams are a mechanism of converting a string to a stream. So you can do things like write to the stream and read from the stream, very similar to how you use cout and the << operator to write to Standard Output Stream and cin and >> operator to read from the Standard Input Stream.

So we initialize a String Stream with our string - namely DOB.
We then read the day, the '/' character, the month, the '/' character and the year from it.

Check the Program.

Click on the image for a clearer view.

2. The 2nd way is using sscanf()
The syntax of sscanf is very similar to scanf, only that you need to specify the string that it needs to scan as the first argument. Note that sscanf() is a C compatible function so our string object (dob) won't work with it. We will have to convert it to a C compatible string. That is attained by using the c_str() functionality built in the string class.
eg string obj -> "12/3/00"
obj.c_str() => char * => "12/3/00\0"

You'll understand better by having a look at the program.

Click on the image for a clearer view.

The result of both the program is the same:-

If you know of any other ways, please bring it to my notice :)

Day 6 - Question : Breaking Strings

2008-05-05T04:12:00.000-07:00

You are given a string containing a string Date of Birth in DD/MM/YYYY format. Eg "15/08/1947". Write a function that takes the string as an input and returns a vector containing 3 elements:
v[0] = Day as an integer
v[1] = Month as an integer
v[2] = Year as an integer

eg:
INPUT : "15/08/1947"
Output: [15, 8, 1947]

Day 5 Solution

2008-05-03T10:25:00.000-07:00

There is nothing special about this problem. No holistic views, no boundary conditions. You guys know "Sorting" right! This problem is to make you use it.

The Algorithm
1. Sort the array from 0 to n-1
2. Return the n-2th element

---

So you can do your regular sorting thing and get the result.

I would like to use this opportunity to introduce you to some more of STL.

Check the program

There is a legacy trick of finding the size of an array in that problem.
Noticed how we did -

sizeof(heights)/sizeof(int)

to get the number of elements in the array!

Then, while converting that array into a vector, we need to give the range of the array. By range I mean, a pointer (or an iterator) from the beginning of the array to the end of the array. Now 'heights' will give us the pointer to the beginning of the array and 'heights + n' to the end.

But will 'heights + n' always give us the pointer to the end of the array?
It will in our case, but it wont for other arrays of other types.
Can you tell why?

Day 5 - The second tallest student

2008-05-03T10:17:00.000-07:00

Problem - You are given an integer array of heights of students in a class. Write a function that returns the height of the 2nd tallest child in the class.

Day 4 Solution

2008-05-02T04:14:00.000-07:00

You can view the problem statement here.

Now you can imagine the gird to be a something like this

Point A could be your home and Point B your school/college.

So you would be thinking that (Ax - Bx) and (Ay - By) would give you your solution. But the solution could be negative as well. So you take the absolute value of (Ax - Bx) and (Ay - By) and add the two to get your answer.

Check the program.

Now the catch is...
While writing/imagining the solution, did you imagine only the positive co-ordinate axis or all the 4 axes? As in, did you imagine only positive co-ordinates for X and Y or did you imagine the negative ones as well?

If you imagined the Negative Axes as well then congrats! You are someone who already looks at boundary conditions. And if you did not, then congrats! You can start looking at boundary conditions for every problem you solve from now on!

In our case, the solution works well no mater which quadrant we are in. But real life problems, I'm afraid, are not so forgiving.

So did you find this post insightful? Keep bringing on your comments. I am looking forward to some readers posting a snapshot of their solutions too!

Day 4 problem - Whats the distance

2008-05-02T03:26:00.000-07:00

Here is todays problem.

You have a square grid extending infinitely in all directions. Your home is at point (hx,hy). You have to reach your college located at point (cx, cy). You can only travel parallel to the direction of the X or the Y axis and each step is 1 unit long. Write a program to find the number of steps between your home and your college.

Write it now. Test it. And come back later to check the solution.

Solution to Day 3 problem.

2008-05-01T05:44:00.000-07:00

View the problem statement here.

This problem is very simple, yet I have included it because I want the readers to start using some STL in their C++ programs.

What is STL?
It stands for Standard Template Library. This library has a lot of classes and functions that can replace a lot of data structures and algorithms that we use on a regular basis.

In order to solve our problem we can use the following algorithm
1. Set height[0] as RES
2. Loop through height, from begin to end

if current_element in height is < RES
set RES to current_element

3. Return RES

So, how do we use STL to do this?
We use STLs Algorithms.

--------------------------------------------------------
#include<algorithm>
#include<vector>

int minHeight(vector<int> height)
{
return *min_element(height.begin(),height.end()) ;
}
--------------------------------------------------------

OK OK, that seems to be too much too soon.
So lets break it down.

Q1. Whats that vector thingy? We were supposed to have an array as an input!
Ans. Vector is an STL class. Vectors are a replacement for Arrays. The <int> tells that its an array of int(s).

Q2. What is min_element?
Ans. min_element is a pre-defined* function in algorithm.h that returns a pointer to the minimum element in a specified range.

Q3. So height.begin(), height.end() are ranges right?
Ans. Exactly. height.begin() returns a pointer to the beginning of the array and height.end() returns a pointer to 1 past the end of the array. Between begin() and end() we have covered the whole array.

We will be talking a lot about using STL subsequently.
You can try the program out and let me know if there are any doubts.

* functions are declared not defined in header files. They are defined in the respective libraries.

Note: In reality, min_element() returns something called an iterator which is similar to a pointer and you don't have to bother much about it right now. STL is a very simple to use library with easy syntax, but the way it is taught in books is a bit daunting. So don't bother much about the syntax if you are reading it for the first time. Just see a few examples and learn from them.

Day 3 - Programming problem: Shortest height

2008-04-30T23:10:00.000-07:00

Question: You are given an array height[] of positive integers containing the heights of the children in a class. Write a function that takes height[] as an input and gives the shortest height as the output.

For example -
Input - [23,29,20,22,23,22,19,25,21,26,23,24,18,30]
Output - 18

Request: Pls take the quiz the right side bar to give feedback on the easiness/difficulty level of the questions. Thanks

Solution to Problem 2

2008-04-29T21:30:00.000-07:00

You can view the problem statement here.

Why did I ask this question now?
Because there are 3 good things in this problem :-
1. You need to understand the problem.
2. There is a lot you can do to optimize the solution
3. If you don't optimize the solution, you may end up screwing your reputation in your job interview.

Remember, anyone can code. But the way anyone will differentiate between you and an average coder is on the basis of

How well you handle the boundary conditions. (Does your code fail for any input)

How efficient your code is.

And how well can you optimize your code.

Many people coming to this blog are students who would be writing programs in their job interviews soon. I can tell from personal experience that the sexiest of companies only ask for programmers who code keeping the above points in their mind.

Ok now coming back to the problem.

We can check for primality by iterating from 2 to (n-1) and if it is divisible by any number in between, we can be sure that it is not a prime number.

However, there is a lot of unnecessary iteration over here.
You might be thinking that, since we are starting from 2, we can stop iterating when i reaches (n/2).

Well you are right. But the number of iterations can be optimized further.

Consider, a number 21. Lets list down its divisors
1 x 21 = 21
3 x 7 = 21
7 x 3 = 21
21 x 1 = 21
After removing the first and the last case. We are left with only 3 x 7 and 7 x 3. Notice the repetition. Once we have 3 we dont need to go till 7 do we?
Now you would argue that, our program will automatically come out of the loop at 3 so there is no question of reaching all the way till 7. Well you are right again. But the problem doesn't come when the input is composite (A number that is not prime). The problem comes when the number is prime. Take 23 for example.
Try dividing it with :-
2 - No
3 - No
4 - No
5 - No
.
.
.
11 - No
And then we come out of the loop.

But do we really need to go all the way till 11?
No we don't.
Applying some common sense, you can sense that after the square root of the number, the order of multiplication starts changing.
Let me illustrate that with an example.

Consider n = 24
2 x 12 = 24
3 x 8 = 24
4 x 6 = 24
6 x 4 = 24
8 x 3 = 24
12 x 2 = 24

The divisors start repeating after i becomes greater than 5. Its basically because, i becomes > 4.89 or Square Root(24). So we only need to iterate till the square root of a number.

Here is the code for the problem.

Now coming back to the 3 points that I had mentioned earlier on why this problem is good.
1. You need to understand the problem. Did you know that, prime numbers can't be negative? I didn't know it when I was asked to write this program the first time.
2. There is a lot you can do to optimize the solution You already have an idea of the optimization now.
3. If you don't optimize the solution, you may end up screwing your reputation in your job interview. If you apply for a job in a company like Google, Microsoft, Trilogy or an uber-cool startup. They are really gonna see how well you are able to optimize your solutions.

Can you find out a way of making the function return still faster for a random input?
Thats your assignment.

Thats all for the day.
Trust you found the post interesting.

Full_Metal

Problem 2

2008-04-29T12:24:00.000-07:00

Todays Problem.

Write a program to check if a number is a Prime Number.
Note: A prime number is a natural number > 1 which is divisible only by 1 and the number itself. This is what Wikipedia say about Prime Numbers.

Solution to Group 3 Problem

2008-04-29T02:36:00.000-07:00

Group 3.

View the question here.

Here we want to practice a bit of recursion.
Whenever you go about writing recursive code, you have to keep two things in mind.
1. There must be a terminating condition.
2. As the number of recursions increase, the problem state should approach the terminating condition.

Lets see that with respect to this program.

Now lets come back to the 2 conditions that we discussed above.

1. There must be a terminating condition. As you see, the (if n < 10) is the terminating condition. It is a terminating condition because a number is returned if that condition is satisfied. (Unlike the default case which calls the function again)
2. As the number of recursions increase, the problem state should approach the terminating condition. This is also satisfied because, we keep dividing the number by 10 in the default condition. So the number will keep becoming smaller and smaller and finally become <10, and the terminating condition will be reached.

OK, so did you find a problem with the program above?
Yes? -> Great!
No? -> If you check the previous post, I have mentioned that whenever we write a program, we should check for boundary conditions. This program won't work for negative numbers.

How to make it work for negative numbers?
This is your assignment.

Request: Please take the quiz or leave your comment to help me make this site more useful. Thanks

Solution to Group 2 Problem

2008-04-29T02:24:00.000-07:00

Group 2

View the problem here.

Here we have to add the sum of digits of a number. We can go about doing it by taking taking 1 digit at a time and adding it to the result.

Note: that whenever you write programs like these, always test for boundary conditions. Eg. Will the program work when the input is 0? What if the number is a negative number? etc.

Please click on the image for clarity.

Request: Please take the quiz or leave your comment to help me make this site more useful. Thanks

Solution to Group 1 problem

2008-04-28T18:48:00.000-07:00

I'll be writing in C++ to start with, will graduate to Java or Ruby if need be.

Group 1.

View the problem statement here.

Click the image to view enlarged version.

Its a good practice to use functions to do the calculation part and use the main() only for calling relevant functions and I/O.

Just click on the images for clarity.

Request: Please take the quiz or leave your comment to help me make this site more useful. Thanks

Categories of questions

2008-04-28T12:09:00.000-07:00

Most of the questions here will sound very trivial to a typical coder. But I am starting off with easy questions and we will graduate to tougher ones after I receive some feedback.

The questions are divided into 3 categories:-

Group 1. This question is for people who are not able to solve the Group 2 question.
Group 2. This question is for people who know find the Group 1 question too easy and the Group 3 question, too tough.
Group 3. This question is for people who found Group 1 and Group 2 questions easy to solve.

Its a lame, yet common sense way to categorize!

Todays Question: Group 3

2008-04-28T12:07:00.002-07:00

Que 1.3> Write a program that finds the sum of the digits of a number, using recursion.

Todays Question: Group 2

2008-04-28T12:05:00.000-07:00

Que 1.2> Write a program to find the sum of the digits in a number.

Todays Question: Group 1

2008-04-28T12:02:00.000-07:00

Que 1.1> Write a program to add 2 numbers.

So you wanna code huh?

2008-04-28T10:03:00.000-07:00

The best way to be a good coder is to write code and learn from other coders better than you.

I will post 1 problem every single day for people who have just started programming. I will post the solution in the night, the same day.

Based on user feedback, I will make the problems tougher or easier. So, do take part in the quiz.