Bloomberg LP Interview Question for Software Engineer / Developers


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

- ChrisK December 14, 2016 | Flag Reply
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.

- quirk March 30, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Shashank Sharma April 30, 2017 | Flag
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"));
    }
}

- salma December 14, 2016 | Flag Reply
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);
		}

- MDX December 14, 2016 | Flag Reply
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.

- NoOne December 14, 2016 | Flag Reply
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;
        }

- turukmakto1990 December 15, 2016 | Flag Reply
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;
	}

}

- Ravikumar.narayanan1985 December 16, 2016 | Flag Reply
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) {
        LinkedList<Character> l = new LinkedList<Character>();
        
        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) {
                    l.add(0, c);
                    continue;
                }
                else if (l.size() == 1) {
                    if (c == l.get(0)) {
                        determinedMiddlePoint = true;
                        l.remove();
                        continue;
                    }
                    else {
                        l.add(0, c);
                        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 {
                        l.add(0, c);
                        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; 
        }
    }
}

- PR December 21, 2016 | Flag Reply
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"

- Shekhar Agrawal February 05, 2017 | Flag Reply
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;
}

- MG March 18, 2017 | Flag Reply
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;
}

- robertgbjones April 17, 2017 | Flag Reply
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;
}

- NeverSummer May 07, 2017 | Flag Reply
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;
}

- NeverSummer May 07, 2017 | Flag Reply
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;
}

- Anonymous November 04, 2017 | Flag Reply
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;
}

- Anonymous November 04, 2017 | Flag Reply
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;
}

- Sekar November 04, 2017 | Flag Reply
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();
    }

}

- A December 07, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More