Implement an algorithm to print all valid
Our first thought here might be to apply a recursive approach where we build the solution for f(n) by adding pairs of parentheses to f (n-1). That’s certainly a good instinct. Let’s consider the solution for n = 3: (()()) ((())) ()(()) How might we build this from n = 2? (()) ()()…
Given an input file with four billion non-negative integers
FOLLOW UP: What if you have only 1 O MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers. There are a total of 232, or 4 billion, distinct integers possible and 231 non-negative integers. Therefore, we know the input file (assuming…
You have 20 bottles of pills
Sometimes, tricky constraints can be a clue. This is the case with the constraint that we can only use the scale once. Because we can only use the scale once, we know something interesting: we must weigh multiple pills at the same time. In fact, we know we must weigh pills from…
Write a function that adds two numbers
Our first instinct in problems like these should be that we’re going to have to work with bits. Why? Because when you take away the+ sign, what other choice do we have? Plus, that’s how computers do it! Our next thought should be to deeply understand how addition works. We can walk…
A magic index in an array A[1… n-1]
Immediately, the brute force solution should jump to mind and there’s no shame in mentioning it. We simply iterate through the array, looking for an element which matches this condition. int magicSlow(int[] array) { for (int i= 0; i < array.length; i++) { if (array[i] == i) { return i; } } return -1;…