HackerRank Contacts problem solution

In this HackerRank Contacts problem, we need to make a list that must add name and find partial string in the list.

Problem solution in Python programming.

class node2(dict) :
    __slots__ = ['numDescendants']
    def __init__(self) :
        self.numDescendants = 0
    def addChild(self, child) :     # child is a character
        self[child] = node2()
        self.numDescendants += 1
    def getNumDescendants(self) :
        return self.numDescendants
    def incNumDescendants(self) :
        self.numDescendants += 1
       

class Contacts() :
    def __init__(self) :
        self.root = node2()
        
    def addName(self, name) :
        def Helper(currNode, suffix) :
            if len(suffix)==0 :
                currNode.addChild('')       # termination character
            else :
                if suffix[0] in currNode :
                    currNode.incNumDescendants()
                    Helper(currNode[suffix[0]], suffix[1:])
                else :
                    currNode.addChild(suffix[0])
                    Helper(currNode[suffix[0]], suffix[1:])
                    
        currNode = self.root
        Helper(currNode, name)

    def findName(self, prefix) :
        def findPrefix(currNode, prefix) :
            if len(prefix)==0 :
                return currNode
            else :
                if prefix[0] in currNode :
                    return findPrefix(currNode[prefix[0]], prefix[1:])
                return -1
        
        nameLoc = findPrefix(self.root, prefix)
        if nameLoc==-1 :
            print(0)
        else : 
            print(nameLoc.getNumDescendants())
        return
    
a = Contacts()
numLines = int(input())
while numLines > 0 :
    command = input()
    if command[0]=='a' :
        a.addName(command[4:])
    elif command[0]=='f' :
        a.findName(command[5:])
    numLines -= 1

Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the contacts function below.
     */
   

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int numQueries = Integer.parseInt(br.readLine());
    HashMap<String, Integer> map = new HashMap<String, Integer>();

    for (int i = 0; i < numQueries; i++){
        String[] data = br.readLine().split(" ");

        if (data[0].equals("add")){
            for (int j = 1; j <= data[1].length(); j++){
                String sub = data[1].substring(0, j);
                if (map.get(sub) == null){
                    map.put(sub, 1);
                } else {
                    map.put(sub, map.get(sub) + 1);
                }
            }
        } else { //query matches
            if (map.get(data[1]) == null){
                System.out.println(0);
            } else {
                System.out.println(map.get(data[1]));
            }

        }
    }
}
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

typedef struct node
{
  char data;
  node* next[26] = { NULL };
  bool delimiter;
  int total;
    
  node()
  {
    for(int i = 0; i < 26; i ++)    
        next[i] = NULL;
    delimiter = false; 
    total = 0;
  }
    
}node;

