Skip to content

Instantly share code, notes, and snippets.

@etcadinfinitum

etcadinfinitum/ctci_writeups.md

Last active January 27, 2020 18:38
Show Gist options
  • Save etcadinfinitum/c9cdeb817c9a33abb5683abc12e75b58 to your computer and use it in GitHub Desktop.
Save etcadinfinitum/c9cdeb817c9a33abb5683abc12e75b58 to your computer and use it in GitHub Desktop.
Download ZIP
A guide to writing up a CTCI problem for ACM's interview prep workshop.
Raw
ctci_writeups.md

Quality Writeups for ACM's CTCI Workshop

By the CTCI BDFL, Lizzy

Prologue

CTCI is one of ACM's most long-running events; it brings value to the CSS students at UWB as well as the club officers who facilitate it. Feel free to ask me about my experience leading the event and how it has brought me value.

In order to maintain the consistent quality that past leads have brought to the event, previous contributors have been following specific conventions in code and documentation of the problems we present in the workshop. This doc is meant to be a comprehensive guide on how it is currently done; feel free to refer to previous sessions in the repo (as well as closed pull requests) for more concrete examples.

Assumptions:

  1. You have a GitHub account
  2. You have been assigned a problem, or picked one yourself and cleared it with the event facilitator

Step 1: Write the Code for your Solution

You can begin by coding up a solution to the problem. You may use any programming language you like. For the purposes of the workshop, the coded solution should have the following traits:

  1. It is written in source files (.py, .cpp, etc)
  2. It is a correct solution
  3. At least two tests are provided with the solution
  4. And most importantly, the source files compile and can be executed

For example, let's say for the sake of illustration, I write a solution to the Fibonacci problem: Given an integer n, find the nth term of the Fibonacci sequence.

My solution would be in a source file called fib.py, and the file's contents are as follows:

def fib(n):
    if n < 2: return 0
    if n == 2: return 1
    return fib(n - 1) + fib(n - 2)

def main():
    print('Testing for Nth term of Fibonacci sequence.')
    ans = fib(0)
    print('N = 0: ', ans)
    assert(ans == 0)
    ans = fib(5)
    print('N = 5: ', ans)
    assert(ans == 3)

if __name__=='__main__':
    main()

Step 2: Update Your Local Copy of the Repository.

If you haven't cloned the repository to your machine, do so now.

git clone https://github.com/UWB-ACM/CTCI

If you have a local copy of the repo, run the following commands to pull new commits:

git checkout master
git pull origin master

Step 3: Add Your Coded Solution to the Repository

Navigate to the folder which corresponds to the session you are contributing to. For example, if I am adding this problem to the Trees session in Winter 2020, I would run the following command: cd 2020-01-Winter/4_trees.

Make a new folder for your coded solution. I will name my folder fibonacci. Now, my session's folder looks like this:

2020-01-Winter/4_trees/
├── fibonacci
└── README.md

Move your source file(s) into the folder you just created. Now, my session's folder looks like this:

2020-01-Winter/4_trees/
├── fibonacci
│   └── fib.py
└── README.md

Step 4: Write the problem description

In the session's folder, there is a file called README.md. This is the "report" that CTCI facilitators use to present the problems and solutions in a CTCI session. Your problem statement and solution explanation will live in this file.

In my Fibonacci example, I am working on Problem #1 for my session. In the README.md file, there is a section that looks like:

<a name="p1"/>

### 1. PROBLEM 1 TODO :bug:

Source: TODO :bug:

#### Scenario

Problem Statement TODO :bug:

#### Example Input

If the problem is simple enough, remove this section. TODO :bug:

#### Function Signature

TODO :bug:

