Interview questions

questions.py

# Sort airline tickets
#
# An "airline ticket" is defined as a tuple containing the departure airport code and arrival airport code.
# For example: ("SFO", "LAX") is a trip from SFO to LAX.
# A "legal trip" is a trip that uses all of the airline tickets, where
# the arrival airport for a ticket must be same as the departure airport for the next ticket.
#
# Example
# Input:  [("SFO", "LAX"), ("LAX", "NYC"), ("ORD", "SFO")]
# Output: [("ORD", "SFO"), ("SFO", "LAX"), ("LAX", "NYC")]


Ticket = tuple[str, str]


def sort_tickets(tickets: list[Ticket]) -> list[Ticket]:
    src_to_dst = {s: d for s, d in tickets}
    dst_to_src = {d: s for s, d in tickets}

    cur = next(iter(src_to_dst.keys() - dst_to_src.keys()))  # source
    trip = []
    while cur:
        nxt = src_to_dst.get(cur)
        if nxt:
            trip.append((cur, nxt))
        cur = nxt

    return trip


# Convert tree to list
#
# Here is a struct definition for a node that works for both binary trees and doubly-linked lists:
#
# struct Node {
#   struct Node* left;
#   struct Node* right;
#   int data;
# }
#
# Given a binary tree made of these nodes, convert it, in-place, into a
# circular doubly-linked list in the same order as an in-order traversal of the tree.
# That is, a traversal of the list and an in-order traversal of the tree should yield the elements in the same order.
# You should return the head of the linked list.
#
# Example
#
# Input:
#     |
#   __4__
#  |     |
#  2     6
# | |   | |
# 1 x   5 7
#
# Output:
# (7) <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> (1)


from dataclasses import dataclass


@dataclass
class _Node:
    left: "Node"
    right: "Node"
    data: int


Node = _Node | None


def tree_to_list(cur: Node) -> tuple[Node, Node]:
    if cur is None:
        return None, None
    lhead, ltail = fallback(tree_to_list(cur.left), cur)
    rhead, rtail = fallback(tree_to_list(cur.right), cur)

    connect(ltail, cur)
    connect(cur, rhead)
    connect(rtail, lhead)

    return lhead, rtail


def fallback(tup: tuple[Node, Node], cur: Node) -> tuple[Node, Node]:
    return tup[0] or cur, tup[1] or cur


def connect(a: _Node, b: _Node):
    a.right = b
    b.left = a