CareerCup

from itertools import combinations


def is_palindrome(my_dict, key_combos):
    results = {}    

    for keys in key_combos:
        phrase = my_dict[keys[0]]+my_dict[keys[1]]

        if phrase == phrase[::-1]:
            results[keys[0]] = my_dict[keys[0]]
            results[keys[1]] = my_dict[keys[1]]

    return results


if __name__ == "__main__":
    my_dict = {"i1": "xenonex", "i2": "xenon", "i3": "none"}

    key_combo = list(combinations(my_dict.keys(), 2))
    key_combo_reverse = [(i[1], i[0]) for i in key_combo]
    key_combo.extend(key_combo_reverse)

    results = is_palindrome(my_dict, key_combo)
    print(results)

from itertools import combinations


def is_palindrome(my_dict, key_combos):
    results = {}    

    for keys in key_combos:
        phrase = my_dict[keys[0]]+my_dict[keys[1]]

        if phrase == phrase[::-1]:
            results[keys[0]] = my_dict[keys[0]]
            results[keys[1]] = my_dict[keys[1]]

    return results


if __name__ == "__main__":
    my_dict = {"i1": "xenonex", "i2": "xenon", "i3": "none"}

    key_combo = list(combinations(my_dict.keys(), 2))
    key_combo_reverse = [(i[1], i[0]) for i in key_combo]
    key_combo.extend(key_combo_reverse)

    results = is_palindrome(my_dict, key_combo)
    print(results)

bool isPalindromePair(const string& s1, const string& s2)
{
	int totalLength = s1.length() + s2.length();
	int maxIndex = totalLength / 2;

	for (int idx = 0; idx <= maxIndex; idx++)
	{
		const string* ptr1 = &s1;
		int idx1 = idx;
		if (idx1 >= s1.length())
		{
			ptr1 = &s2;
			idx1 -= s1.length();
		}

		const string* ptr2 = &s2;
		int idx2 = idx;
		if (idx2 >= s2.length())
		{
			ptr2 = &s1;
			idx2 -= s2.length();
		}
		idx2 = ptr2->length() - 1 - idx2;

		if (ptr1->at(idx1) != ptr2->at(idx2))
			return false;
	}
	return true;
}

void main()
{
	vector<string> dictionary = { "none", "xenon", "nonexexenon" };

	vector<pair<string*, string*>> results;
	for (int i = 0; i < dictionary.size(); i++)
		for (int j = i+1; j < dictionary.size(); j++)
			if (isPalindromePair(dictionary[i], dictionary[j]) || isPalindromePair(dictionary[j], dictionary[i]))
				results.push_back(make_pair(&dictionary[i], &dictionary[j]));

	for (auto&& pair : results)
		printf("%s %s\n", pair.first->c_str(), pair.second->c_str());

	_getch();
}

I think it would be better to concatenate two strings, and starts from two ends to the middle to check if the pair is palindrome.

String palindrome (String str1, String str2)
{
String str = str1.concat(str2);
int headPointer = 0; endPointer = str.length() -1;

while(headPointer != endPointer || endPointer - headPointer != 1)
{
if(!str.charAt(headPointer).equals(str.charAt(endPointer))
return "Not Palidrome";
endPointer++;
headPointer++;
}

if(str.charAt(endPointer).equals(str.charAt(headPointer)))
return "Palindrome";
else
return "Non Palindrome";
}

1) Brute force solution : for look for all pairs (si, sj) with (i < j) check if (si concat sj) is a palindrome. Complexity O(n^2 l) where l is max length of input strings

2)
a) Construct trie over all input strings (mark leaves as regular)
b) All all input strings reverse and add to trie (mark these leaves as reversed)
c) For each node on trie, count number of leaves of type reversed that can be reached via paths that are palindromes , say c(node) is this count
d) Sum c(node) where node is a regular leaf

Complexity O(nl) , but very difficult to prove complexity and get working code in 45 minutes

Here is solution using trie

public class PairOfPalindrome {

    static class ResultHelper {
        public int index1, index2;


        public ResultHelper(int index1, int index2) {
            this.index1 = index1;
            this.index2 = index2;
        }

        @Override
        public String toString() {
            return "{" +
                    "index1=" + index1 +
                    ", index2=" + index2 +
                    '}';
        }
    }

    static class TrieNode {

        public boolean isLeaf = false;
        public Map<Character, TrieNode> children = new HashMap<>();
        public List<Integer> palindromsWithinString = new ArrayList<>();
        public int idOfThisString = -1;
    }

    static class Trie {

        TrieNode root;

        void insert(String toInsert, int myId) {
            if (root == null)
                root = new TrieNode();

            TrieNode pCrawl = root;

            for (int i = toInsert.length() - 1; i >= 0; i--) {

                char currentChar = toInsert.charAt(i);

                if (!pCrawl.children.containsKey(currentChar))
                    pCrawl.children.put(currentChar, new TrieNode());


                if (isPalindrome(toInsert, 0, i))
                    pCrawl.palindromsWithinString.add(myId);

                pCrawl = pCrawl.children.get(currentChar);


            }
            pCrawl.isLeaf = true;
            pCrawl.idOfThisString = myId;


        }

        private boolean isPalindrome(String toInsert, int from, int to) {

            while (from < to && toInsert.charAt(from) == toInsert.charAt(to)) {
                from++;
                to--;
            }

            if (from == to)
                return true;
            return false;
        }

        public List<ResultHelper> search(String toSearch, int myId) {

            List<ResultHelper> resultHelpers = new ArrayList<>();
            if (search(toSearch, myId, resultHelpers))
                return resultHelpers;
            else
                return Collections.EMPTY_LIST;

        }

        private boolean search(String toSearch, int myId, List<ResultHelper> resultHelpers) {
            if (null == root)
                return false;


            TrieNode pCrawl = root;

            for (int i = 0; i < toSearch.length(); i++) {

                char currentChar = toSearch.charAt(i);

                if (!pCrawl.children.containsKey(currentChar))
                    return false;

                pCrawl = pCrawl.children.get(currentChar);

                if (pCrawl.idOfThisString >= 0 && pCrawl.idOfThisString != myId
                        && isPalindrome(toSearch, i, toSearch.length() - 1)) {
                    resultHelpers.add(new ResultHelper(myId, pCrawl.idOfThisString));

                }


            }

            for (int rem : pCrawl.palindromsWithinString) {
                resultHelpers.add(new ResultHelper(myId, rem));
            }

            return true;
        }


    }

    public static void main(String args[]) {

        String[] list = {"abc", "xyxcba", "geekst", "or", "keeg", "bc"};

        Trie trie = new Trie();
        for (int i = 0; i < list.length; i++)
            trie.insert(list[i], i);

        for (int i = 0; i < list.length; i++) {
            List<ResultHelper> result = trie.search(list[i], i);
            if (!result.isEmpty())
                System.out.println(result);
        }


    }

}