Generating An Optimal Interview Question Plan Using A Knowledge Graph And Integer Linear Programming

Soham Datta, Prabir Mallick, Sangameshwar Patil, Indrajit Bhattacharya, Girish K. PalshikarNAACL 2021 · DOI

Introduction

Technical interviewing is a critical yet resource-intensive component of the hiring process. Large organizations often dedicate hundreds of thousands of person-hours annually to conducting interviews, which frequently suffer from subjectivity, inconsistency, and unconscious bias. While automated testing systems like Computerized Adaptive Testing (CAT) are effective for standardized exams, they lack the structure required for human-to-human technical interviews. This paper presents an automated system developed by TCS Research that leverages Knowledge Graphs (KG) and Integer Linear Programming (ILP) to generate personalized, high-quality interview plans.

The Knowledge Graph Framework

At the core of the proposed system is a Knowledge Graph that represents the technical domain. Nodes in the graph correspond to specific concepts (e.g., "Python," "Encapsulation," "Data Structures"), while edges define semantic relationships such as IS-A (inheritance) or HAS-A (composition).

A snippet of the technical Knowledge Graph illustrating concepts and their hierarchical relationships.

This graph allows the system to move beyond simple keyword matching. By understanding the relationships between concepts, the system can identify that a question regarding "Arrays" is inherently linked to "Data Structures," enabling a more nuanced assessment of a candidate's expertise. The graph also aids in automated difficulty scoring by analyzing the node degree of concepts within a question's answer text.

Optimization via Integer Linear Programming

The system treats the selection of interview questions as a mathematical optimization problem. Using ILP, the system balances six distinct objective functions to create a "static plan" tailored to a specific candidate and job role:

  1. Coverage: Maximizing the variety of technical concepts addressed.
  2. Depth: Selecting questions that are conceptually related to allow for "drill-down" exploration.
  3. Breadth: Selecting unrelated questions to test the range of knowledge.
  4. Resume Personalization: Prioritizing concepts found in the candidate's resume.
  5. Job Alignment: Prioritizing concepts relevant to the specific job description.
  6. Novelty: Ensuring variety across different interview instances to prevent question leakage.
Graph representation of question relationships used to calculate depth and breadth weights in the ILP formulation.

The ILP solver adheres to practical constraints, such as a predefined time limit (e.g., 45 minutes) and a specific distribution of question difficulty levels. Despite the underlying complexity of the NP-Hard optimization problem, the system can generate an optimal 45-minute plan in approximately 155 seconds using standard LP rounding approximations.

Evaluation and Results

The system was evaluated using a custom KG of 714 concepts and a bank of 549 annotated questions. The researchers compared the ILP-generated plans against random baselines and existing state-of-the-art question recommenders like DuerQuiz.

Intrinsic evaluations, which measured the overlap between suggested questions and actual interview transcripts from 20 real candidates, showed that the ILP approach significantly outperformed baselines. Furthermore, in a blind human evaluation, three expert interviewers preferred the ILP-generated plans in 19 out of 21 cases when compared to resume-aware random selections.

Conclusion

By formalizing interview preparation as a strategic traversal of a Knowledge Graph, this research provides a path toward more objective and standardized technical assessments. While the current system generates static plans, future work aims to incorporate real-time adaptability to candidate performance and further align mathematical objectives with the subjective values of veteran human interviewers.

Summary updated

BibTeX
@inproceedings{datta2021generating,
  author = {Soham Datta and Prabir Mallick and Sangameshwar Patil and Indrajit Bhattacharya and Girish K. Palshikar},
  title = {{Generating An Optimal Interview Question Plan Using A Knowledge Graph And Integer Linear Programming}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2021},
  doi = {10.18653/v1/2021.naacl-main.160},
}
Figure