Coding Interview Resources

🔰 Master the Coding Interview: Data Structures + Algorithms ⏱ 19.5 Hours 📦 258 Lessons Ultimate coding interview bootcamp. Get more job offers, negotiate a raise, and learn everything you need to get the job you want! Taught by: Andrei Neagoie Join @crackingthecodinginterview to learn with fun 👇👇

Solution: The first idea is to enumerate all permutations (either in lexicographical order, or sort them afterwards) and return the k-th one. But this is quite inefficient. Do we really need to generate permutations we don't care about? E.g. what if we need to return the last permutation of a string "abcd" do we need to generate permutations that start with "a"? Probably not, but can we compute what element the k-th permutation will start with? How many permutations will start with the smallest element in the array? The answer is (n-1)! Therefore, we can compute the first element of the permutation we need to compute. But wait, can we do the same for the second character? Yes we can! The number of permutations that start with the fixed first two characters are (n-2)!. So all we need to do is starting with the first character, compute what character will be on each position in the k-th permutation.