Faits : A. A.a. Par arrêté du Conseil d'Etat de la République et canton de Neuchâtel du 22 avril 2009, A._ a été nommé chef du Service B._ avec effet au 1er septembre 2009. Par décision du 31 mai 2011, le Conseil d'Etat a mis fin à ses rapports de service pour le 31 août suivant, motif pris, notamment, de la rupture définitive de la confiance en ses capacités à conduire le Service B._ et à gérer le personnel. A.b. A._ a recouru contre cette décision au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, qui l'a débouté par jugement du 21 mars 2012. Le Tribunal fédéral a rejeté le recours en matière de droit public qu'il a interjeté contre cet arrêt (cause 8C_369/2012). A.c. En raison de l'effet suspensif attaché à son recours devant le Tribunal cantonal, A._ a continué à percevoir son salaire du 1 er septembre 2011 au 31 mars 2012, soit 87'512 fr. 50 au total, bien qu'il n'eût plus travaillé au service de l'Etat durant cette période. L'intéressé a remboursé à l'Etat un montant de 54'717 fr. 20 qu'il avait perçu de l'assurance-chômage. Le 21 janvier 2014, il a encore restitué la somme de 21'627 fr. 70, tout en indiquant que le solde encore dû, qu'il entendait compenser, correspondait à des frais de représentation non remboursés par l'employeur. B. Par écriture du 31 janvier 2014, l'Etat de Neuchâtel a introduit une action de droit administratif à l'encontre de A._. Il réclamait la restitution de 11'167 fr. 60 (87'512 fr. 50 - 54'717 fr. 20 - 21'627 fr. 70) avec intérêts à 5 % l'an depuis le 1er mai 2012. A cela s'ajoutaient les intérêts sur la somme de 54'717 fr. 20 du 1er mai 2012 au 18 septembre 2012 (1'048 fr. 75) et les intérêts sur la somme de 21'627 fr. 70 du 1er mai 2012 au 20 janvier 2014 (1'892 fr. 40). Le défendeur a conclu, principalement, au rejet de la demande. Il invoquait la compensation, faisant valoir que le montant de 11'167 fr. 60 qui lui était réclamé devait être compensé avec des frais professionnels que devait lui rembourser le demandeur. Reconventionnellement, il concluait à la condamnation de l'Etat de Neuchâtel au paiement d'une somme de 20'000 fr., avec intérêts à 5 % l'an dès le 22 avril 2014, pour des prestations de travail impayées qu'il affirmait avoir fournies. Par arrêt du 25 septembre 2015, la Cour de droit public a condamné A._ à payer au demandeur la somme de 11'167 fr. 60 avec intérêts dès le 1er mai 2002, ainsi que les intérêts calculés "au sens des considérants". Il a par ailleurs condamné l'Etat à verser à A._ la somme de 9'183 fr. 10 fr. au titre "de frais de déplacement au sens large". C. A._ interjette un recours en matière de droit public dans lequel il conclut à l'annulation de l'arrêt attaqué. Principalement, il prend les conclusions suivantes: 1. Dire et constater que les créances respectives des parties concernant les frais que l'Etat de Neuchâtel doit rembourser à A._, soit CHF 10'644.85, et concernant les salaires perçus à tort que A._ doit rembourser à l'Etat de Neuchâtel, soit 11'167.60 fr, sont compensés. 2. Condamner l'Etat de Neuchâtel à payer à Monsieur A._ la somme de CHF 20'000.- avec intérêts à 5 % l'an dès le 22 avril 2014, sous déduction du solde résultant de la compensation de la conclusion numéro 2. Subsidiairement, le recourant conclut à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité cantonale pour nouvelle décision. L'Etat de Neuchâtel conclut au rejet du recours.