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;

}

### Like this:

Like Loading...

*Related*