Analyze DFS, BFS, and A* trade-offs
Company: TikTok
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
Quick Answer: This question evaluates understanding of graph search algorithms, heuristic properties (admissibility and consistency), path optimality and time/space complexity, requiring application of BFS, uniform-cost search, A*, and DFS on a concrete weighted graph.