Topics: String manipulation
Difficulty: 1/10
Topics: String manipulation, Simple math
Difficulty: 1/10
Topics: 2D Array, Indexing
Difficulty: 2/10
My solution:
Part 1: Iterate through the grid to find numbers. If found, check around the number to see if there are any symbols. If so, add the number to the sum and return the sum at the end.
Part 2: Iterate through the grid to find numbers and check if there are any _ around it. Record the location of _ and the number. If the location of _ is already stored, then it means there was already a number associated with it. Multiply the stored number with the current number and add it to the sum. If the location of _ is not stored, then it means this is the first number we found around the _, store the location of _ and the current number.
Topics: 1D Array Algorithm, Sorting
Difficulty: 1/10 (part 1 naive solution), 2/10 (part 1 sorted list approach), 2/10 (part 2)
My solution and thoughts:
Part 1: This part can be simplified into the following problem: Find intersections between two arrays.
Naive approach: For each item in list A, iterate through list B to see if it exists in list B
Runtime: O(m * n)
Better approach: Sort lists A and B and search through them.
Runtime: Sorting: mlogm + nlogn. Find Intersection: O(m + n). Overall: O(mlogm) (assume m > n)
TODO: Is there a quicker solution? O(n)?
Part 2: This part is straightforward. Just store the number of cards in an array as you go and add up at the end. Messed up indexing on the first try so I will rate it as a 2/10.
Topics: Integer Overflow, Range Splitting
Difficulty: 4/10 (part 1) 7/10 (part 2)
Part 1: At first I implemented maps associated with the given inputs, and then realized the ranges are too large so the map would be incredibly large so not possible. Then, I just went through all the inputs checked if the current number is in the range and calculated the destination without creating maps. Then, I realized the numbers were too large so I switched int to long long.
The question itself is not hard but since I encountered two obstacles while solving it, so I rated this part as 4/10.
TODO: can write functions to calculate the destination for each part to make the code look nicer
Part 2: If we naively go through each seed in the range, the solution would run forever. Range splitting took me quite a while to debug so I gave it a 7/10.
Topics: String
Difficulty: 1/10
Topics: Custom Sorting, Logic
Difficulty: 4/10
There are some edge cases in part 2 that took me a while to debug.
Topics: Very Simple Graph Search (just left and right nodes)
Difficulty: 3/10
For part 2, brute force would result in a slow runtime. Need to do it smarter (calculate lcm).
Topics: Math
Difficulty: 2/10
Find a pattern to do it smarter.
Note that for polynomials of degree
Topics: Graph (DFS, cycle detection, cycle length calculation)
Difficulty: 8/10 (Part 1) 10/10 (Part 2) (I'm bad at graph)
For Part 1, use dfs to detect cycle and calculate the length of the cycle.
For Part 2, I tried to mark the boundary points and then use flood fill algorithm to mark all the reachable tiles from boundary as visited. Finally, all the non-visited tiles will be the ones inside the cycle. Not sure why this is not working.
Then, I searched up on reddit and found that you can use shoelace formula to calculate the area of the polygon and then use pick's theorem to calculate the number of integer coordinates lie inside the polygon. The implementation is easy but I've never heard of pick's theorem before so I will give it a 10/10.
Topics: Euclidean distance
Difficulty: 2/10
Thought it's a graph problem but not, shortest distance is just Euclidean distance