Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently constructible.
Recently, Bravyi et al proposed a quantum algorithm which essentially replaces the oracle in Bernstein-Vazirani with a grid-like 2D structure.
What are some other examples of non-oracular versions of famous oracular problems? Also, is it known that the oracles are always efficiently constructible for the famous cases I mentioned?