Flipkart Interview Question Software Analysts
Country: United States
Interview Type: In-Person
It must be something like this:
mul=1;
add=0;
swap=false;
swap_ptr=0;
for i from 0 to n-1
{
if (op==A) {add+=X;}
if (op==M) {mul*=Y; add*=Y;}
if (op==R) {
swap (array[i], array[n-1]);
swap=true;
array[i]=(array[i]*mul+add) mod Z;
swap_ptr=2;
continue;
}
if (swap==true)
if (i<n-swap_ptr)
swap (array[i], array[n-swap_ptr++]);
else {
swap==false;
}
array[i]=(array[i]*mul+add) mod Z;
}
@Ininiaa Why u set swap_ptr to 2 here?And how are you sure that on your first step the add and mult will not overflow as the caluclation can go upto 10^18.
If op==R, we swap ith and n-1th, next time we need to swap i+1th and (n-swap_ptr) which is n-2th.
@Ininiaa I am not saying about this.i am talking about if (op==A) {add+=X;}
if (op==M) {mul*=Y; add*=Y;}
Here there is no mod operation
What lenght sequence could be? First of all idea is that addition and multiplication are associative , also a * b == b * a. If you've got only A and M you could compute X * count A mod Z and Y ^ countM mod Z very fast. But R brokes it over. So you can do this fast computation of addition on multiplication between R operations. Example
AMMARAARMAMAAA
transorm to
first block R second block R third block
R destroys concurrency, you need to compute all blocks sequentially. But inside of them addition and multiplication are independent.
The key is to realize A and M operations can be delayed until you need to calculate the final result. For example, the operation sequence AAMAM (X=1,Y=2) is equal to a single step calculation to the original item a which is: a*4+10. So in the ith operation, you only have to calculate the ith element's final value and update the single step calculation according to the ith operation.
- lniniaa January 05, 2014And when the ith operation is R, what we should do is starting to swap the ith to nth elements one pair per operation (ith and nth, i+1th and n-1th) and apply the single step calculation to the new ith element and move on. If no new R, just keep swapping. When we encounter another R in position j. We should stop the previous swapping and begin a new one from jth to nth.