Need help in writing an algorithm

Question

2.33/5 (2 votes)

See more:

I got this question from Careercup.com. It was asked in a microsoft interview.
Imagine we have a large string like this "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD" which contains multiple palindromes within it, like ABCBA, RACECAR, ARA, IAMAI etc... Now write a method which will accept this large string and return the largest palindrome from this string. If there are two palindromes which are of same size, it would be sufficient to just return any one of them.

Posted 25-Jan-14 18:55pm

puja11191

Add a Solution

Comments

Peter Leow 26-Jan-14 2:10am

An interesting question for a weekend break, this will not be the solution that you want, but I put it here just for idea sharing. try the following regexes on this online regex tester, http://www.freeformatter.com/regex-tester.html:
([A-Z]).?\1
([A-Z])([A-Z]).?\2\1
([A-Z])([A-Z])([A-Z]).?\3\2\1
([A-Z])([A-Z])([A-Z])([A-Z]).?\4\3\2\1
You will see that the largest you can get is at line 3 where it matches RACECAR.
Have a fun weekend, eveybody.

Rahul VB 26-Jan-14 3:37am

Thanks man, fantastic question. Bookmarked

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Ron Beyer · Accepted Answer · 2014-01-25T19:25:00

Normally I wouldn't do this, but it was kind of fun :)

C#

class Program
{
    static void Main(string[] args)
    {
        List<string> palens = Palendromerize("ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD");

        foreach (string palen in palens)
            Console.WriteLine("Palendrome: " + palen);

        Console.ReadKey();
    }

    static List<string> Palendromerize(string s)
    {
        string reverseStr = new string(s.Reverse().ToArray());

        List<string> retVal = new List<string>();

        for (int i = 0; i < s.Length; i++)
        {
            string s1 = new string(' ', s.Length - i - 1) + s;
            string s2 = new string(' ', i) + reverseStr;

            string matches = string.Empty;
            //Now match between the two...
            for (int x = 0; x < Math.Min(s1.Length, s2.Length); x++)
            {
                if (s1[x] == s2[x])
                    matches += s1[x];
                else
                    matches += ' ';
            }

            string[] palens = matches.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);

            for (int m = 0; m < palens.Length; m++)
                if (palens[m].Length >= 3)
                    retVal.Add(palens[m]);
        }

        return retVal;
    }
}

Output:
Palendrome: ABCBA
Palendrome: OHO
Palendrome: RACECAR
Palendrome: ARA
Palendrome: RAR
Palendrome: IAMAI

Basically this works by sliding each string along the other one, only paying attention to the pieces of the string that match up. Then you take any characters that match positions in both strings and add them to an array. Split the array removing empty entries. Then since the minimum length of a palendrome is 3, filter out the ones that are shorter and then add them to the results list.

Karthik_Mahalingam · Accepted Answer · 2014-01-25T19:29:00

Solution 2

check this link
find-longest-palindrome-in-given-string[^]

Try this simple approach using linq:

C#

string input = "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD";
            List<string> allPossibleCombination = new List<string>();
            for (int i = 0; i < input.Length; i++)
                for (int j = 0; j < input.Length; j++)
                    try
                    {
                        allPossibleCombination.Add(input.Substring(i, j));
                    }
                    catch (Exception)
                    {
                        break;
                    }
            var palidroms = allPossibleCombination.Where(k => new string(k.Reverse().ToArray()) == k);
            string max = palidroms.OrderByDescending(k => k.Length).First();
            // output : "RACECAR"

Posted 25-Jan-14 19:29pm

Karthik_Mahalingam

Updated 25-Jan-14 19:46pm

v3

Comments

Rahul VB 26-Jan-14 3:35am

great work.
ctrl + shift + d

Karthik_Mahalingam 26-Jan-14 3:57am

Thanks Rahul :)

Rahul VB 26-Jan-14 4:07am

but Karthik i cant beleive that in interviews they ask to write a code. I mean its a good question. But human mind is unpredictable, suppose you don't answer this question, may be it dint strike you at that time, may be later it will. Asking the logic or pseudo code is understandable, but writing a code like above in an interview might have taken time. What do you say?

Karthik_Mahalingam 26-Jan-14 4:10am

no they wont ask the code for complex logics, they will ask only the algorithm.
if it is technical written round they might ask the code..
if big companies like Microsoft,Google and more... they might ask the code or a mini project too. as they are ready to pay some huge packages :)

puja11191 26-Jan-14 11:08am

HATS OFF TO YOU SIR.. :)

Karthik_Mahalingam 26-Jan-14 13:18pm

Thanks puja :)