Amazon Interview Question
Front-end Software EngineersCountry: India
Interview Type: In-Person
This is easy :S
If stored in array and the array is small, just shift parts of the array over
But this is O(n^2) in the worst cases like "sasasasasasasasa" (delete s)
If you want good big-O performance to handle long strings, walk down your array one character at a time and insert into a linked list (but skip the characters you want to delete). When you are done, the linked list will hold your answer (you can copy it it to an array if you want).
This is O(n).
You can do some tricks with just an array to improve on the brute force also.
if you know the upperbound on string size, you can use a vector/ArrayList too instead of LinkedList
Basically any mutable List ADT... keep inserting the characters you want to keep
We can make a pass through array and will keep adding each characters to another array.If we encounter character that we want to delete then we can use "continue" to skip it..It can be done in time-complexity O(n).
const deleteChar = (inputStr, char = '') => {
if (!char) {
return false;
}
let outputArr = [], index = -1;
let inputStrArr = inputStr.split('')
while(++index < inputStrArr.length) {
if (inputStrArr[index] !== char) {
outputArr.push(inputStrArr[index]);
}
}
return outputArr.join('');
}
console.log(deleteChar('YOSUF', 'F'))
const deleteChar = (inputStr, char = '') => {
if (!char) {
return false;
}
let outputArr = [], index = -1;
let inputStrArr = inputStr.split('')
while(++index < inputStrArr.length) {
if (inputStrArr[index] !== char) {
outputArr.push(inputStrArr[index]);
}
}
return outputArr.join('');
}
console.log(deleteChar('YOSUF', 'F'))
const deleteChar = (inputStr, char = '') => {
if (!char) {
return false;
}
let outputArr = [], index = -1;
let inputStrArr = inputStr.split('')
while(++index < inputStrArr.length) {
if (inputStrArr[index] !== char) {
outputArr.push(inputStrArr[index]);
}
}
return outputArr.join('');
}
console.log(deleteChar('YOSUF', 'F'))
Do it in-place and w/o using any additional storage. Actual one-pass implementation presented below does not use strlen, so allowing us to do it in a single pass:
void subst_all_chars(char* a)
{
int fill_pos = -1;
char subst = 'f';
while (a[i++]){
char chcur = a[i];
if (chcur == subst){ // if the current is the sought char
a[i] = 0;
if (-1 == fill_pos)
fill_pos = i;
}
else { // char that is OK to stay
if (-1 == fill_pos)
continue;
else { // we have previous gap, so copy the current char to this position
a[fill_pos] = chcur;
a[i] = 0;
++fill_pos;
}
}
}
}
I don't find any challenge here. I could do it as in-line alogorithm and that too in one iteration. Please let me know, if you have any input which breaks this program.
Is it really Amazon question? :)
Algorithm:
1. Find out input char position in given string
2. If char is not found then don't do anything. Just return
3. From that position (found in step1), keep copying all chars one position back(left) till end of the string.
void RemoveCharFromString(string& s, char c) {
int i = 0;
for(; (s[i] and toupper(s[i]) != toupper(c)); i++); // Iterate till we found the char or end of the string
if(s[i] == '\0') // means input char is not found. Return input string as it is
return;
for(; s[i]; i++) // move rest of the string one char back
s[i] = s[i+1];
s = (s.substr(0, i-1)); // update input string by reducing last char. (other string size still be original size)
}
int main(int argc, char * argv[])
{
string s("abcdef");
cout << "After removing d from " << s; RemoveCharFromString(s, 'd'); cout << ", the result is: " << s << endl; // result: abcef
s = "abcdef";
cout << "After removing f from " << s; RemoveCharFromString(s, 'f'); cout << ", the result is: " << s << endl; // result: abcde
s = "ABCDEF";
cout << "After removing f from " << s; RemoveCharFromString(s, 'f'); cout << ", the result is: " << s << endl; // result: ABCDE
s = "ABCDEF";
cout << "After removing a from " << s; RemoveCharFromString(s, 'a'); cout << ", the result is: " << s << endl; // result: BCDE
s = "ABCDEF";
cout << "After removing h from " << s; RemoveCharFromString(s, 'h'); cout << ", the result is: " << s << endl; // result: ABCDEF
}
We can do this in place.
- Vs September 20, 2013