Bloomberg Interview Questions/Q 9

From Software Engineers Wiki
Jump to: navigation, search

Royal titles consist of name followed by space and a Roman numeral. Example: Richard IV. The Roman numeral in the title can go to L (50). You are given the roman numerals from 1 to 10:

I II III IV V VI VII VIII IX X. And you are given the 10 multiples up to 50: XX XXX IL L. Numbers between 10 and 50 that are not given can be formed from 10 multiples and a numeral b/w 1 and 9.

Example: 48 is XLVIII wichi is XL (40) plus VIII (8).

You are given an array of Roman titles sort it as follows: sort it on the name unless the names are equal, in which case you have to sort it on the ordinal of the numerals.

Examples:

Henry II, Edward VIII => Eward VII, Henry II
Richard V, Richard II, Richard X => Richard II, Richard V, Richard X

Answer 1

Simple approach is to use std::sort() with custom comparator. The comparator compares first words as regular string. Then it compares the second works based on the translation of Roman numerals. The problem with this approach is that, it translate same string multiple times, and the performance would be bad as number of input string grows.

The comparator.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cctype>
#include <cstring>

unsigned int roman_to_int(const char *str, const char **end)
{
        unsigned int val = 0;
        unsigned int cur, pending;

        pending = 0;

        while (*str != '\0') {
                switch (toupper(*str)) {
                case 'I' :
                        cur = 1;
                        break;
                case 'V' :
                        cur = 5;
                        break;
                case 'X' :
                        cur = 10;
                        break;
                case 'L' :
                        cur = 50;
                        break;
                default :
                        *end = str;
                        return val + pending;
                };

                if (pending) {
                        if (cur > pending) {
                                val += cur - pending;
                                pending = 0;
                        } else {
                                val += pending;
                                pending = cur;
                        }
                } else {
                        pending = cur;
                }
                ++str;
        }

        *end = str;
        return val + pending;
}

class RoyalComparator {
public:
        /* comparator
         * return true if first argument is less than (ordered before) second.
         */
        bool operator() (const std::string &left, const std::string &right) {
                const char *str_left = left.c_str();
                const char *str_right = right.c_str();
                unsigned int val_left, val_right;

                while (true) {
                        /* first difference */
                        if (*str_left != *str_right)
                                return *str_left < *str_right;

                        /* end of the string : two strings are same */
                        if (*str_left == '\0')
                                return false;

                        /* if space, time to look at roman numeral */
                        if (*str_left == ' ')
                                break;

                        ++str_left;
                        ++str_right;
                }

                /* skip spaces */
                while (*++str_left == *++str_right) {
                        if (*str_left == '\0')
                                return false;
                        if (*str_left != ' ')
                                break;
                }

                /* compare roman numeral */
                val_left = roman_to_int(str_left, &str_left);
                val_right = roman_to_int(str_right, &str_right);
                if (val_left != val_right)
                        return val_left < val_right;

                return strcmp(str_left, str_right) < 0;
        }
};

Test program.

int main(void)
{
        std::vector<std::string> names = {
                "Richard V", "Richard IV", "Richard IX",
                "Henry II", "Edward VIII", "Edward L",
                "Richard",
        };

        for (auto ip = names.begin(); ip != names.end(); ++ip)
                std::cout << *ip << std::endl;

        std::sort(names.begin(), names.end(), RoyalComparator());

        std::cout << std::endl;

        for (auto ip = names.begin(); ip != names.end(); ++ip)
                std::cout << *ip << std::endl;
}

Test result:

Richard V
Richard IV
Richard IX
Henry II
Edward VIII
Edward L
Richard

Edward VIII
Edward L
Henry II
Richard
Richard IV
Richard V
Richard IX

Answer 2

To speed up the comparison, for each string, it can create a string that can be directly compared. For example, for "Richard V", it can have a string "Richard 5". Then the comparator compares these converted strings rather than original strings.

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox