Why do i get a "terminated due to timeout" error for my code at hackerrank?

Question

I got a "Terminated due to timeout error" when i ran my code for some specific testcases only. Even though my code compiled successfully for other testcases. Can someone please help me with this?

Link - https://www.hackerrank.com/challenges/phone-book

Problem Statement :

You are given a phone book that consists of people's names and their phone number. After that you will be given some person's name as query. For each query, print the phone number of that person.

Input Format :

The first line will have an integer denoting the number of entries in the phone book. Each entry consists of two lines: a name and the corresponding phone number.

After these, there will be some queries. Each query will contain a person's name. Read the queries until end-of-file.

Constraints:

1<=n<=100000

1<=Query<=100000

A person's name consists of only lower-case English letters and it may be in the format 'first-name last-name' or in the format 'first-name'. Each phone number has exactly 8 digits without any leading zeros.

Output Format :

For each case, print "Not found" if the person has no entry in the phone book. Otherwise, print the person's name and phone number. See sample output for the exact format.

To make the problem easier, we provided a portion of the code in the editor. You can either complete that code or write completely on your own.

My code is as follows :

import java.util.*;
import java.io.*;

class Solution
{
 public static void main(String []args)
 {
  Scanner in = new Scanner(System.in);
  int n=in.nextInt();
  in.nextLine();
  ArrayList<String> name = new ArrayList<String>();
  int[] phone = new int[100000];

  for(int i=0;i<n;i++)
  {
   name.add(in.nextLine());
   phone[i]=in.nextInt();
   in.nextLine();
  }

  while(in.hasNext())
  {
   String s=in.nextLine();
   int a=name.indexOf(s);

   if(a>=0)
   {
    System.out.println(s + "=" + phone[a] );
   }
   else
   {
    System.out.println("Not found");
   }
  }
 }
}

PS:This is my first question on the forum. I'm an amateur learning java. Sorry if i violated any of the many rules of asking a question :( . Please do correct me and help me contribute to the community here in a good way :)

Answer 1

The problem with your logic is that it is implemented using ArrayList which is a sequential structure. Any search in List will be sequential and for large test cases its taking too much time to lookup in your names list.

Hash map is more appropriate for a phone book example as it keeps data in key, value pair and look ups are fast because of hashing

Here is a version that is implemented using HashMap

   Map<String,Integer> phonebook = new HashMap<>();
  Scanner in = new Scanner(System.in);
  int n=in.nextInt();
  in.nextLine();
  for(int i=0;i<n;i++)
  {
     String name=in.nextLine();
     int phone=in.nextInt();
     in.nextLine();
      phonebook.put(name,phone);
  }
  while(in.hasNext())
  {
     String s=in.nextLine();
     Integer phone = phonebook.get(s);
     if(phone==null){
         System.out.println("Not found");
     } else {
         System.out.println(s+"="+phone);
     }
  }

Hope this explains.