Efficient Grouping of a phone number for better memoriazation

Problem: http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-76


You are given a phone number.  To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example, 000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.
• Usual: A group in which all the digits are distinct. For example, 123 or 90.



The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups)
Divide the number into groups such that the quality is maximized.



For example given a phone number 123354401099


Can be grouped as (12)(33)(544)(010)(99) or (12)(335)(44)(010)(99) whose quality score is 6.
We can define a function f which will give the quality score of a grouping as below, 


Where Sn is Phone number of length n and S[n] is the nth digit of phone number S 

Solution:
#include <stdio.h>
#include <string.h>
#include <string>

using namespace std;

struct Score{
int numBest, numGood;
string group;
};

Score scoreOf3(const char *str){
Score r = {0, 0, ""};

if(str[0] == str[1]){
if(str[1] == str[2]){
r.numBest = 1;
}else{
r.numGood = 1;
}
}else if(str[0] == str[2]){
if(str[1] == str[2]){
r.numBest = 1;
}else{
r.numGood = 1;
}
}else if(str[1] == str[2]){
r.numGood = 1;
}

r.group = string("(") + str[0] + str[1] + str[2] + ")";
return r;
}


Score maxScoredGroup(const char *str){

Score r = {0, 0, ""};

int len = strlen(str);

if(len == 0){
;
}else if(len == 1){
//invalid
r.numBest = r.numGood = -1;
}else if(len == 2){
r.numBest = str[0] == str[1];
r.group = string("(") + str + ")";
}else if(len == 3){
r = scoreOf3(str);
}else{
Score r1 = maxScoredGroup(str + 2);
Score r2 = maxScoredGroup(str + 3);
Score r3 = scoreOf3(str);

if(r1.numBest != -1){
r1.numBest += str[0] == str[1];
r1.group = string("(") + str[0] + str[1] + ")" + r1.group;
}

if(r2.numBest != -1){
r2.numBest += r3.numBest;
r2.numGood += r3.numGood;
r2.group = r3.group + r2.group;

}

int s1 = r1.numBest == -1 ? -1 : 2 * r1.numBest + r1.numGood;
int s2 = r2.numBest == -1 ? -1 : 2 * r2.numBest + r2.numGood;

r = s1 >= s2 ? r1 : r2;
}

return r;
}

int main(){

char phone[] = "123354401099";

Score s = maxScoredGroup(phone);

printf("Group = %s\nScore = %d", s.group.c_str(), s.numBest == -1 ? -1 : 2 * s.numBest + s.numGood);
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s