"Neha's cat's name is Raj."
Translation:नेहा की बिल्ली का नाम राज है।
Is cat a feminine noun regardless of the actual gender of the cat in question?
Think of it like the French 'chat'. It is used to refer to a male cat or as a catch-all term for a cat regardless of gender. When it is important to note that the cat in question is female, you would say 'chatte'. Similarly, बिल्ली is feminine but can refer to any cat if the gender of the cat is unknown or is not important to explicitly note. When you do really want to say 'male cat', you would use the word बिल्ला.
Because नाम is a masculine noun. का/की/के takes the gender and number of the thing being possessed. का if it is masculine singular, के if masculine plural and की if feminine.