Topcoder and Leetcode Problems for Review and Practice

James S. Plank, University of Tennessee

The purpose of this web site is to have a bunch of Topcoder (and Leetcode) problems for CS140 and CS302 students to go through on their own for practice. In these files, I will give various hints and perhaps solutions to the problems.

Please email me if you see typos and/or problems with any of these writeups.

Finding the problems on Topcoder

You'll need to create an account at topcoder.com. Then, go to https://arena.topcoder.com and click on the icon on the top of the page that says "practice problems" (you have to point the mouse to the icon to see the text). That will take you to a page with a search bar, and you search for the problem name. The links in the in the writeups have gotten to the point where they work only sporadically, so before you give up, go to this link and search for the problem.

Doing these without Topcoder/Leetcode's Servers

As time has gone on, I'm afraid that Topcoder's servers have become unreliable. I haven't had that problem with Leetcode yet, but you never know. For that reason, I am going through these writeups, and making sure that you can do the problems without having to rely on Topcoder/Leetcode's servers working.

The problem "Cryptography" (SRM 480, D2, 250-Pointer) has a writeup on how to do the problem without Topcoder's servers, and how to test yourself. Please do that problem first, when you're starting to practice with these problems. That will help you form a workflow that works effectively when Topcoder/Leetcode's servers are down.

When I finish writing up a problem and providing testing information so that you can do it without the servers, I will color the problem's listing below in red.

Leetcode

Leetcode is another one of these programming web sites, like Topcoder, that has been a popular tool for job interviewers. I'll sprinkle in some Leetcode problems below as well.

D2 250-point Practice Problems

When students ask me what they can do to prepare for CS302 (and even CS140), my response is always, "Topcoder." The 250-point problems from Division 2 are great in this regard, because they typically require small (10-line) solutions, and are straightfoward. Your goal with these problems should be to get them within 20 minutes or so. When you get better at coding quickly, make that goal 5 minutes!

With these web pages, what you should do is the following:

Go to topcoder and attempt the problem without reading my help. If you get it, great! Go on to the next.
If you are having trouble, especially if you are having trouble getting started or crafting a solution, then click on the web link and read the help/hints. Then go back and try it again.
If this is a problem that I don't assign for labs, I'll try to include a commented solution. That way, you can compare your code to the code of a seasoned veteran, and that may help you learn!

I'm going to order these problems from easiest to hardest, using the success rates from Topcoder as the metric. The S/N designations are whether or not I provide a solution.

