Longest path of matched cards – code

Longest path of matched cards is to link the cards that have the matched suite or figure. This is an Eulerian path problem. An Eulerian path (or Eulerian trail) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). First we link the matched cards as a chain by applying Eulerian path algorithm, then count the length of the chains and return the max number.

We use data structure graph to simulate. Each card can be seen as a node in a graph. The matched two cards means there is a bi-directional edge between them. So the graph is undirected. The graph can be represented as adjacency list.


Hierholzer's algorithm

After the graph is built, we link the matched cards as a Eulerian path (i.e chain). Hierholzer’s algorithm is efficient to solve it. The idea is (1) start from any vertex v and follow a trail of edges until returning to v. The tour formed a closed tour. (2) If there is a vertex u that belongs to the current tour, but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u. (3) keep following unused edges and removing them when we get stuck. When stuck, backtrack to the nearest vertex in the current path that has unused edges. Repeat the process until all the edges have been used. It’s time complexity is O(E). E is the number of edges.

In our implementation, we start from the first key in adjacency list. The node’s degree is used to keep track the unvisited edges. A stack is to track the cards that have been visited. When the edge is visited, its degree will be decreased by 1. When the degree is 0, it is time to backtrack the card that is last visited and has unused edges. So that we bridge other links of the matched cards. Meanwhile the visited card popped from the stack will be saved in a double linked list which link all possible matched cards. This double linked list is the result of one pass of Hierholzer run.

Since we need to find the max number of the chains, we will iterate through all keys (all cards) in the adjacency list as the start node to run Hierholzer’s algorithm. The result is saved in a map. The key is the length of the matched cards in each Hierholzer run. The value is a linked list which maintains the linked matched cards with the same length. The map is sorted by key in descending order. The first key is the max number of the matched cards.

Please note our test case2. 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).


longest path of matched cards

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

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

O Notation:
Time complexity: O(E*V)
Space complexity: O(E+V)
V is total number of cards, E is number of matched cards


Download LongestPathOfMatchedCards.java
Download LongestPathOfMatchedCards.js
Download LongestPathOfMatchedCards.py
Java Coding Interview Pocket Book (2nd Edition)
Doubly linked list implementation

Comments are closed