Here is how you can do it. Make 2 parts of your dataset: a) where gender information is present b) where gender information is missing.
Now dataset from a is the one, on which you will build your model and dataset from part b is the one you are going to predict.
For the dataset from a, treat your gender as (1/0) 2 classes and apply binary logistic model with InterestID as independent variable.Note that you need to transform your InterestID into indicators for each of the category and then remove duplicates for customer ID. If it turns out to be good predictor. Use the estimates of the model to predict the probability of the gender being male or female in dataset from b.
So your train dataset will be like:
UserID Gender(this is target) InterestID_1 InterestID_2 InterestID_3...
3 1 1 0 0
4 1 1 1 0