The polynomial interpolation problem with distinct interpolation points and the polynomial represented in the power basis gives rise to a linear system of equations with a Vandermonde matrix. This system can be solved efficiently by exploiting the structure of the Vandermonde matrix with the aid of the Bjorck–Peyrera algorithm. We are concerned with polynomial least-squares approximation at the zeros of Chebyshev polynomials. This gives rise to a rectangular Vandermonde matrix. We describe fast algorithms for the factorization of these matrices. Both QR and QR-like factorizations are discussed. The situations when the nodes are extreme points of Chebyshev polynomials or zeros of some classical orthogonal polynomial also are considered.