Intuit Interview Question
Senior Software Development EngineersCountry: India
Interview Type: In-Person
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, 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.
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;
}
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|)
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;
}
String s1="129321";
String rev = new StringBuffer(s1).reverse().toString();
if(s1.equals(rev))
System.out.println("Palindrome");
else
System.out.println("Not Palindrome");
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;
}
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;
}
}
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()));
}
}
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.");
}
}
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;
}
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);
}
}
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]
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);
}
}
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);
}
}
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;
}
}
}
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;
}
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.
Posting a CPP code solution.
- Popoyee August 10, 2013