Adobe Interview Question
Country: India
Generally while asking these questions they will say assume Input as below.
S - Source String
C - Char to find.
K - No of times C repeated in string.
N - Length of chars in S.
K < N.
So no need to worry about all chars as same in S.
We may need give solution with K length.
u should have asked interviewer if the string is sorted.
If the given string is sorted then:
Just find the character using binary search and from there start replacing
And how about this :
for(int i=0;i<l/2;i++)
{
if(a[i]=='character to replace')
replace it
elseif(a[l-i]=='character to replace')
replace it
}
u should have asked interviewer if the string is sorted.
If the given string is sorted then:
Just find the character using binary search and from there start replacing
And how about this :
for(int i=0;i<l/2;i++)
{
if(a[i]=='character to replace')
replace it
elseif(a[l-i]=='character to replace')
replace it
}
String str = "abcaera";
char a = 'a';
char r = 'z';
char[] chars = str.toCharArray();
int l = chars.length-1;
int c = 0;
for(int i=0; i<=l/2; i++) {
if(chars[i] == a) {
chars[i] = r;
}
if(chars[l-i] == a) {
chars[l-i] = r;
}
c++;
}
System.out.println("Original String = " + str);
System.out.println("Replaced String = " + new String(chars));
System.out.println("Number of interations = " + c);
Also it would need a binary search algorithm with extra storage for values
1) Traverse the string and build binary search data structure with indexes stored as values(in a linked list) - This is only once
2) Write a replace function that would find the search character using binary search and get the index list
3) Traverse the index list and replace the characters at the index location by direct index reference.
Assuming you are allowed to keep track of a list of each character's positions while the string is built, then the best and average case of 'replaceChar()' would be < O(n). What do you guys think?
import java.util.*;
public class HelloWorld {
static Map<Character, List<Integer>> positions = new HashMap<Character, List<Integer>>();
public static void main(String []args) {
String s = buildString('h','e','l','l','o',' ','w','o','r','l','d');
System.out.println("s: " + s);
System.out.println(positions);
s = replaceChar(s, 'l', 'X');
System.out.println("s: " + s);
}
static String buildString(char... chars) {
String s = null;
for (char c : chars) {
s = append(s, c);
}
return s;
}
static String append(String s, char c) {
if (s == null) s = "";
String newS = s + c;
List<Integer> charPositions = positions.get(c);
if (charPositions == null) {
charPositions = new ArrayList<Integer>();
positions.put(c, charPositions);
}
charPositions.add(newS.length()-1);
return newS;
}
static String replaceChar(String s, char c, char newC) {
List<Integer> charPositions = positions.get(c);
if (charPositions == null) return s;
char[] charArr = s.toCharArray();
for (int pos : charPositions) {
charArr[pos] = newC;
}
return new String(charArr);
}
}
Output is:
s: hello world
{w=[6], d=[10], =[5], e=[1], r=[8], o=[4, 7], l=[2, 3, 9], h=[0]}
s: heXXo worXd
How abt using Merge sort/binary search concept by diving array into half.....ord( log n).
#include <stdlib.h>
#include <stdio.h>
void replacCharinString( char *cpystr, int i, int j, char *x, char *y){
if( i==j){ if(cpystr[i]== *x) cpystr[i]= *y; return;}
replacCharinString( cpystr,i,(i+j)/2, x,y);
replacCharinString( cpystr,(i+j)/2+1,j, x,y);
}
main(){
int i,count;
char a,b;
char str[100];
printf("enter a string ");
scanf("%s",str);
a=getchar(); // this is used to get rid of "\n" as a character;
printf("enter a character that u need to replace in given string ");
a=getchar();
b=getchar(); // this is used to get rid of "\n" as a character;
printf("enter a character that by which u wnat to replace in given string ");
b=getchar();
i=0;count=0;
while ( str[i] != '\0'){ i++; count++;}
replacCharinString( str,0,count-1,&a,&b);
printf("Replaced string is %s\n",str);
scanf("%d",&i);
}
I don't think it's possible if we don't know the indices of the replaced char. Perhaps we could create a kind of proxy around the string and perform the update lazily when the string is requested. Otherwise, it can't be better than O(n), because the worst case requires to modify all the characters.
- Danstahr April 23, 2014