void Add(node *root, string toadd)
{
    int size = toadd.size();
    for(int i = 0; i < size; i++)
    {
        int index = toadd[i] - 'a';
        if(root->next[index] == NULL)
        {
            node *newnode = new node;
            newnode->data = toadd[i];
            newnode->total = newnode->total + 1;
            if(i == size - 1) 
                newnode->delimiter = true;
            root->next[index] = newnode;
        } 
        else
        {
           node *temp =  root->next[index];
           temp->total = temp->total + 1;
            if(i == size - 1) 
                temp->delimiter = true; 
        }
        root = root->next[index];
    }
}
void Find(node *root, string tofind)
{
   int size =  tofind.size();
   for(int i = 0; i < size; i++)
   {
       int index = tofind[i] - 'a';
       if(root->next[index] == NULL)
       {
          cout<<0<<endl;
          return;
       }
       else
       {
          root =  root->next[index];    
       }
   }
   if(root == NULL)
   {
        cout<<0<<endl;
        return;
   }
    else
        cout<<root->total<<endl;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int noofcommands = 0;
    cin>>noofcommands;
    
    node *root = new node;
    root->data = '#';
       
    for(int i = 0; i < noofcommands; i++)
    {
        string operation;
        cin>>operation;
        if(operation.compare("add") == 0)
        {
          string toadd;
          cin>>toadd;
          Add(root, toadd);
        }
        else
        {
          string tofind;
          cin>>tofind;
          Find(root, tofind);
        }
    }
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct node_t{
    char data;
    struct node_t *children[26]; //One pointer to node per alphabet
    int words;
    int prefixes;
}node;

node *create_node(char data){
    node *t = (node *)malloc(sizeof(node));
    
    if(t)
    {
        memset(t, 0, sizeof(node));
        t->data = data;
    }
    return t;
}

int find_prefix(node *root, char *prefix){
    char c = *prefix;
    
    if(root == NULL){
        return 0;
    }
        
    
    if(root->data == '0'){ //This is the root of the trie
        return find_prefix(root->children[c - 'a'], prefix);
    }
    
    else if(root->data == c){
        prefix++;
        if(*prefix == ''){ //We're done searching            
            return root->prefixes;
        }
        else{
            return find_prefix(root->children[*prefix - 'a'], prefix);
        }
    }
    printf("Did not find a matchn");
    return 0;
}

//Assumes all input chars are lower case
void add_word(node *root, char *str){
    char c = *str;
    //printf("char: %c, diff: %dn",c, c - 'a');
    if(root == NULL){
        printf("Root is nulln");
        return;
    }
    
    if(c == ''){  
        printf(" Should never come heren");
        return;
    }
    
    if(root->children[c - 'a'] == NULL){
           root->children[c - 'a'] = create_node(*str);  
           //printf("Created the childn");
           if(root->children[c - 'a'] == NULL){
               printf("Failed to create noden");
               return;
           }
    }    
    
    root->children[c - 'a']->prefixes++;
    
    str = str + 1;
    //printf("child: %llu, data: %cn", (unsigned long long)root->children[c - 'a'], root->children[c - 'a']->data);
    //printf("str: %cn",*str);
    if(*str == ''){  //We have reached the end of the word
        root->words++;
        return;
    }
    add_word(root->children[c - 'a'], str);    
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int num_ops; 
    int i = 0;
    char op[5];
    char str[28];
    
    node *root = create_node('0');
    if(root == NULL){
        printf("Main: root is NULLn");
        return 0;
    }
    
    scanf("%d", &num_ops);
    while(i < num_ops){
        scanf("%s %s", op, str );
        //printf("Read: %s %sn", op, str);
        if(!strcmp(op, "add")){
            add_word(root, str);
        }
        else if(!strcmp(op, "find")){
            printf("%dn", find_prefix(root, str));
        }
        i++;
    }
    
    return 0;
}

Problem solution in JavaScript programming.

function processData(input) {
    var lines = input.split("n");
    var operations = lines[0];
    var root = createNode();
    
    if (operations < 1 || operations > Math.pow(10, 5))
    {
        console.log(0);
        return;
    }
    
    for (var i=1; i<=operations; i++)
    {
        var op = lines[i].split(" ");
        var contact = op[1].toLowerCase();
        var invalid = (contact.length < 1 || contact.length > 21);
                
        switch (op[0])
        {
            case "add":
                if (!invalid)
                    addContact(contact);
                break;
                
            case "find":
                console.log((invalid ? 0 : findPartial(contact)));
                
                break;
        }
    }
    
    function createNode()
    {
        // children, numberOfChildren, endOfContact
        return [{}, 0, 0];
    }
    
    function addContact(name)
    {
        var pn = root;
        for (var i=0; i<name.length; i++)
        {
            var c = name[i];
            
            if (!pn[0][c])
                pn[0][c] = createNode();
            
            pn[0][c][1]++;
            pn = pn[0][c];
        }
        
        // set end of contact name 
        pn[2] = 1;
    }
    
    function findPartial(str)
    {
        var pn = root;
        
        for (var i=0; i<str.length; i++)
        {
            var c = str[i];
            
            if (!pn[0][c])
            {
                return 0;
            }
            
            pn = pn[0][c];
        }
        
        // return count;
        return pn[1];
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});