Bloomberg LP Interview Question
Financial Software DevelopersCountry: United Kingdom
Interview Type: In-Person
void palindrome(char *str)
{
int i = 1;
int count = 0;
while (str[i] != '\0')
{
if (str[i - 1] == str[i + 1]) {
int j = i, k = i;
while (str[j] == str[k] && j >= 0 && str[k] != '\0')
{
count++;
k++;
j--;
}
j++;
k--;
while (j <= k)
{
cout << str[j];
j++;
}
i = k;
}
else
i++;
cout << endl;
}
}
int main()
{
char *s = "ABCDCBAAA";
char *s1 = "DEFABCBAYT";
palindrome(s);
palindrome(s1);
return 0;
}
// Time :O(n2) , Space :O(n2)
public int longestPalindromeSubString(String str) {
if (null == str || str.length() == 0)
return 0;
if (str.equals(new StringBuilder(str).reverse().toString()))
return str.length();
int t[][] = new int[str.length()][str.length()];
for (int i = 0; i < str.length(); i++) {
t[i][i] = 1;
}
for (int l = 2; l <= str.length(); l++) {
for (int i = 0; i < str.length() - l + 1; i++) {
int j = i + l - 1;
if (str.charAt(i) == str.charAt(j)) {
if (l == 2) {
t[i][j] = 2;
} else {
t[i][j] = 2 + t[i + 1][j - 1];
}
} else {
t[i][j] = Math.max(t[i + 1][j], t[i][j - 1]);
}
}
}
System.out.println(t[0][str.length() - 1]);
return t[0][str.length() - 1];
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
string input = "DEFABCBAYT";
int[] arr = new int[input.Length - 1];
for (int x = 1; x < input.Length ; x++)
{
arr[x-1] = (int)input[x] - (int)input[x - 1];
}
int sum = 0;
int i, j, k;
for ( i=arr.Length;i>=1;i--)
{
for ( j = 0; j <= arr.Length - i; j++)
{
sum = 0;
for ( k = j; k < j+i-1; k++)
{
sum += arr[k];
}
if (sum == 0)
{
Console.WriteLine(i.ToString() + " " + j.ToString());
Console.ReadLine();
return;
}
}
}
}
}
}
{using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
string input = "DEFABCBAYT";
//check(input);
Console.WriteLine(checkinput(input));
Console.ReadLine();
}
static string checkinput(string input)
{
int[] arr = new int[input.Length - 1];
for (int x = 1; x < input.Length; x++)
{
arr[x - 1] = (int)input[x] - (int)input[x - 1];
}
int sum = 0;
int i, j, k;
for (i = arr.Length; i >= 1; i--)
{
for (j = 0; j <= arr.Length - i; j++)
{
sum = 0;
for (k = j; k < j + i - 1; k++)
{
sum += arr[k];
}
if (sum == 0)
{
return input.Substring(j,i);
}
}
}
return "";
}
}
}
}
public class LongestPallindrome {
public static void main(String[] args) {
String str = "DEFABCBAYT";
int l =str.length();
if(str.trim().length()==0)
{
System.out.println("String is empty");
System.exit(0);
}
String maxPal = SubString(str,l);
if(maxPal != null)
System.out.println(maxPal);
else
System.out.println("No Pallindrome in String");
}
public static String SubString(String str, int l) {
String str1 = "",str2 = "";
int max =0,l1 = 0;
for(int i =-1;i<l-1;i++)
{
str1 ="";
for(int j =i+1;j<l;j++){
str1 = str1+str.charAt(j);
l1 = str1.length();
if(pallindrome(str1,l1) )
{
if(max<l1)
{
max=l1;
str2 = str1;
}
}
}
}
if(max >0)
return str2;
else
return null;
}
public static boolean pallindrome(String str1,int l) {
String str2 = "";
for(int i= l-1;i>=0;i--)
{
str2= str2+str1.charAt(i);
}
if(str2.equals(str1))
return true;
else
return false;
}
}
string FindBiggestPalindromeSubstring(string const& s)
{
string tmp, palindrome;
for (size_t i = 1; i < s.size() - 1; i++) {
if (s[i] == s[i + 1]) { // Even palindrome
for (size_t j = i, k = i + 1; j >= 0; j--, k++) {
if (s[j] == s[k]) {
tmp = s.substr(j, k - j + 1);
if (tmp.size() > palindrome.size())
palindrome = tmp;
} else
break;
}
} else if (s[i - 1] == s[i + 1]) { // Odd palindrome
for (size_t j = i - 1, k = i + 1; j >= 0; j--, k++) {
if (s[j] == s[k]) {
tmp = s.substr(j, k - j + 1);
if (tmp.size() > palindrome.size())
palindrome = tmp;
}
else
break;
}
}
}
return palindrome;
}
public static string findMaxPlaindrome(string str)
{
if (String.IsNullOrEmpty(str))
{
return "";
}
string ret = "";
int maxLenght = 0;
for (int i = 0; i < str.Length; i++)
{
int max = i;
int min = i;
while (max < str.Length && min >= 0 && str[max] == str[min])
{
min--;
max++;
}
min++;
max--;
if (max - min > maxLenght)
{
maxLenght = max - min;
ret = str.Substring(min, max - min + 1);
}
}
return ret;
}
if (String.IsNullOrEmpty(str))
{
return "";
}
string ret = str.Substring(0, 1);
for (int i = 0; i < str.Length; i++)
{
//handel even
int max = i;
int min = i;
while (max < str.Length && min >= 0 && str[max] == str[min])
{
min--;
max++;
}
min++;
max--;
string p1 = "";
p1 = str.Substring(min, max - min + 1);
if (p1.Length > ret.Length)
{
ret = p1;
}
//handle odd
max = i + 1;
min = i;
while (max < str.Length && min >= 0 && str[max] == str[min])
{
min--;
max++;
}
string str2 = "";
min++;
max--;
if (max - min > 0)
{
str2 = str.Substring(min, max - min + 1);
}
if (str2.Length > ret.Length)
{
ret = str2;
}
}
return ret;
def generate_substrings(s):
x = [s[i:j+1] for i in xrange(0, len(s), 1) for j in xrange(len(s), 0, -1) if len(s[i:j+1]) > 1]
return list(set(x))
def reverse_str(s):
if s == s[::-1]:
return True
def get_palindrome(s):
sub_list = generate_substrings(s)
rev = [s for s in sub_list if reverse_str(s)]
max_pal = reduce(lambda x,y:x if(len(x)>len(y)) else y, rev)
return max_pal
if __name__=='__main__':
print get_palindrome('AABCDCBA')
{{
def generate_substrings(s):
x = [s[i:j+1] for i in xrange(0, len(s), 1) for j in xrange(len(s), 0, -1) if len(s[i:j+1]) > 1]
return list(set(x))
def reverse_str(s):
if s == s[::-1]:
return True
def get_palindrome(s):
sub_list = generate_substrings(s)
rev = [s for s in sub_list if reverse_str(s)]
max_pal = reduce(lambda x,y:x if(len(x)>len(y)) else y, rev)
return max_pal
if __name__=='__main__':
print get_palindrome('AABCDCBA')
}}
def generate_substrings(s):
x = [s[i:j+1] for i in xrange(0, len(s), 1) for j in xrange(len(s), 0, -1) if len(s[i:j+1]) > 1]
return list(set(x))
def reverse_str(s):
if s == s[::-1]:
return True
def get_palindrome(s):
sub_list = generate_substrings(s)
rev = [s for s in sub_list if reverse_str(s)]
max_pal = ''
if rev:
max_pal = reduce(lambda x,y:x if(len(x)>len(y)) else y, rev)
return max_pal
if __name__=='__main__':
print get_palindrome('DEFABCBAYT')
public static String findLargestPalindromeSubsequence(String str) {
if (str == null || str.length() < 2)
return str;
final char[] arr = str.toCharArray();
for (int seqLength = arr.length - 1; seqLength > 0; --seqLength) {
int start = 0;
while (start + seqLength < arr.length) {
if (isPalindrome(arr, start, start + seqLength))
return new String(arr, start, seqLength+1);
start++;
}
}
return String.valueOf(arr[0]);
}
public static boolean isPalindrome(char[] arr, int start, int end) {
while (start < end)
if (arr[start++] != arr[end--])
return false;
return true;
}
public static String findLargestPalindromeSubsequence(String str) {
if (str == null || str.length() < 2)
return str;
final char[] arr = str.toCharArray();
for (int seqLength = arr.length - 1; seqLength > 0; --seqLength) {
int start = 0;
while (start + seqLength < arr.length) {
if (isPalindrome(arr, start, start + seqLength))
return new String(arr, start, seqLength+1);
start++;
}
}
return String.valueOf(arr[0]);
}
public static boolean isPalindrome(char[] arr, int start, int end) {
while (start < end)
if (arr[start++] != arr[end--])
return false;
return true;
}
public static String findLargestPalindromeSubsequence(String str) {
if (str == null || str.length() < 2)
return str;
final char[] arr = str.toCharArray();
for (int seqLength = arr.length - 1; seqLength > 0; --seqLength) {
int start = 0;
while (start + seqLength < arr.length) {
if (isPalindrome(arr, start, start + seqLength))
return new String(arr, start, seqLength+1);
start++;
}
}
return String.valueOf(arr[0]);
}
public static boolean isPalindrome(char[] arr, int start, int end) {
while (start < end)
if (arr[start++] != arr[end--])
return false;
return true;
}
#include <iostream>
#include<typeinfo>
using namespace std;
void FindPolindrome(
std::string::const_iterator itB,
std::string::const_reverse_iterator itR,
const unsigned int nRemain,
std::string& polyndrome )
{
if( nRemain <= 1 ) return;
// check for polindrome
unsigned int check = nRemain/2;
std::string::const_iterator myitB = itB;
std::string::const_reverse_iterator myitR = itR;
bool bSuccess(true);
for( unsigned int un = 0; un< check; ++ un)
{
if( *myitB != *myitR )
{
bSuccess = false;
break;
}
++myitB; ++myitR;
}
if( bSuccess )
{
std::string::const_iterator itE = itR.base();
++itE;
polyndrome = std::string( itB, itE );
}
else
{
std::string polyndrome1;
std::string polyndrome2;
std::string::const_iterator itB1,itB2;
std::string::const_reverse_iterator itR1,itR2;
itB1 = itB2 = itB;
itR1 = itR2 = itR;
unsigned int nNewRemain = nRemain-1;
FindPolindrome(++itB1, itR1, nNewRemain, polyndrome1);
FindPolindrome(itB1, ++itR1, nNewRemain, polyndrome2);
if( polyndrome1.size() > polyndrome2.size() )
{
polyndrome = polyndrome1;
}
else
{
polyndrome = polyndrome2;
}
}
}
int main()
{
std::string str;
std::string polyndrome;
std::cin >> str;
FindPolindrome( str.cbegin(), str.crbegin(), str.size(), polyndrome );
std::cout << polyndrome;
return 0;
}
#include <iostream>
#include<typeinfo>
using namespace std;
void FindPolindrome(
std::string::const_iterator itB,
std::string::const_reverse_iterator itR,
const unsigned int nRemain,
std::string& polyndrome )
{
if( nRemain <= 1 ) return;
// check for polindrome
unsigned int check = nRemain/2;
std::string::const_iterator myitB = itB;
std::string::const_reverse_iterator myitR = itR;
bool bSuccess(true);
for( unsigned int un = 0; un< check; ++ un)
{
if( *myitB != *myitR )
{
bSuccess = false;
break;
}
++myitB; ++myitR;
}
if( bSuccess )
{
std::string::const_iterator itE = itR.base();
++itE;
polyndrome = std::string( itB, itE );
}
else
{
std::string polyndrome1;
std::string polyndrome2;
std::string::const_iterator itB1,itB2;
std::string::const_reverse_iterator itR1,itR2;
itB1 = itB2 = itB;
itR1 = itR2 = itR;
unsigned int nNewRemain = nRemain-1;
FindPolindrome(++itB1, itR1, nNewRemain, polyndrome1);
FindPolindrome(itB1, ++itR1, nNewRemain, polyndrome2);
if( polyndrome1.size() > polyndrome2.size() )
{
polyndrome = polyndrome1;
}
else
{
polyndrome = polyndrome2;
}
}
}
int main()
{
std::string str;
std::string polyndrome;
std::cin >> str;
FindPolindrome( str.cbegin(), str.crbegin(), str.size(), polyndrome );
std::cout << polyndrome;
return 0;
}
#include <iostream>
#include<typeinfo>
using namespace std;
void FindPolindrome(
std::string::const_iterator itB,
std::string::const_reverse_iterator itR,
const unsigned int nRemain,
std::string& polyndrome )
{
if( nRemain <= 1 ) return;
// check for polindrome
unsigned int check = nRemain/2;
std::string::const_iterator myitB = itB;
std::string::const_reverse_iterator myitR = itR;
bool bSuccess(true);
for( unsigned int un = 0; un< check; ++ un)
{
if( *myitB != *myitR )
{
bSuccess = false;
break;
}
++myitB; ++myitR;
}
if( bSuccess )
{
std::string::const_iterator itE = itR.base();
++itE;
polyndrome = std::string( itB, itE );
}
else
{
std::string polyndrome1;
std::string polyndrome2;
std::string::const_iterator itB1,itB2;
std::string::const_reverse_iterator itR1,itR2;
itB1 = itB2 = itB;
itR1 = itR2 = itR;
unsigned int nNewRemain = nRemain-1;
FindPolindrome(++itB1, itR1, nNewRemain, polyndrome1);
FindPolindrome(itB1, ++itR1, nNewRemain, polyndrome2);
if( polyndrome1.size() > polyndrome2.size() )
{
polyndrome = polyndrome1;
}
else
{
polyndrome = polyndrome2;
}
}
}
int main()
{
std::string str;
std::string polyndrome;
std::cin >> str;
FindPolindrome( str.cbegin(), str.crbegin(), str.size(), polyndrome );
std::cout << polyndrome;
return 0;
}
int main()
{
map<char,int> test_m;
char var;
string str="DEFABCBAYT";
char chr_arr[str.length()+1];
strcpy(chr_arr,str.c_str());
map<char,int> ::iterator it_i;
for(int i=0;i<str.length();i++)
{ it_i=test_m.find(chr_arr[i]);
if(it_i != test_m.end())
{
test_m[chr_arr[i]] = test_m[chr_arr[i]] +1;
if((test_m[chr_arr[i]] ) %2==0)
var= ' ';
else
var=chr_arr[i];
}
else
{ test_m[chr_arr[i]] = 1;
var=chr_arr[i];
}
}
map<char,int> ::iterator it;
list<char> out_list;
if(var != ' ')
out_list.push_back(var);
for(it=test_m.begin();it != test_m.end();it++)
{
for(int i=0 ;i<(it->second/2);i++)
{
out_list.push_back(it->first);
out_list.push_front(it->first);
}
}
list<char>::iterator itl;
for(itl = out_list.begin();itl != out_list.end();itl++)
cout << *itl;
#include <iostream>
#include<typeinfo>
using namespace std;
void FindPolindrome(
std::string::const_iterator itB,
std::string::const_reverse_iterator itR,
const unsigned int nRemain,
std::string& polyndrome )
{
if( nRemain <= 1 ) return;
// check for polindrome
unsigned int check = nRemain/2;
std::string::const_iterator myitB = itB;
std::string::const_reverse_iterator myitR = itR;
bool bSuccess(true);
for( unsigned int un = 0; un< check; ++ un)
{
if( *myitB != *myitR )
{
bSuccess = false;
break;
}
++myitB; ++myitR;
}
if( bSuccess )
{
std::string::const_iterator itE = itR.base();
++itE;
polyndrome = std::string( itB, itE );
}
else
{
std::string polyndrome1;
std::string polyndrome2;
std::string::const_iterator itB1,itB2;
std::string::const_reverse_iterator itR1,itR2;
itB1 = itB2 = itB;
itR1 = itR2 = itR;
unsigned int nNewRemain = nRemain-1;
FindPolindrome(++itB1, itR1, nNewRemain, polyndrome1);
FindPolindrome(itB1, ++itR1, nNewRemain, polyndrome2);
if( polyndrome1.size() > polyndrome2.size() )
{
polyndrome = polyndrome1;
}
else
{
polyndrome = polyndrome2;
}
}
}
int main()
{
std::string str;
std::string polyndrome;
std::cin >> str;
FindPolindrome( str.cbegin(), str.crbegin(), str.size(), polyndrome );
std::cout << polyndrome;
return 0;
}
static String getPaliSubString(String str)
{
if(str==null || str.length()<=1)
return str;
int i=0, j=str.length()-1;
int st = -1, end = -1;
while(i<j)
{
char charI = str.charAt(i);
char charJ = str.charAt(j);
if(charI==charJ)
{
if(st==-1 && end ==-1)
{
st = i;
end = j;
}
}
else
{
if(i>0 && str.charAt(i-1)==charJ)
{
st = --i;
end = j;
}
else if(j<str.length()-1 && str.charAt(j+1)==charI)
{
st = i;
end = ++j;
}
else
{
st = -1;
end = -1;
}
}
i++;
j--;
}
if(st!=-1 && end!=-1)
return str.substring(st,end+1);
else
return str.substring(0,1);
}
static String getPaliSubString(String str)
{
if(str==null || str.length()<=1)
return str;
int i=0, j=str.length()-1;
int st = -1, end = -1;
while(i<j)
{
char charI = str.charAt(i);
char charJ = str.charAt(j);
if(charI==charJ)
{
if(st==-1 && end ==-1)
{
st = i;
end = j;
}
}
else
{
if(i>0 && str.charAt(i-1)==charJ)
{
st = --i;
end = j;
}
else if(j<str.length()-1 && str.charAt(j+1)==charI)
{
st = i;
end = ++j;
}
else
{
st = -1;
end = -1;
}
}
i++;
j--;
}
if(st!=-1 && end!=-1)
return str.substring(st,end+1);
else
return str.substring(0,1);
}
// ZoomBA : Better optimised code
def is_palindrome( s, i, j ){
!exists ( [i : (j - i)/2 + i + 1 ] ) :: {
s[ $.item ] != s[ i + j - $.item ]
}
}
def find_max_palindrome( string ){
max_palindrome = [0,0] ; r = [0:#|string|]
join ( r, r ) :: {
i = $.item.0 ; j = $.item.1
continue( max_palindrome.1 - max_palindrome.0 > j - i ||
!is_palindrome( string , i, j ) )
max_palindrome.0 = i ; max_palindrome.1 = j
false
}
string[ max_palindrome.0 : max_palindrome.1 ]
}
s = "DEFABCBAYT"
r = find_max_palindrome( s )
println(r)
//
//
// 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);
}
}
The solution below tries to form a palindrome centered on each index i of String. Considering even and odd scenarios.Time:O(n^2) where n is length of string, Space: O(1)
- guilhebl May 24, 2016