<!-- Don't remove -->
Go to [Solution](#s1)   [Top](#top)

After finishing my writeup of the problem, it now looks like this:

<a name="p1"/>

### 1. Fibonacci

Source: [GeeksForGeeks](https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)

#### Scenario

Given an integer `n`, find the `n`th term of the Fibonacci sequence.

#### Example Input

If the sequence starts as `0, 1, 1, 2, 3, 5, 8, 13, 21`, I should get the following output:

```
Input: n = 1    Output: 0
Input: n = 4    Output: 2
Input: n = -1   Output: 0
```

#### Function Signature

C++:

```c++
int fibonacci(int n) {
    // your code here
}
```

Python:

```python
def fibonacci(n):
    # your code here
```

<!-- Don't remove -->
Go to [Solution](#s1)   [Top](#top)

Step 5. Write the Solution Section in the README

Just like writing up the problem statement in the readme file, there should be a solution section in the readme. It is templated for you.

The each solution you add will have the following elements:

  1. One or more short paragraphs explaining the approach to the problem and steps taken to write a solution.
  2. The solution method which solves the problem given.

Most problems only require one solution; sometimes, two different approaches are part of the problem statement (i.e. "Solve problem; solve problem without using additional data structures, modifying the input in-place").

In my Fibonacci example, only one working solution is needed, so I modify the headers of the readme file accordingly. The organization of the solution is relatively flexible; the priority should be to organize the given iterations of the problem statement.

The solution section of the readme looks like so at first:

<!-- Don't remove -->
<a name="s1"/>

### 1. SOLUTION 1 TODO :bug:

Source: TODO :bug:

#### Naive/Simple Solution

TODO :bug:

#### Optimal Solution

TODO :bug:

#### Testing The Solutions OR Driver For Solution

TODO :bug:

<!-- Don't remove -->
Go to [Top](#top)

Afterwards, my writeup reads as follows:

### 1. Fibonacci

Source: [GeeksForGeeks](https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)

#### Solution

We can calculate the `n`th term of the Fibonacci sequence by establishing 
the first two numbers in the sequence as base cases.

The first term is 0; the second term is 1. So, if n <= 1, we know the 
value should be 0. Likewise, if n == 2, we know the value is 1.

We establish a recursive call which takes the sum of the two previous 
terms in the sequence; the recursive implementation is as follows:

```python3
def fib(n):
    if n < 2: return 0
    if n == 2: return 1
    return fib(n - 1) + fib(n - 2)
```

#### Driver For Solution

The solution code is [in the repository](https://github.com/UWB-ACM/CTCI/2020-01-Winter/4_trees/fibonacci/fib.py).

It produces the following output:

```console
$ python3 fib.py
Testing for Nth term of Fibonacci sequence.
N = 0:  0
N = 5:  3
```

<!-- Don't remove -->
Go to [Top](#top)

Step 6: Commit Your Solution and Open a Pull Request

After completing the previous steps, my repository's state currently looks like:

:) lizzy@cranberries: ~/acm/ctci/2020-01-Winter/4_trees $ git status
On branch master
Your branch is up to date with 'origin/master'.

Changes not staged for commit:
  (use "git add <file>..." to update what will be committed)
  (use "git checkout -- <file>..." to discard changes in working directory)

	modified:   README.md

Untracked files:
  (use "git add <file>..." to include in what will be committed)

	fibonacci/

no changes added to commit (use "git add" and/or "git commit -a")

There are two points of note:

  1. I have uncommitted changes
  2. I am on the master branch

Unless you are a repository administrator, you will not have sufficient privileges to commit to the master branch. However, you will be able to create a new branch and open a pull request to have your changes merged.

To do this, pick a branch name. It should be something logical; for my example, I will use the branch name fibonacci.

Now, run the following commands:

$ git checkout -b fibonacci       # creates a new branch with the given name and switches to the new branch
$ git add --all                   # add files incrementally if you see fit
$ git commit                      # this will open a new editor so you can write a commit message
$ git push origin fibonacci       # move your new commit to the GitHub repository

After pushing your changes, you might see a message like this:

$ git push origin fibonacci
....
remote: Resolving deltas: 100% (3/3), completed with 3 local objects.
remote: 
remote: Create a pull request for 'fibonacci' on GitHub by visiting:
remote:      https://github.com/UWB-ACM/CTCI/pull/new/fibonacci
remote: 
To https://github.com/UWB-ACM/CTCI
 * [new branch]      fibonacci -> fibonacci

In this case, git gave us a hyperlink to open a new pull request. Whether or not you get this message, you should go to the web UI for GitHub to open a Pull Request for your new changes. Pull Requests give the workshop facilitators the following benefits:

  1. Giving you a second pair of eyes to validate your work and make suggestions via code reviews
  2. Getting the chance to read through the problem's solution before they have to present it to a room full of their peers
  3. Ensuring the content being delivered is complete and correct (to the best of your knowledge and theirs)

From here, you will likely have one of your peers leave feedback in the form of a code review. When everyone agrees that the problem is ready to be presented, you will receive an approving review on your PR and you can merge it into the master branch.

Epilogue

This guide is not meant to be a crash course in git usage; there are a ton of resources out there for git. If you want to learn, I'd start with the following resources:

This guide is not intended to be a crash course in Markdown, either. Check out some of these resources for extra ideas:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment