algorithm

Apply a permutation to a vector

In this article we are going to discuss an interview question that is asked quite frequently in companies like Facebook, Microsoft, or Google. The problem statement goes as follows: Given an vector<T> A of elements of type T of length Nand a vector<size_t> P where Pis a permutation of numbers from [0-N-1]you need to apply the permutation Pto the vector A. You are not allowed to use more than O(1) additional space. For example suppose A=['a','b','c','d'] and P=['2','0','4','1']. After applying P to A, the latter becomes: ['c','a','d','b']. P[i] basically tell you which element of A should go in position i in the final arrangement of… Read More »Apply a permutation to a vector