94.7% - N - SRM 609, D2, 250-Pointer (MagicalStringDiv2). Strings.
94.0% - N - SRM 605, D2, 250-Pointer (AlienAndPassword). Strings.
93.7% - S - SRM 608, D2, 250-Pointer (OneDimensionalRobotEasy). Simulate a robot with a for loop and three if statements.
93.2% - N - SRM 714, D2, 250-Pointer (RangeEncoding). One for loop.
92.3% - N - SRM 719, D2, 250-Pointer (LongLiveZhangzj). Inserting strings into a set, and then finding them.
92.2% - S - SRM 616, D2, 250-Pointer (WakingUpEasy). Successively run through a vector, subtracting from a value, until it is ≤ 0.
91.9% - N - SRM 480, D2, 250-Pointer (Cryptography). Sort and use long long's.
91.7% - S - SRM 702, D2, 250-Pointer (TestTaking). Some subtraction and some tertiary expressions.
89.2% - N - SRM 603, D2, 250-Pointer (MiddleCode) - Strings, and evaluating two solutions to a simple problem.
89.2% - N - SRM 734, D2, 250-Pointer (TheRoundCityDiv2). Do a brain-dead nested for loop and count.
88.4% - N - SRM 603, D7, 250-Pointer (BoundingBox) - Graph some points to figure out the answer.
88.1% - N - SRM 564, D2, 250-Pointer (FauxPalindromes). Practice with strings.
87.1% - S - SRM 698, D2, 250-Pointer (Initials). A three-line practice problem with strings.
86.6% - N - SRM 708, D2, 250-Pointer (SafeBetting). Simple simulation..
86.2% - S - SRM 695, D2, 250-Pointer (BearNSWE). Maintaining the Bear's (x,y) coordinate, and then using the distance formula.
85.8% - S - SRM 697, D2, 250-Pointer (TriangleMaking). Reasoning about a triangle, and using sorting to make your life easier.
85.6% - N - SRM 704, D2, 250-Pointer (SwapAndArithmetic). Sort and traverse.
85.5% - S - SRM 673, D2, 250-Pointer (BearSong). Create a map and traverse it.
83.2% - N - SRM 666, D2, 222-Pointer (DevuAndGame). Simulate a really easy game.
82.4% - N - SRM 722, D2, 250-Pointer (HillClimber). Run through a vector and keep track of stuff.
80.0% - S - SRM 705, D2, 250-Pointer (SuperUserDo). Simulate and count.
79.0% - S - TCO 2016, Q1A, 250-Pointer (EllysTimeMachine). Sscanf() and sprintf().
77.9% - N - SRM 707, D2, 250-Pointer (Cross). Processing a vector of strings.
77.7% - N - SRM 706, D2, 250-Pointer (ThreeIncreasing). Thinking about a problem in the correct order.
73.9% - N - SRM 700, D2, 250-Pointer (Xylophone). Mod.
72.0% - S - SRM 686, D2, 250-Pointer (TreeAndVertex). Count edges coming out of nodes of a tree.
71.0% - S - SRM 688, D2, 250-Pointer (ParenthesesDiv2Easy). Run through a string and maintain a counter.
70.9% - N - TCO 2017, Q1A, 250-Pointer (PingPongQueue). Simulate a simple system.
70.1% - N - SRM 736, D2, 250-Pointer (A0Paper). Run through a vector backward.
69.8% - S - SRM 691, D2, 300-Pointer (Plusonegame). Counting digits and building a return string.
69.8% - N - SRM 499, D2, 250-Pointer (SimpleGuess). Using a set and a simple enumeration of (X,Y) pairs.
68.7% - N - SRM 701, D2, 250-Pointer (SquareFreeString). Simple enumeration and substrings.
68.4% - N - SRM 604, D2, 250-Pointer (FoxAndWord). Simple enumeration and .substr().
68.4% - N - SRM 718, D2, 250-Pointer (RelativeHeights). Maps, sets and some string processing.
66.7% - N - SRM 730, D2, 250-Pointer (IntervalIntersections). Determine if two intervals intersect.
66.1% - S - SRM 699, D2, 250-Pointer (UpDownHiking). Keep track of two values per day for N days.
65.8% - N - SRM 689, D2, 250-Pointer (SimilarUserDetection). Strings and sets.
64.3% - N - SRM 587, D2, 250-Pointer (InsertZ). Strings and problem solving.
63.0% - S - SRM 741, D2, 250-Pointer (DigitStringDiv2). Enumerating substrings and converting them to integers.
62.4% - S - SRM 696, D2, 250-Pointer (Ropestring). Counting rope lengths, and then using them to create a return string.
60.4% - N - SRM 720, D2, 250-Pointer (DistinctGridEasy). Using a set to count distinct elements.
60.2% - S - TCO 2017, Q1B, 250-Pointer (WaterAndOxygen). Algebra.
59.3% - N - SRM 643, D2, 250-Pointer (TheKingsArmyDiv2). Using the find() method for strings, and running though the characters in a vector of strings.
57.9% - N - SRM 350, D2, 250-Pointer (DistanceBetweenStrings). Strings.
57.2% - N - SRM 739, D2, 250-Pointer (HungryCowsEasy). Using lower_bound() on a map.
57.0% - S - SRM 597, D2, 250-Pointer (LittleElephantAndDouble). Multiple ways to do a problem.
52.3% - S - SRM 679, D2, 250-Pointer (ListeningSongs). Break the problem into parts, and use sort() to help you.
52.0% - S - SRM 663, D2, 250-Pointer (ChessFloor). Enumerate two letters and run through a two-dimensional vector.
49.1% - S - SRM 729, D2, 250-Pointer (BrokenChessboard). Two for loops and a mod.
48.4% - S - SRM 717, D2, 250-Pointer (NiceTable). You'll be tempted to try to be smart, but instead, look at the constraints and do two power set enumerations.
47.4% - S - SRM 693, D2, 250-Pointer (TriangleEasy). This is a simple O(n³) enumeration, but you have to use the right O(n³) enumeration.
46.3% - N - SRM 623, D2, 250-Pointer (CatchTheBeatEasy). Create a multimap and traverse it.
44.6% - S - SRM 183, D2, 350-Pointer (CountGame). You'll want to think of game strategy, but if you simply use dynamic programming, you'll get the answer quickly!
44.0% - N - SRM 583, D2, 250-Pointer (SwappingDigits). A simple solution works, but you can make it much faster if you think it through a little more.
43.9% - N - SRM 606, D2, 250-Pointer (EllysSubstringSorter). Gives you practice with the substr() method, and sort().
39.8% - S - SRM 709, D2, 250-Pointer (RoboFactory). Thinking precisely.
34.2% - N - Leetcode problem 134 - Gas Station. Using graphics to think through a problem.

