"He has two bottles of mayonnaise."

Translation: El are două sticle de maioneză.

[KelseyW11]

Are "de" and "cu" interchangeable in this type of sentence?

[ChrisDim72]

No they are not !!. "cu" means "with" mayonnaise not "of" mayonnaise, which is pretty different.