Finding a function f(n) which will bring T(n) runtime to O(log^4(n)) (Interview question)
I'm solving the case where $c=1$. Doing it for arbitrary $c$ is made in a similar fashion.

Let take $f(N) = 2^{2^{2^{\sqrt{\frac{\log^{[3]} N}{2}}}}}$.
so that for every integer $N$ we have :
$$T\left(2^{2^{2^N}}\right) = 2 T\left(f\left(2^{2^{2^N}}\right)\right)+1
= 2 T\left( 2^{2^{2^\sqrt{N/2}}} \right)+1.$$

I'm assuming in your question that you are only interested in functions $f$ that are increasing over $\mathbf{N}$.
Let prove that $T(N) = \Theta(\log^{[4]} N)$, that is proving that there exists two positive constants $A,B$ such that for sufficiently big $N$, $$ A\log N \leq T\left(2^{2^{2^{N}}}\right) \leq B\log N.$$

Let assume the last inequality holds up to some $\sqrt{N}&gt;1$, with constant $A=1$ and some  $B &gt; 1$.
Then 
$$f\left(2^{2^{2^N}}\right) = 2 T\left( 2^{2^{2^\sqrt{N-1}}} \right)+1,$$
and so by hypothesis: 
$$\log N = 2 \log\sqrt{N/2} +1 \leq  T\left(2^{2^{2^N}}\right) \leq 2 B\log\sqrt{N/2}+1 = B \log N +1-B \leq B\log N.$$

We can then conclude by induction, jumping by successive squaring, using the increasing property of $T$ to fill the gaps.