Interesting. I'd find the permutations one trickier, and yes I've encountered permutations in math and have been a programmer a long time). Here's why I'd find it tricky.
There is an obvious recursive algorithm, but I'd be worried that if I gave that the interviewer would quibble about stack usage (although it is going to be linear in the number of items being permuted which should be OK most of the time).
Thinking a bit more, I can see that it should be possible to do an iterative algorithm that needs little or no state other than the last permutation generated and that given a sorted input string would generate the permutations in lexicographic order. The basic idea is that if you partition the string into two parts, AB, such that no permutation of B exists that is lexicographically after B, then the next permutation of AB is formed by replacing B with the lexicographically first permutation of B, and then exchanging the last character of A with the first character of the new B. (I think that will generate them all, in order--but I've not seriously analyzed it--I'm just riffing off the top of my head as I type here, like I'd be doing in an interview).
OK, now I'd worry about that step of replacing B with the lexicographically first permutation of B. That can be done by sorting B, but then the interviewer might complain about all that sorting. Aha! The lexicographically last permutation of B and the first permutation or reverses of each other, and reversal can be done in O(n). (And maybe it can be done even faster with some kind of doubly linked list to store strings as list of elements, where a string is represented by a pointer into the list, a length, and a direction flag...something to think about).
Anyway, the permutation question is fraught with potential pitfalls. I'd be smart enough, I hope, to do all the above musings out loud to give the interview a chance to jump in and tell me "It's OK...I just want to see if you can write code, so go ahead with the recursive solution".
That second problem is straightforward. It's just binary search. The rotated array doesn't change anything fundamental about it--it just slightly complicates the check to see which half the target element must lie in. There will always be at least one "normal" half--that is, a half where all the elements are sorted. You can recognize a normal half be the left endpoint being less than the right endpoint. You check for the target in a normal half the usual way. If the target is not in the normal half you check, it must be in the other half (or not in the array at all).