## Bloomberg LP Interview Question for Financial Software Developers

• 0

Country: United Kingdom
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

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)

``````public class LongestPalindromic {

public static void main(String[] args) {
System.out.println(longestPalindromicSubstring("AABCDCBA"));
System.out.println(longestPalindromicSubstring("DEFABCBAYT"));
}

public static String longestPalindromicSubstring(String s) {
if (s == null || s.equals("")) {
return null;
}
if (s.length() == 1) {
return s;
}
char[] c = s.toCharArray();

int low = -1;
int hi = -1;
int len = s.length();
int maxL = 0;
int maxI = -1;
int maxJ = -1;

for (int i = 1; i < c.length; i++) {
// even
hi = i;
low = i - 1;
while(low >= 0 && hi < len && c[low] == c[hi]) {
if ((hi - low + 1) > maxL) {
maxL = hi - low + 1;
maxI = low;
maxJ = hi;
}
hi++;
low--;
}

// odd
hi = i + 1;
low = i - 1;
while(low >= 0 && hi < len && c[low] == c[hi]) {
if ((hi - low + 1) > maxL) {
maxL = hi - low + 1;
maxI = low;
maxJ = hi;
}
low--;
hi++;
}
}

if (maxL > 1) {
return s.substring(maxI, maxJ + 1);
}

return s.substring(0, 1);
}

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````palindrome :: Eq a => [a] -> [a]
palindrome [] = []
palindrome [x] = [x]
palindrome xs
| xs == reverse xs = xs
| otherwise = let p = palindrome (init xs )
r = palindrome (tail xs ) in if length p > length r then p else r``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````//Haskel
palindrome :: Eq a => [a] -> [a]
palindrome [] = []
palindrome [x] = [x]
palindrome xs
| xs == reverse xs = xs
| otherwise = let p = palindrome (init xs )
r = palindrome (tail xs ) in if length p > length r then p else r``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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());
return;
}
}
}

}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
string input = "DEFABCBAYT";

//check(input);

Console.WriteLine(checkinput(input));
}

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 "";
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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')

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

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')
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) and O(1) space

``````s = 'ABCDCBAAA'
best = 0
out = ''
for i in range(len(s)):
for j in range(i+1,len(s)):
substr = s[i:j]
if substr == substr[::-1]:
print(substr)
if len(substr) > best:
best = len(substr)
out = substr
print(out)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

There are two solutions than can run in O(n) : the first one is the optimized Manacher algorithm and the second one uses a suffix tree.

Both are well discussed and detailed on the geeksforgeeks website.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//
//
//  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
//
//
//

public class LPMain004 {

/**
*
* int findMidpoint(String text)
*
* I admit, it took a while longer than average to figure out
* a question like this might take me a bit longer. Bit with all
* such seemingly difficult talks, when you take the time to break
* 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);

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I see lot of O(n^2) solution but I believe this can be solved in O(n) using hashmap which stores letters as keys and its index as values. I'll try to hash(el-oh-el) out the solution and edit post.

Comment hidden because of low score. Click to expand.
0
of 0 vote

It's quite easy to derive a squared time algorithm (we just choose a center of the potential palindrome at each character and in between characters, and try to grow a palindrome from that center).
But there is a linear time algorithm for this. Manacher's algorithm.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.