## Bloomberg LP Interview Question for Financial Software Developers

• 1
of 1 vote

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

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/#demoForm
explains an elegant solution.

The answer I gave there was not even close (I checked it later after the interview).. got a reject

Comment hidden because of low score. Click to expand.
3

It doesn't seem that hard. On the first pass through this problem, you consider every character of the string to be a center of a palindrome, and then start comparing the character to the left and the right until you reach the end of the string or a pair that is unequal. The string containing the matched pairs is your palindrome if its length is 3 or greater.

The thing that makes this a little hard is that a palindrome could have an even number of letters. To get an algorithmn which will handle both even and odd without too much complexity do the following:
For each substring center of repeating characters in string a
j = 0;
while ( a[center.lowindex - j] == a[center.highindex + j] j++;
if j>1 return the substring(a, center.lowindex-j+1, center.lowindex + j -1);

This, of course, assumes that center, the substring of repeating elements, is not considered to be an interesting palindrome.

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

is there a way u can explain that .. i couldnt understand that stuff ? :(

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

Hi all,

here is code in C:

``````#include<stdio.h>
#include<string.h>

int main(){
int len,i,j=0,index,tempindex,count,tempcount;
char str,*ptr;
printf("\nEnter String: ");
scanf("%s",str);
len=strlen(str);
ptr=str;
index=0;
count=0;

//finding longest palindrome of odd length
for(i=1;i<len-1;i++){
j=1;
while(((i-j) >= 0) && ((i+j) < len) && (str[i-j]==str[i+j]))
j++;

if(j-1>count){
index=i;
count=j-1;
}
}

if(count>=1){
index=index-count;
count=2*count+1;
}

//finding longest palindrome of even  length
tempcount=0;
tempindex=0;
for(i=0;i<len-1;i++){
j=0;
while(((i-j) >= 0) && ((i+j+1) < len) && (str[i-j]==str[i+j+1]))
j++;

if(j>tempcount){
tempindex=i;
tempcount=j;
}
}

if(tempcount>0)
{
tempindex=tempindex-tempcount+1;
tempcount=tempcount*2;
}

//if even palindrome's length is greater than odd palindrome's length
if(tempcount>count)
{
index=tempindex;
count=tempcount;
}

printf("\nindex=%d, count= %d",index,count);

if(count==0)
printf("\nNo Palindrome");
else{
ptr=ptr+index;
ptr[count]=NULL;
printf("\nLongest Palindrome: %s",ptr);
}

}``````

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

I guess the tree thing is better..

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

reverse the given string and do the longest common subsequence routine between the string and the reveresed string.....

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

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

that program didnt work when i tested it with a very long sequence

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

could u tell me what was input.

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

the array size in the program is 100
if u want larger input ,increse array size
it will work.

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

gotcha, I just tried it really quickly last night before bed, I didn't really feel like trying to figure out why it didnt work.

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

i tried it
it works

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

``````#include<stdio.h>

int main(){

char st;
int index=0;
int max=-1;
int offset=0;
int midindx=0;

// Input

printf("\nEnter String:");
scanf("%s",st);

//max palindrome of odd length
while(st[index+offset] != NULL){
offset=0;
while((index >= offset) && (st[index + offset] != NULL ) && (st[index + offset] == st[index - offset])){
if(offset>max){
max = offset;
midindx=index;
}

offset++;
}
index++;
}

if(max != -1){
printf("\nMax Odd length palindrome of length %d is : %.*s\n",2 * max +1,2 * max +1, &st[midindx-max]);
}

//max palindrome of even length

int index1=0;
int max1=-1;
int offset1=0;
int midindx1=0;

while((st[index1 + offset1] != NULL) && (st[index1 + offset1 + 1] != NULL)){
offset1=0;
while((st[index1 + offset1 + 1] != NULL) && (index1 >= offset1) && (st[index1 - offset1] == (st[index1 + offset1 + 1] ))){
if(offset1 > max1){
max1 = offset1;
midindx1 = index1;
}
offset1++;
}
index1++;
}

if(max1 != -1){
printf("\nMax Even length palindrome of length %d is : %.*s\n",2 * max1 + 2,2 * max1 + 2, &st[midindx1-max1]);
}
}``````

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

Hey Ravi.. ur code works!
can u give me the logic behind it ? also cud u also explain how u print using %.*s?

thanks a lot!
-Labhesh

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

i have gone through this question ..my solution is based on this matrix view

X M A D A M Y X
X 1 0 0 0 0 0 0 1
M 0 1 0 0 0 1 0 0
A 0 0 1 0 1 0 0 0
D 0 0 0 1 0 0 0 0
A 0 0 1 0 1 0 0 0
M 0 1 0 0 0 1 0 0
Y 0 0 0 0 0 0 1 0
X 1 0 0 0 0 0 0 1

we have created this matrix putting 0 when characters in row and column are different and 1 when equal. its easy to see that all the palindromes will lie around the main diagonal (in the direction of second diagonal). in this way we can find out all the palindromes in the given string and of course the palindrome with maximum length.

only problem is the space.

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

use a sparse matri, also forget setting or checking one diagonal it will always be equal.

i assume this me efficient for large strings

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

``````#include <stdio.h>
#include <stdlib.h>

int palindrome(char* s, int p, int r)
{
int x1, x2;

if (p == r) {
return 1;
}
else if (p > r)
return 0;
else {
if (s[p] == s[r]) {
return 2 + palindrome(s,p+1,r-1);
}
else {
x1 = palindrome(s,p,r-1);
x2 = palindrome(s,p+1,r);
return (x1 > x2) ? x1 : x2;
}
}
}

int main(int argc, char* argv[])
{
char s;

printf("Enter a string\n");
scanf("%s",s);

printf("Longest length is %d\n",palindrome(s,0,strlen(s)-1));
}``````

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

Dude.. did u check with the input

edse
efge

these are not palindromes... but.. it returns max length of palindrome:3

this is because u are returning 2+ pal();

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

can we write a subroutine that tests for a palindrome and then check substrings with end characters deleted from the original string? i'm guessing this is a O(n^3) algorithm.

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

#include <iostream>
#include <string>

using namespace std;

int main()
{
string str;
string palindrome;
cin >> str;
for(int i=1; i <= str.length()-2; ++i)
{
int temp = 1;
while(((i-temp) >= 0) && ((i+temp) <= str.length()-1) && (str[i-temp] == str[i+temp]))
++temp;
if(temp > 1)
{
string newPalindrome = str.substr(i-(temp-1), 2*(temp-1)+1);
if(newPalindrome.length() > palindrome.length())
palindrome = newPalindrome;
}
}

cout << endl << palindrome;

}

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

Why dont you guys include comments along with the code? It will be so much helpful.

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

Longest Common Substring is not the solution , since it doesn't take contiguous character into consideration.

e.g MADZAM , MAZDAM will return MADAM as the longest palindrome which is not correct.

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

Substring is different from subsequence. Substring should be contiguous.

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

Hmm... I was recently asked to develop an algorithm that counts the number of palindromes in a string (excluding palindromes inside other palidromes). Below is the c# code I turned in. Can anyone let me know if it works or if it contains a bug, etc. I decided to google palindromes after I already turned in my code, which is how I found this site. Thanks.

using System;

namespace PalindromeCount
{
class Program
{
static void Main(string[] args)
{
bool terminate = false;

do
{
Console.WriteLine("\nEnter input string below:");
string inputString = Console.ReadLine();

string palindromes = "";
int Count = GetPalindromeCount(inputString,
ref palindromes);

string output = "\nPalindrome count: ";
output += Count.ToString();
output += "\nPalindromes: ";
output += palindromes;
Console.WriteLine(output);

Console.WriteLine("\nTerminate (Y/N):");
string input = Console.ReadLine();

if (string.Compare(input, "Y", true) == 0)
{
terminate = true;
}

} while (terminate == false);
}

//This method returns the number palindromes
//within the input string
//it stores the palindromes found in
//the palindromes argument
public static int GetPalindromeCount(string str,
ref string palindromes)
{
palindromes = "";
int lastEndIndex = 0;
return GetPalindromeCount(str,
0,
str.Length - 1,
ref lastEndIndex,
ref palindromes);
}

//This is a recursive method that counts
//the number of palindromes
//within a subset (substring) of the input string
//between the startindex and endindex

//if the entire substring is not a palindrome, this method
//looks for the next palindrome by searching for the longest
//leftmost palindrome of the substring. This is done by
//reducing the end index by 1 until a palindrome is found.
//However, the endindex cannot be reduced beyond the
//end index (lastEndIndex) of the last leftmost
//palindrome found. This ensures that smaller
//palindromes within larger leftmost palindromes are not
//counted

//Upon searching for the longest leftmost palindrome,
//this method then calls it self again with a substring
//that is one chararcter less to the left of the input
//substring. Again, by using the lastEndIndex as a limit
//smaller palindromes within previously found leftmost
//palindromes are avoided

private static int GetPalindromeCount(string str,
int startIndex,
int endIndex,
ref int lastEndIndex,
ref string palindromes)
{
//The length of the substring must be greater than 1
//because the length of palidromes must be 2 or more

//The endindex is reduced during recursion, however,
//the endindex must be greater than the lastendindex
//to prevent smaller leftmost palidromes within longer
//leftmost palindromes
if (startIndex >= endIndex || lastEndIndex >= endIndex)
{
return 0;
}

//return 1 and exit, if the entire substring is a
//palindrome
else if (IsPalindrome(str, startIndex, endIndex))
{
//add the newly found palidrome to the list
//of palindromes
palindromes += str.Substring(startIndex,
endIndex - startIndex + 1)
+ " ";
return 1;
}

else
{
int Count = 0;

//get the longest leftmost palindrome
//of the substring found
string left = GetLeftmostPalindrome(str,
startIndex,
endIndex - 1,
lastEndIndex);
if (left.Length > 1)
{
//set the last leftmost last index found
lastEndIndex = startIndex + left.Length - 1;
Count = 1;

//add the newly found palidrome to the list
//of palindromes
palindromes += left + " ";
}

//search for other palidromes but avoid those within
//previously found leftmost palidromes
//by using lastEndIndex
return GetPalindromeCount(str,
startIndex + 1,
endIndex,
ref lastEndIndex,
ref palindromes)
+ Count;
}
}

//This method returns the longest leftmost palidrome
//of the substring, if found
//or an empty string
private static string GetLeftmostPalindrome(string str,
int startIndex,
int endIndex,
int lastEndIndex)
{
//The length of the substring must be greater than 1
//because the length of palidromes must be 2 or more

//The endindex is reduced during recursion, however,
//the endindex must be greater than the lastendindex
//to prevent smaller leftmost palidromes within longer
//leftmost palindromes
if (startIndex >= endIndex || lastEndIndex >= endIndex)
{
return "";
}

//return 1 and exit, if the entire substring is a
//palindrome
else if (IsPalindrome(str, startIndex, endIndex))
{
return str.Substring(startIndex,
endIndex - startIndex + 1);
}

//reduce the substring by 1 character to the right
//and try again
else
{
return GetLeftmostPalindrome(str,
startIndex,
endIndex - 1,
lastEndIndex);
}
}

//return true if the substring is a palindrome
private static bool IsPalindrome(string str,
int startIndex,
int endIndex)
{
//The length of the substring must be greater than 1
//because the length of palidromes must be 2 or more
if (startIndex >= endIndex)
{
return false;
}

int left = startIndex;
int right = endIndex;
char[] strChars = str.ToCharArray();

do
{
if (strChars[left] != strChars[right])
{
return false;
}

left++;
right--;

} while (left < right);

return true;
}
}
}

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

This code is case sensitive
MadAm says no palindrome

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

You can make it not case sensitive by going to IsPalindrome(...) and converting the input string to upper case before processing

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

Why all the trouble of trees and things. Reverse the string and then find the intersection of the string and the reversed string.

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

Ozzy, think again.

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

for OZZy:
Your solution is correct, but not efficient. It takes O(n^2) time to find the intersection of the string and the reversed string (since it is not sorted number and you can not sort them).

In stead, we can create two suffix arrays(or suffix trees) for string and reversed string respectively, and then easily get the longest common character of hneighbor elements.

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

Why would it take O(n^2) in Ozzy's case? I think it would be O(n).

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

Why would it take O(n^2) in Ozzy's case? I think it would be O(n).

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

Why would it take O(n^2) in Ozzy's case? I think it would be O(n).

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

Here is fully working code:

void DetectPalindrome(char *str){
int j=0;
int len=1;
int sz=(int)strlen(str);

//find the center point of the palindrome
for(int i=j+1;i<sz;i++){
if(str[i-1]==str[i+1]){
j=i;
//find the length of palindrome
while((j-len-1>=0) && (j+len+1<sz) && str[j-len-1]==str[j+len+1])len++;

//print
for(int k=j-len;k<=j+len;k++)
cout<<str[k];
cout<<endl;
len=1;
}
}
}

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

its working, only for the pattern like ABCDEDCBA though.
For strings like ABCDDCBA need to modify the code a bit

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.