Translation:The interview with the President
대통령-과 인터뷰 = the President "and/with" the interview
--> "과" is a conjunction linking 2 nouns, 'President' and 'interview'
대통령과-의 인터뷰 [ 의, ties/association ] ~ The interview "in relation" with the President
--> 의 ( in relation ) added to 대통령과 ( with the President ) converts the expression into a phrasal determiner which can describe the noun 'interview'