Came along this by accident via Google, but I do not like to let the last answer stand: None of what excavating says below is incorrect, but I want to mention that - coming more from chemistry than metallurgy - the terms interstitial alloy and substitutional alloy are completely correct. Different fields, slightly different nomenclature.
I. e. chromium and iron provide a substitutional alloy, i. e. Cr occupies the place of iron in the lattice. Carbon and iron form an interstitial alloy, since Carbon occupies the interstitital spaces (= holes) in the lattice. Both can happen at the same time, i. e. when you mix Carbon, Chromium and Iron.
Iron carbide (or cementite), Fe3C, is an intermetallic compound with a structure different from that of iron. Neither iron nor carbon is here a substitutional or interstitial element… this is a new compound with (relatively) fixed stoichiometry.