D1 250-point Problems (or D2 500-point Problems)

These are harder than the problems above, and often fit into some class of algorithm from CS140 or CS302. The percentages for the D2, 500-pointers are much lower than the D1, 250 pointers for two reasons: First, the programmers in D1 are better. Second, by the time the D2 programmers get to the 500-point problem, they may not have time to complete it. Keep that in mind.

77.2% - N - SRM 736, D1, 250-Pointer (DigitRotation). Strings and math.
77.2% - N - SRM 722, D1, 250-Pointer (TCPhoneHome). String/Number manipulation and maps.
74.2% - N - SRM 619, D1, 250-Pointer (SplitStoneGame). A straightforward dynamic program.
73.3% - N - SRM 590, D1, 250-Pointer (FoxAndChess). Vectors and Strings.
72.6% - N - SRM 728, D1, 250-Pointer (Halving). Maps, recursion.
70.2% - N - SRM 468, D1, 250-Pointer (T9). Create a map, whose vals are vectors of strings. Parse a string and create a return value.
70.0% - N - SRM 685, D1, 250-Pointer (MultiplicationTable2). A couple sets and a vector.
68.2% - N - SRM 737, D1, 250-Pointer (AliceAndBobEasy). Either you know the Sprague-Grundy theorem or you don't. Once you do, then this is a nice practice problem with bit arithmetic.
65.9% - S - SRM 612, D1, 250-Pointer (EmoticonsDiv1). I solve this as a classic Breadth-First Search, where you create the graph as you process the BFS queue.
63.1% - S - TCO 2017, Q1A, 500-Pointer (CheeseSlicing). Dynamic programming.
62.9% - S - SRM 702, D1, 300-Pointer (GridSortMax). A greedy algorithm on vectors.
59.8% - N - SRM 739, D1, 250-Pointer (ForumPostEasy). Simple enumeration.
59.5% - N - SRM 596, D2, 500-Pointer (ColorfulRoad). Good practice for Dijkstra's Algorithm, Dynamic Programming or Toplogical Sort.
57.0% - N - TCO 2016 Round 1A, 500-Pointer (EllysSocks). Straightforward Dynamic Program.
54.7% - S - SRM 727, D1, 250-Pointer (OnlySanta). Logic.
53.5% - N - SRM 183, D2, 550-Pointer (BridgeSort). Simple sorting.
53.5% - S - SRM 686, D1, 250-Pointer (BracketSequenceDiv1). Dynamic programming, plain and simple.
52.7% - N - SRM 731, D1, 250-Pointer (TreesAndBrackets). Recursion on a tree -- Dr. Plank takes a blow to his self-esteem.
51.9% - S - TCO 2015 Round 1A, 250-pointer (Similars). Gives you good practice using bits as sets.
50.7% - N - SRM 730, D1, 250-Pointer (StonesOnATree). Postorder tree traversal, plus some thought.
50.5% - N - SRM 733, D1, 250-Pointer (MinimizeAbsoluteDifferenceDiv1). Using next_permutation() and avoiding a pitfall.
49.7% - N - SRM 706, D2, 500-Pointer (SellingFruits). Avoiding pitfalls.
49.6% - S - SRM 700, D1, 300-Pointer (FindingFriend). Running through a vector and maintaining the correct information to solve the problem.
49.4% - N - SRM 741, D1, 250-Pointer (DigitStringDiv1). Dynamic programming.
48.5% - S - SRM 614, D1, 250-Pointer (MinimumSquare). I go over this problem in my CS494 class. These are the lecture notes. It's one of those problems that I beat to death. Sorry.
47.8% - N - SRM 740, D1, 250-Pointer (RainForecast). Probability -- easy programming.
47.0% - S - SRM 708, D2, 500-Pointer (BuildingStrings). Iteratively solving a problem with strings.
46.1% - N - SRM 671, D1, 250-Pointer (BearCries). Dynamic programming.
44.7% - N - SRM 734, D1, 250-Pointer (TheRoundCityDiv1). Prime factoring, power set enumeration, thinking.
43.0% - S - SRM 604, D2, 500-Pointer (PowerOfThreeEasy). I solve this using a power set enumeration, and teach this in CS302.
41.6% - S - SRM 699, D1, 250-Pointer (OthersXor). Nice problem to practice bits and thinking about XOR's.
39.9% - S - SRM 714, D2, 500-Pointer (RemovingParenthesis). A straightforward dynamic programming counting problem.
39.3% - N - SRM 701, D1, 250-Pointer (PartisanGame). Dynamic Programming.
38.5% - N - SRM 738, D1, 250-Pointer (FindThePerfectTriangle). Enumeration, plus some reasoning about triangles.
37.2% - S - SRM 641, D1, 250-Pointer (TrianglesContainOrigin). Geometry and Maps. I walk through the solution in my CS494 class and include the presentation here.
36.8% - S - SRM 721, D1, 250-Pointer (RememberWords). A little logic; a little math; a binary search instead of algebra.
34.7% - S - SRM 682, D2, 550-Pointer (TopBiologist). A Div/Mod enumeration.
32.8% - S - SRM 699, D2, 500-Pointer (LastDigit). Dynamic programming with big integers.
32.5% - S - SRM 695, D1, 300-Pointer (BearPasswordLexic). Turn a vector into a map, and a map into a string.
30.0% - S - SRM 705, D2, 500-Pointer (AlphabetOrderDiv2). DFS on a directed graph.
28.9% - N - SRM 347, D1, 250-Pointer (Aircraft). Either use calculus, or a really neat binary search.
25.0% - S - SRM 686, D2, 500-Pointer (SegmentsAndPoints). This is not a hard problem. I suspect the low scores were due to time constraints from the 250-point problem.
22.0% - N - SRM 691, D1, 300-Pointer (Sunnygraphs). The coding here is not bad -- a simple DFS that does not even have to be recursive. The hard part is turning that into a solution. This is a nice problem to make you think precisely about graphs.
20.0% - S - SRM 344, D2, 500-Pointer (SimpleRotationDecoder). A Div/Mod enumeration plus string manipulation.
19.9% - S - SRM 700, D2, 500-Pointer (XMarksTheSpot). Power set enumeration.
16.9% - S - SRM 707, D2, 500-Pointer (StepsConstruct). Breadth First Search.

