This folder contains information from the competitive coding class taught by Andrew Carr and Mitchell Probst during the BYU Fall 2017 semester. There is a Powerpoints directory that contains the slides shown to classmembers, which we did regularly at the beginning of the semester. However, as the problems became more unwieldly, we switched to working on the problems in class together.
There is also a folder called PythonFiles which contain a few specific functions written to help explain some of the Learn and Gos (this is the name used for each topic, Learn first together with us as a class, then Go and code it up yourself. Last, there is a BrainTeasers folder which contain the brain teasers we asked the students and corresponding solutions.
The class was setup with everything being run through Hackerrank using an e-mail account we created for this purpose:
Username: acme.coding.competition@gmail.com
Password: Ask your ACME professor.
If you are NOT part of the BYU ACME curriculum, but want access to the Hackerrank problems that were created by us, please feel free to send either one of us an e-mail at: mitchellprobst@gmail.com or andrewcarr06@gmail.com.
Future classes may choose to re-use the same Learn and Gos, because Hackerrank will allow you to modify start/end times of a contest, however we found no way to erase the leaderboard, so it will become critical to closely track each user and their performance on the Learn and Gos.
The class had several core components: Discussing Problem Solving Techniques, Learn and Gos, In-class Blitzes, Interviewing Skills, and Language Projects.
We opened the class by asking them to solve several common brain teasers that they might get in an interview class. Some of them are located in the BrainTeasers folder, several people may have seen these problems before, we did not make them up ourselves.
Following the brain teasers, we spent a day teaching the Problem Solving techniques found in Cracking the Coding Interview, a text by Gayle Laakmaan McDowell. The techniques are:
- Look for BUD (Bottlenecks, Unnecessary Work, Duplication)
- DIY (Do it Yourself, How would you solve it in real life?)
- Simplify and Generalize (Start With Extra Assumptions Initially, Then Adapt)
- Base Case and Build (Start Small and Build Up)
- Data Structure Brainstorm (Will The Right Structure Simplify The Problem?)
We had 10 Learn and Gos throughout the semester, each with its own theme, such as focusing on strings, trees, recursion, grids, ... Every Learn and Go has at least one tutorial problem that is meant to be solved together in class, then at least 3 other problems varying in difficulty to appease to both novice programmers and experienced ones. For grading purposes, we asked the students to complete at least one non-tutorial problem to receive full credit for a Learn and Go. Each problem is considered binary just like the Coding Competitions, you either solve a problem or you do not. No partial credit was given. The number of points they are given reflects how difficult we felt the problems were. Students needed 10 points for full credit (which equates to one non-tutorial problem).
Each problem built by us is available through an admin page on Hackerrank.
Learn and Go 0 - Python Essentials
This is a tutorial set meant to help students learn how to use Python, as we assume many juniors take this course and they are not expected to know much about Python. Each problem in this Learn and Go was built by us:
- Learn and Go 0-0: Lists (This problem introduces how to read input from hackerrank and using Python lists)
- Learn and Go 0-1: Simple Array Sum (This problem exists in Hackerrank but we re-created it removing the helper code)
- Learn and Go 0-2: Compare The Triplets (Also already exists but helper code removed)
- Learn and Go 0-3: Kangaroo (We changed the constraints of this Hackerrank problem to require a Mathematical Solution)
Learn and Go 1 - Data Structures
This Learn and Go contains numerous tutorial problems to ease students into competitive coding. Each problem can be solved very simply by just using the correct data structure.
- Migratory Birds
- DefaultDict Tutorial
- Collections.deque()
- Left Rotation
- No Idea!
- Learn and Go 1-2: Sets (This problem was taken from the Rocky Mountain Regional Contest in 2015)
- Components in a graph (Uses something called disjoint sets)
Learn and Go 2 - Parsing
This topic is still full of mostly simple problems, meant to ask students to begin learning how to make multiple pieces of information work together.
- Zipped! (Very important tutorial because NumPy isn't available in CC, Zipped! teaches you how to iterate over the columns of nested lists)
- Learn and Go 2-1: Vending Machine 2 (Taken from the 2017 Winter CC hosted at BYU from Pariveda, a great problem for simple maps).
- Counting Valleys
- Missing Numbers
Learn and Go 3 - Number Theory
This Learn and Go has several problems involving primes, or other mathematical topics that almost should be solved on paper before trying to code up solutions.
- Project Euler #3: Largest prime factor
- Project Euler #2: Even Fibonacci numbers
- Project Euler #16: Power digit sum
- Leonardo's Prime Factors (lots of students struggled on this one)
- Beautiful Days at the Movies
- Learn and Go 3-3: Mixed Bases (A problem asking students to write code to change from one base to another, including a base 1)
Learn and Go 4 - Strings
Python can do some neat things in String Manipulation, and strings show up often. We introduce students to some string problems.
- CamelCase
- Mars Exploration
- Super Reduced String
- Sherlock and the Valid String
- Learn and Go 4-3: 4th Grade (Problem taken from Pariveda's 2017 BYU Winter CC)*
* Although many coders warn about eval() in Python, it can be used to solve this problem in one-line.
Learn and Go 5 - Abstract
This section was reserved for some of the more abstract CS concepts that ACME students likely haven't been exposed to yet. Things like Bit manipulation or implementing grid searching.
Learn and Go 6 - Grids
Coding Competitions and other interviews often give problems for grids. Students saw an example that uses color and walks through what a grid challenge is doing. Talking about boundary checking, storing results, and possibly recursing through a grid were all mentioned.
- Grid Challenge
- Cavity Map (Andrew received this in an interview question)
- Connected Cells in a Grid
- The Grid Search
- Castle on the Grid
Learn and Go 7 - Recursion
We added this Learn and Go that wasn't originally planned because we felt that many students in our class weren't comfortable with recursion. We taught the difference between head recursion and tail recursion.
- Fancy Printing (A toy recursion problem Andrew built to show the class the difference between head and tail recursion)
- Tree: Height of a Binary Tree
- Fibonacci Modified
Learn and Go 8 - BFS/DFS
We saved searching until after ACME students had completed their lab on Breadth-first Search, hoping that we could reinforce principles that they learned in class. Most students struggled on this challenge and only a handful actually completed one of the problems listed here.
- Snakes and Ladders: The Quickest Way Up
- Breadth First Search: Shortest Reach
- PacMan - DFS
- PacMan - BFS
Learn and Go 9 - Dynamic Programming
Many people have a hard time wrapping their heads around Dynamic Programming conceptually. We felt that having a Learn and Go would help students understand its usefulness. Similar to LaG 8, most students did not complete any problem, despite the instruction we gave.
- The Longeset Common Subsequence
- Stock Maximize
- Bricks Game
- The Longest Increasing Subsequence
- The Maximum Subarray
- Knapsack
Throughout the semester we held numerous coding competitions to try and practice techniques taught in the Learn and Gos as well as to simulate the environment of the Coding Competition (No googling, only using standard docs as references, up to 3 working together but limited to a single computer). We had 7 blitzes throughout the semester. The problems are not necessarily in order form easy to hard, as we wanted the students to have to practice assessing the difficulty level of a problem. Hackerrank lets you hide the difficulty of the challenges.
Blitz0-2 - From LaG 0 to LaG 2
Contained several problems, most of which were incredibly simple, the hardest is Balanced Brackets, another common interview question.
Blitz3-5 - From LaG 3 to LaG 5
This blitz came after LaG 5, which included a grid problem in order to assess if the students had any previous exposure to grids, we intentionally put that problem first, along with the other hard problem second to try and trip students up who just try and go down the list one at a time.
- Cavity Map (From Learn and Go 6)
- Separate the Numbers
- Word Order
- "Holy" Numbers (Another trick problem, the problem never states that N is an integer, just that it is a number. So one test case has a decimal number like 13.46, if students cast it to an int, or round it, they get a run time error, or if they leave it as a string and check each "digit", they will attempt to check ".", which may result in a KeyError)
- Sum vs XOR
Blitz #3 - Pre-ACM Blitz
The ACM was pushed back a few weeks, so we ended up doing another blitz that was full of problems, lots of primarily simple ones.
- Summing the N series
- Equalize the Array
- Sock Merchant
- Special Multiple
- Project Euler #28: Number spiral diagonals
- Game of Thrones - I
- Athlete Sort
Blitz #4 - Pre-ACM Blitz
We held this blitz on the Thursday before the ACM. Once again loaded with problems in order to encourage the students to spend more time assessing problems and carefully choosing which ones to tackle first. Because of that, many of the challenges have simple solutions
- Ice Cream Parlor
- Two Strings
- Maximizing XOR
- The Time in Words
- Weighted Uniform Strings
- Encryption
- Missing Numbers
- Beautiful Triplets
- Minimum Distances
InterviewBlitz - Tackling Interview Questions
This blitz is primarily composed of problems from Cracking the Coding Interview, meant to show students how they can apply their competitive coding skills to interview settings.
- One Away CtCI (This problem is written in the CtCI book, but we made it a Hackerrank problem)
- Cycle Detection
- Is This a Binary Search Tree?
- Bob and Ben
BlitzHard - Actual ACM Problems
One of the items of feedback our students gave us post competition was that most of our competitions had "easy" problems, usually composed of one trick and being finished. The students asked for harder problems that reflected 'real ACM problems' during a blitz. Our choice of making them easier was primarily because our blitzes are only one hour long, but we decided to take the easiest problems from the 2017 ICPC and put them into a blitz.
- Need for Speed (solved using binary search)
- Posterize (solved using Dynamic Programming)
- Secret Chamber at Mount Rushmore (solved using BFS)
SpeedBlitz - Coding Quickly
On the last day of class we chose to implement a Speed Blitz. We included what we thought were 12 of the easiest problems from the entire semester, primarily the tutorial problems from our Learn and Gos, but a few other easy ones. We started at the top of the list and began each problem at the same time, and ranked how fast students were able to code solutions to these problems. We wanted to spend ~5 minutes on each problem in order to do many, but probably spent about ~7-8 on each instead, so we only got through 7 or 8 of them.
- Learn and Go 0-0: Lists (From LaG 0)
- Learn and Go 1-2: Sets (From LaG 1)
- Zipped! (From LaG 2)
- Project Euler #3: Largest prime factor (From LaG 3)
- CamelCase (From Blitz0-2 or LaG 4)
- Lonely Integer (From LaG 5)
- Learn and Go 2-1: Vending Machine 2 (See LaG 2)
- Left Rotation (From LaG 1)
- Counting Valleys (From LaG 2)
- Designer PDF Viewer (From Blitz0-2)
- "Holy" Numbers (From Blitz3-5)
- Sum vs XOR (From Blitz3-5)
We spent two days teaching students about interview skills as suggested from Cracking the Coding Interview. One of the best insights can be found in the powerpoint for that day, creating a matrix for answers to common interview questions related to work you have done. We also spent two class days letting students practice technical interviews with us:
- N time n space array
- Delete a node in a singly-linked list
- incrementing a number where each digit is stored in a list eg. 4753 = [4, 7, 5, 3]
- Determine if a number is a Power of 10
- Find if a cycle exists in a singly linked list
- Taking the union of two lists
Many students in ACME have little to no experience coding, probably did not enjoy CS 142, but now can code well in Python. We wanted to introduce them to some of the more popular languages they may see, and just introduce them to the concept of applying techniques they learned in competitive coding to other languages. For the class we taught them four different languages. Each language was supposed to have a day of instruction, and a full day of students working, but due to the fact this year's ACM Coding Competition happened on November 4th, we lost several class days. Instead we gave them 25-30 minutes of instruction and then let them work on their own. The languages covered was JavaScript, C++, Clojure, and R.
For most language projects we expected them to solve easy challenges that they had already seen at the beginning of the semester.
For R, we gave them a chance to play around with the datasets and showed them how to plot data and quickly return the moments of the data.
- ICPC Previous Problems
- Cracking the Coding Interview
- 2016 Rocky Mountain Regional ACM Contest
- Lucid's 2016 Fall Coding Competition
- Lucid's Repository for 2016 Fall Competition
- Lucid's 2017 Fall Coding Competition
- Lucid's Repository for 2017 Fall Competition
- Pariveda's 2017 Winter Coding Competition
* None of these links in this readme are maintained by us, and as such are subject to being broken in the future.