Posts

Showing posts from November, 2016

Do two strings differ by N or less characters?

Recently I saw a very nice interview question: given two strings, can you tell quickly whether they differ by no more than one character? The two-pointers approach works well for this question. However, when we expand the problem to ask "do two given strings differ by no more than N characters?" then it becomes problematic with the two-pointers approach. The problem is that for a case like this one: String 1: abc8 String 2: a123456bc7 N: 8 The answer is "yes", because you can remove all the numbers (8 numbers in total) and the two remaining strings will match. But if you're operating with pointers then when you get to the first mismatched element ('b' and '1') which pointers do you move? The first, second, or both? If you go this route recursively chances are you'll end up with an exponential solution. One way to solve this problem is using Dynamic Programming . The idea requires solving the problem for smaller strings and use that

Don't lose on Tic-Tac-Toe 99% of the time with this simple strategy!

The game of Tic-Tac-Toe  has been played billions of times and has been around for thousands of years. There is a well-defined strategy to win the game 100% of the time - it is there in the Wiki. But there is a simpler strategy that can guarantee you (or a computer) victory in 99% of the cases (well, victory + draws in 99% of the time). Without further due, here is the proposed algorithm: 1) If the computer can win in the next move, then: win! 2) If the human can win in the next move, then: computer blocks it! 3) If the center hasn't been played yet: computer plays the center! 4) If the diagonals are open: computer plays them randomly! 5) Computer keeps track of its last move: plays as far away as possible! As you can see, 1-2-3 are straightforward moves and super easy to implement. 4 is not as simple as there is a variant (see code for more info). The case number 5 is actually simple to implement: keep track of the last move played, and then try to play a move from the far