D1 500-point Problems (or D2 1000-point Problems)

For these, I rank them by (number correct / number opened), but I also report (number correct / number submitted). It's hard to gauge these, again, because it's hard to know how much time a competitor had when he/she opened the problem. There is also the issue that with some of these programs, programming up the solution is really easy once you've figured out the solution, so the second numbers will be pretty high, even though the problem is hard.

50.3% / 60.9% - N - SRM 740, D1, 500-Pointer (DieDesign). Dynamic programming.
47.4% / 93.2% - N - SRM 699, D1, 500-Pointer (FromToDivisible). This is a BFS problem where you have to convert their graph to a tractable one using GCD().
29.8% / 80.9% - N - SRM 720, D1, 500-Pointer (Subgraphs). Thinking recursively about graphs.
26.8% / 87.2% - N - SRM 647, D1, 500-Pointer (CtuRobots). Dynamic Programming.
24.9% / 48.0% - N - SRM 383, D1, 500-Pointer (Floorboards). Enumeration.
19.1% / 21.5% - N - SRM 729, D1, 450-Pointer (FrogSquare). BFS where you need to only consider a subset of the graph to make it tractible.
14.6% / 25.3% - N - SRM 727, D1, 600-Pointer (GroupTheNumbers). Some reasoning, and writing some large-number arithmetic.
10.4% / 64.6% - N - SRM 621, D1, 500-Pointer (TreesAnalysis). Topological sort.
13.1% / 43.4% - N - SRM 734, D1, 400-Pointer (CardCounter). Dynamic programming.
12.0% / 61.4% - N - SRM 470, D2, 1000-Pointer (ActivateGame). Minimum spanning tree.
11.3% / 62.9% - N - SRM 713, D1, 500-Pointer (DFSCount). DFS, Dynamic programming and bit arithmetic.
7.1% / 52.5% - N - SRM 652, D1, 500-Pointer (MaliciousPath). Fun with Dijkstra's algorithm.
6.8% / 44.7% - S - SRM 348, D2, 1000-Pointer (IncreasingSubsequences). I use this as an example when I teach Topological Sort in CS302.
5.9% / 61.1% - S - SRM 702, D2, 1000-Pointer (SubsetSumExtreme). Dynamic programming with bit arithmetic. How can it get any better than that?
4.1% / 26.3% - S - TCO 2007, Q1, 1000-Pointer (Alarmed). Converting a problem to a graph, and then doing DFS on it.
3.3 / 33.9% - N - TCO 2017, Q1A, 1000-Pointer (PolygonRotation). This is a problem that makes you reason about geometry. My solution relied on line intersection, plus maps. There's nothing here that a CS302 student cannot solve -- you just have to work through it step by step.
0.35 / 20.0% - N - SRM 594, D2, 1000-Pointer (FoxAndGo2). DFS (plus a little thinking)