We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Tries: Contacts
  2. Discussions

Tries: Contacts

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 505 Discussions, By:

recency

Please Login in order to post a comment

  • mikekuehn1
    6 months ago+ 0 comments

    Working Python recursive OOP implementation of Trie. Storing the size rather than computing recursively is essential to pass the tests.

    class PrefixTree():
        
        def __init__(self, is_end=False):
            self.d = dict()
            self.is_end = is_end
            self.size = 0
        
        # Recursively add character by character
        def add(self, word):
            # Base case: empty or existing word
            if len(word) == 0 or self.find(word):
                return -1
            if word[0] not in self.d.keys():
                self.d[word[0]] = PrefixTree()
            # Base case: one character word
            if len(word) == 1:
                self.d[word[0]].is_end = True
            # Recursive case: add the remaining characters
            else:
                self.d[word[0]].add(word[1:])
            # Caching the size is the key to good runtime in 'find()'
            self.size += 1
        
        # Returns number of matches for a prefix
        def find(self, prefix):
            # Base case: we're at the end node of the prefix
            if len(prefix) == 0:
                return self.size + (1 if self.is_end else 0)
            # Base case: we can't reach the next character
            if prefix[0] not in self.d.keys():
                return 0
            # Recursive case: keep looking
            return self.d[prefix[0]].find(prefix[1:])
    
    0|
    Permalink
  • erikw
    11 months ago+ 0 comments

    Simple Ruby Trie OOP solution:

    class Contacts
      def initialize
        @root = ContactNode.new
      end
    
      def add(name)
        node = @root
        name.each_char do |c|
          idx = c2i(c)
          node.children[idx] = ContactNode.new if node.children[idx].nil?
          node = node.children[idx]
          node.count += 1
        end
      end
    
      def find_count(partial)
        node = @root
        partial.each_char do |c|
          idx = c2i(c)
          return 0 if node.children[idx].nil?
    
          node = node.children[idx]
        end
        node.count
      end
    
      private
    
      def c2i(c)
        c.ord - 'a'.ord
      end
    end
    
    class ContactNode
      attr_accessor :count, :children
    
      def initialize(alphasize = 26)
        @count = 0
        @children = Array.new(alphasize)
      end
    end
    
    contacts = Contacts.new
    gets.to_i.times do
      op, arg = gets.split
      case op
      when 'add'
        contacts.add(arg)
      when 'find'
        puts contacts.find_count(arg)
      end
    end
    
    0|
    Permalink
  • pabloemilioandr1
    1 year ago+ 0 comments

    Trie solution in python - storing number of matches in each node when inserting

    class TrieNode:
        def __init__(self, char):
            self.char = char
            self.children = {}
            self.valid_children = 0
    
    
    class Trie:
        def __init__(self):
            self.root = TrieNode("")
        
        def insert(self, node, word):
            if not word:
                new_node = TrieNode("*")
                node.children["*"] = new_node
                node.valid_children += 1
                return 1
            elif word[0] in node.children:
                new_node = node.children[word[0]]
            else:
                new_node = TrieNode(word[0])
                node.children[word[0]] = new_node
            valid_children = self.insert(new_node, word[1:])
            node.valid_children += valid_children
            return valid_children
        
        def find_matches(self, query):
            node = self.root
            
            for char in query:
                if char in node.children:
                    node = node.children[char]
                else:
                    return 0
            return node.valid_children 
        
        def number_of_valid_children(self, prefix):
            return self.find_matches(prefix)
    
    def contacts(queries):
        trie = Trie()
        result = []
        for query in queries:
            op, value = query[0], query[1]
            if op == "add":
                trie.insert(trie.root, value)
            elif op == "find":
                result.append(trie.number_of_valid_children(value))
        return result
                
    
    0|
    Permalink
  • yuangao212
    1 year ago+ 0 comments

    Anyone knows why the same logic implemented with array and object have different results in PHP?

    <?php
    
    $n = intval(trim(fgets(STDIN)));
    
    // $trie = [[], 0];
    // 
    // function addToTrie(array &$node, string $s, int $idx) 
    // {
    //     if ($idx === strlen($s)) {
    //         return;
    //     }
    //     $key = $s[$idx];
    //     if (!isset($node[0][$key])) {
    //         $node[0][$key] = [[], 0];
    //     } 
    //     $node[0][$key][1] ++;
    //     addToTrie($node[0][$key], $s, $idx+1);
    // }
    // 
    // function readFromTrie(array $node, string $s): int
    // {
    //     foreach (str_split($s) as $key) {
    //         if (!isset($node[0][$key])) {
    //             return 0;
    //         }
    //         $node = $node[0][$key];
    //     }
    //      return $node[1];
    // }
    
    class Node {
        public $children = [];
        public $count = 0;
    }
    
    $trie = new Node;
    
    function addToTrie(Node $node, string $s, int $idx)
    {
        if ($idx === strlen($s)) {
            return;
        }
        $key = $s[$idx];
        if (!isset($node->children[$key])) {
            $node->children[$key] = new Node;
        } 
        $node->children[$key]->count ++;
        addToTrie($node->children[$key], $s, $idx+1);
    }
    
    function readFromTrie(Node $node, string $s)
    {
       foreach (str_split($s) as $key) {
           if (!isset($node->children[$key])) {
               return 0;
           }
           $node = $node->children[$key];
       }
        return $node->count;
    }
    
    for ($n_itr = 0; $n_itr < $n; $n_itr++) {
        $first_multiple_input = explode(' ', rtrim(fgets(STDIN)));
    
        $op = $first_multiple_input[0];
    
        $contact = $first_multiple_input[1];
        
        
        if ($op === 'add') {
           addToTrie($trie, $contact, 0);
        } elseif ($op === 'find') {
           echo readFromTrie($trie, $contact) . PHP_EOL;
        }
    }
    
    0|
    Permalink
  • nkstatedev
    1 year ago+ 0 comments
    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    
    class Node:
        def __init__(self, val):
            self.val = val
            self.next = []
            self.count = 1
            
        @staticmethod
        def add(root, contact):
            for i in contact:
                found = False
                for child in root.next:
                    if child.val == i:
                        child.count += 1
                        root = child
                        found = True
                        break
                if not found:
                    char = Node(i)
                    root.next.append(char)
                    root = char
        
        @staticmethod
        def find(root, contact):
            count = 0
            for i in contact:
                found = False
                for child in root.next:
                    if i == child.val:
                        count = child.count
                        root = child
                        found = True
                        break
                if not found:
                    count = 0
                    break
            print(count)
            
    if __name__ == '__main__':
        n = int(input().strip())
        root = Node(0)
        for n_itr in range(n):
            first_multiple_input = input().rstrip().split()
            op = first_multiple_input[0]
            contact = first_multiple_input[1]
            if op == 'add':
                Node.add(root, contact)
            if op == 'find':
                Node.find(root, contact)
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy