brokensandals.net -> Programming challenges

My solutions, with detailed explanations, for various programming challenges.

 Euler 1 I compare five solutions to a simple problem: summing multiples of 3 and 5. Euler 2 I explore Fibonacci numbers a little bit by comparing seven solutions to a simple problem. Array Manipulation A deceptively simple-sounding problem: perform a series of updates to an array, and report the highest value in the array at the end. The trick is doing this quickly for a large array or large number of updates. I explain a couple efficient solutions. Count Triplets You're asked to count the how many triplets can be formed with indices of an array such that their values are in geometric progression. I explain O(N3) and O(N) solutions. Hints are available. Matrix Layer Rotation This problem asks you to find the outcome of "rotating" a matrix in a specific way a given number of times, without going through each iteration. I explain the solution and discuss program structure in detail. Maximum Subarray Sum A challenging problem: given an array, find the subarray whose sum modulo a given number is highest. I explain the solution with illustrations. Hints are available. Sock Merchant and Ransom Note Two beginner problems focused on hashtables. I compare and contrast functional and imperative approaches for each, and also discuss a tradeoff between time and space efficiency. Hints are available. Special String Again A string problem in which you must count the number of substrings meeting certain criteria. I explain O(N3), O(N2), and O(N) solutions. Hints are available.