## 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;

}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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 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.

Comment hidden because of low score. Click to expand.
0

Will this work for string "abcc"?

Comment hidden because of low score. Click to expand.
0

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]...

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
*/
#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 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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

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.

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

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

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

Comment hidden because of low score. Click to expand.
0

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

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

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

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

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``

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

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

}

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

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.");

}
}

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

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

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]``````

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

}

}``````

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

}

}``````

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

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

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

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.

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.

### 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.