Intuit Interview Question for Senior Software Development Engineers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

Posting a CPP code solution.

bool HasPalindrome(char *str)
{
	for(int i=1; i < strlen(str); i++)
	{
		if( str[i] == str[i+1] && str[i-1] == str[i+2])
			return true;
		if(str[i-1] == str[i+1])
			return true;

	}
	return false;

}

- Popoyee August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wow.. That's Very clean, simple and Very Optimized solution. That's Great!!
But Looking at code, if the input is "xyz" which does not contain any palindrome,
the function breaks with array index out of bound in second iteration because

i=2

and
array for index

str[i+2]

is out of bound.

Please correct me if i'm wrong.

- csenasa August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wat about "madam";
     i dnt think it would work here.

- manish27.p August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

csenasa, you are correct. I have corrected it below.

bool HasPalindrome(char *str)
{

	int n = strlen(str);
	for(int i=1; i < n - 1; i++)
	{
		if( i < n - 2 && str[i] == str[i+1] && str[i-1] == str[i+2])
			return true;
		if(str[i-1] == str[i+1])
			return true;

	}
	return false;

}

When input string is "madam"


when i will be 2
str[i] will be 'd', it will go in 2nd if and str[i-1] will be equal to str[i+1] so it will return true.

- Popoyee August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will this work for string "abcc"?

- Anonymous August 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nope it wont work for abcc. but its not hard to add on... you may want to add on something like str[i-1] == str[i]...

- stevejabs August 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This problem can be solved with a stack-based approach. I have tested the following code and it works.

/**
* Description: Evaluates whether a string contains a palindrome or not
* Author: Carlos F. Perea
* License: Open
*/
#include <iostream>
#include <string>
#include <stack>
#include <assert.h>

using namespace std;

/**
* Checks whether a string contains a palindrome
* @param string	String to be checked
* @return   bool	True if the string contains a palindrome, false otherwise
*/
bool isPalindrome(string str)
{
	stack<char> s;
	for (int i = 0; i < str.size(); ++i)
	{
		char currentCharacter = str.at(i);
		if (!s.empty())
		{
			char topCharacter = s.top();
			if (currentCharacter == topCharacter)
				return true;
			if (s.size() > 1)
			{
			    s.pop();
			    char secondOnTop = s.top();
                if (currentCharacter == secondOnTop)
                    return true;
                else
                    s.push(topCharacter);
			}
		}
		s.push(currentCharacter);
	}
	return false;
}

int main()
{
	string testString1 = "1234xyzyx5678";
	string testString2 = "madam";
	string testString3 = "abcc";
	string testString4 = "not";
	string testString5 = "abcdefghijklmnopqrstuvwxyz";
	// test the different words
	assert(isPalindrome(testString1) == true);
	assert(isPalindrome(testString2) == true);
	assert(isPalindrome(testString3) == true);
	assert(isPalindrome(testString4) == false);
	assert(isPalindrome(testString5) == false);
	return 0;
}

- cfperea August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is neat! At the same time, I wanted to bring your attention to the fact that you are only using the last 2 characters at most. So maintaining a stack is probably an overkill.

- Gary December 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a stack and see if a pop can ever be made. If a pop is possible, then there is a palindrome, else not.

- Learner August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

It's so simple. Let the string be: S and it's reverse be: Sr. Find the lcsubstr = LCSubstr(S, Sr). if length(lcsubstr) > 1 return True; else return False. Overall complexity will be O(|S|^2)

Note: LCSubstr(S1, S2) finds the longest common substring of S1 and S2. It's complexity is O(|S1|*|S2|)

- Sunny Mitra August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# code, simple solution:

public static Boolean HasPalindrome(String value) {
      if (String.IsNullOrEmpty(value))
        return false;

      // We are not supposed to find out the longest palindrom, 
      // so we may let ourself to fail on "apqabaqpa" 
      // with detecting "apqabaqpa", providing we are able to find out "aba"
      for (int i = 0; i < value.Length - 1; ++i) {
        int index = value.IndexOf(value[i], i + 1);

        if (index < 0)
          continue;

        Boolean hasCounterExample = false;

        for (int j = 0; j < (index - i - 1) / 2; ++j)
          if (value[j + i + 1] != value[index - j - 1]) {
            hasCounterExample = true;

            break;
          }

        if (!hasCounterExample)
          return true;
      }

      return false;
    }

- Dmitry Bychenko August 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String s1="129321";
String rev = new StringBuffer(s1).reverse().toString();

if(s1.equals(rev))
System.out.println("Palindrome");
else
System.out.println("Not Palindrome");

- Gareth Dsouza August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you are checking the exact characters it works for full string palidromes like madam but not for " Contains a Palindrome " words like cmadamc

- Anonymous March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a Cpp solution.

#include <iostream>
#include <string>

bool hasPalindrome(std::string aString);

using namespace std;

