Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
your program wont compile . See the definition of your hashinit function. If you are writing proper code ( not pseudocode) , make sure you write compiled code.
import java.util.HashSet;
public class RemoveDuplicates {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(removeDuplicates("amazon development center", "aenr"));
}
public static char[] removeDuplicates(char[] source, char[] remove){
HashSet<Character> set = new HashSet<Character>();
for(int i=0 ; i < remove.length ; i++)
set.add(remove[i]);
int copyIndex =0;
for(int i=0 ; i < source.length ; i++){
if(!set.contains(source[i]))
source[copyIndex++] = source[i];
}
return new String(source).substring(0, copyIndex).toCharArray();
}
public static char[] removeDuplicates(String source, String remove){
if(source != null && remove != null)
return removeDuplicates(source.toCharArray(), remove.toCharArray());
if(source != null)
return source.toCharArray();
return null;
}
}
Hash set is not needed , it's needs a big data structure in memory. As qn is to support only 256 int, we can simply create an array of 256.
int remove[256] = {0};
iterate through second parameter and make each char to 1;
like if "A" is found,
then remove['a' ] = 1 ;
while doing the search we can do a simple search -- remove['a'] is 0 or 1, this will give the most efficient search.
My logic is correct but my code is not running properly...pls help me
#include<stdio.h>
#include<conio.h>
void strRemove(char *source, char *remove )
{ int Remov[256];
int i;
for(i=0;i<256;i++)
Remov[i]=-1;
for(i=0;remove[i]!='\0';i++)
{
if(Remov[remove[i]]==-1)
{
Remov[remove[i]]=1;
}
}
for(int j=0;((Remov[source[j]]==-1) && (source[j]!='\0'));j++)
{
printf("%c",source[j]);
}
}
int main()
{
strRemove("amazon development center","aenr");
getch();
}
int hashtable[256] ={0};
void strRemove(char *p , char *remove);
void hashInit(char *remove);
bool hashfind(char value);
bool hashfind(char value)
{
if(0 != hashtable[tolower(value)])
{
hashtable[tolower(value)]++;
return 1;
}
else
{
hashtable[tolower(value)]++;
return 0;
}
}
void strRemove(char *p , char *remove)
{
int newlen =0, tempIndex = 0;
char *tp = p,*tp2 = p;
printf("\n The Input String is : %s \n",p);
while('\0' != *tp)
{
if(0 == hashfind(*tp))
{
*tp2 = *tp;
tempIndex++;
tp2++;
}
tp++;
}
p[tempIndex] = '\0';
printf("\n The String is : %s and len : %d\n",p,tempIndex);
}
import java.util.*;
public class RemoveDupli {
public static void main(String[]args){
System.out.println(removeDuplicates("amazon development center", "aenr"));
}
public static String removeDuplicates(String source, String remove){
int copyIndex = 0;
if(source!=null && remove!=null)
{
char[]source1 = source.toCharArray();
char[]remove1 = remove.toCharArray();
HashSet<Character> set = new HashSet<Character>();
for(int i= 0; i<remove1.length; i++)
set.add(remove1[i]);
for(int i=0; i<source1.length; i++) {
if(!set.contains(source1[i]))
source1[copyIndex++] = source1[i];}
return new String(source1).substring(0, copyIndex);
}
return null;
}
}
The solution can be optimised for space by having only 27 char array , instead of 256. here is the compiled and tested code
/* this function initializes the hash table */
void init_hash( char *remove, char *p){
int i;
memset(p,'0',26);
p[26] = '\0';
while(*remove){
p[*remove - 97] = *remove;
remove++;
}
}
/* this function checks if hash search is successful or not */
int is_hash(char c, char* p){
if(p[c-97] == c)
return 1;
else
return 0;
}
/*this functions remove all the characters in remove string from
* the source string
* eg : source : aabbcc
* remove : ab
* output : cc */
void strRemove(char *source , char *remove){
char *p = source;
char s[27];
int i;
init_hash(remove,s);
for( i=0;i<strlen(p);i++){
if(is_hash(p[i],s))
p[i]=' ';
else
printf("%c",p[i]);
}
printf("\n");
}
now from main
char source[] = "amazon development centre";
char remove[] ="aenr";
strRemove(source,remove);
#include <iostream>
#include <bitset>
using namespace std;
void strRemove(char *source, char *remove)
{
if ( !source || !remove )
return;
bitset<256> hash;
while(*remove)
hash.set(*remove++);
int i = 0, j = 0;
while(source[j])
{
if ( !hash.test(source[j]) )
source[i++] = source[j];
j++;
}
source[i] = '\0';
}
int main()
{
char str[] = "amazon development centre";
char remove[] = "aenr";
strRemove(str,remove);
cout<<str;
return 0;
}
void strRemove(char * source,char * remove)
{
char *p,*temp,*last;
last=&source[strlen(source)];
p=source;
temp=remove;
while(*p)
{
while(*temp)
{
if(*p==*temp)
{
p=memcpy(p,p+1,last-p)-1;
break;
}
temp++;
}
temp=remove;
p++;
}
}
package stringss;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* write a function strRemove(char *source, char *remove )
This function will delete all the chars that exist in string remove from array source,
number of iteration should be only 1. Make the searching efficient.
Example
("amazon development center", "aenr")
"mzo dvlpmt ct".
Criteria - First parameter should be modified , no need to create an extra string.
* @author Musi
*
*/
public class DeletionStr {
String myStr;
String myRemover;
List removers;
DeletionStr(String s, String r){
myStr =s;
myRemover=r;
removers = new ArrayList();
}
/**
*
*/
public void deleteString() {
char remover[] = myRemover.toCharArray();
int l = remover.length;
for(int i=0;i<l;i++) {
removers.add(remover[i]);
}
int len= myStr.length();
char source[] = myStr.toCharArray();
System.out.println(source);
int j=0;
for(int i=0;i<len;i++) {
if( search(source[i]))
source[j] = source[i];
else
source[j++] =source[i];
// System.out.print(source[j]);
}
for(int i=j;i<len;i++)
source[i]=' ';
System.out.println();
// System.out.println(myStr);
System.out.println(source);
}
/**
*
* @param c
* @return
*/
public boolean search(char c) {
if(removers.contains(c))
return true;
else
return false;
}
/**
*
* @param args
*/
public static void main(String args[]) {
DeletionStr str = new DeletionStr("amazon development center", "aenr");
str.deleteString();
}
}
#include<stdio.h>
void strrem(char *str,char *rem)
{
int a[128]={0};
char *p=str;
char *q=str;
int j=0;
while(*rem!=0)
{
a[*rem]=1;
rem++;
}
q=p;
while(*p!=0)
{
if(a[*p-0])
{
if(q==str)
q=p;
}
else
{
*q=*p;
q++;
j++;
}
p++;
}
memset(str+j, 0, strlen(str) -(j+1));
}
int main(int argc, _TCHAR* argv[])
{
char str[]="amazon development center";
char *p="aenr";
strrem(str,p);
printf("reversed string=%s\n",str);
}
- Biswaranjan January 30, 2012