There is a new extraterrestrial language that uses the latin alphabet (a-z). The order of letters are unknown to you. Given an array of non-empty words from the dictionary such that words are sorted lexicographically by the rules of this language, derive and return the order of the letters in the language.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
[
 "wrt",
 "wrf",
 "er",
 "ett",
 "rftt"
]

Output: <code>"wertf"</code></pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
[
 "z",
 "x"
]

Output: <code>"zx"</code></pre>
Example 3:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
[
 "z",
 "x",
 "z"
] 

Output: <code>""</code>&nbsp; Explanation: The order is not valid, return <code>""</code>.</pre>
Note:
<ol>
<li>Assume all letters are in lowercase.</li>
<li>Assume that if a is a prefix of b, then a should appear before b in the given dictionary.</li>
<li>If the order is not valid, return an empty string.</li>
<li>If there are multiple valid order of letters, return any one of them is fine.</li>
</ol>

Extraterrestrial Dictionary

Given an array of integers representing people sitting in a row, return the minimum number of swaps needed such that all couples are sitting next to each other. A swap is considered as any two people in the row standing up and switching seats.
The given array consists of values from 0 to 2N - 1 where N is the number of couples. Couples are paired by the order of numbers. (0, 1) is the first couple, (2, 3) is the second couple etc.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need one swap: move the second (row[1]) and third (row[2]) person.
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are next to each other so we don't need to swap any people.
</pre>

Hold Hands

You have an integer n representing the number of courses you need to take and the courses are labeled from 0 to n-1.
Some courses have prerequisite courses. In order to take course 0, you need to have completed course 1. This is represented as a pair: [0, 1].
Given n and a list of pairs representing prerequisite courses, return the ordering of courses to complete all the courses from 0 to n-1.
Return an empty array if no such ordering exists. If there are multiple orderings, return the order that is lexicographically smallest.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: 2, [[1,0]] 
Output: <code>[0,1]</code> Explanation:&nbsp;In order to take course 1 you need to complete course 0. So the output would be <code>[0,1] .</code></pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: <code>[0,1,2,3]</code> Explanation:&nbsp;There are a total of 4 courses to take. In order to take course 3 you should have completed courses 1 and 2. Both courses 1 and 2 should be taken after you complete course 0. One correct course order is <code>[0,1,2,3]</code> it's the lexicographically smallest. Another correct ordering is <code>[0,2,1,3]</code>&nbsp;but&nbsp;it's&nbsp;not&nbsp;the&nbsp;lexicographically&nbsp;smallest.</pre>

Schedule Classes

Given n nodes which are labeled from 0 to n-1 and a 2D list representing undirected edges (each edge is represented as a pair of nodes), return true if the edges make a tree.
Assume valid input and no repeated edges in the list of given edges. [0,1] and [1,0] are the same so they won't occur more than once in the list of given edges.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: <code>n = 5</code>, and <code>edges = [[0,1], [0,2], [0,3], [1,4]]</code> Output: true</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: <code>n = 5, </code>and <code>edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]</code> Output: false</pre>
&nbsp;

Valid Tree

Given an integer n which represents n nodes labeled from 0 to n-1 and a list of edges (each edge is a pair of nodes), return the number of connected components in the undirected graph.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: <code>n = 5</code> and <code>edges = [[0, 1], [1, 2], [3, 4]]</code></pre>
<pre> 0 3
 | |
 1 --- 2 4 Output: 2</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: <code>n = 5</code> and <code>edges = [[0, 1], [1, 2], [2, 3], [3, 4]]</code> </pre>
<pre> 0 4
 | |
 1 --- 2 --- 3</pre>
<pre style="white-space: pre-wrap; word-break: keep-all;"> Output:&nbsp;&nbsp;1</pre>
Note: Assume there are no duplicate edges that appear. [1, 0] is the same as [0, 1] and they wont appear twice.

Count Connected Components In Graph

Given an array called org and an array of arrays called seqs, return True if there is only one org sequence that can be reconstructed by the sequences in seqs.
The org sequence is a permutation of integers from 1 to n where 1 &lt;= n &lt;= 10000. Reconstruction is defined as building the shortest common supersequence of sequences in the seqs (the shortest sequence such that all sequences in&nbsp;<code>seqs</code>&nbsp;are subsequences of it).
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
org: [1,2,3], seqs: [[1,2],[1,3]]

Output:
false

Explanation:
`[1,2,3]` is not the only one sequence that can be reconstructed, because `[1,3,2]` is also a valid sequence that can be reconstructed.
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
org: [1,2,3], seqs: [[1,2]]

Output:
false

Explanation:
The reconstructed sequence can only be `[1,2]`.
</pre>
Example 3:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

Output:
true

Explanation:
The sequences `[1,2]`, `[1,3]`, and `[2,3]` can reconstruct the sequence `[1,2,3]` in only one way.
</pre>
Example 4:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

Output:
true
</pre>

Problem Title	Difficulty	Frequency in Interviews
Extraterrestrial Dictionary	Hard
Schedule Classes	Medium
Count Connected Components In Graph	Medium
Valid Tree	Medium
Hold Hands	Hard
Reconstruct Sequence	Medium

Most Frequently Asked Graph Interview Questions

Sort By: Company Questions

Sort By: Problem Type