Bloomberg LP Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
You don't have to do anything actually... I, V, L and X are in already sorted :)
public static void main(String[] args) {
List<String> kings = Arrays.asList(new String[]{"Edward VII","Richard II","Richard III", "Henry II","Richard X"});
Collections.sort(kings);
for(String king: kings)
System.out.print(king+" ");
}
Sorry the question as posted first was missing the first line. Here it is complete:
* 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).
* <p>
* 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
#include<bits/stdc++.h>
using namespace std;
int romanToInt(string s){
int res=0;
for(int i=0;i<s.length();++i){
if(s[i]=='L')
res+=50;
else if(s[i]=='X'){
if(i<s.length()-1 && (s[i+1]=='L') )
res-=10;
else
res+=10;
}
else if(s[i]=='V')
res+=5;
else if(s[i]=='I'){
if(i<s.length()-1 && (s[i+1]=='X' || s[i+1]=='V') )
res--;
else
res++;
}
}
return res;
}
bool comp(string a,string b){
istringstream isA(a);
istringstream isB(b);
string splitStringA[2],splitStringB[2];
string temp;
int i=0;
while(isA>>temp)
splitStringA[i++]=temp;
i=0;
while(isB>>temp)
splitStringB[i++]=temp;
if(splitStringA[0]<splitStringB[0])
return true;
else if(splitStringA[0]>splitStringB[0])
return false;
else
return romanToInt(splitStringA[1])<=romanToInt(splitStringB[1]);
}
int main(){
string names[6]={"Richard V","Henry VI","Edward II","Richard XXV","Henry IX","Edward LII"};
sort(names,names+6,comp);
for(int i=0;i<6;++i)
cout<<names[i]<<endl;
return 0;
}
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;
public class NameComparator implements Comparator<String> {
public NameComparator() {
super();
init();
}
public int compare(String name1, String name2) {
String[] name1Split = name1.split(" ");
String[] name2Split = name2.split(" ");
if (name1Split[0].compareTo(name2Split[0]) == 0) {
int roman1 = convertRomanToInt(name1Split[1]);
int roman2 = convertRomanToInt(name2Split[1]);
return (roman1 == roman2 ? 0 : (roman1 > roman2 ? 1 : -1));
} else {
return name1Split[0].compareTo(name2Split[0]);
}
}
private Map<Character, Integer> intForRoman = new HashMap<>();
private void init() {
intForRoman.put('I', 1);
intForRoman.put('V', 5);
intForRoman.put('X', 10);
intForRoman.put('L', 50);
}
private int convertRomanToInt(String roman) {
char[] arr = roman.toCharArray();
int total = 0;
int maxNumeral = 0;
for (int i = arr.length - 1; i >= 0; i--) {
int val = intForRoman.get(arr[i]);
if (val >= maxNumeral) {
maxNumeral = val;
total += val;
} else {
total -= val;
}
}
return total;
}
public static void main(String[] args) {
NameComparator romanComparator = new NameComparator();
TreeSet<String> kingName = new TreeSet<>(romanComparator);
kingName.add("Henry II");
kingName.add("Edward VII");
kingName.add("Henry I");
kingName.add("Edward X");
System.out.println(kingName);
}
}
//
// 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 which 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 => Edward VII, Henry II
// Richard V, Richard II, Richard X => Richard II,
// Richard V, Richard X
//
// -- haldokan August 12, 2016
// Bloomberg LP Software Analyst C++
//
// Run with VM arguments -ea to enable assert testing
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//
import java.util.*;
class RomanTitle implements Comparable<RomanTitle> {
String name;
String rank;
/*
* In a production environment, an exception would be thrown
* for an ill formed Roman Title.
*
*/
public RomanTitle(String romanTitle) {
String[] splited = romanTitle.split("\\s");
this.name = splited[0];
this.rank = splited[1];
}
public String toString() {
return name+" "+rank;
}
/**
* This solution shows the ability to easily test between
* Roman Numberals 1 thru 10. A slightly more extensive
* algorithm would be needed to do 1 thru 50. But this basic
* design conveys the essence of this problem demonstrating
* an effective use of built-in java.io.* classes to resolve
* the problem in a manner that's easily readable.
*
* In other words: All the logic needed to figure out to
* compare Roman Numerals between 1 thru 50 can be either
* concentrated in this compareTo() method or imported from
* a library dedicated to comparing Roman Numerals from here.
*
* Everything else would remain the same!
*
*/
static String ranks = "I II III IV V VI VII VIII IX X";
@Override
public int compareTo(RomanTitle o) {
if ( name.compareToIgnoreCase(o.name) != 0 )
return name.compareToIgnoreCase(o.name);
else {
int r1 = ranks.indexOf(rank);
int r2 = ranks.indexOf(o.rank);
return r1 - r2;
}
}
}
public class LPMain003 {
static String[] sortNames(String[] romanTitles) {
Vector<RomanTitle> titles = new Vector<RomanTitle>();
for( String title : romanTitles )
titles.add(new RomanTitle(title));
Collections.sort(titles);
String[] results = new String[titles.size()];
int i = 0;
for( RomanTitle title : titles )
results[i++] = title+"";
return results;
}
public static void main(String[] args) {
String[] names1 = { "Henry II", "Edward VIII" };
String[] test1 = { "Edward VIII", "Henry II" };
String[] names2 = { "Richard V", "Richard II", "Richard X" };
String[] test2 = { "Richard II", "Richard V", "Richard X" };
assert Arrays.equals(sortNames(names1), test1);
assert !Arrays.equals(sortNames(names1), names1);
assert Arrays.equals(sortNames(names2), test2);
assert !Arrays.equals(sortNames(names2), names2);
}
}
/*
* If you were pressed for time and did not have the
* luxury to implement a really cool Roman Numerals to
* Decimal evaluator, you could use this very same
* technique just take the time to fill in all the values
* between 1 thru 50 in Roman Numerals.
*
* ;)
*
*/
static String ranks =
"I II III IV V VI VII VIII IX X" +
"XI XII XIII XIV XV XVII XVIII XIX XX" +
"XXI XXII XXIII XXIV XXV XXVI XXVII XXVIII XXIX XXX" +
"XXXI XXXII XXXIII XXXIV XXXV XXXVI XXXVII XXXVIII XXXIX XXXX" +
"XXXXI XXXIII XXXIIII XXXXIV XXXXV XXXXVI XXXXVII XXXXVIII XXXXIX XXXXX";
@Override
public int compareTo(RomanTitle o) {
if ( name.compareToIgnoreCase(o.name) != 0 )
return name.compareToIgnoreCase(o.name);
else {
int r1 = ranks.indexOf(rank);
int r2 = ranks.indexOf(o.rank);
return r1 - r2;
}
}
//
//
// Given a string find biggest palindrome substring. For example for
// given string "AABCDCBA" output should be "ABCDCBA" and for given string
// "DEFABCBAYT" output should be "ABCBA".
//
// -- Preeti May 24, 2016 in United Kingdom,
// Bloomberg LP Interview Question for Financial Software Developers
//
// Run with VM arguments -ea to enable assert testing
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//
public class LPMain004 {
/**
*
* int findMidpoint(String text)
*
* I admit, it took a while longer than average to figure out
* the right way to go about this. So in an interview situation,
* a question like this might take me a bit longer. Bit with all
* such seemingly difficult talks, when you take the time to break
* the task into smaller tasks, the ideal solution sort of
* presents itself on it's own. In this case, taking the time to find
* the mid point first, then figuring out how big the palindrome is
* made this simple solution possible and understandable.
*
* @param text of string to search
* @return location of midpoint
*/
static int findMidpoint(String text) {
// First reject any string less than 3 characters
if (text.length() > 2) {
// second try to find the midpoint
for (int x = 1; x < text.length() - 1; x++) {
char c1 = text.charAt(x - 1);
char c2 = text.charAt(x + 1);
if (c1 == c2)
return x;
}
}
return -1;
}
/**
*
* int findPalindrome(String text)
*
* This method merely takes the midpoint and then checks successive
* characters from the midpoint until the end of the string is
* reached or the characters being compared are no longer the same.
*
* @param text of string to search
* @return text of the palindrome
*/
static String findPalindrome(String text) {
// First: Find midpoint if there is one ...
int x = findMidpoint(text);
if (x == -1)
return "";
// using the midpoint, find out how big the palindrome is
String palindrome = text.charAt(x) + "";
int offset = 1;
while (true) {
try {
char c1 = text.charAt(x - offset);
char c2 = text.charAt(x + offset);
if (c1 != c2)
break;
palindrome = c1 + palindrome + c2;
offset++;
} catch (IndexOutOfBoundsException e) {
break;
}
}
return palindrome;
}
public static void main(String[] args) {
String test1 = "AABCDCBA";
String results1 = "ABCDCBA";
String test2 = "DEFABCBAYT";
String results2 = "ABCBA";
assert findPalindrome(test1).equals(results1);
assert !findPalindrome(test1).equals(test1);
assert findPalindrome(test2).equals(results2);
assert !findPalindrome(test2).equals(test2);
}
}
Replace the roman number into an integer and sort the vector(below is simple implementation of roman to int)
int romanToInt(string s)
{
int n=s.size();
int q,w,sum=0,e=0;
for(int i=0;i<n;i++)
{
if(s[i]=='X')q=10;
else if(s[i]=='I')q=1;
else if(s[i]=='L')q=50;
else if(s[i]=='D')q=500;
else if(s[i]=='C')q=100;
else if(s[i]=='V')q=5;
else q=1000;
if(i+1<n){
if(s[i+1]=='X')w=10;
else if(s[i+1]=='I')w=1;
else if(s[i+1]=='L')w=50;
else if(s[i+1]=='D')w=500;
else if(s[i+1]=='C')w=100;
else if(s[i+1]=='V')w=5;
else w=1000;}else w=0;
if(q>=w)sum+=q;
if(q<w)sum-=q;
}
return sum;
}
- frestuc August 23, 2016