Analyze DFS, BFS, and A* trade-offs

Q: Analyze DFS, BFS, and A* trade-offs

This is a Coding & Algorithms interview question from TikTok for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a weighted graph with nodes {S,A,B,C,D,G} and edges: S–A(2), S–B(5), A–C(2), B–C(1), C–D(2), D–G(1), B–G(20). Heuristic for A*: h(A)=4, h(B)=3, h(C)=2, h(D)=1, h(G)=0, h(S)=5. (1) Starting at S, list the node expansion order and final path found by BFS (on unweighted edges), by uniform-cost search, and by A* using the given h (break ties alphabetically). (2) Prove whether h is admissible and consistent. (3) Compare time and space complexity of DFS, BFS, UCS, and A* on this graph family (branching factor b, depth d), and explain a case where DFS wins in memory but fails in optimality. (4) Show the condition under which A* reduces to Dijkstra’s algorithm and illustrate it with the provided h.

Analyze DFS, BFS, and A* trade-offs

Comments (0)