Same-page links
EasyOnline Assessment
Find the links that a crawler collected which all lead to the same page.
Every link has the form scheme://host[:port]/path[?query][#fragment]. The scheme is http or https, the path always starts with /, and the port, query and fragment are optional. Two links lead to the same page when they have the same canonical form, which you get like this:
- The scheme and the host are lowercased. The path, the query and everything else keep their case.
- A leading
www.is removed from the host. - The port is removed if it is the default for the scheme (
80forhttp,443forhttps). Any other port stays and is part of the canonical form. - The fragment (
#and everything after it) is removed. - The query is split at
&into pieces. Empty pieces are dropped, and so is every piece whose name (the text before its first=, or the whole piece if there is no=) starts withutm_. The remaining pieces are sorted in ascending string order (by character code, whole piece compared) and joined with&. If no piece remains, the?is dropped too. - A trailing
/is removed from the path, unless the path is just/.
http and https are different schemes, so http://a.com/ and https://a.com/ are different pages.
Input: links, a list of strings in the format above.
Output: the groups of links that share a canonical form, only counting canonical forms shared by at least two links. Each group is a list of 0-based indices into links in ascending order, and the groups are ordered by their smallest index. If no two links share a canonical form, return [].
Example 1
- Input:
- [["HTTP://WWW.Shop.com/a#top","http://shop.com/a","http://shop.com/b"]]
- Output:
- [[0,1]]
- Explanation
- Links 0 and 1 differ only by the uppercase host, the leading www. and the fragment, so both become http://shop.com/a. Link 2 has another path and stays alone, so it is not reported.
Example 2
- Input:
- [["https://x.org:443/p?utm_source=n&b=2&a=1","https://x.org/p?b=2&a=1&","https://x.org:8443/p?a=1&b=2","http://x.org/docs/","http://x.org/docs"]]
- Output:
- [[0,1],[3,4]]
- Explanation
- Link 0 drops the default port 443 and the utm_source piece, and its query sorts into a=1&b=2. Link 1 reaches the same query by sorting and dropping the empty piece. Link 2 keeps port 8443, so it is a different page. Links 3 and 4 are /docs/ and /docs over http, so they form the second group.
Example 3
- Input:
- [["http://a.com/Home","http://a.com/home","http://a.com/?utm_x=1&&","https://a.com/","http://www.a.com/?utm_y"]]
- Output:
- [[2,4]]
- Explanation
- The paths differ in case (/Home against /home), so links 0 and 1 are different pages. Links 2 and 4 are both the root once their utm_ pieces and empty pieces are dropped (utm_y has no = but still starts with utm_). Link 3 is https, so it is not in their group.
Constraints
0 <= links.length <= 200- Each link is at most 150 characters; hosts contain letters, digits, dots and hyphens and are never just
www - Paths, queries and fragments contain no spaces; a fragment, if present, comes last (after the query)