CareerCup

What is the scenario? Are we going to query it later? What kind of queries?

Tries...

We use general tree kind of structure,in which root node is does not contain any any data but it contain pointers between 1 to 9, depending upon numbers distribution.For example suppose India have numbers starting from 9,8,7 then root node contain 3 pointer pointing the sub trees each containing a int data point and at max 10 pointers.
search : O(1);
insert : O(1);
delete : O(1);
If the number can also have different countries then at root node we add an additional layer which tell information's about country code.
this does not increase complexity.

Since there are no requirements other than storing the phone numbers in a space efficient way, I'd answer this question by saying compress them using a standard compression algorithm such as DEFLATE.

Ternary search tree (trie)

Trie!

if u only want to store and frequency of querying is less then u can use B tree..

the efficient way to do this is to use HASH algorithm. use any simple algorithm modular division. implement it using a singly linked list. the order for serching and storing will be in constant time i.e O(1) time.

Step 1 : Sort the million phone numbers.
Step 2 : Store the first phone number at location 0 and at all the subsequent locations just store the difference between the current number and the previous number.

eg : hypothetical sorted phone numbers : 55555, 55556, 55557, 55559...
get stored as 55555, 1, 1, 2...

Look up : O(n)
Insertion: O(n)
Deletion: O(n2)
Space conserved as any digit at any level would only be stored once. With 1 million numbers there is a likely hood that a particular sequence is repeated more often for example say could be numbers in a particular series :
65423444444
65423444445
...
65423444449
Please find below the code that implements the idea.

#include "stdafx.h"
#include <iostream>
#include <memory>

struct All_0_to_9_Node;
typedef All_0_to_9_Node* AllDigitPtr ;
typedef std::unique_ptr<All_0_to_9_Node> AllDigitUniquePtr;

/*
Representing a number something like this : 
If there are million number there is a likely hood that each number is going to be closer to the other one 
in which case lot of these entities would get reused and further memory would only be allocated if there number in that 
direction else it would be an empty pointer.
For example for a number like : 6043.......1 The representation would look something like below

[0]-> nullptr
[1]-> nullptr
[2]-> nullptr					[0]-> nullptr
[3]-> nullptr					[1]-> nullptr  [0]-> nullptr
[4]-> nullptr					[2]-> nullptr  [1]-> nullptr
[5]-> nullptr					[3]-> nullptr  [2]-> nullptr								 [0]-> nullptr
[6]------------>[0]------------>[4]----------> [3]--------->	....................		 [1]-> nullptr
[7]-> nullptr	[1]-> nullptr	[5]-> nullptr  [4]-> nullptr								 [2]-> nullptr
[8]-> nullptr	[2]-> nullptr	[6]-> nullptr  [5]-> nullptr								 [3]-> nullptr
[9]-> nullptr	[3]-> nullptr	[7]-> nullptr  [6]-> nullptr								 [4]-> nullptr
				[4]-> nullptr	[8]-> nullptr  [7]-> nullptr								 [5]-> nullptr
				[5]-> nullptr	[9]-> nullptr  [8]-> nullptr								 [6]-> nullptr
				[6]-> nullptr				   [9]-> nullptr								 [7]-> nullptr
				[7]-> nullptr																 [8]-> nullptr
				[8]-> nullptr																 [9]-> nullptr
				[9]-> nullptr
*/
typedef struct NoNode{
	AllDigitPtr pNextDigitList; 
	short nNo;
	NoNode():nNo(0),pNextDigitList(nullptr){}
	NoNode(short no,AllDigitPtr pNextDigit):nNo(no),pNextDigitList(pNextDigit){}
	~NoNode(){
		if(nullptr != pNextDigitList)
		{
			delete pNextDigitList;
			pNextDigitList= nullptr;
		}
	}
}NoNode;

typedef NoNode* NoNodePtr ;

