## Bloomberg LP Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

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

``````/*
Assumptions:
- He means add characters to the front
of the given input to form a palindrome.
- Instead of "bcabc" he meant "cbabc" because
"bcabc" is not a palindrome
- I assume, he as well means inserting minimum characters,
because it would otherwise just being addinig
n - 1 characters assuming the character at
position 0 of input is the middle character, which
would satisfy all the samples and description.
- Because of the many assumptions, I add a simplification
to only consider "odd-size" palindromes (which have
mirror character, -> do not mirror in-between characters)

Solution O(n^2)
- Adding minimal amount to the front, means finding
the longest palindrome that mirrors the front part
of the input completely.
e.g. "abzbahik" would be "abzba" "hik" needs to be
reversed and inserted at the front
- Then "insert" the missing characters to the front
- There is a O(n) solution for finding the palindrome
you may look it up, I didn't include it here...
*/

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string extendPalindrome(const string& input)
{
if(input.length() <= 1) return input;

// find mirror point (as mentioned only consider odd palindrome for simplicity)
int pos = 0;
for(int i = 1; i <= input.length() / 2; i++) // i: mirror point
{
for(int j = 1; i + j < input.length() && i - j >= 0; j++)
{
if(input[i + j] != input[i - j]) break;
if(j == i) pos = i;
}
}

// insert at beginning
int rem = input.length() - (pos + pos + 1);
if(rem == input.length()) return input;
string result = input.substr(pos + pos  + 1, rem);
reverse(result.begin(), result.end());
result.append(input);
return result;
}

int main()
{
cout << "a: " << extendPalindrome("a") << endl;
cout << "ab: " << extendPalindrome("ab") << endl;
cout << "abc: " << extendPalindrome("abc") << endl;
cout << "bazabc: " << extendPalindrome("bazabc") << endl;
cout << "cbazabc: " << extendPalindrome("cbazabc") << endl;
}
/* output
a: a
ab: bab
abc: cbabc
bazabc: cbazabc
cbazabc: cbazabc
*/``````

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

The O(n) algorithm to find the longest palindromic sub-string is called the Manacher's Algorithm.

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

Here's an update to your solution.
I added two loops, first one for palindromes of odd length and second loop for palindromes of even length starting at index 0 in the string. It works irrespective of the length of string input being even or odd.

``````class Solution {
public:
string shortestPalindrome(string s) {
if(s.length()<=1){
return s;
}
int pos=0;
int pos1 =0;
for(int i=1;i<=s.length()/2;i++){
for(int j=1;j<=i && (i+j)<s.length();j++){
if(s[i-j]!=s[i+j]){
break;
}
if(j==i){
pos1=i*2;
}
}
}
int pos2 =0;
for(int i=0;i<=s.length()/2;i++){
for(int j=0;j<=i && (i+j+1)<s.length();j++){
if(s[i-j]!=s[i+j+1]){
break;
}
if(j==i){
pos2=i+j+1;
}
}
}
pos=max(pos1,pos2);
cout<<pos1<<","<<pos2<<":"<<pos;
if(pos+1 >= s.length()){
return s;
}
string temp=s.substr(pos+1,s.length());
reverse(temp.begin(),temp.end());
return temp+s;
}
};``````

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

``````class Solution {
public static String makePlaindrom(String s){
if(s.length()<=1)
return s;
StringBuilder pl=new StringBuilder(s);
int len=s.length();
for (int i = len-2; i >=0; i--) {
pl.append(s.charAt(i));
}
return pl.toString();
}
/*Driver function to check for above function*/
public static void main (String[] args) {
System.out.println("a>> "+makePlaindrom("a"));
System.out.println("ab>> "+makePlaindrom("ab"));
System.out.println("abc>> "+makePlaindrom("abc"));
System.out.println("abcde>> "+makePlaindrom("abcde"));
}
}``````

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

``````if (str.length() > 1) {
String palinStr = str.substring(1, str.length());
System.out.println(new StringBuffer(palinStr).reverse() + str);
} else {
System.out.println(str);
}``````

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

While Chris is correct, the question is ill posed. As of now, one trivial answer is : reverse and append, thus :

``x + ( x ** -1 ) // is the answer``

But then, given the problem becomes "min no of char to be added"
then, we can do slightly better.

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

``````char[] chArr = str.toCharArray();
int mid = chArr.length/2;
boolean isPalindrome = true;
for(int i = mid; i >= 0; --i){
isPalindrome = true;
for(int j = 1; j < chArr.length-i && j < i; j++){
if(chArr[i-j] != chArr[i+j]){
isPalindrome = false;
break;
}
}
if(isPalindrome){
StringBuffer strBuff = new StringBuffer();
for(int k = chArr.length-1; k > 2*i; --k){
strBuff.append(chArr[k]);
}
strBuff.append(str);
System.out.println(strBuff.toString());
break;
}
isPalindrome = true;
}``````

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

