# Longest path of matched cards – code

Longest path of matched cards is to link the cards that have the matched suite or figure. After the link is formed, count the max number of linked cards from the given card. This question sounds like a graph or sorting problem. But actually it is a doubly linked list problem. Each card connects to the next cards only by suite or figure. So it can connect to previous node or next node. When adding a new card, you only check the first or the last node in the linked list. If it matches with the first node, add the card at the front. If it matches with the last node, add the card to the last. If it doesn’t match either, create a new linked list with the card.

After having the linked list constructed, it is time to find the longest path. If the card is in the middle of the linked list, it can reach both ends. Count the number of nodes from the given card to both ends. Then return the number which is bigger.

Amazon Interview Question (CareerCup):
As we all know that poker cards have four suites: Spades, Hearts, Clubs and Diamonds with figures from 1 to 13.Now you are given a set of poker cards, you can pick any one card as the first card. And except for the first card, you can only pick the card that has the same suit or figure with the previous one.Return the max number of cards you can. For example: [(H, 3), (H, 4), (S, 4), (D, 5), (D, 1)], it returns 3 as follows: (H,3)–>(H,4)–>(S,4)

## Doodle

Output:
Links: [[(H, 3), (H, 4), (S, 4)], [(D, 1), (D, 5)]]
Max number of cards from (H, 3): 3
Links: [[(D, 5), (D, 1), (H, 1), (H, 3), (H, 4), (S, 4)]]
Max number of cards from (H, 3): 4

O Notation:
Time complexity: O(n)
Space complexity: O(n)
n is total number of cards