Adobe Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
void getCommon(char *s1,char *s2,char *sCommon)
{
for(int i=0;i<strlen(s1);i++)
{
for(int j=0;j<strlen(s2);j++)
{
if(s1[i] == s2[j])
{
bool bFound = false;
for(int k=0; k<strlen(sCommon);k++)
{
if(s1[i] == sCommon[k])
{
bFound = true;
break;
}
}
if(!bFound)
{
sCommon = strcat(sCommon,&s1[i]);
}
break;
}
}
}
}
#include<iostream>
#include<string>
#include<algorithm>
std::string find_intersection(std::string & first, std::string & second)
{
std::sort(std::begin(first),std::end(first));
std::sort(std::begin(second), std::end(second));
int length = std::min(first.length(), second.length());
std::string result(length,' ');
std::set_intersection(std::begin(first),std::end(first),std::begin(second),std::end(second),std::begin(result));
result.shrink_to_fit();
return result;
}
int main()
{
std::string first="GermanTown";
std::string second="Georgia";
std::cout<<find_intersection(first,second)<<"\n";
return 0;
}
package com.careercup.practice;
public class LongestCommonString {
String LCS(String a , String b)
{
if(a.length() == 0 || b.length() == 0)
{
return "";
}
String op1 = (a.charAt(0) == b.charAt(0) ? a.charAt(0) : "") + LCS(a.substring(1), b.substring(1)) ;
String op2 = (a.charAt(0) == b.charAt(0) ? a.charAt(0) : "") + LCS(a.substring(0), b.substring(1));
String op3 = (a.charAt(0) == b.charAt(0) ? a.charAt(0) : "") + LCS(a.substring(1), b.substring(0)) ;
if(op1.length() > op2.length() && op1.length() > op3.length())
return op1;
else if(op2.length() > op1.length() && op2.length() > op3.length())
return op2;
else
return op3;
}
public static void main(String[] args) {
LongestCommonString lcs = new LongestCommonString();
System.out.println(lcs.LCS("Bangalore", "Mysore"));
}
}
public class CommonCharacter {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "bangalore";
String str2 = "mysore";
System.out.println("Common Characters::"+ getCommonSubString(str1, str2));
}
private static String getCommonSubString(String str1, String str2) {
String commonSubstring = "";
for (int i = 0; i < str1.toCharArray().length; i++) {
for (int j = i; j < str2.toCharArray().length; j++) {
if (str1.toCharArray()[i] == str2.toCharArray()[j]) {
commonSubstring += ch1[i];
j++;
}
}
}
return commonSubstring;
}
}
public class CommonCharacterFromTwoString {
public static void main(String[] args){
String str1 = "bangalorea";
String str2 = "patnaa";
String str3 = commonCharacter(str1,str2);
System.out.println("FinalString :"+str3);
}
public static String commonCharacter(String first,String second){
String finalString = "";
for(int i=0;i<first.length();i++){
for(int j=0;j<second.length();j++){
if(first.charAt(i)==(second.charAt(j))){
finalString+=first.charAt(i);
break;
}
}
}
return finalString;
}
}
with additional bool array[26] (which is O(1) ), just maintain information if a character has been seen. Complexity is O(M+N), M and N string length respectively
bool arr[26] = {false};
foreach(char c in FirstString)
{
arr[ToLower(c) - 'a'] = true;
}
foreach(char c in SecondString)
{
if(arr[ToLower(c) - 'a'] == true)
{
print c;
}
}
Without string library in C, I also prevent duplicates in common words, means there would be no result such as orrre,should be ore enough.
char* commonWords(char* a, char* b){
char *str= (char*)malloc(256);
int i=0;
int j=0;
int index=0;
while(a[i]!='\0'){
j=0;
while(b[j]!='\0'){
//compare
if(a[i]==b[j]){
//compare if exist this alphabet
int flag = 0;
for(int m=0;m<index;m++){
if(str[m]==a[i])
flag = 1;
}
if(flag==0){
str[index]=a[i];
index++;
}
}
j++;
}
i++;
}
return str;
}
void getcommon(char *s, char *r)
{
int len1=strlen(s);
int len2=strlen(r);
char* common;
if(len1>len2)
{
common = (char*)malloc(len2*sizeof(char)+ 1);
}
else
{
common = (char*)malloc(len1*sizeof(char)+ 1);
}
char *newLabel = common;
int i,j;
int k=0;
for(i=0;i<len1;i++)
{
for(j=1;j<len2;j++)
{
if(s[i]==r[j])
{
common[k]=s[i];
k++;
}
}
}
common[k]='\0';
printf("%s",newLabel);
}
void getcommon(char *s, char *r)
{
int len1=strlen(s);
int len2=strlen(r);
char* common;
if(len1>len2)
{
common = (char*)malloc(len2*sizeof(char)+ 1);
}
else
{
common = (char*)malloc(len1*sizeof(char)+ 1);
}
char *newLabel = common;
int i,j;
int k=0;
for(i=0;i<len1;i++)
{
for(j=1;j<len2;j++)
{
if(s[i]==r[j])
{
common[k]=s[i];
k++;
}
}
}
common[k]='\0';
printf("%s",newLabel);
}
public class CommonCharacterFromTwoString {
public static void main(String[] args){
String str1 = "bangalorea";
String str2 = "patnaa";
String str3 = commonCharacter(str1,str2);
System.out.println("FinalString :"+str3);
}
public static String commonCharacter(String first,String second){
String finalString = "";
for(int i=0;i<first.length();i++){
for(int j=0;j<second.length();j++){
if(first.charAt(i)==(second.charAt(j))){
finalString+=first.charAt(i);
break;
}
}
}
return finalString;
}
}
To find out the common characters we can find out the hash of characters for both string and compare the output hash array.
This solution would work in O(n)
void common(char *str1,char *str2)
{
map<char,int> mp,mp2;
int l1=strlen(str1),l2=strlen(str2);
for(int i=0;i<l1;i++)
mp[str1]=1;
for(int j=0;j<l2;j++)
mp2[str2]=1;
for(map<int,int>::iterator it = mp.begin(); it != mp.end(); ++it) {
char c=it->first;
if(mp2[c])
cout<<mp2[c];
}
}
}
public class LongestSubstring {
public static String longestSub(String x1, String x2)
{
int l1=x1.length();
int l2=x2.length();
int arr[][]=new int[l1+1][l1+1];
int pos=0;
int len=0;
for(int x=1;x<=l1;x++)
{
for(int y=1;y<=l2;y++)
{
if(x1.charAt(x-1)==x2.charAt(y-1))
{
arr[x][y]=arr[x-1][y-1]+1;
if(arr[x][y]>len)
{
len=arr[x][y];
pos=x;
}
}
}
}
return x1.substring(pos-len,pos);
}
public static void main(String[] args) {
System.out.println(longestSub("harjeet","harpal"));
}
}
public class LongestSubstring {
public static String longestSub(String x1, String x2)
{
int l1=x1.length();
int l2=x2.length();
int arr[][]=new int[l1+1][l1+1];
int pos=0;
int len=0;
for(int x=1;x<=l1;x++)
{
for(int y=1;y<=l2;y++)
{
if(x1.charAt(x-1)==x2.charAt(y-1))
{
arr[x][y]=arr[x-1][y-1]+1;
if(arr[x][y]>len)
{
len=arr[x][y];
pos=x;
}
}
}
}
return x1.substring(pos-len,pos);
}
public static void main(String[] args) {
System.out.println(longestSub("harjeet","harpal"));
}
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s="bINDIAanglore";
string m ="mysINDIAore";
int sl = s.length();
int ml= m.length();
int a[256];//={0};
memset(a,0,256);
for(int i=0;i<sl;i++){
a[s[i]] =1;
}
for(int i=0;i<ml;i++){
if(a[m[i]]==1)
cout<<m[i];//]==1;
}
return 0;
}
#include<bits/stdc++.h>
- Abhishek Singh January 20, 2016using namespace std;
int main()
{
string s="bINDIAanglore";
string m ="mysINDIAore";
int sl = s.length();
int ml= m.length();
int a[256];//={0};
memset(a,0,256);
for(int i=0;i<sl;i++){
a[s[i]] =1;
}
for(int i=0;i<ml;i++){
if(a[m[i]]==1)
cout<<m[i];//]==1;
}
return 0;
}