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.

Sometimes when a new card is added, it makes two linked lists merge as one. For example, we have the first linked list of (H,3), (H,4), (S,4), and the second linked list (D,1), (D5). When adding new card (H,1), it connect two linked lists to be one (D,5), (D,1), (H,1), (H,3), (H,4), (S,4). When merging, there are 4 cases to consider: the first link’s front node connects to the second link’s front node; the first link’s front node connects to the second link’s last node; the first link’s last node connects to the second link’s front node; the first link’s last node connects to the second link’s last node.


longest path of matched cards

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)

Java

JavaScript

Python

Doodle

longest path of matched cards 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


Download LongestPathOfMatchedCards.java
Download LongestPathOfMatchedCards.js
Download LongestPathOfMatchedCards.py
Java Coding Interview Pocket Book (2nd Edition)
Java coding interview questions(YouTube)

Comments are closed