Four Questions Asked: 1. To find a longest palindrome in a string. 2. What is a HashSet ? Difference between HashSet and TreeSet. 3. Given a list List and a function f: x - y, convert the list to map i.e. Map 4. What happens in the background (whole procedure) when you type a URL till the page is displayed ?

Question

Four Questions Asked: 1. To find a longest palindrome in a string. 2. What is a HashSet ? Difference between HashSet and TreeSet. 3. Given a list List and a function f: x -> y, convert the list to map i.e. Map 4. What happens in the background (whole procedure) when you type a URL till the page is displayed ?

Oleksiy Druzhynin · Accepted Answer

Task. To find a longest palindrome in a string.
Test1. “asd abba dsa” -> asd abba dsa
Test2. “abba” - > abba
Test3. “abcdefedcbn” -> bcdefedcb
Test4. “abcdefefedcba” -> efe
Test5. “abcdefeefedcba” -> abcdefeefedcba
Test6. “abccccccccccba” ->
Algo. Find candidate of middle seq. Check palindrom. Set middle seq to next or last seq in founded palindrom.

template
	std::pair
		getCurrentSequence(RandomAccessIterator current, RandomAccessIterator last)
{
	if (current == last)
		return make_pair(current, last);

	auto seqBegin = current, seqEnd = current;
	while (seqEnd != last && *seqBegin == *seqEnd)
		seqEnd++;
	return make_pair(seqBegin, seqEnd);
}

template
	std::pair
		getLongestPalindrome(RandomAccessIterator first, RandomAccessIterator last)
{
	if (first == last)
		return make_pair(first, last);

	auto bestPalindrome = getCurrentSequence(first, last);
	if (bestPalindrome.second == last)
		return bestPalindrome;

	auto middleSeq = getCurrentSequence(bestPalindrome.second, last);
	while (middleSeq.second != last)
	{
		auto palindromeBegin = middleSeq.first;
		auto palindromeEnd = middleSeq.second;
		auto lastSeqBegin = palindromeBegin;
		while (palindromeBegin != first && palindromeEnd != last)
		{
			if (*lastSeqBegin != *(palindromeEnd - 1))
				lastSeqBegin = palindromeEnd;

			auto beforePalindromeBegin = palindromeBegin - 1;
			auto afterPalindromeEnd = palindromeEnd + 1;
			if (*beforePalindromeBegin != *(afterPalindromeEnd - 1))
				break;
			palindromeBegin = beforePalindromeBegin;
			palindromeEnd = afterPalindromeEnd;
		}

		if (distance(bestPalindrome.first, bestPalindrome.second) < distance(palindromeBegin, palindromeEnd))
			bestPalindrome = make_pair(palindromeBegin, palindromeEnd);

		if (middleSeq.second == palindromeEnd)
			middleSeq = getCurrentSequence(palindromeEnd, last);
		else
			middleSeq = make_pair(lastSeqBegin, palindromeEnd);
	}

	return bestPalindrome;
}

Anonymous · Answer

#!/usr/bin/python

import sys

def ispalind(str) :
   isodd=True;
   if len(str)%2==0:
     isodd=False;
   stack = [];
   for x in range(0,len(str)/2):
      stack.append(str[x]);
   for x in range(len(str)/2+len(str)%2, len(str)):
      if stack.pop() != str[x]:
         return False;
   return True;

maxpalind=0;
if len(sys.argv) > 0:
   #print "ispalind(",sys.argv[1],") =",ispalind(sys.argv[1]);
   instr=sys.argv[1];
   for ii in range(0, len(instr)-1):
     for jj in range(2, len(instr)-ii+1):
        ss = instr[ii:ii+jj];
        if ispalind(ss):
           print ss,"-> is a palind";
           if(len(ss) > maxpalind):
              maxpalind=len(ss);
        else:
           print ss,"-> is NOT a palind";

print "maxpalind=", maxpalind

Google

Google interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches