CS50 - week 1 - Problem Set 1/4

Harvard runs an introductory computer science course, called CS50. The purpose of the said course is to give a taste of programming to the students. During the 12 lessons there are multiple programming languages one get exposed to upon completing the series, so far I've got introduced to Scratch and the very basics of C.

Last year I already tried to get into the course, but as usual I only made the first lesson. Now I'm jumping straight into the C parts to avoid getting bored with the repeated lesson. In the CS50 series each lesson has problem sets, homework assignments which are testing the level of understanding of the given subject.

In Lesson 1 there are four tasks to complete, and during this week I will complete them and write here how I've tackled them, primary because I think these tasks could be great candidates for software engineer coding interviews. 

Task 1: Mario level 1 (PSET 1 - 1/4)

The task is to create a software, which fulfills the following acceptance criteria:

The program takes a number as an input and then draws a half pyramid which has as many levels as the input number.

So let's pretend that we got this task at a coding interview. Based on the Google Sample Interview (and several other resources, like Cracking The Coding Interview), we need to follow the success recipe bellow:

1. Write example(s)
2. Ask questions about the given task
3. Scribble down a suggested solution with simple symbols or sentences
4. Try to think about optimization solutions! What is the big O of your algorithm?
5. Write the code of your solution at the board
6. Give some test cases to validate your solution

As a first step let's formalize an example:

Input: 3

Output:

     #

  ##

###

Questions to ask with answers in parenthesizes:

• Can we assume, that the input is an integer? (Yes, the input is an integer.)
• Can we assume, that the input equals or bigger than 0? (No, the input integer could be any number, but you need to draw the half pyramid if the input is bigger than zero.)
• Does the running environment has any memory or storage constraint? (Let's pretend, that it does not have any constraints for the sake of simplicity.)
• Can we set a boundary for the input? (Yes, let's say, that the lower boundary of the input is -1000, and the upper boundary is 1000.)

Plan to solve the issue:

1. Write a command to the user on the console - prompt her for a number!
2. Check if the input is bigger, than 0.
3. If not, let's write a message to the user and terminate.
4. Else let's write N-1 times a white space and than a # in the first row
5. In the second row let's write N-2 times a white space and than two hashtags
6. And so on until we reach the last row where we only want to write down hashtags

Optimization:

In the above solution we iterate thrice:
- once from 0 to N-1 for the rows with the help of variable I
- in each row we iterate from N-1-I to 0 with the help of variable J to write down white spaces
- in each row we iterate from 0 to I with the help of variable K to write down hashtags

Basically we are drawing a matrix, where each cell either could be a space or a hashtag. The matrix with and height are both N where N is the input number. As we see basically we iterate in N rows and in each rows N times to fill the cells. The big O for the algorithm is N². As far as I'm concerned, we cannot fight this to a lower number (prove me wrong with a comment! :) ).

The code itself:

#include <stdio.h>


int main(void) {
 
    // Prompt the user for the input number
    printf("Please provide a number:\n");
    int inputNumber;
    scanf("%d", &inputNumber);

 if (inputNumber < 0) {
  printf("Please re-run the program and give a bigger number, than 0.\n");

        // Let's return an error code!
        return -1;
    }
    else {

        for (int i = 0; i < inputNumber; i++) {
           for (int j = inputNumber -1 - i; j > 0; j--) {
               printf(" ");
           }

           for (int k = 0; k <= i; k++) {
               printf("#");
           }

           printf("\n");
        }
    }
}

Test cases to mention:

1. Do not try to input anything else than a valid int, as in the specification we assumed, that the input will be an integer.
2. Try to input a 0, expect the error message.
3. Try to input a negative number, expect the error message.
4. Try to input a big integer, expect that the console won't be able to draw it accordingly.

That's all for today, tomorrow I will cover Mario level 2! :) Thanks for tuning in!