Amazon Interview Question
Country: United States
string minus(string s1, string s2)
{
set<char> s(s2.begin(), s2.end());
string ret;
for (string::iterator it = s1.begin(); it != s1.end(); ++it)
{
if (s.find(*it) == s.end())
ret.push_back(*it);
}
return ret;
}
inplace version:
void inplace_minus(string& s1, string s2)
{
set<char> s(s2.begin(), s2.end());
int offset=0;
for (string::iterator it = s1.begin(); it != s1.end(); ++it)
{
if (offset > 0)
{
*(it-offset) = *it;
}
if (s.find(*it) != s.end())
++offset;
}
s1.erase(s1.end() - offset, s1.end());
}
In the non inplace version what if the match is found at s.end() , in that case the returned string ret will still contain that character
public static String RemoveChar(String str1,String str2){
String temp ="",str3 = null, str4 = null;
for(int i=0;i<str1.length();i++){
int flag =0;
str3 = str1.substring(i,i+1);
for(int j =0; j<str2.length();j++){
str4 = str2.substring(j,j+1);
if(str3.equalsIgnoreCase(str4)){
flag=1;
break;
}
}
if(flag == 0){
temp +=str3;
}
}
return temp;
}
public static void minus(String s1, String s2) {
LinkedList<Character> str = new LinkedList<Character>();
for (int i = 0; i < s1.length(); i++) {
str.add(s1.charAt(i));
}
for (int i = 0; i < s2.length(); i++) {
for (int j = 0; j < str.size(); j++) {
int n = str.indexOf(s2.charAt(i));
if (n == -1)
break;
str.remove(n);
}
}
}
string str1 ={ "xmlldldd"};
string str2 = { "dld"}:
pick every character of str1 and perform binary search in str2 .
if found str1[i] = str1[i+1];
else
char= str[i++]
Complexity of this code think depends on size of character in str1 ,
O(logn) + O (logn) +O(log n) .....size of str1 times
~~
O(logn)
#include<stdio.h>
#include <string.h>
char str1[10],str2[10];
char str3[10];
main()
{
printf("enter string 1 ");
scanf("%s",str1);
printf("enter string 2 ");
scanf("%s",str2);
int i,j;
int pos=0;
int len = strlen(str1);
int len2 = strlen(str2);
printf("str len %d",len);
for(i=0;i<len;i++){
for(j=0;j<len2;j++)
{
if(str1[i] == str2[j])
{
str1[i] = '\0';
}
}
}
#if 1
for(i=0;i<len;i++){
if(str1[i] != '\0')
{
//str1[i] = str1[i+1];
str3[pos] = str1[i];
pos++;
}
}
#endif
puts(str3);
// time complexity is O(m*n) + O(m)
}
int main()
{
char str2[]="and";
char str1[]="amazon";
int len=strlen(str2);
int bit_map=0;
for(int i=0;i<len;i++)
{
int j=1;
j=j<<(str2[i]-97);
if(!(j&bit_map))
bit_map=bit_map|j;
}
int start=0;
len=strlen(str1);
for(int i=0;i<len;i++)
{
int j=1;
j=j<<(str1[i]-97);
if(!(j&bit_map))
swap(str1[i],str1[start++]);
}
memset(str1+start,'\0',len-start);
getchar();
return 0;
}
string removecommonchars(string str1, string str2){
std::map<char, int> strmap;
int length = str1.length();
if(length == 0)
return str1;
for (int i = 0; i < length, i++){
char ch = str1[i];
strmap.insert(std::pair<char, int> (ch, 1));
}
int length2 = str2.length();
for(int i = 0; i < length2; i++){
char ch2 = str2[i];
//If that key exists inside the map, set its value to 0
if(strmap.find(ch2) != strmap.end()){
strmap.find(ch2)->second = 0;
}
}
int location = 0;
for(int i = 0; i < length; i++){
char ch = str1[i];
if(strmap.find(ch)->second == 1){
str1[location] = str1[i];
location++;
}
}
//setting the end of the string to null
str[location] = 0;
return str1;
}
time complexity = twice the size of the first string + the size of the second string = O(n)
n is the length of the longer string
Hi why not store string 2 in a char array and use .contains property of arraylist.
My code for the question is below. Please whether the code is Fine or is it not correct way to Implement
String s1="AMAZON";
String s2="AND";
String s3 = "";
Character c;
ArrayList al=new ArrayList();
for(int i=0;i<s2.length();i++)
al.add(s2.charAt(i));
for(int i=0;i<s1.length();i++)
{
c=s1.charAt(i);
if(!al.contains(c))
s3+=c;
}
System.out.println("Output is"+s3);
public class Practice {
public static void main(String[] args)
{
String a="sanchit";
String b="ai";
char[] b1 =b.toCharArray();
char[] a1;
a1=a.toCharArray();
boolean[] temp=new boolean[256];
int j=0;
for(int i=0; i<b1.length;i++)
{
temp[b1[i]]=true;
}
for(int i=0;i<a1.length;i++)
{
if(temp[a1[i]]==false)
{
a1[j]=a1[i];
j++;
}
}
// a1[j]=0;
for(int i=0;i<j;i++)
{ System.out.print(a1[i]);}
}
}
HashMap mapA=new HashMap();
HashMap mapB=new HashMap();
mapA.put("a","a");
mapA.put("b", "b");
mapB.put("a", "a");
Iterator mapAIterator = mapA.keySet().iterator();
Iterator mapBIterator =mapB.keySet().iterator();
while (mapAIterator.hasNext()) {
String key = mapAIterator.next().toString();
if (!mapB.containsKey(key)) {
System.out.println(key);
}
}
string removeChar(string s, string t){
string result = "";
set<char> ss;
set<char>::iterator it;
int lengthT = t.size();
int lengthS = s.size();
if (lengthS < 1 || lengthT < 1) return s;
for(int i = 0; i < lengthT; i++){
if (t[i] >= 'A' && t[i] <= 'Z') t[i] = t[i] + 32;
ss.insert(t[i]);
}
for(int i = 0 ; i < lengthS; i++){
if(s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] + 32;
}
cout << "size of set: " << ss.size() << endl;
for(it = ss.begin(); it != ss.end(); it++){
cout << *it << endl;
}
for (int i =0; i < lengthS; i++){
it = ss.find(s[i]);
if (it == ss.end()) result = result + s[i];
}
return result;
}
Enter every letter of second string in a hash or we can take a 26 characters bit array and for every character in second string flag or set bit in that array.
- DashDash February 04, 2013Now checking for characters in first string is a easy job