Microsoft Interview Question SDE1s
Country: United States
Interview Type: In-Person
Not necessarily.
1. Here its a string matching situation rather than character
2. You might end up shrinking the original string in case the pattern to be replaced is longer than the new pattern (e.g. BC -> U). In this case you have to start from the beginning of the original array. Whereas in expansion starting from the back is efficient
//str is given string and word is string to be replaced with.
public void replaceStringPattern(char[] str,char[] word){
int count=0,length=str.length,lengthOfWord=word.length;
//count how many times pattern is repeated.
for(int i=0;i<length-2;i++){
if(str[i]=='B' && str[i+1]=='C') count++;
}
//new size of string so that replaced string can fit into str.
newLength=length+count*(lengthOfWord-2);
str[newLength]='\0';
//replacing pattern from back.
for(int i=length-1;i>=1;i--){
if(str[i]=='C' && str[i-1]=='B'){
int k=lengthOfWord-1;
while(k>=0){
s[newLengh-1]=word[k];
k--;
newLength--;
}
i--;
}
else{
s[newLength-1]=s[i];
newLength--;
}
}
}
This could be the possible solution :
(Assumption: Original string size 'N')
1) Calculate total no of BC 's in the given string s1 and store it in count variable.
2)
-replace with 2 'u' or 1 'uv' if the count=1 => Size is s1 is still N
-replace with 'uv' if the count=2=> Size of s1 is still N
-replace with 3 'u' or 1 'uv'+1 'u' or 1 'uvw' if the count=3 => Size of s1 is still N.
.
.
.
So on.
An algorithm on similar lines would work.
Here goes the algorithm :
1) Count the total no of BC 's in string s1 and store in count variable.
2)Let the string size be 'N'
3)Effective size change upon replacement with
-'u' is -1 as 2 characters 'B' and 'C' in 'BC' are replaced by only one charachter 'u'
-'uv' is 0
-'uvw' is +1
4)Algorithm :
if(N is even)
{
replace all 'BC' s with 'uv' s
}
else if(N is odd)
{
replace one 'BC' with 'uv' , remaining half 'BC' with 'u' , remaining half 'BC' with 'uvw'
}
I use kmp to make it, and I think first you should compute the length of target like 'BC' and then length of repalce strings like 'U', 'UV', 'UVW' and compare them to decide when find the target string, whether copy the string forward or backword, here is my program, time complexity is near to O(n) and space complexity is using by kmp of O(targe), and there is anything wrong, please let me know, thanks.
#include<iostream>
using namespace std;
/*
In an interview I was asked a question on strings. The problem is given a string s1= "ABCDBCCDABCD".
and a pattern "BC". we have to replace this pattern with other string ("UVW" or "U"or "uv").
Do this without creating new string.
Take the case to replace "BC" with following
a) "uvw" s1=AUVWDUVWCDAUVWD .
b) "U" s1=AUDUCDAUD .
c) "UV" s1=AUVDUVCDAUVD
*/
void get_next(char *p, int len, int *next) {
int j = -1;
int i = 0;
next[i] = -1;
while(i < len - 1) {
if(j == -1 || p[i] == p[j]) {
++i;
++j;
if(p[i] != p[j])
next[i] = j;
else
next[i] = next[j];
} else {
j = -1;
}
}
}
char *kmp_search(char *src, char *pattern) {
int i = 0;
int j = 0;
int len_s = strlen(src);
int len_p = strlen(pattern);
int *next = (int*)malloc(sizeof(int) * len_p);
memset(next, 0, sizeof(int) * len_p);
get_next(pattern, len_p, next);
while(i < len_s && j < len_p) {
if(j == -1 || src[i] == pattern[j]) {
++i;
++j;
} else {
j = next[j];
}
}
free(next);
if(j >= len_p)
return src + i - len_p;
else
return NULL;
}
void string_replacement(char *src, char *target, char *replace) {
int direction = 0; // move forward or backward: 0 for forward, 1 for backward
int move_len = 0;
char *p = NULL;
int len_t = strlen(target);
int len_r = strlen(replace);
char *temp_old = NULL;
char *temp_new = NULL;
char *temp = NULL;
if(!src || !target || !replace) {
cout << "check input" << endl;
return;
}
if(len_r > len_t)
direction = 1;
p = kmp_search(src, target);
while(p) {
temp = replace;
move_len = strlen(src) - (p - src) - len_t;
temp_old = p + len_t;
temp_new = p + len_r;
if(direction) {
while(move_len > 0) {
*(temp_new + move_len - 1) = *(temp_old +move_len - 1);
move_len--;
}
} else {
while(*temp_old)
*temp_new++ = *temp_old++;
*temp_new = '\0';
}
while(*temp)
*p++ = *temp++;
p = strstr(src, target);
}
}
int main(int argc, char *argv[]) {
char src[30] = "ABCDBCCDABCD";
char target[] = "BC";
char replace[] = "U";
string_replacement(src, target, replace);
cout << src << endl;
cin.get();
return 0;
}
char* replace_string(char* dst, char* tmpl, char *str)
{
char* p1 = dst;
char* p2 = tmpl;
int count = 0;
while(*p1)
{
if (*p2 == 0)
{
count++;
p2 = tmpl;
}
if (*p1 != *p2)
{
p2 = tmpl;
p1++;
}
else
{
p1++;
p2++;
}
}
int tmpl_size = (int)strlen(tmpl);
int src_size = (int)strlen(str);
int dst_size = strlen(dst);
int value = abs(tmpl_size - src_size);
dst = (char*)realloc(dst, sizeof(char) * value * count + dst_size+1);
p1 = dst;
p2 = tmpl;
while(*p1)
{
if (*p2 == 0)
{
p2 = tmpl;
int location = (p1 - dst);
memcpy(p1 + value, p1, sizeof(value) * abs(dst_size - location));
memcpy(p1 - tmpl_size, str, sizeof(char)* src_size);
p1 += value;
}
if (*p1 != *p2)
{
p2 = tmpl;
p1++;
}
else
{
p1++;
p2++;
}
}
return dst;
}
In C# string is immutable and you cannot modify existing string. So you have to use StringBuilder to do that. I am not sure if below answer is acceptable or not. Please provide your feedback.
public void ReplaceString()
{
string[] replaceList = new String[] { "UVW", "U", "UV" };
string str = "ABCDBCCDABCD";
int i = 0;
StringBuilder strBld = new StringBuilder();
foreach (string r in replaceList)
{
strBld.Clear();
i = 0;
for (i = 0; i < str.Length - 1; i++)
{
if (str[i] == 'B' && str[i + 1] == 'C')
{
strBld.Append(r);
i++;
}
else
{
strBld.Append(str[i]);
}
}
Console.WriteLine(" Replace with {0} and new string {1}", r, strBld);
}
}
Try to use char array (C string). StringBuilder is a highly abstracted class, do not use it (also it contains Replace method which we are trying to rewrite).
#include "stdafx.h"
#include <iostream>
using namespace std;
void s_replace(char* s, const char* pattern, const char* replacement)
{
int pattern_len = -1;
while (pattern[++pattern_len] != '\0') ;
int replacement_len = -1;
while (replacement[++replacement_len] != '\0') ;
int delta = replacement_len - pattern_len;
int length = -1;
while (s[++length] != '\0') ;
int i = -1;
int j = 0;
while (++i < length) {
if (s[i] == pattern[j]) {
if (j == pattern_len - 1) {
if (delta != 0) {
int start = length - 1;
int step = -1;
int end = (length + delta) - (i + 1);
if (delta < 0) {
start = i + 1;
step = 1;
end += i + 1;
}
length += delta;
int k = -1;
while (++k < end) {
s[start + delta] = s[start];
start += step;
}
}
j = -1;
while (++j < replacement_len)
s[i - pattern_len + 1 + j] = replacement[j];
j = 0;
i += delta;
} else
j++;
}
}
s[length] = '\0';
}
int _tmain(int argc, _TCHAR* argv[])
{
char* tmpl = "ABCDBCCDABCD";
char* pattern = "BC";
char* replacement = "00"; // "UVW";
char s[20];
strcpy_s(s, tmpl);
cout << s << endl;
s_replace(s, pattern, replacement);
cout << s << endl;
return 0;
}
private static void FindPattern(string givenString, string pattern, string replace)
{
string toReturn = givenString;
List<int> matchesFound = new List<int>();
for (int i = 0; i < givenString.Length; i++)
{
int si = i;
int j = 0;
while (j < pattern.Length && givenString[si] == pattern[j])
{
si++;
j++;
}
if (j == pattern.Length)
{
matchesFound.Add(i);
}
}
int initialOffset = replace.Length - pattern.Length;
int offset = 0;
for (int i = 0; i < matchesFound.Count; i++)
{
int actualPosition = matchesFound[i] + offset;
toReturn = toReturn.Substring(0, actualPosition) + replace + toReturn.Substring(actualPosition + pattern.Length);
offset = offset + initialOffset;
}
Console.WriteLine(toReturn);
}
private static void FindPattern(string givenString, string pattern, string replace)
{
string toReturn = givenString;
List<int> matchesFound = new List<int>();
for (int i = 0; i < givenString.Length; i++)
{
int si = i;
int j = 0;
while (j < pattern.Length && givenString[si] == pattern[j])
{
si++;
j++;
}
if (j == pattern.Length)
{
matchesFound.Add(i);
}
}
int initialOffset = replace.Length - pattern.Length;
int offset = 0;
for (int i = 0; i < matchesFound.Count; i++)
{
int actualPosition = matchesFound[i] + offset;
toReturn = toReturn.Substring(0, actualPosition) + replace + toReturn.Substring(actualPosition + pattern.Length);
offset = offset + initialOffset;
}
Console.WriteLine(toReturn);
}
Pre-calculate the space required with a first pass: O(N). Lets say the extra space required is X. (X can be +ve, -ve or 0)
Pseudo Algorithm:
Case a (X is positive):
Allocate X additional memory (or N+X new memory, as per interviewers feedback).
Have two pointers one at the end of the memory and another at the end of the actual text
i.e.
int p1 = N -1;
int p2 = N + X - 1;
while(p1 != 0 || p2 != 0)
{
bool flag = false;
if(arr[p1] == 'C')
{
// Lookup the match.
if(arr[p1-1] == 'B')
flag = true;
}
if(flag)
// loop three times and replace U V W
}
Case b:
X will be negative.
If X is negative. Just start from the beginning
i.e.
p1 = 0 and p2 = 0. Continue one pointer with the text reading and another pointer replacing the text.
Case c:
X=0; No magic here. Starting from any side would work fine.
There should not be a new string and allocating new memory for the extra characters alone will break the indexing of the string.
Question is similar to one of question of Cracking The Code Interview book
- Chandan Singh March 24, 2013Replace all the space in string with "%20" without using extra string .