Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
We can use a hastable for both the cases. once create a HashMap<Telno, name>. Now we can get a name in O(1) time using map.getKey("telno").
Similarly for second case use a hashMap<"name",telno> here if map encounters a duplicate keys it will append the results to the same key and you will get an arraylist of telephones for that name.
Agree with Nikhil. But you can also do it with just one hashmap.
1. Declare a directory map Map<String,List<String>>
Key can be either number or name.
2. Parse through the original directory. If name already exist in map, add number to value list, else create new arraylist and add number and store against the name. Also make another entry with number as key and name as value.
Once you map is populated, retrieval is O(1). Most of these type of questions are based on preprocessing. When you get question involving huge data, consider preprocessing.
package com.sunil.carrercup;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class TelephoneDirectory {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
Map<String,ArrayList> map=new HashMap<String, ArrayList>();
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Set<String> map_key;
ArrayList<String> tel_no = null;
String phone_no;
boolean repeat;
System.out.println("Enter 3 employee phone number information");
for(int i=0;i<5;i++)
{
repeat=false;
System.out.println("Enter :"+(i+1)+"Employee Information:");
System.out.println("****************************************************");
System.out.println("Enter Name:");
String name=br.readLine();
System.out.println("Enter the Telphone no:");
phone_no=br.readLine();
map_key=map.keySet();
for(String s:map_key)
{
if(s.equals(name))
{
tel_no=map.get(s);
tel_no.add(phone_no);
repeat=true;
}
}
if(!repeat)
{
tel_no=new ArrayList<String>();
tel_no.add(phone_no);
}
map.put(name, tel_no);
}
//for retrieving information
System.out.println("Enter the name of employee for phone no:");
String name1=br.readLine();
List<String> detail_phone=map.get(name1);
for(String p:detail_phone)
System.out.println("Phone no:"+p);
// ArrayList<String> telephone_no=new ArrayList<String>();
// telephone_no.add("8431079337");
// map.put("sunil", telephone_no);
System.out.println("map"+map);
//System.out.println("Keys are:"+map_key);
//for(String st:map_key)
//System.out.println(map.get(st));
}
}
//Telephone Dir
//Search by telephone no
//Search by name
//A person can have more than 1 telehpne no
//But a telephone no should be assigned to 1 person
#include<iostream>
#include<map>
using namespace std;
bool isTelNoExists(multimap<string,string> &mp,int num)
{
stringstream ss;
ss << num;
string str = ss.str();
std::pair<multimap<string,string>::iterator,multimap<string,string>::iterator> p = mp.equal_range(str);
multimap<string,string>::iterator it1 = p.first;
multimap<string,string>::iterator it2 = p.second;
return it1 != it2;
}
void AddContactToDir(multimap<string,string> &mp,string name,int pNo)
{
if(isTelNoExists(mp,pNo) == true) return;
stringstream ss;
ss << pNo;
string str = ss.str();
mp.insert(std::make_pair(str,name));
mp.insert(std::make_pair(name,str));
}
void SearchContact(multimap<string,string> &mp,string name)
{
std::pair<multimap<string,string>::iterator,multimap<string,string>::iterator> p = mp.equal_range(name);
multimap<string,string>::iterator it1 = p.first;
multimap<string,string>::iterator it2 = p.second;
cout<<"\nSearch Contact by name "<<name<<endl;
if(it1 == it2)
{
cout<<name<<" "<<"does not exists in Dir"<<endl;
}
else
{
cout<<"\nContact Details ";
while(it1 != it2)
{
cout<<it1->second<<" ";
it1++;
}
}
}
void SearchContact(multimap<string,string> &mp,int num)
{
stringstream ss;
ss << num;
string str = ss.str();
cout<<"\nSearch Contact by Phone no "<<endl;
multimap<string,string>::iterator it = mp.find(str);
if(it == mp.end())
{
cout<<"\nNo Person found corresponding to Tel No"<<num<<endl;
return;
}
cout<<"\nContact Found "<<it->second<<" "<<num<<endl;
}
int main()
{
multimap<string,string> mp;
AddContactToDir(mp,"Satveer",100);
AddContactToDir(mp,"Suman",101);
AddContactToDir(mp,"Sunil",102);
AddContactToDir(mp,"Suman",103);
AddContactToDir(mp,"Satveer",104);
AddContactToDir(mp,"Sunil",105);
SearchContact(mp,"Suman");
SearchContact(mp,104);
return 0;
}
It looks similar to a database scenario where we store the data in a table and build indexes to optimize search.
- kr.neerav June 16, 2014Lets store the data in the form of an array of objects sorted by phone numbers. So to search via a phone number it takes O(logN), for binary search.
For efficient search via names we can create a balanced BST with names as key and a list of Ids, of the array containing phone number and name, as nodes. Better use a trei for efficient storage. This takes care of efficient searching from names. O(logN) in case of balanced BST and O(L) in case of trie where L is the length of the name.