Tag Archives: graph

Minimum Height Trees

leetcode 310. For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a… Read More »

Reconstruct Itinerary

leetcode. 332 Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK. Note: If there are multiple valid itineraries, you should return the itinerary that… Read More »

Longest Increasing Path in a Matrix

This one is from leetcode: link Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed). Example 1: nums = [ [9,9,4],… Read More »

Tallest box

Given n boxes with length and width. A box with smaller length and smaller width can be put on a box with larger length and larger width. Each box height is 1. Find the tallest box that they can put together. In general, we can build the box with m-dimension. For example, if we have:… Read More »

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word must exist in the dictionary. For example, given: start = “hit” end = “cog” dict = [“hot”,”dot”,”dog”,”lot”,”log”] This is a… Read More »

Detect circle in directed graph — DFS

To detect circle in directed graph, it is important to mark the node with 3 types: 1. Node hasn’t been visited yet. 2. Node is being visiting which means node is processing, but it hasn’t finished DFS of all outgoing edges. 3. Node is visited, which means not only node itself, but also outgoing edges have been… Read More »

Topological sorting by dfs

This is problem is from careerup link: You have an vector like this [JFK, LXA, SNA, RKJ, LXA, SNA] each 2 group define a route. so, JFK -> LXA SNA -> RKJ LXA -> SNA Find the path from departure to destination. note: departure and destination are not known. The final destination should be JFK->… Read More »

Find order of characters in alien language

This is a very interesting question from geeksforgeek. link Problem: Given a sorted dictionary (array of words) of an alien language, find order of characters in the language. Example Input: words[] = {“baa”, “abcd”, “abca”, “cab”, “cad”} Output: Order of characters is ‘b’, ‘d’, ‘a’, ‘c’ Note that words are sorted and in the given language… Read More »