Bloomberg LP Interview Question Software Engineer / Developers
>So, the problem boils down to just finding the longest palindrome in the string
Nope.
Consider:
MADM: No Palindrome
MADAM: Pal. of 5 characters!
compare first element with last
if different insert into last.
go to next element repeat the above steps till start < last.
if mad
check if m == d if no add m in the last
check a with d if no then add d
a no need to check
we get madam
No this should work.
MADM
first step:
(1) compare M with M no change.
(2) compare A with D insert A into last that means after D.
when I say last that means just after the the char we compare.
(3) A - no need, same pointer.
I did not test it, but how about this algo:
1. Find identical (if any) characters with the maximum distance: xMadMij
2a. (identical characters)
Merge the 2 parts of the string that goes towards the head/tail:
xm...mij -> xjim...mijx
2b. (no identical characters):
Mirror the string at the last character: ad -> ada
3. Ignore the merged parts in the further computations: (Remainder is "ad")
4. recurse (continue with 1.)
To be more specific,we need to find the length of the longest palindromic subsequence(LCS of string and its reverse).Say its n1 and our string length is n .
n-n1 will fetch u the desired result
Try ADAXDA correct answer would be ADAXADA
your approach would result in ADXADAXDA if I understood it right.
I think Grisch is right
Ragavenderan, your approach is right, this is what sameerud has mentioned earlier. @Anonymous, the LCS of ADAXDA and it's reverse (ADXADA) will be ADADA (or ADXDA) of size 5 (=n1). So n-n1 = 1, means insertion of only one character isrequired. This is the best approach in my opinion. Thanks sameerud and Ragavenderan.
step1:
For any string of length n such that if all characters are unique then n-1 characters are required to make it unique.
Step2:
Say if there are 2 identical characters...see eg below
if given string is abcdbefg find identical characters
In eg it is 'b'..the string within identical characters is "cd"
The string on left side of these identical characters is "a"
The string on right side of these identical characters is "fg"
Merge left and right it will become "afg"
Goto step1 with string "cd" and "afg" seperately.
Sum these : It will be 1 and 2
So final answer will be 3...Below is working code
#include <stdio.h>
#include <string.h>
#define LARGE_NUM 60000
static int some = 0;
/*
s[] : Given string is of the form cde where c,d,e are substrings within
start: index to start of string say 'd'
end : index of end of string say 'd'
li : start of left string
lj : end of left string
ri : start of left string
rj : end of right string
*/
int function(int start,int end,int li,int lj,int ri,int rj,char s[])
{
int len;
int count = LARGE_NUM, temp_count;
char substr[100];
int i,j,temp = LARGE_NUM;
int endcharsCount = 0;
some++;
if(li > lj && ri <=rj ) // if left hand side is empty
{
endcharsCount = (rj - ri) + 1;
rj = -1;
ri = 0;
}
else if(ri > rj && li <= lj) // if right hand side is empty
{
endcharsCount = (lj - li) + 1;
lj = -1;
li = 0;
}
{
if((end - start == 0) || (end - start == 1 && s[start] == s[end]) || (end < start))
{//if thrz onli 1 char || start,end are 2 chars which are same
count = 0;
}
else //this is for i/p : < d >
{
for(i = start ; i <= end-1 ; i++)
{
for(j=i+1; j <= end ; j++)
{
if(s[i] == s[j]) //this is to find < > and 'd' in between
{
temp = function(i+1,j-1,start,i-1,j+1,end,s);
if(temp < count)
count = temp;
}
}
}
if(temp == LARGE_NUM)//then all characters within 'start' and 'end' are unique
{
count = end - start;
// 'n' diff chars means n-1 chars are required to form palindrome
}
}
//this is for c1(characters on left) and c2(characters on right)
// merge left and right and make an array called substr[] and make a recursive call with
if(li <= lj && ri <= rj)
{
for(i = li,j = 0; i <= lj ; i++, j++)
substr[j] = s[i];
for(i = ri; i <= rj ; i++, j++)
substr[j] = s[i];
substr[j] = '\0';
count = count + function(0,j-1,0,-1,0,-1,substr); // 0 to j are new elements in substring which was formed by merging
}
}
return (count+endcharsCount);
}
int main()
{
char *s = "characters";
int count = -1;
count = function(0,strlen(s)-1,0,-1,0,-1,s);
printf("Num of changes required : %d\nNo of times function executed :%d",count,some);
}
Since you forgot 'e' in the string :) , lets take the string as abcdbfg
According to your argument, all you need to insert is 3 characters, but in this case I guess you will end up inserting 4
The palindrome will be:
gfabcdcbafg - gf at the beginning, c in the center and a towards the end
or
agfbcdcbfga - gf in the beginning, c in the center and a at the end.
let str1="AXBCXAD"
reverse it str2="DAXCBXA"
Find the longerst common sequence. check lecture 15 of MIT algorithm course by Prof. Charles Leiserson
pairup the characters
eg:
_AXBC_XAD
DAX_CBXA_
Number of "_" give the required number of extra characters!!
sorry, the LCS is "AXCXA" in the above case. The LCS algorithm gives a way to pair up the charaters in str1 and str2
Using simple stuff (malloc's, null-terminated strings with char *'s , doing everything yourself - no-one said it HAD to be as far from C as possible), the following does it right. Noth that the implementation of string concatenation is not the most generic one (can't do in-place concatenation on the right-hand side argument, but we don't need it here so the whole thing gets simpler). A bit of handling pointers right will also endear you more to the interviewer...
unsigned int stringLen(const char *startStr)
{
unsigned int i=0;
while (*startStr++) i++;
return i;
}
void sliceString(const char *startStr, const int &startPos, const unsigned int &stringLength, char *destination)
{
if (stringLength > 0)
{
const char *cur = startStr + startPos;
char *dest = destination;
for (unsigned int i=0;i<stringLength;i++)
{
*dest++ = *cur++;
}
*(destination+stringLength) = 0;
}
else
{
*destination = 0;
}
}
bool checkAnagram(const char *stringSlice, const unsigned int &stringLength)
{
if (stringLength > 1)
{
bool isAnagram = true;
unsigned int i=0;
while (i < stringLength - 1 - i)
{
if (stringSlice[i] - stringSlice[stringLength - 1 - i])
{
isAnagram = false;
break;
}
i++;
}
return isAnagram;
}
else return true;
}
void invertString(const char *stringSlice, char *invertedStringSlice, const unsigned int &stringLength)
{
if (stringLength>0)
{
unsigned int i=0;
for (i=0;i<stringLength;i++)
{
invertedStringSlice[i] = stringSlice[stringLength - 1 - i];
}
invertedStringSlice[stringLength] = 0;
}
else *invertedStringSlice = 0;
}
void concatString(const char *leftSlice, const char *rightSlice, char *result)
{
unsigned int i=0;
const char *left = leftSlice;
const char *right = rightSlice;
while (*left)
{
*result++ = *left++;
}
while (*right)
{
*result++ = *right++;
}
*result = 0;
}
char *makeMinimumAnagramFromString(const char *startStr)
{
unsigned int i;
unsigned int startStrLen = stringLen(startStr);
unsigned int bestStartIndex = 0;
unsigned int bestAnagramLength = 1;
if (startStrLen > 0)
{ char *slice = (char *)malloc((startStrLen+1)*sizeof(char));
for (i=0;i<startStrLen-1;i++)
{
for (unsigned int j=2;j<=startStrLen-i;j++)
{
sliceString(startStr, i, j, slice);
if (checkAnagram(slice, j))
{
if (j > bestAnagramLength)
{
bestStartIndex = i;
bestAnagramLength = j;
}
}
}
}
char *anagram = (char *)malloc((startStrLen+1)*sizeof(char));
char *leftAnagram = (char *)malloc((startStrLen+1)*sizeof(char));
char *rightAnagram = (char *)malloc((startStrLen+1)*sizeof(char));
char *invertedLeftAnagram = (char *)malloc((startStrLen+1)*sizeof(char));
char *invertedRightAnagram = (char *)malloc((startStrLen+1)*sizeof(char));
char *result = (char *)malloc((2*startStrLen+1)*sizeof(char));
sliceString(startStr, bestStartIndex, bestAnagramLength, anagram);
sliceString(startStr, 0, bestStartIndex, leftAnagram);
sliceString(startStr, bestStartIndex + bestAnagramLength, startStrLen - (bestStartIndex + bestAnagramLength), rightAnagram);
invertString(leftAnagram, invertedLeftAnagram, bestStartIndex);
invertString(rightAnagram, invertedRightAnagram, startStrLen - (bestStartIndex + bestAnagramLength));
concatString(leftAnagram, invertedRightAnagram, result);
concatString(result, anagram, result);
concatString(result, rightAnagram, result);
concatString(result, invertedLeftAnagram, result);
return result;
}
else return const_cast<char *>(startStr);
}
My cents:
1. Compare 1st and Last (nth) element.
If same {do nothing}
Else
Copy the 1st element to the last (n+1)th position.
2. Now increment 'i' and decrement 'n-1', now compare them (we have to make sure in this case that our i!=j, where j is the pointer of nth decrement.
It will work for MAD!
1. Compare M -- D, NOT equal, now copy M into a new DYNAMIC array which will give us result: MADM
2. Now compare A -- A, in this our loop will exit and will copy 'A' into n-1th position which is previous position where M was copied. This will be also a dynamic array.
Hope this works!
My cents:
1. Compare 1st and Last (nth) element.
If same {do nothing}
Else
Copy the 1st element to the last (n+1)th position.
2. Now increment 'i' and decrement 'n-1', now compare them (we have to make sure in this case that our i!=j, where j is the pointer of nth decrement.
It will work for MAD!
1. Compare M -- D, NOT equal, now copy M into a new DYNAMIC array which will give us result: MADM
2. Now compare A -- A, in this our loop will exit and will copy 'A' into n-1th position which is previous position where M was copied. This will be also a dynamic array.
Hope this works!
Approach mentioned by Ragavenderan is correct and the best. Find the LCS of string and it's reverse and calculate the length (say n1). Then the minimum no. of character required will be n-n1.
Example if string is "ADAXDA", the LCS of ADAXDA and it's reverse (ADXADA) will be ADADA (or ADXDA) of size 5 (=n1). So n-n1 = 1, means insertion of only one character is required.
package bloomberspractice;
public class Main
{
public static void main(String[] args)
{
String str1 = "aaa";
String strrev = "";
String tempstr1 = "";
String tempstr = "";
String stradd = "";
String finalstrrev = "";
int i = 0;
int j = 0;
boolean flag = true;
while(flag)
{
j = str1.length() - 1;
for(i = 0; i <= str1.length()-1; i++)
{
if(!(str1.charAt(i) == str1.charAt(j)))
{
stradd = "" + str1.charAt(i);
strrev = "";
for(int l = j + 1; l <= str1.length() -1; l++)
{
strrev = strrev + str1.charAt(l);
}
tempstr1 = str1;
str1 = "";
for(int m = 0; m <= j; m++)
{
str1 = str1 + tempstr1.charAt(m);
}
str1 = str1 + stradd;
str1 = str1 + strrev;
break;
}
else
{
j--;
}
}
finalstrrev = "";
for(int i1 = str1.length()-1; i1 >=0; i1-- )
{
finalstrrev = finalstrrev + str1.charAt(i1);
}
//System.out.println("str1 in loop " + str1);
//System.out.println("finalstrrev in loop " + finalstrrev);
//System.out.println();
if(str1.equals(finalstrrev))
{
flag = false;
}
}
System.out.println("str1 " + str1);
System.out.println("finalstrrev " + finalstrrev);
/*
int o[] = new int[4];
o[0] = 1;
o[1] = 4;
o[2] = 7;
o[3] = 6;
int e[] = new int[4];
e[0] = 2;
e[1] = 5;
e[2] = 9;
e[3] = 8;
boolean bool_o = true;
boolean bool_e = true;
int tempe = 0;
int temoo = 0;
int temp = 0;
for(int i = 0; i < 4; i++)
{
if(o[i] % 2 != 0)
{
bool_o = true;
}
else
{
bool_o = false;
}
if(e[i] % 2 == 0)
{
bool_e = true;
}
else
{
bool_e = false;
}
if(bool_o == false && bool_e == false)
{
temp = o[i];
o[i] = e[i];
e[i] = temp;
}
else if(bool_o == false && bool_e == true)
{
}
}
for(int i = 0; i < 4; i++)
{
System.out.println("a[i] " + o[i]);
}
for(int i = 0; i < 4; i++)
{
System.out.println("b[i] " + e[i]);
}*/
}
}
String str1 = "aaa";
String strrev = "";
String tempstr1 = "";
String tempstr = "";
String stradd = "";
String finalstrrev = "";
int i = 0;
int j = 0;
boolean flag = true;
while(flag)
{
j = str1.length() - 1;
for(i = 0; i <= str1.length()-1; i++)
{
if(!(str1.charAt(i) == str1.charAt(j)))
{
stradd = "" + str1.charAt(i);
strrev = "";
for(int l = j + 1; l <= str1.length() -1; l++)
{
strrev = strrev + str1.charAt(l);
}
tempstr1 = str1;
str1 = "";
for(int m = 0; m <= j; m++)
{
str1 = str1 + tempstr1.charAt(m);
}
str1 = str1 + stradd;
str1 = str1 + strrev;
break;
}
else
{
j--;
}
}
finalstrrev = "";
for(int i1 = str1.length()-1; i1 >=0; i1-- )
{
finalstrrev = finalstrrev + str1.charAt(i1);
}
//System.out.println("str1 in loop " + str1);
//System.out.println("finalstrrev in loop " + finalstrrev);
//System.out.println();
if(str1.equals(finalstrrev))
{
flag = false;
}
}
System.out.println("str1 " + str1);
System.out.println("finalstrrev " + finalstrrev);
the solution is very easy. We can solve it in O(n^2).
int dp[100][100];
void init(int l){
for(int i=0;i<l;i++) for(int j=0;j<l;j++) dp[i][j]=-1;
}
int minChars(int start,int end,char *s){
if(start>=end) return 0;
//check if already calculated
int &a=dp[start][end];
if(a!=-1) return a;
if(s[start]==s[end]) return a=minChars(start+1,end-1,s);
else return a = min(1+minChars(start+1,end,s),1+minChars(start,end-1,s));
}
main(){
char s[100];
cin>>s;
init(strlen(s));
cout<<minChars(0,strlen(s)-1,s)<<endl;
}
int minIns(std::string str)
{
int n = str.size();
if (n == 0 || n == 1)
return 0;
int **min = new int *[n+1];
for (int i = 0; i < n+1; i++)
min[i] = new int[n];
for (int i = 1; i <= n; i++)
{
for (int j = n-1; j >= 0; j--)
{
if (i == 1)
min[i][j] = 0;
else
{
if (j + i > n)
min[i][j] == -1;
else
{
int tempMin = std::min(min[i-1][j] + 1, min[i-1][j+1] + 1);
if (str[j] == str[j+i-1])
tempMin = std::min(tempMin, min[i-2][j+1]);
min[i][j] = tempMin;
}
}
}
}
return min[n][0];
}
Firstly, find the length Longest Palindrome Subseqence(a.k.a LPS), noted as len(LPS)
Then the answer is len(string) - len(LPS)
For instance, given w = daebceccbad
Firstly, we use DP to get len(LPS) = 9, LPS(w) = dabcccbad
so, we need to add 2 more letter, they are 2 'e'
Actually, this is a greedy strategy, we always find the already built longest palindrome. Then what we need to add is the letters that are not in the LPS.
The LPS algorithm is very classic.
Tell me if I am wrong.
Firstly, find the length Longest Palindrome Subseqence(a.k.a LPS), noted as len(LPS)
Then the answer is len(string) - len(LPS)
For instance, given w = daebceccbad
Firstly, we use DP to get len(LPS) = 9, LPS(w) = dabcccbad
so, we need to add 2 more letter, they are 2 'e'
Actually, this is a greedy strategy, we always find the already built longest palindrome. Then what we need to add is the letters that are not in the LPS.
The LPS algorithm is very classic.
Tell me if I am wrong.
Approach with recursion:
#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <vector>
#include <limits.h>
std::string build_string(std::vector<char> const& pref, std::stack<char> const& suf) {
std::string res(pref.begin(), pref.end());
std::stack<char> st = suf;
while (!st.empty()) {
res.push_back(st.top());
st.pop();
}
return res;
}
void make_pal_r(const char *p, const char *e, int cnt, std::vector<char> &pref, std::stack<char> &suf, std::map<int, std::string> &out) {
if (p >= e) {
if (p == e) pref.push_back(*p);
if (out.find(cnt) == out.end())
out.insert(std::map<int, std::string>::value_type(cnt, build_string(pref, suf)));
pref.pop_back();
return;
}
if (*p == *e) {
pref.push_back(*p);
suf.push(*e);
make_pal_r(p+1, e-1, cnt, pref, suf, out);
pref.pop_back();
suf.pop();
} else {
pref.push_back(*p);
suf.push(*p);
make_pal_r(p+1, e, cnt+1, pref, suf, out);
pref.pop_back();
suf.pop();
pref.push_back(*e);
suf.push(*e);
make_pal_r(p, e-1, cnt+1, pref, suf, out);
pref.pop_back();
suf.pop();
}
}
std::string make_palindrome(std::string &s, int &cnt) {
cnt = INT_MAX;
std::string res;
std::vector<char> pref;
std::stack<char> suf;
std::map<int, std::string> out;
make_pal_r(s.c_str(), s.c_str() + s.size() - 1, 0, pref, suf, out);
std::map<int, std::string>::iterator it = out.begin(),
end = out.end();
for (; it != end; ++it) {
if (it->first < cnt) {
cnt = it->first;
res = it->second;
}
}
return res;
}
int main() {
std::string input = "daebceccbad";
int cnt = 0;
std::string output = make_palindrome(input, cnt);
std::cout << "input = " << input << " output = " << output << " cnt = " << cnt << std::endl;
return 0;
}
A little optimized and short:
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <limits.h>
void make_pal_r(const char *p, const char *e, int cnt, std::vector<char> &pref, std::stack<char> &suf, std::string &out, int &out_cnt) {
if (cnt > out_cnt) return;
if (p >= e) {
if (p == e) pref.push_back(*p);
out.assign(pref.begin(), pref.end());
std::stack<char> st = suf;
while (!st.empty()) {
out.push_back(st.top());
st.pop();
}
out_cnt = cnt;
if (p == e) pref.pop_back();
return;
}
if (*p == *e) {
pref.push_back(*p);
suf.push(*e);
make_pal_r(p+1, e-1, cnt, pref, suf, out, out_cnt);
pref.pop_back();
suf.pop();
} else {
pref.push_back(*p);
suf.push(*p);
make_pal_r(p+1, e, cnt+1, pref, suf, out, out_cnt);
pref.pop_back();
suf.pop();
pref.push_back(*e);
suf.push(*e);
make_pal_r(p, e-1, cnt+1, pref, suf, out, out_cnt);
pref.pop_back();
suf.pop();
}
}
int main() {
int cnt = INT_MAX;
std::vector<char> pref;
std::stack<char> suf;
std::string input = "opusefipa";
std::string output;
make_pal_r(input.c_str(), input.c_str() + input.size() - 1, 0, pref, suf, output, cnt);
std::cout << "input = " << input << " output = " << output << " cnt = " << cnt << std::endl;
return 0;
}
In a string of length n1 if the length of the longest palindrome is n2 (n2 <= n1), then to convert the entire string to a palindrome it would take (n1 - n2) characters. So, the problem boils down to just finding the longest palindrome in the string (which has been discussed in before on this site.)
- caffeine_coder November 21, 20091. PLATE
n1 = 5
n2 = 1
chars needed = 4
Result: PETLALTEP
2. MADA
n1 = 4
n2 = 3
chars needed = 1
Result: MADAM