Faits : A. A._ a été engagée en qualité d'ingénieure informatique à la direction des systèmes d'information et de communication de la Ville de Genève dès le 1 er janvier 2010. Elle avait tout d'abord un statut d'auxiliaire. Elle a ensuite été nommée employée avec effet au 1 er janvier 2011. Le 10 septembre 2014, le Conseil administratif de la Ville a ouvert à son encontre une enquête administrative. Celle-ci a été confiée à des juristes du service juridique de la Ville, qui ont rendu leur rapport le 11 mai 2015. Il ressortait notamment de celui-ci que l'employée semblait disposer des compétences techniques requises pour son poste. Il lui était toutefois reproché d'avoir adopté à plusieurs reprises un comportement inapproprié envers certains collègues et son supérieur hiérarchique, d'avoir manqué de vigilance et de contrôle pour des plateformes informatiques (avec une responsabilité partagée de son supérieur hiérarchique), d'avoir omis de signaler un conflit d'intérêts lors de l'élaboration du cahier des charges d'un appel d'offres et d'avoir introduit manuellement (avec toutefois la participation de son supérieur hiérarchique) des heures en sa faveur dans le système de décompte horaire, apparemment pour compenser du travail effectué pendant un congé maternité. Le 13 mai 2015, le Conseil administratif a transmis le rapport d'enquête à A._ en l'informant qu'il envisageait de la licencier pour motif objectivement fondé. L'intéressée était invitée à se déterminer jusqu'au 1 er juin 2015 et à faire savoir si elle désirait être entendue par une délégation du Conseil. A._ a pris position par écriture du 29 mai 2015. Les 23 juin et 22 juillet 2015, assistée d'une secrétaire syndicale, elle a eu des entretiens avec B._, directeur général de la Ville de Genève. Par décision du 29 juillet 2015, le Conseil administratif a résilié les rapports de service de A._ avec effet au 30 novembre 2015. L'employée était libérée de son obligation de travailler jusqu'au terme du délai de congé. Par lettre du 12 août 2015, A._ a demandé à être entendue oralement par une délégation du Conseil administratif. Elle a précisé qu'elle avait demandé une telle audition dans un courrier d'accompagnement à ses déterminations du 29 mai 2015 sur le rapport d'enquête. En outre, elle affirmait avoir réitéré sa demande lors de l'entretien qu'elle avait eu avec B._ le 23 juin 2015. Elle demandait le retrait de la décision du 29 juillet 2015. Le 14 septembre 2015, le Conseil a répondu qu'elle avait été valablement entendue par B._, quand bien même elle n'avait pas sollicité d'audition dans ses observations du 29 mai 2015. Le Conseil a rappelé, par ailleurs, qu'elle avait eu la possibilité de se déterminer tant oralement que par écrit. Il déclarait, en conclusion, qu'il n'entrerait pas en matière sur sa demande de retrait de la décision litigieuse. B. Par écriture du 14 septembre 2015, A._ a recouru devant la Cour de justice de la République et canton de Genève (Chambre administrative). Elle a contesté l'existence d'un motif de licenciement et s'est plainte d'avoir été licenciée sans avoir été entendue par une délégation de l'exécutif communal. Le juge délégué a tenu une audience de comparution des parties. En outre, il a procédé à l'audition de la secrétaire syndicale qui avait assisté A._ ainsi que de B._. Le représentant de la Ville a confirmé que celle-ci n'avait pas reçu le courrier accompagnant les déterminations de l'employée du 29 mai 2015. Statuant le 24 novembre 2015, la Chambre administrative a constaté la nullité de la décision du 29 juillet 2015 et, pour ce motif, a déclaré irrecevable le recours porté devant elle. C. La Ville de Genève forme un recours en matière de droit public dans lequel elle conclut à l'annulation de l'arrêt attaqué et à la confirmation de sa décision de licenciement. Subsidiairement, elle conclut au renvoi de la cause à la juridiction cantonale pour nouvelle décision. Préalablement, elle a demandé l'effet suspensif à son recours. A._ a conclu au rejet tant du recours que de la requête d'effet suspensif. D. Par ordonnance du 11 mars 2016, le juge instructeur a attribué l'effet suspensif au recours.