Microsoft Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
/**
* Compare the chars at the given position are equal
*/
const charsAreEqual = (str, leftRide, rightRide) =>
str.charAt(leftRide) == str.charAt(rightRide);
/**
* Check the rides are in Range
*/
const rideInRange = (str, leftRide, rightRide) =>
leftRide > 0 && rightRide < str.length;
const longestSubstringPalindrome = str => {
let longest = 0;
let palindrome;
for (let i = 1; i < str.length; i++) {
let leftRide = i - 1;
let rightRide = i + 1;
// The left (i1) ride decreases one position while the right (i2)
// increases one on each iteration. Iterate while the chars at i2 and i2
// are the same. Compare at any iteration if the lenth i2 - i1 becomes longer
// than the previously marked as longest. In this case, update the longest and the
// palindrome variable. Then increase the riding i's.
while (charsAreEqual(str, leftRide, rightRide)
&& rideInRange(str, leftRide, rightRide)) {
if (rightRide - leftRide > longest) {
palindrome = str.substring(leftRide, rightRide+1);
longest = rightRide - leftRide;
}
leftRide--;
rightRide++;
}
}
return palindrome;
}
longestSubstringPalindrome('aaababaacaacadaada');
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Palindrome {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String st = sc.next();
Palindrome pl = new Palindrome();
int max = 1;
String sb = st.substring(0, 1);
for (int i = 0; i < st.length(); i++) {
for (int j = i; j < st.length(); j++) {
if (pl.longestPalindrom(st.substring(i, j + 1))) {
if (max < (j - i)) {
max = j - i;
sb = st.substring(i, j + 1);
}
}
}
}
System.out.println(sb);
}
public boolean longestPalindrom(String s) {
if (s == null || s.length() <= 1)
return true;
for (int i = 0; i < s.length() / 2; i++) {
if (s.charAt(i) == s.charAt(s.length() - i - 1))
continue;
else
return false;
}
return true;
}
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char myarray[30]="feveffeve";
void reverse_str(char* str)
{
for(int i=0; i<(int)strlen(str)/2; i++){
char temp = str[i];
str[i] = str[strlen(str)-i-1];
str[strlen(str)-i-1] = temp;
}
}
int main()
{
if(NULL == myarray){
printf("Please provide correct string!!");
return -1;
}
printf("String length: %d\n", strlen(myarray));
int length = 0;
for(int i=0; i<=strlen(myarray)-2; i++){
for(int j=1; j<=(strlen(myarray)-i-1); j++){
if(length > j){
break;
}
char *sub1 = (char*)calloc(j, sizeof(char));
char *sub2 = (char*)calloc(j, sizeof(char));
strncpy(sub1, myarray+i, j);
strncpy(sub2, myarray+i+1, j);
reverse_str(sub2);
if(!strcmp(sub1,sub2)){
printf("%s, %d\n",sub1, j);
if(length < j){
length = j;
}
}
free(sub1);
free(sub2);
}
}
printf("Length of largest palindrome : %d", length+1);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char myarray[30]="feveffeve";
void reverse_str(char* str)
{
for(int i=0; i<(int)strlen(str)/2; i++){
char temp = str[i];
str[i] = str[strlen(str)-i-1];
str[strlen(str)-i-1] = temp;
}
}
int main()
{
if(NULL == myarray){
printf("Please provide correct string!!");
return -1;
}
printf("String length: %d\n", strlen(myarray));
int length = 0;
for(int i=0; i<=strlen(myarray)-2; i++){
for(int j=1; j<=(strlen(myarray)-i-1); j++){
if(length > j){
break;
}
char *sub1 = (char*)calloc(j, sizeof(char));
char *sub2 = (char*)calloc(j, sizeof(char));
strncpy(sub1, myarray+i, j);
strncpy(sub2, myarray+i+1, j);
reverse_str(sub2);
if(!strcmp(sub1,sub2)){
printf("%s, %d\n",sub1, j);
if(length < j){
length = j;
}
}
free(sub1);
free(sub2);
}
}
printf("Length of largest palindrome : %d", length+1);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char myarray[30]="feveffeve";
void reverse_str(char* str)
{
for(int i=0; i<(int)strlen(str)/2; i++){
char temp = str[i];
str[i] = str[strlen(str)-i-1];
str[strlen(str)-i-1] = temp;
}
}
int main()
{
if(NULL == myarray){
printf("Please provide correct string!!");
return -1;
}
printf("String length: %d\n", strlen(myarray));
int length = 0;
for(int i=0; i<=strlen(myarray)-2; i++){
for(int j=1; j<=(strlen(myarray)-i-1); j++){
if(length > j){
break;
}
char *sub1 = (char*)calloc(j, sizeof(char));
char *sub2 = (char*)calloc(j, sizeof(char));
strncpy(sub1, myarray+i, j);
strncpy(sub2, myarray+i+1, j);
reverse_str(sub2);
if(!strcmp(sub1,sub2)){
printf("%s, %d\n",sub1, j);
if(length < j){
length = j;
}
}
free(sub1);
free(sub2);
}
}
printf("Length of largest palindrome : %d", length+1);
return 0;
}
Something like this?
def longest_substring_palindrome(string)
max_length = 0
substrings = []
(1...string.length).each do |range|
string.chars.each_cons(range) do |substring|
substrings << substring
end
end
substrings.each do |substring|
max_length = [max_length, substring.length].max if is_palindrome?(substring)
end
max_length
end
def is_palindrome?(string)
string == string.reverse
end
Something like this?
def longest_substring_palindrome(string)
max_length = 0
substrings = []
(1...string.length).each do |range|
string.chars.each_cons(range) do |substring|
substrings << substring
end
end
substrings.each do |substring|
max_length = [max_length, substring.length].max if is_palindrome?(substring)
end
max_length
end
def is_palindrome?(string)
string == string.reverse
end
#include <iostream>
#include <string>
using namespace std;
class Palindrome {
public:
string s;
Palindrome(string s):s(s) {}
void longestSubstringPalindrome();
};
void Palindrome::longestSubstringPalindrome() {
int max_len = 1;
int len = s.length();
int i = 1;
int j;
int k;
int start = 0;
while(i < len) {
// considering odd.
j = i -1;
k = i + 1;
int len_so_far = 1;
while( j >=0 && k <len) {
if(s[j] == s[k]) {
j--;
k++;
len_so_far +=2;
continue;
}
break;
}
if(max_len < len_so_far) {
max_len = len_so_far;
start = j + 1;
}
// Cosidering Even case
if(s[i] == s[i+1]) {
j = i - 1;
k = i + 2;
len_so_far = 2;
while( j >=0 && k <len) {
if(s[j] == s[k]) {
j--;
k++;
len_so_far +=2;
continue;
}
break;
}
}
if(max_len < len_so_far) {
max_len = len_so_far;
start = j + 1;
}
i++;
}
cout<<"Longest Palindrom substring is of length " << max_len << " : "<< s.substr(start,max_len) <<"\n";
}
O(N^2)
- sudip.innovates October 13, 2017