Walmart Labs Interview Question Software Developers
Country: India
Interview Type: Written Test
#include <bits/stdc++.h>
using namespace std;
void solver(string s1, string s2){
int n=s1.size();
int m=s2.size();
if(m>n){
cout<<"-1";
return;
}
string resStr="";
int res=INT_MAX;
for(int i=0;i<=n-m;i++){
string temp=s1.substr(0,i)+s2+s1.substr(i+m);
int operation=0;
for(int j=i;j<i+m;j++){
if(temp[j]!=s1[j]){
operation++;
}
}
bool isPossible=true;
for(int j=0;j<(n+1)/2;j++){
if((j<i || n-j-1>=i+m) && temp[j]!=temp[n-j-1]){
/* atleast one word should be outside of the substring range and it should be of same character,
so change the character which is outside of range with the inside character */
if(j<i){
temp[j]=temp[n-j-1];
}
else{
temp[n-j-1]=temp[j];
}
operation++;
}
else if(temp[j]!=temp[n-j-1]){
/* this means both start and end index are now in range of substring so if the substring itself
is not making palindrome, just break out, since we cannot change the substring as we need it compulsarily */
isPossible=false;
break;
}
}
if(isPossible==true){
if(res>operation){
resStr=temp;
res=operation;
}
}
}
if(res==INT_MAX){
cout<<"-1";
return;
}
cout<<res<<" "<<resStr<<endl;
}
int main(){
string word[]={"abbd","aaaaa","abcd"};
string prev_word[]={"mr","bbb","zc"};
for(int i=0;i<3;i++){
solver(word[i],prev_word[i]);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
int l1=s1.length(),l2=s2.length();
int ans=INT_MAX;
if(l2>l1){
cout<<-1<<endl; // not possible
return 0;
}
for(int i=0 ; i<l1-l2+1 ; i++){
string temp=s1.substr(0,i)+s2+s1.substr(i+l2); // place s2 in all possible positions in s1
int cost=0;
// calculate cost to place s2
for(int j=i ; j<i+l2 ; j++){
if(s1[j]!=temp[j])
cost++;
}
int z=0;
// find the cost to convert new string to palindrome
for(int j=0 ; j<ceil(l1/2.0) ; j++){
if((j<i || j>=i+l2) && temp[j]!=temp[l1-j-1]) // if s2 is in the first half of new string
cost++;
else if(temp[j]!=temp[l1-j-1] && (l1-j-1<i || l1-j-1>=i+l2)) // if s2 is in the second half of new string
cost++;
else if(temp[j]!=temp[l1-j-1]){ // if s2 is in both halves
z=1;
break;
}
}
if(z==0)
ans=min(ans,cost);
}
if(ans==INT_MAX)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
Python Code
def count_op(s1,s2):
if s1==s2:
return 0
replace = 0
d1={};d2={}
for i in s1:
d1[i] = d1.get(i,0)+1
for i in s2:
d2[i] = d2.get(i,0)+1
for i in d2:
if i not in d1:
replace+= d2[i]
elif d2[i]>d1[i]:
replace+= d2[i] - d1[i]
return replace
s1 = input()
s2= input()
print(count_op(s1,s2))
import java.io.*;
import java.util.*;
import java.lang.*;
public class substringpalindrome
{
public static void main(String args[])
{
String s1,s2,snew,sleft,sright,rev;
int l1,l2;
Scanner s=new Scanner(System.in);
int[] arr=new int[20];
s1=s.next();
s2=s.next();
l1=s1.length();
l2=s2.length();
int count=0,mini=9999;
for(int i=0;i<=l1-l2;i++)
{
if(i==0)
{
sleft=s2;
sright=s1.substring(i+l2,l1);
snew=sleft+sright;
}
else
{
sleft=s1.substring(0,i);
sright=s2;
snew=sleft+sright+s1.substring(i+l2,l1);
}
StringBuilder sb=new StringBuilder(snew);
sb.reverse();
rev=sb.toString();
if(snew.equals(rev))
{
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j)!=s1.charAt(i+j))
{
count+=1;
}
}
if(count<mini)
{
mini=count;
}
}
}
System.out.println(mini);
}
}
import java.io.*;
import java.util.*;
import java.lang.*;
public class substringplaindrome
{
public static void main(String args[])
{
String s1,s2,snew,sleft,sright,rev;
int l1,l2;
Scanner s=new Scanner(System.in);
int[] arr=new int[20];
s1=s.next();
s2=s.next();
l1=s1.length();
l2=s2.length();
int count=0,mini=9999;
for(int i=0;i<=l1-l2;i++)
{
if(i==0)
{
sleft=s2;
sright=s1.substring(i+l2,l1);
snew=sleft+sright;
}
else
{
sleft=s1.substring(0,i);
sright=s2;
snew=sleft+sright+s1.substring(i+l2,l1);
}
StringBuilder sb=new StringBuilder(snew);
sb.reverse();
rev=sb.toString();
if(snew.equals(rev))
{
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j)!=s1.charAt(i+j))
{
count+=1;
}
}
if(count<mini)
{
mini=count;
}
}
}
System.out.println(mini);
}
}
simple java solution
import java.io.*;
import java.util.*;
import java.lang.*;
public class substringpalindrome
{
public static void main(String args[])
{
String s1,s2,snew,sleft,sright,rev;
int l1,l2;
Scanner s=new Scanner(System.in);
int[] arr=new int[20];
s1=s.next();
s2=s.next();
l1=s1.length();
l2=s2.length();
int count=0,mini=9999;
for(int i=0;i<=l1-l2;i++)
{
if(i==0)
{
sleft=s2;
sright=s1.substring(i+l2,l1);
snew=sleft+sright;
}
else
{
sleft=s1.substring(0,i);
sright=s2;
snew=sleft+sright+s1.substring(i+l2,l1);
}
StringBuilder sb=new StringBuilder(snew);
sb.reverse();
rev=sb.toString();
if(snew.equals(rev))
{
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j)!=s1.charAt(i+j))
{
count+=1;
}
}
if(count<mini)
{
mini=count;
}
}
}
System.out.println(mini);
}
}
#include <bits/stdc++.h>
using namespace std;
void solver(string s1, string s2){
int n=s1.size();
int m=s2.size();
if(m>n){
cout<<"-1";
return;
}
string resStr="";
int res=INT_MAX;
for(int i=0;i<=n-m;i++){
string temp=s1.substr(0,i)+s2+s1.substr(i+m);
int operation=0;
for(int j=i;j<i+m;j++){
if(temp[j]!=s1[j]){
operation++;
}
}
bool isPossible=true;
for(int j=0;j<(n+1)/2;j++){
if((j<i || n-j-1>=i+m) && temp[j]!=temp[n-j-1]){
/* atleast one word should be outside of the substring range and it should be of same character,
so change the character which is outside of range with the inside character */
if(j<i){
temp[j]=temp[n-j-1];
}
else{
temp[n-j-1]=temp[j];
}
operation++;
}
else if(temp[j]!=temp[n-j-1]){
/* this means both start and end index are now in range of substring so if the substring itself
is not making palindrome, just break out, since we cannot change the substring as we need it compulsarily */
isPossible=false;
break;
}
}
if(isPossible==true){
if(res>operation){
resStr=temp;
res=operation;
}
}
}
if(res==INT_MAX){
cout<<"-1";
return;
}
cout<<res<<" "<<resStr<<endl;
}
int main(){
string word[]={"abbd","aaaaa","abcd"};
string prev_word[]={"mr","bbb","zc"};
for(int i=0;i<3;i++){
solver(word[i],prev_word[i]);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
void solver(string s1, string s2){
int n=s1.size();
int m=s2.size();
if(m>n){
cout<<"-1";
return;
}
string resStr="";
int res=INT_MAX;
for(int i=0;i<=n-m;i++){
string temp=s1.substr(0,i)+s2+s1.substr(i+m);
int operation=0;
for(int j=i;j<i+m;j++){
if(temp[j]!=s1[j]){
operation++;
}
}
bool isPossible=true;
for(int j=0;j<(n+1)/2;j++){
if((j<i || n-j-1>=i+m) && temp[j]!=temp[n-j-1]){
/* atleast one word should be outside of the substring range and it should be of same character,
so change the character which is outside of range with the inside character */
if(j<i){
temp[j]=temp[n-j-1];
}
else{
temp[n-j-1]=temp[j];
}
operation++;
}
else if(temp[j]!=temp[n-j-1]){
/* this means both start and end index are now in range of substring so if the substring itself
is not making palindrome, just break out, since we cannot change the substring as we need it compulsarily */
isPossible=false;
break;
}
}
if(isPossible==true){
if(res>operation){
resStr=temp;
res=operation;
}
}
}
if(res==INT_MAX){
cout<<"-1";
return;
}
cout<<res<<" "<<resStr<<endl;
}
int main(){
string word[]={"abbd","aaaaa","abcd"};
string prev_word[]={"mr","bbb","zc"};
for(int i=0;i<3;i++){
solver(word[i],prev_word[i]);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
void solver(string s1, string s2){
int n=s1.size();
int m=s2.size();
if(m>n){
cout<<"-1";
return;
}
string resStr="";
int res=INT_MAX;
for(int i=0;i<=n-m;i++){
string temp=s1.substr(0,i)+s2+s1.substr(i+m);
int operation=0;
for(int j=i;j<i+m;j++){
if(temp[j]!=s1[j]){
operation++;
}
}
bool isPossible=true;
for(int j=0;j<(n+1)/2;j++){
if((j<i || n-j-1>=i+m) && temp[j]!=temp[n-j-1]){
/* atleast one word should be outside of the substring range and it should be of same character,
so change the character which is outside of range with the inside character */
if(j<i){
temp[j]=temp[n-j-1];
}
else{
temp[n-j-1]=temp[j];
}
operation++;
}
else if(temp[j]!=temp[n-j-1]){
/* this means both start and end index are now in range of substring so if the substring itself
is not making palindrome, just break out, since we cannot change the substring as we need it compulsarily */
isPossible=false;
break;
}
}
if(isPossible==true){
if(res>operation){
resStr=temp;
res=operation;
}
}
}
if(res==INT_MAX){
cout<<"-1";
return;
}
cout<<res<<" "<<resStr<<endl;
}
int main(){
string word[]={"abbd","aaaaa","abcd"};
string prev_word[]={"mr","bbb","zc"};
for(int i=0;i<3;i++){
solver(word[i],prev_word[i]);
}
return 0;
}
JUST HELPING THE COMMUNITY, ATLEAST NOT ME, BUT MY CODE WILL BE IMMORTAL HERE
What about the case s1 = "abc" and s2 = "def"?
- Raghu October 18, 2018