int main()
{
    std::string palin_1 = "xyyz";
    std::string palin_2 = "malayalam";
    std::string not_palin_1 = "abc";
    std::string not_palin_2 = "egha";
    
   cout << palin_1 << " - " << hasPalindrome(palin_1)  << endl; 
   cout << palin_2 << " - " << hasPalindrome(palin_2)  << endl; 
   cout << not_palin_1 << " - " << hasPalindrome(not_palin_1)  << endl; 
   cout << not_palin_2 << " - " << hasPalindrome(not_palin_2)  << endl; 
   
   return 0;
}

bool hasPalindrome(std::string aString){
    
    for(size_t i =1;i < aString.length(); i++)
    {
        if(aString[i-1] == aString[i] || aString[i-1] == aString[i+1])
        {
            return true;
        }
        
    }
    
    return false;
}

- Meghamind August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int has_palindrome(char* s)
{
char* tmp = s;

while (*tmp++) {
if (*(tmp+1) && *s == *(tmp+1))
return 1;
s++;
}

return 0;
}

- Neel August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(hasPalindrome("abczxy1yxzabc".toCharArray()));
		System.out.println(hasPalindrome("xmadedame".toCharArray()));
		System.out.println(hasPalindrome("1234abba5671".toCharArray()));
		
	}
	
	public static boolean hasPalindrome(char[] s) {
		int j = s.length - 1;
		int midPoint = s.length / 2;
		boolean hasPalindrome = false;
		for (int i=0;i<s.length; i++) {
			if (i == midPoint) {
				break;
			}
			if (s[i] == s[j]) {
				hasPalindrome = true;
			} else {
				hasPalindrome = false;
			}
			j--;
		}
		return hasPalindrome;
	}
}

- Addy27 September 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and

bool isPalindrome(const char* in)
{
const char* ptrStart = in;
const char* ptrEnd = in+strlen(in)-1;
int i = 0;
while(i < strlen(in)/2)
{
if(*ptrStart != *ptrEnd)
return false;
ptrStart++;
ptrEnd--;
i++;
}
return true;
}

and

- Anonymous October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isPalindrome(const char* in)
{
    const char* ptrStart = in;
    const char* ptrEnd = in+strlen(in)-1;
    int i = 0;
    while(i < strlen(in)/2)
    {
        if(*ptrStart != *ptrEnd)
            return false;
        ptrStart++;
        ptrEnd--;
        i++;
    }
    return true;
}

- Phyo October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String checkPalin(String str){
		int len=str.length()-1;
		int count=0;
		for(int i=0; i<len/2; i++){
			if(str.charAt(i)!=str.charAt(len--)){
				//count++;
				return "not palin";
			}else{
				count++;
			}
		}
		
		if(count==len/2)
			return "palin";
		
		return "not palin";

}

- Jai November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package org.test.string;

/**
* @author naresh
*
*/
public class Palindrome {

static boolean hasPalindrome(char[] arr){
boolean val = false;
if(arr.length % 2 != 0){
int mid = arr.length / 2;
for(int i = 1 ; i <= mid ; i++){
if(arr[mid - i] == arr[mid + i]){
val = true;
}else{
break;
}
}
}
return val;
}

public static void main(String[] args) {
System.out.println(hasPalindrome("121".toCharArray()));
}
}

- naresh meena November 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package trial;
import java.util.*;

class Palindrome
{
public static void main(String args[])
{
String Input_string, Reverse_string="";
Scanner in = new Scanner(System.in);

System.out.println("Enter a string to check if it is a palindrome");
Input_string = in.nextLine();

int length = Input_string.length();

for ( int i = length - 1 ; i >= 0 ; i-- )
Reverse_string = Reverse_string + Input_string.charAt(i);

if (Input_string.equals(Reverse_string))
System.out.println("Palindrome.");
else
System.out.println("Not a Palindrome.");

}
}

- Anonymous January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have used a very basic approach. Hope it will help you guys.

public static void main(String[] args) {
    isPalindromeSubstring isp = new isPalindromeSubstring();
    String s="abcdefghijklmnbb";
    isp.functionPalindrome(s);
    if(isp.done==false)
      System.out.println("No aplindrome substring");
  }
  
  public void functionPalindrome(String s){
    if(checkPalindrome(s) && s.length()>=2 && done==false){
      done=true;
      System.out.println("String contains palindrome which is "+s);
      return;
    }
    else{
      if(s.length()>=2){
      functionPalindrome(s.substring(1));
      functionPalindrome(s.substring(0, s.length()-1));
    }
    }
    
  }
  
  boolean checkPalindrome(String s){
    int j=s.length()-1;
    for(int i=0;i<=j;i++){
      if(s.charAt(i)==s.charAt(j))
        j--;
      else{
        return false;
      }
    }
    
    return true;
  }

- razik.islam February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		System.out.println(hasPalindrome("abczxy1yxzabc"));
		System.out.println(hasPalindrome("arora"));
		System.out.println(hasPalindrome("1234abba4321"));
	}
	
	public static boolean hasPalindrome(String input) {
		
		char[] s = input.toCharArray();
		Stack st = new Stack();
		boolean hasPalindrome = false;
		for (int i=0;i<s.length; i++) {
		st.push(s[i]);
		}
		String reversed ="";
		for (int i=0;i<s.length; i++) {
		reversed=reversed+st.pop();
		}
		return reversed.equals(input);
	}
}

