Module Project - Algorithms

Sprint: Algorithms

Modules: A First-Pass Solution and Writing Better Solutions

Note: this module project repository is for Module 3 (A First-Pass Solution) and Module 4 (Writing Better Solutions) of the Algorithms Sprint.

Objectives for A First-Pass Solution

• Effectively ask for help by giving the expected vs. experienced behavior, explaining what specific actions they've taken so far, and providing all relevant information and code
• Interpret a problem, specification, or diagram and construct a plan for implementing a solution in code
• Implement a first-pass solution after selecting from a naïve, brute-force, or greedy approach

Objectives for Writing Better Solutions

• Evaluate a first-pass solution and reflect on its validity to decide if the solution needs revision
• Apply techniques such as memoization or heuristics to improve an existing first-pass solution

Introduction

This module project requires you to practice each of the learning objectives by synthesizing them to solve the included challenges. For Module 3, you will complete a first-pass solution for each of the problems. Then, in Module 4, you will improve your previous solution by applying the techniques you learned during pre-instruction and the Guided Project.

These types of algorithmic challenges simulate many of the problems that you might receive during a job interview. They require you to practice using all of your data structures knowledge, problem-solving capabilities, and algorithmic practice that you've done thus far. The more practice you get at applying these skills, the more likely you are to do well under pressure in a job interview setting. Additionally, this practice deepens your understanding through application.

Instructions and/or Completion Requirements

A First-Pass Solution

Each directory contains a separate problem that you must solve. Inside each directory, you'll find instructions for that problem, a test file, and an empty skeleton file.

There isn't an official prescribed order for tackling the problems, though a subjective ranking of the given problems from easiest to hardest might go something like this:

1. single_number
2. moving_zeroes
3. product_of_all_other_numbers
4. sliding_window_max
5. eating_cookies

For each problem, cd into the directory, read the instructions for the challenge, implement your solution in the skeleton file, then test it using the provided test file.

The later problems get progressively more difficult, especially when it comes to deriving a more performant solution. Don't feel bad if you aren't able to figure them out within the project's timeframe. Again, always remember that so long as you put in an earnest effort into attempting to solve these problems, you're learning and getting better. Getting the 'right answer' is just the proverbial cherry on top of the sundae.

Note: Remember, you need to get a first-pass solution for each of the problems for the Module 3 Project. For the Module 4 Project, you will work on improving those solutions and optimizing them for performance.

Writing Better Solutions

For the Module 4 project, your main objective is to work on improving at least two of your first-pass solutions from Module 3. In particular, for one of your first-pass solutions, assess the runtime and space complexity of the implementation, think about why it's inefficient and how it could be improved, then implement the improved solution.

Resources

When you confront a problem you haven't encountered before, the general strategy (adapted from George Pólya's Problem Solving Principles) is as follows:

UPER

Stretch goals

You will follow the same process as above for each of these stretch problems. Make sure you complete the requirements for this module project, before moving on to the stretch problems.

1. rock_paper_scissors
2. making_change
3. knapsack

Tests

Each problem folder contains a test file. Getting all of those tests to pass is how you know that you adequately completed the problem.

Make sure you run and pass the tests for each problem before moving on to the next challenge.