In a coding interview, graphs can be given in many different formats. You might not even be told that the input is a graph.
Here are four most common graph representations in coding interviews ⬇️
𝟭. 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗠𝗮𝘁𝗿𝗶𝘅 - An n x n 2D matrix where the value in each square denotes whether there exists an edge between two vertices.
𝟮. 𝗠𝗮𝘁𝗿𝗶𝘅 - A more subtle but common format where each square represents a vertex. The problem statement will tell you how these vertices are connected.
𝟯. 𝗔𝗿𝗿𝗮𝘆 𝗼𝗳 𝗘𝗱𝗴𝗲𝘀 - You will be given a 2D array and each element will contain a pair of vertices that have an edge connecting them. They appear in [v1,v2] format, meaning there is an edge going from v1 to v2.
𝟰. 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗟𝗶𝘀𝘁 - The most convenient format, typically implemented with a hashmap. The key represents a vertex and the value represents the list of its neighbors.
—
Preparing for coding interviews? Check out neetcode.io/
NeetCodeIO
In a coding interview, graphs can be given in many different formats. You might not even be told that the input is a graph.
Here are four most common graph representations in coding interviews ⬇️
𝟭. 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗠𝗮𝘁𝗿𝗶𝘅 - An n x n 2D matrix where the value in each square denotes whether there exists an edge between two vertices.
𝟮. 𝗠𝗮𝘁𝗿𝗶𝘅 - A more subtle but common format where each square represents a vertex. The problem statement will tell you how these vertices are connected.
𝟯. 𝗔𝗿𝗿𝗮𝘆 𝗼𝗳 𝗘𝗱𝗴𝗲𝘀 - You will be given a 2D array and each element will contain a pair of vertices that have an edge connecting them. They appear in [v1,v2] format, meaning there is an edge going from v1 to v2.
𝟰. 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗟𝗶𝘀𝘁 - The most convenient format, typically implemented with a hashmap. The key represents a vertex and the value represents the list of its neighbors.
—
Preparing for coding interviews? Check out neetcode.io/
6 months ago | [YT] | 821