← Qualcomm Interview Insights

Qualcomm·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
May 2026

Summary

Qualcomm GPU Engineer interview with a classic pathfinding problem that felt more CS-fundamentals than GPU-specific. Not what I was expecting going in.

Questions Asked (1)

Q1

Implement A* search to find the shortest path through a 2D grid maze, where some cells are walls. Given a start and goal cell, return the path or indicate that none exists. Be prepared to discuss heuristic choice, correctness conditions, and how complexity compares to BFS and Dijkstra.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I knew A* well enough but fumbled the heuristic discussion a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints (grid size, movement allowed, heuristic choice) and then outline the A* algorithm: maintain open and closed sets, use a priority queue ordered by f = g + h, and reconstruct the path when the goal is reached. Emphasize the heuristic's admissibility and consistency for optimality, and compare complexity to BFS and Dijkstra.

Pro tip: Mention that using a consistent heuristic (e.g., Manhattan distance for 4-directional movement) ensures that once a node is expanded, its optimal cost is found, allowing you to skip re-expansion and improve efficiency. Also, note that A* reduces to Dijkstra when h=0 and to greedy best-first when h dominates, showing you understand the trade-offs.

1. Clarify problem and constraints

Ask about grid size, movement directions (4 or 8), whether diagonal moves have different costs, and if the heuristic must be admissible. This ensures you tailor the solution correctly.

2. Choose heuristic and data structures

Select an appropriate heuristic (e.g., Manhattan for 4-dir, Euclidean/Octile for 8-dir) and explain why it's admissible and consistent. Use a priority queue for open set and a hash set or 2D array for closed set.

3. Outline A* algorithm

Describe the main loop: pop node with lowest f, if goal return path, else expand neighbors, update g and f scores, and push to open set if not closed or if better path found. Mention path reconstruction via parent pointers.

4. Discuss correctness and complexity

Explain that with an admissible heuristic, A* is optimal; with a consistent heuristic, it's optimally efficient (no re-expansions). Compare time complexity: A* is O(b^d) worst-case but often better; BFS is O(V+E) for unweighted; Dijkstra is O(E + V log V) for weighted.

5. Address edge cases and trade-offs

Mention handling of no path (return empty), start=goal, and memory usage. Discuss when to use A* vs BFS/Dijkstra: A* for single-target with good heuristic, Dijkstra for multiple targets or unknown heuristic, BFS for unweighted.

Key Points to Mention

  • Heuristic admissibility (never overestimates) and consistency (monotonicity) ensure optimality and efficiency.
  • A* uses f = g + h; g is cost from start, h is estimated cost to goal.
  • Priority queue (min-heap) for open set; closed set to avoid revisiting.
  • Complexity: A* time O(b^d) worst-case, but with good heuristic much faster; space O(b^d). BFS O(V+E) for unweighted; Dijkstra O(E + V log V) for weighted.
  • A* is optimal for tree search with admissible h; for graph search, need consistent h or re-expansion handling.
  • Manhattan distance for 4-dir grids, Euclidean/Octile for 8-dir; h=0 makes A* Dijkstra.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.