Bloomberg LP Interview Question for Financial Software Developers


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

- guilhebl May 24, 2016 | Flag Reply
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;
}

- raghu.aok May 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

My solution in 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

- Lukasz May 26, 2016 | Flag Reply
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

- Lukasz May 26, 2016 | Flag Reply
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];
	}

- Raj May 25, 2016 | Flag Reply
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;
using System.Threading.Tasks;

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

}
}
}

- Anonymous May 26, 2016 | Flag Reply
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;
using System.Threading.Tasks;

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

//check(input);

Console.WriteLine(checkinput(input));
Console.ReadLine();
}

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

- Anonymous May 26, 2016 | Flag Reply
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;
		
	}
}

- Heba May 27, 2016 | Flag Reply
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;
}

- funcoolgeek May 27, 2016 | Flag Reply
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;

}

- mark.nag June 01, 2016 | Flag Reply
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;

- mark.nag June 02, 2016 | Flag Reply
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')

- Anonymous June 09, 2016 | Flag Reply
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')
}}

- Indraja June 09, 2016 | Flag Reply
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')

- Indraja.Punna June 10, 2016 | Flag Reply
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;
	}

- mrnakumar June 15, 2016 | Flag Reply
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;
	}

- mrnakumar June 15, 2016 | Flag Reply
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;

}

- mrnakumar June 15, 2016 | Flag Reply
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)

- anonymous June 30, 2016 | Flag Reply
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;
}

- Anonymous July 18, 2016 | Flag Reply
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;
}

- srikanth bethi July 18, 2016 | Flag Reply
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;
}

- Anonymous July 18, 2016 | Flag Reply
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.

- christophe0pelletier September 18, 2016 | Flag Reply
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;

- agrawaankit60 September 22, 2016 | Flag Reply
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;
}

- S.Manjula September 23, 2016 | Flag Reply
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);
	}

- Anonymous October 18, 2016 | Flag Reply
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);
	}

- 256.cool October 18, 2016 | Flag Reply
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)

- NoOne October 18, 2016 | Flag Reply
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
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//

public class LPMain004 {

	/**
	 * 
	 * int findMidpoint(String text)
	 * 
	 * I admit, it took a while longer than average to figure out
	 * the right way to go about this. So in an interview situation, 
	 * a question like this might take me a bit longer. Bit with all
	 * such seemingly difficult talks, when you take the time to break
	 * the task into smaller tasks, the ideal solution sort of 
	 * 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);

	}

}

- perry.anderson November 25, 2016 | Flag Reply
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.

- tnutty2k8 August 01, 2017 | Flag Reply
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.

- Alex September 14, 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