- S.Arora April 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I tried a python code, check here

def checkPalindrome(inputString = ""):
    if inputString[::-1] == inputString:
        return True
    else:
        return False

strings = "abcdefeabc"
for i in range(len(strings)):
    for j in range(i+1, len(strings)):
        if strings[i] == strings[j]:
            if checkPalindrome(strings[i:j+1]):
                print strings[i:j+1]

- Raymend June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class HasPalindrome {

	public static void palindromeCheck(String str, int startIndex, int lastIndex, int index)
	{
		while(index != str.length()-3)
		{
			palindrome(str,0,2,index);
			index++;
		}
	}
	public static void palindrome(String str, int startIndex, int lastIndex, int index)
	{	
		int i=0,j=0,k = 0;
		while(j != str.length()-index)
		{
			int notEqual = 0;
			for(  i = k,j = i+index ; i < j ; i ++, j--)
			{
				if(str.charAt(i) != str.charAt(j))
					notEqual++;
			}

			if(notEqual == 0)
			{
				System.out.println(str.substring(k,k+index+1));	
			}
			k ++;
		}
	}


	public static void main(String[] args) {

		String str = "1234xyzyx5678";
		palindromeCheck(str,0,2,2);

	}


}

- Anonymous July 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class HasPalindrome {

	public static void palindromeCheck(String str, int startIndex, int lastIndex, int index)
	{
		while(index != str.length()-3)
		{
			palindrome(str,0,2,index);
			index++;
		}
	}
	public static void palindrome(String str, int startIndex, int lastIndex, int index)
	{	
		int i=0,j=0,k = 0;
		while(j != str.length()-index)
		{
			int notEqual = 0;
			for(  i = k,j = i+index ; i < j ; i ++, j--)
			{
				if(str.charAt(i) != str.charAt(j))
					notEqual++;
			}

			if(notEqual == 0)
			{
				System.out.println(str.substring(k,k+index+1));	
			}
			k ++;
		}
	}


	public static void main(String[] args) {

		String str = "1234xyzyx5678";
		palindromeCheck(str,0,2,2);

	}


}

- Anonymous July 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class HasPalindrome {
	
	public static void main(String [] args){
		
		HasPalindrome pn = new HasPalindrome();
		
		if(pn.hasPalindrome("malayalam")){
			
			System.out.println("Palindrome");
			
		} else {
			
			System.out.println("Not Palindrome");
			
		}	
	}
	
	public boolean hasPalindrome(String original){
		
		boolean isTrue = false;
		int i = original.length()-1;
		int j=0;
		while(i > j){
			if(original.charAt(i) != original.charAt(j)){
				isTrue = false;
			} else {
				isTrue = true;
			}
			i--;
			j++;
		}
		if(isTrue = true){
			return true;
		} else {
			return false;
		}
	}
}

- codingNoob March 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool HasPalidrome(string testString)
{
for (int i = 0; i < testString.Length; i++)
{
if (i < testString.Length-1 && testString[i] == testString[i+1])
return true;
else if (i < testString.Length-2 && testString[i] == testString[i+2])
return true;
}
return false;
}

- shak August 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hasPalindrome(String str){

// check null
if(str == null)
    return false;

str = str.toLowerCase();
int len = str.length();
if (len == 1)
    return true;

// check if there is a possibility of the subStr being a palindrome
	for (int i =0; i< len) {
		for (j = len-1; j>i; j- -){
			if(str.charAt(i).equalsIgnoreCase(str.charAt(j))){
				String subStr = str.subString(i, j);
				if(isPalidrome(subStr))
					return true;
			}			
		}
	}
return false;
}

isPalidrome (String subStr){
	if (subStr == null) return false;
	String rev = String.reverse();
	if (subStr.equals(rev))
		return true;
	}
	return false;
}

- dhirendra.sinha January 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;

public class Palindrome {

//Input Samples : "1234xyzyx5678" , "abcdefeabc" , "abcba1234xyzyx5678abcdefeabc"
public static String input = null;
public static void main(String[] args) {

Scanner scan = new Scanner(System.in);
input = scan.next();
int count = 0;
char[] charArray = input.toCharArray();
if(input.length() == 2) {
if(charArray[0] == charArray[1]) {
System.out.println(input);
count++;
}
}
for(int i=1; i< (charArray.length-1); i++) {
if(charArray[i-1] == charArray[i+1]) {
isPalindrom(charArray, i-1, i, i+1);
count++;
}
}

if(count == 0) {
System.out.println("Input "+input+" is not a Palindrome");
}

}

public static void isPalindrom(char[] charArray, int left, int loc, int right) {
if(left <= 0 || right >= charArray.length) {
System.out.println("Found the end");
if(right > 1) {
System.out.println(input.substring(left, right+1));
}
return;
}

if(charArray[left] == charArray[right]) {
isPalindrom(charArray, left-1, loc, right+1);
}else {
System.out.println(input.substring(left+1, right));
}

}


}


// I have not covered scenario example 2 letters as palindrome with in a string, //considered minimum as 3 char.

- Laxmikanth P G December 25, 2016 | 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