Senior Research Interview Questions

3,378 senior research interview questions shared by candidates

In an undirected connected graph G = (N, A), an Euler tour is a walk that starts at some node, visits each arc exactly once, and returns to the starting node. A graph is Eulerian if it contains an Euler tour. Show that in an Eulerian graph, the degree of every node is even. Next, show that if every node in a connected graph has an even degree, the graph is Eulerian. Establish the second result by describing an O(m) algorithm for determining whether a graph is Eulerian and, if so, will construct an Euler tour. (Hint: Describe an algorithm that decomposes any graph with only even-degree nodes into a collection of arc-disjoint cycles, and then converts the cycles into an Euler tour.)
avatar

Senior OPerations Research Scientist

Interviewed at Optym

3.9
Dec 24, 2022

In an undirected connected graph G = (N, A), an Euler tour is a walk that starts at some node, visits each arc exactly once, and returns to the starting node. A graph is Eulerian if it contains an Euler tour. Show that in an Eulerian graph, the degree of every node is even. Next, show that if every node in a connected graph has an even degree, the graph is Eulerian. Establish the second result by describing an O(m) algorithm for determining whether a graph is Eulerian and, if so, will construct an Euler tour. (Hint: Describe an algorithm that decomposes any graph with only even-degree nodes into a collection of arc-disjoint cycles, and then converts the cycles into an Euler tour.)

Viewing 2981 - 2990 interview questions

See Interview Questions for Similar Jobs

Glassdoor has 3,378 interview questions and reports from Senior research interviews. Prepare for your interview. Get hired. Love your job.