Since the Euler-Lagrange equation for an autonomous Lagrangian $L(q,\dot q)$ is $$ \frac{\partial L}{\partial q} - \frac{d}{dt}\left(\frac{\partial L}{\partial \dot q}\right) = L_q - \dot q L_{q\dot q} - \ddot q L_{\dot q\dot q}, $$ it follows that finding an autonomous Lagrangian for the ODE $\ddot q = f(q,\dot q)$ is equivalent to solving the second order linear PDE $$ L_q - \dot q L_{q\dot q} - f(q,\dot q) L_{\dot q\dot q} = 0 $$ for $L(q,\dot q)$. The Lagrangian is said to be nondegenerate if $L_{\dot q\dot q}$ is nonzero.
To keep the notation simple, write $\dot q = p$, so that the equation becomes $$ L_q - p L_{qp} - f(q,p) L_{pp} = 0.\tag1 $$ This is a hyperbolic linear PDE on the region in the domain of $f$ in the $qp$-plane where $p\not=0$, so local solutions in such a region will exist, even when one requires that $L_{pp}\not=0$. (Note that, given any two solutions $L$ and $L'$ for which, say $L_{pp}$ and $L'_{pp}$ are positive, then any positive linear combination of those solutions will also be a non-degenerate solution, so, at least away from the line $p=0$, there always exist (locally) many distinct nondegenerate Lagrangians for the equation $\ddot q = f(q,\dot q)$.) Whether or not there is a 'global' solution (especially a nondegenerate one), i.e., a solution in the entire domain of $f(p,q)$ in the $qp$-plane, depends on global properties of $f$ and its domain. It is not immediately clear whether, along the locus $p=0$, there will exist a $C^2$ solution $L$ for which $L_{pp}$ is nonzero.
It may be of interest to note that one can avoid having to solve a second order PDE to construct $L$. The usual process for solving the inverse problem by 'multipliers' reduces the problem to first solving a first order PDE and then computing a couple of line integrals. This goes as follows:
One interpretation of the critical curves curves of the Lagrangian $L$, written as $\dot q- p\,dt = \dot p - f(q,p)\,dt=0$$\mathrm{d} q- p\,dt = \mathrm{d}p - f(q,p)\,dt=0$ in the $tqp$-space is as the null curves of the closed $2$-form $$ \omega = (\mathrm{d}L_p - L_q\,\mathrm{d}t)\wedge (\mathrm{d}q - p\,\mathrm{d}t) = L_{pp}\,(\mathrm{d}p - f(q,p)\,\mathrm{d}t)\wedge (\mathrm{d}q - p\,\mathrm{d}t), $$ So regarding $f(q,p)$ as known, one seeks a nonzero function $g(q,p)$ such that the $2$-form $$ \omega = g(p,q)\,(\mathrm{d}p - f(q,p)\,\mathrm{d}t)\wedge (\mathrm{d}q - p\,\mathrm{d}t) $$ be closed. Now The equation $\mathrm{d}\omega=0$ is the first order linear PDE $$ p\,g_q + f(q,p)\,g_p + f_p(q,p)\,g = 0,\tag2 $$ which can be solved by the usual method of characteristics away from the points where $p = f(q,p) = 0$ (where the characteristics may not foliate). Taking a nonvanishing solution $g(q,p)$ of (2), use the closedness of the corresponding $\omega$ to write it as the exterior derivative of a $1$-form $$ \omega = \mathrm{d}\bigl(a(q,p)\,\mathrm{d}t + b(q,p)\,\mathrm{d}q\bigr). $$$$ \begin{aligned} \omega &= \bigl(f(p,q)g(p,q)\mathrm{d}q - pg(q,p)\,\mathrm{d}p\bigr)\wedge\mathrm{d}t + g(p,q)\,\mathrm{d}p\wedge{d}q \\ &= \mathrm{d}\bigl(a(q,p)\,\mathrm{d}t + b(q,p)\,\mathrm{d}q\bigr), \end{aligned} $$ (This can be done by the usual homotopy formula from Poincaré's Lemma, treatingwhere $t$ as a parameter)$b_p = g$ and $\mathrm{d}a = fg\mathrm{d}q - pg\,\mathrm{d}p$. Then $L(q,p) = a(q,p) + pb(q,p)$ is the desired nondegenerate Lagrangian, with $L_{pp} = g(q,p)\not=0$.
It's not always possible for (2) to have a nonvanishing solution $g$ in a neighborhood of the locus $p=0$, though. For example, if $f(q,p)=p$, then (2) becomes $p(g_q+g_p) + g=0$, so $g$ has to vanish along $p=0$. On the other hand, if, for example, $f(q,p) = p^2h(q,p)$ for some smooth $h$, one can divide equation (2) by $p$ to get the non-singular equation $$ g_q + ph(q,p)\,g_p + \bigl(2+ph_p(q,p)\bigr)\,g = 0,\tag2 $$$$ g_q + ph(q,p)\,g_p + \bigl(2h(q,p)+ph_p(q,p)\bigr)\,g = 0,\tag2 $$ which clearly has nonvanishing solutions $g$ near $p=0$.