• Jan 4, 2020

  • Practice problems.
  1. https://www.hackerrank.com/challenges/ctci-bubble-sort/problem. Just implement a bubble sort. One loop through n-1, check if bigger than next, swap if so. Then simply wrap the whole thing in a blind loop to run n times, which guarantees it’ll be sorted when finished.
  2. https://www.hackerrank.com/challenges/mark-and-toys/problem. Basic sort.
  3. https://www.hackerrank.com/challenges/ctci-comparator-sorting/problem. Write a comparator method of a class. Pass two objects, do whatever logic, then return -1 if obj1 goes before obj2 or 1 if opposite. Then you can pass the Class.comparator function as a key to a sort call, or whatever.
  4. https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem. Tougher, but I really enjoyed this one. Success rate was low, in the 30s. Sliding window for median, remember you can access it by index (middle if n odd, (middle + middle-1) if n even). To remove/insert in the sliding window, use the bisect module for speed.
  5. https://www.hackerrank.com/challenges/ctci-merge-sort/problem. Brainstormed this one for about 30m and then chose not to implement. The question is basically “write you own merge sort”. O(nlogn). This allows you to count the inversions. No thanks.
  6. https://www.hackerrank.com/challenges/ctci-making-anagrams/problem. Simple. My solution was cool.
  7. https://www.hackerrank.com/challenges/alternating-characters/problem. The easy ones are easy.
  8. https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem. Little more complicated, but in syntax. Nothing algorithmically special here.
  9. https://www.hackerrank.com/challenges/special-palindrome-again/problem. Tired of palindromes. I don’t like these problems.
  10. https://www.hackerrank.com/challenges/common-child/problem. Didn’t care to do this one either. Don’t like longest common subsequence problems. Remember the table of 1s and 0s, slowly sum as you move down and right.
  11. https://www.hackerrank.com/challenges/minimum-absolute-difference-in-an-array/problem. Nice change of pace. GREEDY algorithms. If you find yourself facing a quadratic solution, just sort! See if that helps.
  12. https://www.hackerrank.com/challenges/luck-balance/problem. Simple.
  13. https://www.hackerrank.com/challenges/greedy-florist/problem. Solved, but dumb question. It’s worded very ambiguously, and I had to modify the footer because the main function was completely missing a required argument (first time I’ve seen this on hackerrank).
  14. https://www.hackerrank.com/challenges/angry-children/problem. Easy. Fast. Don’t forget outside of this section; consider a sort!
  15. https://www.hackerrank.com/challenges/reverse-shuffle-merge/problem. Not gonna touch this one. Not worth my time, since it’s limited. Trying to understand the problem description alone took 10 minutes.
  16. https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem. Find a pair within 1d array, so iterate through it once, build a complement map.
  17. https://www.hackerrank.com/challenges/swap-nodes-algo/problem. Didn’t do. This question takes 30 minutes to read.
  18. https://www.hackerrank.com/challenges/triple-sum/problem. One you have to think about, doesn’t fit a standard pattern. Solve an easy case and you’ll see you’re best off approaching along a specific dimension (q).
  19. https://www.hackerrank.com/challenges/minimum-time-required/problem. An interesting one as well. Basically implement your own binary search. Find best and worst case for lower and upper bounds, bisect them, calc the result, then shift one bound depending upon what the produced value is. Put this all in a loop `while lower_bound < upper_bound`.
  20. https://www.hackerrank.com/challenges/maximum-subarray-sum/problem. <30% solve rate. Took a stab at it. Started with ~30m of whiteboarding. Reached the conclusion that the module of the sum is the modulo of (the sum of the modulos of the individuals). This is the key piece.
  21. https://www.hackerrank.com/challenges/making-candies/problem. Not really a search problem, just walk through the simulation. My solution was the right complexity (passed 35/49 tests), just needed smaller optimizations here and there.
  22. https://www.hackerrank.com/challenges/flipping-bits/problem. “Flipping bits” is just subtracting from the max size. So if you flip bits on a 32bit unsigned integer x, the result is 2^32-1-x.
  23. https://www.hackerrank.com/challenges/ctci-big-o/problem. Check if a number is prime. To do so, iterate only over odd numbers (because even divides by 2), and only up to square root of x. Every pair of factors, if it exists, has one number below the sqrt and one above, so you only need to check up to the integer at floor(sqrt(x)).
  • Only 30 problems left. The average difficulty is a little on the easier side, too. The hardest is like 40% pass rate. I’ll try to do most tomorrow so that I can focus on the open-ended questions monday. Behavioral, design, etc.
  • To switch two items in an array in python in one operation, just do:
  • list[index1], list[index2] = list[index2], list[index1]
  • Instead of doing quotient = math.floor(num/den) and rem = num % den, get both with quotient, rem = divmod(num, den).
  • Oh shit. You can also get the quotient directly with // in py3. 11 // 2 results in 5. Don’t need math.floor everywhere.
  • If n is given for a problem to be 10^9, you probably need a linear solution. If 10^5, try to find an nlogn algorithm. If 10^4, quadratic is ok.
  • Red-black trees are colored to preserve balance.
  • Push, meditate.
  • Ordered more preferred stock.
  • AFC playoffs. Texans and Titans moving on.
  • Supercontest. Disabled the emailer during the offseason.
  • The machine was out of disk space, so I sshed in and ran docker system prune -af to free up 17.89GB. Remember to create the network and restart the nginx-proxy containers as well after this operation.