Microsoft Interview Question
InternsCountry: India
Interview Type: In-Person
I just read the definition of inplace. I always thought that no extra memory (except for small variables) can be used!
This seems valid except that in an inplace algorithm, input is replaced by output (ref Wikipedia). You are using O(n) memory for output. The original string needs to be modified into output.
Thanks anyways! :)
No extra memory is being used here, whatever String is being passed in, a boolean array of 128 length is being created therefore space is not dependent on the input in this case, therefore Space = O(1).
O(1) space does not always mean using a single variable, it can be a constant sized array like in this proposed solution. I'm 99.99% sure if you gave this solution to your interviewer, he would have been satisfied.
If we are just talking about English characters, then a single integer variable can serve as our hashmap; with A to Z mapped to bits 0 to 25 within the integer.
@IntwPrep.MS usually strings can be composed of ASCII or Unicode values for instance. During an interview, it is ideal to clarify the kind of strings we are dealing with and probably proceed to determine whether we would use 128 or 256 characters.
Hey guys, I think it would be simplest just to use a HASHSET.
With the if statement we try to add the current character to the hash set; if we succeed, it means that the char is encountered for the first time, so we increment the counter i, otherwise (when if returns false), we just remove the particular char. Note that the value of i is not incremented.
Hope it helps. :)
public static String cocoBee(String str){
StringBuilder sb = new StringBuilder(str);
HashSet<Character> hs = new HashSet<>();
for(int i = 0; i < sb.length(); ){
if(hs.add(sb.charAt(i))){
i++;
}
else{
sb.deleteCharAt(i);
}
}
return sb.toString();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
String str = scanner.next();
String str2 = cocoBee(str);
System.out.println(str2);
}
I think the question is about removing duplicate characters from the string. For example: If the string is "amazon", the output should be "amzon".
This can be done in O(N) using a HashMap.
Algorithm:
1. Traverse the string character by character
2. Enter the character in the HashMap<Character, Boolean> as key if it is not already present
3. If a character is already in HashMap, we found a duplicate.
4. Based on the requirement, we can either just display the characters and skip the duplicate characters OR store the characters in a character array and return the resultant array as a String.
OP, you asked for O(n) solution and he gave you O(n) solution. I'm sure the interviewer wasn't satisfied because you gave him O(nlog(n)) at best.
@Alex
In-place means constant space, independent on the input size. In this case the hashmap can be a single integer irrespective of the input string length. Hence inplace.
Remove duplicates from string..does that mean
abaaabbcdeee = abcd or = ababcde ?
If its second then its easy to do in O(n)
Can use hash table, whenever a character is encountered put in hash table if not already present, otherwise return an indication character is already present
Keep two pointers, read pointer and write pointer. Readpointer moves always by one character ahead, write pointer moves ahead only when the hash table results in successful insert of character.
int hash_add(char c)
{
/* bitmap is array of 127 bits or 16 bytes, each bit represents one ASCII
character, if set it is already present in hash table otherwise not */
if( bitmap[ (c - 'a')/8 ] & (0x1 << (c-'a')%8) )
return 1; /* already set */
bitmap[ (c - 'a')/8 ] & (0x1 << (c-'a')%8);
return 0;
}
unsigned int remove_duplicates(char *string)
{
unsigned int rc = 0;
char *rp = string;
char *wp = string;
while( *rp != '\0' )
{
if( hash_add( *rp ) == 0 )
{
*wp++ = *rp;
}
else
rc++;
rp++;
}
*wp = '\0'
return rc;
}
Time complexity O(n), space complexity is O(1)
I think it formated my white space automatically while posting
If your string is " Hello World "
Your output should be "Hello World"
I faced the same question in the interview. I think what the meant was this
The array AMAZON would become AMZON\n. Just add a special character at the end to specify that you would have your result before that. In this case you just cant erase a string you have to copy the char 'Z' at index 2 and shift all the remaining characters by one.
This problem is little more involved than simple removal of duplicates.
Assuming that string contain ASCII chars (array can be extended to 256 for extended ASCII), below solution in Java will take O(n) time:
public static String removeDupChars(String input) {
if(input==null || input.length() == 0) {
return input;
}
String newStr = "";
int[] charSet = new int[128];
for(char c : input.toCharArray()) {
if(charSet[c] == 0) {
newStr = newStr + c;
}
charSet[c]++;
}
return newStr;
}
Idea to do it inplace is to swap the dupes to the end of the array and maintain a variable that tells you end of the unique values , result will be char [] from 0 to end. See code below :-
Note : string builder is just a syntactical sugar , we already have result in input array from 0 to end
public static string RemoveDupesInPlace(this string input)
{
bool[] present = new bool[255];
int end = input.Length - 1;
char temp;
char[] inputArray = input.ToArray<char>();
StringBuilder builder = new StringBuilder();
for (int i = 0; i < inputArray.Length && i < end; i++)
{
if (present[inputArray[i] - 'a'])
{
temp = inputArray[end];
inputArray[end] = inputArray[i];
inputArray[i] = temp;
end--;
i--;
}
else
{
present[inputArray[i] - 'a'] = true;
}
}
foreach (var item in inputArray.Take(end))
{
builder.Append(item);
}
return builder.ToString();
}
class RemoveDup(
val str: String) {
def removedup(): String = {
val a = new Array[Boolean](256)
val sb = new StringBuffer
str.foreach(c => {
if (a(c.toInt) == false) {
a(c.toInt) = true
sb.append(c)
}
})
sb.toString
}
}
object RemoveDup {
def main(args: Array[String]):Unit = {
val inst = new RemoveDup("amazon")
val after: String = inst.removedup
println(after)
}
}
/* assume ASCII */
int remove_duplicates(char *str)
{
char *cp, *currentp;
unsigned char map[32] = {0};
for (currentp = str, cp = str; *cp; cp++)
{
if (!(map[*cp >> 3] & ( 1 << (*cp & 7))))
{
map[*cp >> 3] |= (1 << (*cp & 7));
*currentp++ = *cp;
}
}
*currentp = '\0';
return currentp - str;
}
i am just going to help you out with logic:
first take the string in a variable
secondly use a loop construct to loop until the stringlength
use an if clause and compare the string character by character
if the character repeats two times go for else clause and increment the array of characters by +1 (this step eliminates the dual characters)
similarly for all
characters in an array and then print the array it display the series of character without duplicates .
Thus you can achieve it.
NOTE: take string as array of character as you take in C-lang.
Hope it was useful.
Thank U.-
public static String dup(String word)
{
boolean check =false; //"";
HashSet<Character>s = new HashSet<Character>();
String result = "";
for(int i = 0 ; i < word.length();++i)
{
check =s.add(word.charAt(i));
if(word.charAt(i)>='a'&&word.charAt(i)<='z')
{
char ch = (char)((char)word.charAt(i)-'a'+'A');
check =s.add(ch);
if(check==true)
{
result += word.charAt(i);
}
}
else if(word.charAt(i)>='A'&&word.charAt(i)<='Z')
{
char ch = (char)((char)word.charAt(i)-'A'+'a');
check =s.add(ch);
if(check==true)
{
result += word.charAt(i);
}
}
else
{
if(check==true)
{
result += word.charAt(i);
}
}
}
return result;
}
StringBuilder myNewString = new StringBuilder();
for (int i = 0; i < str.Length; i++)
{
if (i == 0 && str[i] == ' ')
continue;
if (i == str.Length - 1 && str[i] == ' ')
continue;
if (i > 0)
{
if (str[i] == ' ' && str[i - 1] == ' ')
continue;
else
{
myNewString.Append(str[i]);
}
}
}
return myNewString.ToString();
suppose your string is " Hello World "
your output should be "Hello World"
I think it is nor possible to do it in O(n) time complexity without extra space. In order to remove duplicates we have to keep track of elements which have been already processed or time complexity will be bigger cause multiple check of the same elements is required.
This can be resolved using a simple approach - no hashmaps. You can reduce your complexity to O(N) by simply using an array of size 128 characters (to represent ASCII values). This boolean array will track the characters you encounter as you iterate through the string.
Implementation below:
- vincethecoder December 19, 2013