Dataford
Interview QuestionsInterview GuidesExperiencesCoaching
New
Pricing
Get started
Dataford
Popular roles
Software EngineerData AnalystData ScientistData EngineerBusiness AnalystAI EngineerMachine Learning EngineerProduct Manager
Browse
Browse All RolesEvery role hub, from analyst to MLBrowse All CompaniesCompany-specific interview loopsAll Interview GuidesThe full guide library
Top questions by role
Software EngineerData AnalystData ScientistData EngineerBusiness AnalystAI EngineerMachine Learning EngineerProduct Manager
Top questions by skill
SQLPythonStatisticsMachine LearningA/B TestingSystem DesignGenerative AIProduct SenseMetricsBehavioral
Browse all questions →Try a mock interview
Experiences
Practice
Mock InterviewsTimed interview simulations with feedbackCoaching1:1 coaching with people at your target companiesSuccess PathYour 6-week structured planModulesCurated lessons by topicWebinarsTalks from ex-Big Tech data leadsPlaygroundA free-form scratch editor
Learn
BlogInterview strategy and career adviceTech Job Market ReportHiring trends across data and AI rolesFor UniversitiesDataford for career centersAbout DatafordWho we are and how we build
Pricing
Build my plan
Cycle Detection in Loyalty Graphs
00:00
5 left

Cycle Detection in Loyalty Graphs

EasyPython

Problem

CRED models loyalty reward dependencies as a directed graph: an edge u -> v means reward rule u depends on reward rule v. A circular dependency can prevent reward evaluation from completing.

Given the number of reward rules and a list of directed edges, determine whether the graph contains at least one cycle.

Formal Specification

Implement has_cycle(n, edges), where n is an integer representing reward rules labeled 0 through n - 1, and edges is a list of two-element lists [u, v] representing a directed edge from u to v. Return True if any directed cycle exists, otherwise return False.

The graph may be disconnected and may contain multiple edges between the same pair of vertices. A self-loop, such as [2, 2], is a cycle.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(edges) <= 2 * 10^5
  • Each edge contains exactly two integers
  • 0 <= u, v < n for every edge [u, v]

Function Signature

def has_cycle(n, edges):
Interviewer

Your question is Cycle Detection in Loyalty Graphs. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.
CodePython 3
Sign up free to run your codeLog inLn 2
Run your code to see test output here.