``````public class test {

public static void main(String args[]) {
String value = "abc";
String palindrome = "";
String temp="";
boolean isPalindrome= checkPalindrome(value);
if (!isPalindrome) {
System.out.println("given string is not palindrome");
for (int i = value.length() - 1; i >= 0; i--) {
temp = temp + value.charAt(i);
if (checkPalindrome(temp+value)){
palindrome = temp + value;
break;

}
}

} else {

System.out.println("Given String is a palindrome");
}

System.out.println(palindrome);
}

private static boolean checkPalindrome(String value){
StringBuilder builder = new StringBuilder();
boolean isPalindrome=false;

for (int i = value.length()-1; i >= 0; i--) {
builder.append(value.charAt(i));
}
if(value.equalsIgnoreCase(builder.toString())){
isPalindrome=true;
}
return isPalindrome;
}``````

}

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

``````public class MakePalindrome {

public static void main(String[] args) {
System.out.println(makePalindrome("a"));    // null
System.out.println(makePalindrome("ab"));   // bab
System.out.println(makePalindrome("aa"));   // null
System.out.println(makePalindrome("aba"));  // null
System.out.println(makePalindrome("abba")); // null
System.out.println(makePalindrome("abc"));  // cbabc
System.out.println(makePalindrome("abac")); // cabac
System.out.println(makePalindrome("caba")); // cabac
System.out.println(makePalindrome("abbc")); // cbbabbc
System.out.println(makePalindrome("abacdcefec")); // abacdcefecdcaba
}

private static String makePalindrome(String s) {

if (s == null || s.isEmpty() || s.length() == 1) return null;

final int length = s.length();

Outcome o1 = detectPalindrome(s, true);
Outcome o2 = detectPalindrome(new StringBuilder(s).reverse().toString(), false);

Outcome o = Outcome.pickShortest(o1, o2);
if (o == null) return null;

// otherwise
if (o.extendLeft) {
StringBuilder sb = new StringBuilder();
for (int i = length-1; i > length-1-o.extensionSize; i--) sb.append(s.charAt(i));
return sb.toString() + s;
}
else {
StringBuilder sb = new StringBuilder();
for (int i = o.extensionSize-1; i >= 0 ; i--) sb.append(s.charAt(i));
return s + sb.toString();
}
}

private static Outcome detectPalindrome(String s, boolean forward) {

final int length = s.length();
boolean determinedMiddlePoint = false;

// left to right
int i = 0;
for (; i < length; i++) {
char c = s.charAt(i);
if (!determinedMiddlePoint) {
if (l.size() == 0) {
continue;
}
else if (l.size() == 1) {
if (c == l.get(0)) {
determinedMiddlePoint = true;
l.remove();
continue;
}
else {
continue;
}
}
else if (l.size() >= 2) {
if (c == l.get(0) || c == l.get(1)) {
determinedMiddlePoint = true;
if (c == l.get(1)) l.remove();
l.remove();
continue;
}
else {
continue;
}
}
}
else {
if (!l.isEmpty()) {
if (c == l.get(0)) {
l.remove();
continue;
}
// otherwise
return new Outcome(true, length-1); // not feasible, just skip first char
}
else {
break; // feasible, patch left
}
}
}
if (!determinedMiddlePoint) return new Outcome(true, length-1);

// otherwise
if (i == length) {
if (l.isEmpty()) return null;

// otherwise
return new Outcome(forward?false:true, l.size());
}

// otherwise
if (i < length) {
if (l.isEmpty()) return new Outcome(forward?true:false, length-i);

// otherwise
throw new IllegalStateException(i + " " + l);
}

// otherwise
throw new IllegalStateException(i + " " + l);
}

private static class Outcome {
private final boolean extendLeft;
private final int extensionSize;

private Outcome(boolean extendLeft, int extensionSize) {
this.extendLeft = extendLeft;
this.extensionSize = extensionSize;
}

private static Outcome pickShortest(Outcome o1, Outcome o2) {
if (o1 == null) return o2;

if (o2 == null) return o1;

return (o1.extensionSize < o2.extensionSize)? o1: o2;
}
}
}``````

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

For "abc", wouldn't the answer be "ba" ==> so it becomes "abcba"
and For "ab", wouldn't the answer be "a" ==> so it becomes "aba"

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

``````function processJavaScript(str){
return str.split('').reverse().slice(0, str.length - 1).join('') + str;
}``````

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

``````#include <iostream>
#include <string>
#include <sstream>

bool isPalindrome( std::string::const_iterator begin, std::string::const_iterator end )
{
bool result = true;
-- end;
while ( begin < end )
{
if ( * begin ++ != * end -- )
{
result = false;
break;
}
}
return result;
}

