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;…
Implement an algorithm to determine
You should first ask your interviewer if the string is an ASCII string or a Unicode string. Asking this question will show an eye for detail and a solid foundation in computer science. We’ll assume for simplicity the character set is ASCII. If this assumption is not valid, we would need to increase the…
There’s a staircase
Start simple. You’re standing on the landing and want to reach the first step, #1. There’s just one way to do it—take one step up. Now let N = 2. There are two ways to get to the second step. Either you take two single steps in succession or you take one double…
You have to get from point A to point B
You don’t know whether you can get there. What do you do? The MBA answer: “I would pull out my cell phone and enter point A and point B in Google Maps. If point B isn’t on Google Maps, I’d take a taxi and submit the receipt to accounting. Next question?” The computer…
Given a list of millions of words, design an algorithm
Many problems involving a dictionary can be solved by doing some pre-processing. Where can we do preprocessing? Well, if we’re going to create a rectangle of words, we know that each row must be the same length and each column must be the same length. So let’s group the words of the dictionary…