typedef struct All_0_to_9_Node {
	NoNodePtr m_NoPtrs[10];
	All_0_to_9_Node(){
		for(int i=0;i<10;i++)
		{
			m_NoPtrs[i]=nullptr;
		}
	}

	~All_0_to_9_Node(){
		for(int i=0;i<10;i++)
		{
			if(nullptr != m_NoPtrs[i])
			{
				delete m_NoPtrs[i];
				m_NoPtrs[i]=nullptr;
			}
		}
	}

	bool IsValidDigit(short nNo){return (nNo >= 0 && nNo <= 9) ? true : false;}

	/*
		Checks if the digit is already present in current node
	*/
	bool IsDigitPresent(short nNo){
		if( IsValidDigit(nNo) && (nullptr != m_NoPtrs[nNo])) return true;
		return false;
	}
	/*
	returns true if already present and if not present would add it. 
	would return false if the number is not already present.
	*/
	bool AddDigit(short nNo, bool bIsLastDigit= false){

		if(!IsValidDigit(nNo)) { return false;}
		if(IsDigitPresent(nNo)) {return true;}
		m_NoPtrs[nNo]= CreateDigitNode(nNo,bIsLastDigit);
		return true;
	}
	/*
		Creates a node for the particular digit in question
	*/
	NoNodePtr CreateDigitNode(short nNo, bool bIsLastDigit){

		AllDigitPtr pNextNoPtr = bIsLastDigit? nullptr:new All_0_to_9_Node();
		return new NoNode(nNo,pNextNoPtr);
	}
	/*
		Node insertion works very simple. It picks up the current digit and tries adding the same. 
		If it's already present then it won't add the same else a new one would get created. 
		Else it would chip of the number just added and the pass the remianing number to the corresponding 
		digits child node to get added. If would stop adding any further then the length of the number reduces to 1
		return true if able to add the number and false otherwise.
	*/
	bool InsertNo(const std::string& strMobileNo){
		short nNo = strMobileNo.at(0) - 48;

		if(AddDigit(nNo,strMobileNo.length()==1? true : false))
		{
			if(strMobileNo.length() > 1)
			{
				std::string strRemainingNo(strMobileNo.substr(1));
				m_NoPtrs[nNo]->pNextDigitList->InsertNo(strRemainingNo);
			}
			return true; // done adding the mobile number;
		}
		return false;
	}
	/*
		Looks up for the number one digit at a time. It would keep pivoting into the appropriate hive for he remaining part of the 
		number. 
	*/
	bool FindNumber(const std::string& strMobileNo){
		short nNo = strMobileNo.at(0) - 48;
		if(IsDigitPresent(nNo))
		{
			if(strMobileNo.length() == 1) return true;
			std::string strRemainingNo(strMobileNo.substr(1));
			return m_NoPtrs[nNo]->pNextDigitList->FindNumber(strRemainingNo);
		}
		return false;
	}

}All_0_to_9_Node;


int _tmain(int argc, _TCHAR* argv[])
{
	AllDigitUniquePtr pRootNode(new All_0_to_9_Node());

	pRootNode->InsertNo("23412233355");
	pRootNode->InsertNo("23435523343");
	bool bRetVal = pRootNode->FindNumber("23435523341");
	std::cout << "23435523341 : Found =" << std::boolalpha<< bRetVal<<std::endl;
	bRetVal =pRootNode->FindNumber("23412233355");
	std::cout << "23412233355 : Found =" << std::boolalpha<< bRetVal<<std::endl;
	return 0;
}

Well the question really comes down to removing redundancy since most phone numbers share a lot in common.

If we take north america for example we realize that the phone number consists of the following:

Area Code - 3 digits.
Prefix - 3 digits
Suffix - 4 digits.

so the numbers:
512 - 321 - 1200
512 - 321 - 1201
512 - 321 - 1202
512 - 321 - 1203
.....
512 - 321 - 1209

share lots in common.

So we can create one table for Area Code, one table for prefixs another table for the suffix.

So the TelephoneNumber table would consist of a link to the Area Code table, a link to the Prefix table and an entry for the suffix and the last digit. Then if I wanted to find the number 512 - 321 - 1209 I would do:

Join the area code table for 512, then the suffix table for 312 and then find the row which has a suffix of 120 and last digit of 9.

Assuming the phone number is of format:
+xxx-xxx-xxx-xxxx (13 digits), So theoretically it can have 10^13 numbers which is 10 trillion possibilities, so given only 1 million numbers, but it will be very sparse.

Choose a hash function, something like add all digits (call it "s") and choose the last 5 digits of the number and add "s" to this number.

Now, based on the hash function, we will be able to map each number to a location in an 100,000 sized array.
When we have a collision, then we can store the number in a linkedList which can keep growing with load factor.

So search, insertion and deletion would be O(load factor).

we can use a array[100], and each element contain two field, one is a integer, say(86) is China and (1) is USA, another field can be a root of B-Tree, storing all the tele numbers of the country if the number is international.
Time complexity: O(logn) for delete , insert and query