Microsoft Interview Question Software Engineers
Team: Cloud services
Country: United States
c++, implementation
struct Person {
string name;
string phoneNumber;
};
class PhoneBook {
private:
vector<Person> book;
map<string, int> names;
map<string, int> phones;
int readCount;
mutex mtx;
public:
PhoneBook(vector<Person> people) : readCount(0) {
vector<Person>::iterator it;
for (it = people.begin(); it != people.end(); it++) {
if (names.find(it->name) != names.end()) continue;
if (phones.find(it->phoneNumber) != phones.end()) continue;
book.push_back(*it);
names.insert(make_pair(it->name, book.size() - 1));
phones.insert(make_pair(it->phoneNumber, book.size() - 1));
}
}
Person LookupByName(string name) {
map<string, int>::iterator it;
Person p;
mtx.lock();
readCount++;
mtx.unlock();
it = names.find(name);
if (it != names.end()) p = book[it->second];
mtx.lock();
readCount--;
mtx.unlock();
return p;
}
Person LookupByPhoneNumber(string phoneNumber) {
map<string, int>::iterator it;
Person p;
mtx.lock();
readCount++;
mtx.unlock();
it = phones.find(phoneNumber);
if (it != phones.end()) p = book[it->second];
mtx.lock();
readCount--;
mtx.unlock();
return p;
}
void AddPerson(Person person) {
while (true) {
mtx.lock();
if (readCount == 0) break;
mtx.unlock();
}
if (names.find(person.name) == names.end() && phones.find(person.phoneNumber) == phones.end()) {
book.push_back(person);
names.insert(make_pair(person.name, book.size() - 1));
phones.insert(make_pair(person.phoneNumber, book.size() - 1));
}
mtx.unlock();
}
};
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading;
namespace PhoneBook {
public struct Person {
public Person( string name, string phoneNumber ) {
Name = name;
PhoneNumber = phoneNumber;
}
public string Name { get; }
public string PhoneNumber { get; }
}
public class Phonebook {
private readonly object _lock = new object();
private readonly ConcurrentDictionary<string, Person> _indexByName;
private readonly ConcurrentDictionary<string, Person> _indexByPhoneNumber;
public Phonebook( IEnumerable<Person> people ) {
_indexByName = new ConcurrentDictionary<string, Person>();
_indexByPhoneNumber = new ConcurrentDictionary<string, Person>();
foreach ( var p in people ) {
_indexByName.AddOrUpdate( p.Name, p, (s, pers) => pers );
_indexByPhoneNumber.AddOrUpdate( p.PhoneNumber, p, (s, pers) => pers );
}
}
public Person? LookupByName( string name ) {
Person pers;
var res = _indexByName.TryGetValue( name, out pers );
return res ? (Person?)pers : null;
}
public Person? LookupByPhoneNumber( string phoneNumber ) {
Person pers;
var res = _indexByPhoneNumber.TryGetValue( phoneNumber, out pers );
return res ? (Person?)pers : null;
}
public void AddPerson( Person person ) {
Monitor.Enter( _lock );
var res1 = LookupByName( person.Name );
var res2 = LookupByPhoneNumber( person.PhoneNumber );
if ( res1 != null && res2 != null ) {
Monitor.Exit( _lock );
return;
}
Person p;
if ( res1 != null ) {
_indexByPhoneNumber.TryRemove( ((Person)res1).PhoneNumber, out p );
_indexByPhoneNumber.TryAdd( person.PhoneNumber, person );
}
if ( res2 != null ) {
_indexByName.TryRemove( ((Person)res2).Name, out p );
_indexByName.TryAdd( person.Name, person );
}
_indexByName.AddOrUpdate( person.Name, person, (s, pers) => person );
_indexByPhoneNumber.AddOrUpdate( person.PhoneNumber, person, (s, pers) => person );
Monitor.Exit( _lock );
}
}
}
c# implementation
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading;
namespace PhoneBook {
public struct Person {
public Person( string name, string phoneNumber ) {
Name = name;
PhoneNumber = phoneNumber;
}
public string Name { get; }
public string PhoneNumber { get; }
}
public class Phonebook {
private readonly object _lock = new object();
private readonly ConcurrentDictionary<string, Person> _indexByName;
private readonly ConcurrentDictionary<string, Person> _indexByPhoneNumber;
public Phonebook( IEnumerable<Person> people ) {
_indexByName = new ConcurrentDictionary<string, Person>();
_indexByPhoneNumber = new ConcurrentDictionary<string, Person>();
foreach ( var p in people ) {
_indexByName.AddOrUpdate( p.Name, p, (s, pers) => pers );
_indexByPhoneNumber.AddOrUpdate( p.PhoneNumber, p, (s, pers) => pers );
}
}
public Person? LookupByName( string name ) {
Person pers;
var res = _indexByName.TryGetValue( name, out pers );
return res ? (Person?)pers : null;
}
public Person? LookupByPhoneNumber( string phoneNumber ) {
Person pers;
var res = _indexByPhoneNumber.TryGetValue( phoneNumber, out pers );
return res ? (Person?)pers : null;
}
public void AddPerson( Person person ) {
Monitor.Enter( _lock );
var res1 = LookupByName( person.Name );
var res2 = LookupByPhoneNumber( person.PhoneNumber );
if ( res1 != null && res2 != null ) {
Monitor.Exit( _lock );
return;
}
Person p;
if ( res1 != null ) {
_indexByPhoneNumber.TryRemove( ((Person)res1).PhoneNumber, out p );
_indexByPhoneNumber.TryAdd( person.PhoneNumber, person );
}
if ( res2 != null ) {
_indexByName.TryRemove( ((Person)res2).Name, out p );
_indexByName.TryAdd( person.Name, person );
}
_indexByName.AddOrUpdate( person.Name, person, (s, pers) => person );
_indexByPhoneNumber.AddOrUpdate( person.PhoneNumber, person, (s, pers) => person );
Monitor.Exit( _lock );
}
}
}
Hi roman
In AddPerson method, you used "TryRemove, TryAdd" then AddOrUpdate.
It seems like duplicate for me. why did you use remove/add & addorupdate at the same time?
package com.careercup.phonebook;
public class MainEx {
public static void main(String[] args) {
Person person1 = new Person("jmk", "8743562734");
Person person2 = new Person("emmt", "3332322343");
Person person3 = new Person("eclipse", "654345678");
Phonebook pb = new Phonebook();
pb.addPerson(person1, person2, person3);
System.out.println(pb.lookUpByName("jmk"));
}
}
package com.careercup.phonebook;
import java.util.Map.Entry;
import java.util.concurrent.ConcurrentHashMap;
public class Phonebook {
private ConcurrentHashMap<String, Person> _db = new ConcurrentHashMap<String, Person>();
public Phonebook() {
}
public Person lookUpByName(String name) {
for (Entry<String, Person> e : _db.entrySet()) {
if (e.getValue().getName().equals(name)) {
return e.getValue();
}
}
return null;
}
public Person lookUpByPhoneNumber(String phoneNumber) {
return _db.get(phoneNumber);
}
public synchronized void addPerson(Person person) {
_db.put(person.getPhoneNumber(), person);
}
public synchronized void addPerson(Person... persons) {
for (Person person : persons) {
_db.put(person.getPhoneNumber(), person);
}
}
}
package com.careercup.phonebook;
public class Person {
private String name;
private String phoneNumber;
public Person() {
super();
}
public Person(String name, String phoneNumber) {
super();
this.name = name;
this.phoneNumber = phoneNumber;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getPhoneNumber() {
return phoneNumber;
}
public void setPhoneNumber(String phoneNumber) {
this.phoneNumber = phoneNumber;
}
@Override
public String toString() {
return "Person [name=" + name + ", phoneNumber=" + phoneNumber + "]";
}
}
Thanks for the responses. @zr.roman, I was wondering why you added TryRemove and TryAdd statements with If conditions. Because, the AddOrUpdate statements at the end will do the required updates. why we need to remove and add the items explicitly if we doing AddOrUpdate?
Yes, good question, and frankly, my first version was exactly as you described in your question: the method "AddPerson" contained only 2 method calls - _indexByName.AddOrUpdate and _indexByPhoneNumber.AddOrUpdate.
But - tests failed!
The reason is the following:
imagine, the phone book contains the entry "Tom, 123-456-789", and you try to insert entry "Tom, (+1)123-456-789", i.e. the update of the existing record (phone number should be updated).
The method _indexByName.AddOrUpdate works OK: it detects that the key "Tom" already exists in _indexByName, and it overwrites the whole record.
But method _indexByPhoneNumber.AddOrUpdate is a problem. Because before calling this method, _indexByPhoneNumber contains record "123-456-789, {Tom}" and when you put "(+1)123-456-789, {Tom}" into method, it detects that there is no key "(+1)123-456-789" and creates a new entry "(+1)123-456-789, {Tom}", so _indexByPhoneNumber will contain two entries:
"(+1)123-456-789, {Tom}"
and
"123-456-789, {Tom}",
and it is incorrect, because we intended to update the record, not to insert another one. So, I explicitly remove the old record and insert the new one, which is actually the update of the removed record.
The same (mirror situation) is with _indexByName, when you try to update the name of a person, while the phone number is not changed (I assume that there are no 2 or more persons with the same phone number, and it makes sense).
So, I added TryRemove and TryAdd statements with If conditions.
struct Person
{
string name;
string phno;
Person()
{
}
Person(string x, string y)
{
name=x;
phno=y;
}
};
class PhoneBook
{
std::map<std::string, std::string> phoneBook;
public:
PhoneBook(std::vector<struct Person>& p)
{
for(size_t i=0; i<p.size(); i++)
{
phoneBook.insert(std::pair<string,string>(p[i].name, p[i].phno));
}
}
Person LookUpByName(string name)
{
map<string,string>::iterator it;
Person p;
it = phoneBook.find(name);
if(it != phoneBook.end())
{
p.name = it->first;
p.phno = it->second;
}
return p;
}
Person LookUpByPhNo(string phno)
{
map<string,string>::iterator it;
Person p;
for(it= phoneBook.begin(); it!= phoneBook.end(); ++it)
{
if(it->second == phno)
{
p.name = it->first;
p.phno= it->second;
}
}
return p;
}
void AddPerson(Person p)
{
map<string,string>::iterator it;
std::lock_guard<std::mutex> locker(mu);
it= phoneBook.find(p.name); //Case of updation
if(it != phoneBook.end())
it->second = p.phno;
phoneBook.insert(std::pair<string,string>(p.name, p.phno));
}
};
struct Person
{
string name;
string phno;
Person()
{
}
Person(string x, string y)
{
name=x;
phno=y;
}
};
class PhoneBook
{
std::map<std::string, std::string> phoneBook;
public:
PhoneBook(std::vector<struct Person>& p)
{
for(size_t i=0; i<p.size(); i++)
{
phoneBook.insert(std::pair<string,string>(p[i].name, p[i].phno));
}
}
Person LookUpByName(string name)
{
map<string,string>::iterator it;
Person p;
it = phoneBook.find(name);
if(it != phoneBook.end())
{
p.name = it->first;
p.phno = it->second;
}
return p;
}
Person LookUpByPhNo(string phno)
{
map<string,string>::iterator it;
Person p;
for(it= phoneBook.begin(); it!= phoneBook.end(); ++it)
{
if(it->second == phno)
{
p.name = it->first;
p.phno= it->second;
}
}
return p;
}
void AddPerson(Person p)
{
map<string,string>::iterator it;
std::lock_guard<std::mutex> locker(mu);
it= phoneBook.find(p.name); //Case of updation
if(it != phoneBook.end())
it->second = p.phno;
phoneBook.insert(std::pair<string,string>(p.name, p.phno));
}
};
class PhoneBook
{
shared_timed_mutex write;
typedef unordered_map<string, std::shared_ptr<Person>> PersonMap;
PersonMap _map;
public:
PhoneBook()
{
}
void addPerson(const Person & p)
{
lock_guard<shared_timed_mutex> w(write);
shared_ptr<Person> s (new Person(p));
_map[p.name] = s;
_map[p.phone] = s;
}
string lookupByPhone(string phone)
{
return lookup(phone).name;
}
string lookupByName(string name)
{
return lookup(name).phone;
}
private:
Person lookup(string key)
{
shared_lock<shared_timed_mutex> r(write);
PersonMap::iterator i = _map.find( key );
if (_map.end() == i) {
Person pp;
return pp;
}
return *(*i).second.get();
}
};
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
class Person{
String phoneNumber;
String personName;
public Person(String phoneNumber, String personName) {
super();
this.phoneNumber = phoneNumber;
this.personName = personName;
}
@Override
public String toString() {
return "Person [phoneNumber=" + phoneNumber + ", personName=" + personName + "]";
}
public String getPhoneNumber() {
return phoneNumber;
}
public void setPhoneNumber(String phoneNumber) {
this.phoneNumber = phoneNumber;
}
public String getPersonName() {
return personName;
}
public void setPersonName(String personName) {
this.personName = personName;
}
}
public class PhoneBook {
private ConcurrentHashMap<String, Person> phoneNumberMap;
private ConcurrentHashMap<String, Person> personNameMap;
private Lock l ;
public PhoneBook(List<Person> person){
phoneNumberMap = new ConcurrentHashMap<String, Person>();
personNameMap = new ConcurrentHashMap<String, Person>();
l = new ReentrantLock();
for(Person p: person){
AddPerson(p);
}
}
public void AddPerson(Person p){
if(phoneNumberMap.containsKey(p.getPhoneNumber()) && personNameMap.containsKey(p.getPersonName())){
//already presnt
return ;
}
try{
l.lock();
if(phoneNumberMap.containsKey(p.getPhoneNumber())){
Person oldPerson = phoneNumberMap.get(p.getPhoneNumber());
phoneNumberMap.put(p.getPhoneNumber(), p);
personNameMap.remove(oldPerson.getPersonName());
personNameMap.put(oldPerson.getPersonName(), p);
}
else if(personNameMap.containsKey(p.getPhoneNumber())){
Person oldPerson = personNameMap.get(p.getPhoneNumber());
personNameMap.put(p.getPhoneNumber(), p);
phoneNumberMap.remove(oldPerson.getPersonName());
phoneNumberMap.put(oldPerson.getPersonName(), p);
} else{
personNameMap.put(p.getPersonName(), p);
phoneNumberMap.put(p.getPhoneNumber(), p);
}
}finally{
l.unlock();
}
}
public Person lookupByName(String name){
return personNameMap.get(name);
}
public Person lookupByPhonenumber(String phoneNumber){
return phoneNumberMap.get(phoneNumber);
}
}
TRIE?
- afrika November 10, 2015