Technical Interview Question:

Implement a Trie (Prefix Tree) data structure using a doubly linked list with the following operations:

1. insert(word: str) - Inserts a word into the trie.
2. search(word: str) - Returns true if the word is in the trie.
3. startsWith(prefix: str) - Returns true if there is any word in the trie that starts with the given prefix.

Create a class TrieNode which contains a doubly linked list representation of the trie and implement the above operations.

class TrieNode:
    def __init__(self, char):
        self.char = char
        self.children = {}
        self.is_word = False
        self.prev = None
        self.next = None

class Trie:
    def __init__(self):
        self.root = TrieNode('')

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                newNode = TrieNode(char)
                node.children[char] = newNode
                newNode.prev = node
                if node.next:
                    node.next.prev = newNode
                    newNode.next = node.next
                node.next = newNode
            node = node.children[char]
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char in node.children:
                node = node.children[char]
            else:
                return False
        return node.is_word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char in node.children:
                node = node.children[char]
            else:
                return False
        return True

Explanation:

• We start by defining a TrieNode class representing each node in the trie. Each node contains a character, a dictionary to store its children nodes, a boolean flag to indicate if it marks the end of a word, and references to its previous and next nodes in the doubly linked list.
• The Trie class initializes with a root node and implements the insert, search, and startsWith methods as per the requirements.
• The insert method iterates through the characters of the input word, checking if the character exists in the current node's children. If not, it creates a new node and updates the doubly linked list references.
• The search method traverses the trie to check if the word exists by following the character paths.
• The startsWith method checks if there are any words in the trie that start with the given prefix by following the character paths as well.

This implementation of Trie with a doubly linked list provides an efficient way to store, search, and query words based on prefixes.