std::string asPalindrome( const std::string & input )
{
using namespace std;

ostringstream extra;
string::const_iterator begin = input.begin( );
string::const_iterator end   = input.end( );
while ( ! isPalindrome( begin, end ) )
{
-- end;
extra << * end;
}
return extra.str( ) + input;
}

int main( )
{
using namespace std;

cout << "a"       << " -> " << asPalindrome( "a" )       << ", expected a"      << endl;
cout << "ab"      << " -> " << asPalindrome( "ab" )      << ", expected bab"     << endl;
cout << "abc"     << " -> " << asPalindrome( "abc" )     << ", expected cbabc"   << endl;
cout << "bazabc"  << " -> " << asPalindrome( "bazabc" )  << ", expected cbazabc" << endl;
cout << "cbazabc" << " -> " << asPalindrome( "cbazabc" ) << ", expected cbazabc" << endl;
}``````

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

#include <iostream>

void reverseString(std::string& str)
{
size_t len = str.size() / 2;
size_t rv = str.size() - 1;

for (size_t i = 0; i < len; ++i, --rv)
{
char tmp = str[rv];
str[rv] = str[i];
str[i] = tmp;
}
}

std::string makePalindrome(const std::string& src)
{
if (src.size() <= 1)
{
return src;
}

std::string result = src.substr(1, (src.size() - 1));
reverseString(result);
return result.append(src);
}

int main()
{
std::string src1 = "abc";
std::string src2 = "ab";
std::string src3 = "a";

std::cout << makePalindrome(src1).c_str() << std::endl;
std::cout << makePalindrome(src2).c_str() << std::endl;
std::cout << makePalindrome(src3).c_str() << std::endl;

return 0;
}

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

``````#include <iostream>

void reverseString(std::string& str)
{
size_t len = str.size() / 2;
size_t rv = str.size() - 1;

for (size_t i = 0; i < len; ++i, --rv)
{
char tmp = str[rv];
str[rv] = str[i];
str[i] = tmp;
}
}

std::string makePalindrome(const std::string& src)
{
if (src.size() <= 1)
{
return src;
}

std::string result = src.substr(1, (src.size() - 1));
reverseString(result);
return result.append(src);
}

int main()
{
std::string src1 = "abc";
std::string src2 = "ab";
std::string src3 = "a";

std::cout << makePalindrome(src1).c_str() << std::endl;
std::cout << makePalindrome(src2).c_str() << std::endl;
std::cout << makePalindrome(src3).c_str() << std::endl;

return 0;
}``````

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

#include<iostream>
#include<string.h>

using namespace std;

int main() {
string str = "cbabc";

int len=str.size();
for(int i=0; i<len; i++)
{
if(str[i] != str[len-i-1])
{
str.insert(i,1, str[len-i-1]);
len = str.size();

}
}
cout<<"\n STR:"<<str;
}

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

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

using namespace std;

int main() {
string str = "cbabc";

int len=str.size();
for(int i=0; i<len; i++)
{
if(str[i] != str[len-i-1])
{
str.insert(i,1, str[len-i-1]);
len = str.size();

}
}
cout<<"\n STR:"<<str;
}``````

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

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

using namespace std;

int main() {
string str = "cbabc";

int len=str.size();
for(int i=0; i<len; i++)
{
if(str[i] != str[len-i-1])
{
str.insert(i,1, str[len-i-1]);
len = str.size();

}
}
cout<<"\n STR:"<<str;
}``````

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

``````class Main {

//Given a string, add some characters to the from of it so that it becomes a palindrome. E.g.1) If input is "abc" then "bcabc" should be returned. 2) input -> "ab" output -> "bab" 3) input -> "a" output -> "a"
public static void main(String[] args) {
String output = makePalindrome("abc");
System.out.println(output);
}

private static String makePalindrome(String input){
if(input.length() <= 1){
return input;
}
StringBuilder sb = new StringBuilder();
for(int index = input.length() - 1; index >= input.length() / 2; index--){
sb.append(input.charAt(index));
}
sb.append(input);
return sb.toString();
}``````

}

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

``````String str = "abc";

if (str == null || str.isEmpty()) {
System.out.println( str);
}

char current = str.charAt(0);
int count = 1;

StringBuilder output = new StringBuilder();

for (int i=str.length()-1; i>0;i--) {
output.append(str.charAt(i));
}``````

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

``````String str = "abc";

if (str == null || str.isEmpty()) {
System.out.println( str);
}

char current = str.charAt(0);
int count = 1;

StringBuilder output = new StringBuilder();

for (int i=str.length()-1; i>0;i--) {
output.append(str.charAt(i));
}``````

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.