Samsung Interview Question for SDE1s
- 0of 0 votes
There are N nodes in a graph connected by exactly N-1 edges. There is exactly 1 shortest path from one node to any other node. The nodes are numbered from 1 to N. Given Q queries which tell source node and the destination nodes. Find the most visited node after traveling those Q paths. For example, say Q=3- sudhiammula November 23, 2018 in India
and 3 queries are
So travel from node 1 to node 5, then from node 2 to node 4, then from node 3 to node 1. Finally, find what is the most visited node after the Q queries.
Finding every path and incrementing every visited node count is a naive solution. The interviewer asked me to optimize it.
| Report Duplicate | Flag | PURGE
Samsung SDE1 Trees and Graphs
Interview Type: In-Person
Open Chat in New Window