We show that the early termination algorithm in [Kaltofen and Lee, JSC, vol. 36, nr. 3--4, 2003] for interpolating a polynomial that is a linear combination of $t$ Chebyshev polynomials of the first kind can be modified to use $2t+1$ randomized evaluation points; Kaltofen and Lee required $2t+2$ randomized evaluation points. Our variants work for scalar fields of any characteristic. The number $2t+1$ of evaluations matches that of the early termination version of the Prony sparse interpolation algorithm for the standard basis of powers of the variable [Kaltofen, Lee and Lobo, Proc. ISSAC 2000]. Our interpolation algorithm can compute the term locator polynomial in $O(t^2)$ field arithmetic operations while storing $O(t)$ intermediate field elements by Heinig's Toeplitz solver with singular sections [Heinig and Rost, "Algebraic Methods for Toeplitz-like Matrices and Operators," Birkhäuser, 1984]. We describe a slight modification for the Levinson-Durbin-Heinig algorithm that mirrors the Berlekamp-Massey algorithm for Hankel matrices.