DeeKaying @ Nettle

So, I was lurking on the AlgoGeeks group when I came across this interesting question posted by Piyush from IIIT-Allahabad. Apparently, it came in a DE Shaw interview. The original question is: Given N heaps numbered sequentially from 1 to N that contain atleast 1 counter each, players move in turns to pick counters from the heaps. The rules of the game are such that counters can only be picked from the lowest numbered heap that is not empty. The question is: design an algorithm for optimal play that will determine which player will win given a configuration of heaps. Here's my answer: There are only 2 types of heaps in this problem: 1. Optional heaps -> have > 1 coins 2. Non-optional heaps -> have = 1 coins For optional heaps, optimal play dictates that you either pick all the elements from the heap or leave just one element in the heap when you play your turn. This is an obvious constraint because otherwise, you're putting your opponent in the driving seat with ...

This is a follow up post to my earlier post on printing all possible permutations of a string (also called Anagrams) using the C++ Standard Library. The earlier post is located here . This post should have come on this blog about 3 years ago. I'm no longer interested in solving problems like this but I wanted to put this up for the millions of people who get this problem in interviews and the like and to retain the same for posterity. So, previously we've discussed how to print all possible permutations of a string without duplicates using the standard C++ library functions. That's all fine and dandy if we want to use the standard libraries – especially next_permutation , but what happens if we have to write our own code to do so? In this blog post I'll present recursive solutions to the problem of printing all the possible permutations of a string. I'll even take up the case where the input string contains repeated letters later on in this post. The resul...

Update : This is part 1 of a 2 part series of posts that discuss generating all possible permutations/anagrams of a given string. This post discusses how to use the next_permutation function provided by the standard C++ library to generate the anagrams iteratively. The next post discusses a custom recursive implementation of how to achieve the same thing. See:  Recursively printing all permutations of a string containing duplicate characters. Have you ever thought of how to generate and display/print all possible permutations of a string (containing duplicate characters) such that every legal permutation appears atmost once in the final output, without taking a humungous amount of memory to keep track of all the permutations you have generated? This particular function utilizes a cool STL algorithm and generates all possible permutations of a string only once (whether the original string contained duplicates or not). int dup_permute(char *str, size_t length) {   ...