In scientific computing, the problem of finding an analytical representation of a given function (Formual Presented) is ubiquitous. The most practically relevant representations are polynomial interpolation and Fourier series. In this article, we address both problems in high-dimensional spaces. First, we propose a quadratic-time solution of the Multivariate Polynomial Interpolation Problem (PIP), i.e., the N(m, n) coefficients of a polynomial Q, with deg(Q)≤n,, uniquely fitting f on a determined set of generic nodes P⊆ℝ^m are computed in O(N(m, n)²) time requiring storage in O(mN(m, n)). Then, we formulate an algorithm for determining the N(m, n) Fourier coefficients with positive frequency of the Fourier series of f up to order n in the same amount of computational time and storage. Especially in high dimensions, this provides a fast Fourier interpolation, outperforming modern Fast Fourier Transform methods. We expect that these fast and scalable solutions of the polynomial and Fourier interpolation problems in high-dimensional spaces are going to influence modern computing techniques occurring in Big Data and Data Mining, Deep Learning, Image and Signal Analysis, Cryptography, and Non-linear Optimization.