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
Wednesday, April 30, 2008
Tuesday, April 29, 2008
Solution to Problem 2
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
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
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
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.
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
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
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
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
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
Monday, April 28, 2008
Solution to Group 1 problem
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
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
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!
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
Que 1.3> Write a program that finds the sum of the digits of a number, using recursion.
So you wanna code huh?
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.
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.
Subscribe to:
Posts (Atom)