Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher, Kiayias, and Yung is extended to the polynomials whose degrees are allowed to be distinct. Specifically, for a finite field F, positive integers n, r, t and distinct elements z1,z2,…,zn∈F, we present a probabilistic algorithm which can recover polynomials p1,p2,…,pr∈F[x] of degree less than k1,k2,…,kr respectively for a given instance 〈yi,1,…,yi,r〉i=1n satisfying pl(zi)=yi,l for all l∈{1,2,…,r} and for all i∈I⊂{1,2,…,n} such that |I|=t with probability at least 1−n−t|F| and with time complexity at most O(rn4) if t⩾max{k1,k2,…,kr,n+∑j=1rkjr+1}. Next, by using this algorithm, we present a probabilistic decoder for interleaved Reed–Solomon codes. It is observed that interleaved Reed–Solomon codes over F with rate R can be decoded up to burst error rate rr+1(1−R) probabilistically for an interleaving parameter r. Then, it is proved that q-folded Hermitian codes over Fq2q with rate R can be decoded up to error rate qq+1(1−R) probabilistically.