Microsoft Interview Question
Program Managerspublic List<string> Tokenize(string input, string delimeters)
{
HashSet<char> delims = new HashSet<char>(delimeters);
List<string> strings = new List<string>();
StringBuilder sb = new StringBuilder();
foreach (char ch in input)
{
if (delims.Contains(ch))
{
if (sb.Length > 0)
strings.Add(sb.ToString());
sb.Clear();
}
else
sb.Append(ch);
}
if(sb.Length>0) //Required for the case when there is no delimeter at the end of the input string
strings.Add(sb.ToString());
return strings;
}
Though I am not super happy about the code and repeat of logic, right now I couldn't find any improvement.
/*
* Assuming that we are dealing with ascii strings
*/
private static List<String> delimit(String str, String delimit){
//Flags to set the delimiters to true
boolean[] flag = new boolean[128];
List<String> l = new ArrayList<String>();
int pivot=0;
String temp;
for(int i=0 ; i < delimit.length() ; i++){
flag[(int)delimit.charAt(i)] = true;
}
for(int i=0; i <str.length() ; i++ ){
if(flag[(int)str.charAt(i)]){
temp = str.substring(pivot,i);
if(temp.length() > 0) {
l.add(temp);
}
pivot = i+1;
}
}
l.add(str.substring(pivot));
return l;
}
/*
* Assuming that we are dealing with ascii strings
*/
private static List<String> delimit(String str, String delimit){
//Flags to set the delimiters to true
boolean[] flag = new boolean[128];
List<String> l = new ArrayList<String>();
int pivot=0;
String temp;
for(int i=0 ; i < delimit.length() ; i++){
flag[(int)delimit.charAt(i)] = true;
}
for(int i=0; i <str.length() ; i++ ){
if(flag[(int)str.charAt(i)]){
temp = str.substring(pivot,i);
if(temp.length() > 0) {
l.add(temp);
}
pivot = i+1;
}
}
l.add(str.substring(pivot));
return l;
}
My answer will goes like this
1. Create the hash map of the delimineters
2. Now scan through the string, if the charater is in the hash map, tokenize that string at that locaction.
Time complexity -> O(m) for creating heap + O(n) scaning the main string
However this approach will work good for ascii characters.
For any kind of string, I think using BST will be better choice
Time complexity -> O(mlogm) for creating heap + O(nlogm) scaning the main string
please check below code using hashing .suggestions are always accepted.
void print(char *str,int start,int end)
{
cout<<endl;
while(start<end)
{
cout<<str[start++];
}
}
void deleim_print(char *str,char *del)
{
char hash[256]={0,};
int start=0;
for(int i=0;del[i]!='\0';i++)
hash[del[i]]++;
for(int i=0;str[i];i++)
{
if(hash[str[i]]>=1)
{
print(str,start,i-1);
start=i+1;
}
}
}
Is this consider "efficient"? This should be O(n)...
import java.util.ArrayList;
public class SubString {
public static String subString(String s, ArrayList<Character> deli) {
String result = "";
char[] temp = s.toCharArray();
for (int i = 0; i < temp.length; i++) {
if (!deli.contains(temp[i])) {
result += temp[i];
} else {
result += ", ";
}
}
return result;
}
public static void main(String args[]) {
ArrayList<Character> arr = new ArrayList<Character>();
arr.add('c');
arr.add('g');
System.out.println(subString("abbcdeffghujsb", arr));
}
}
public string[] DelimitString(string strInput, char[] chDelimChars)
{
string[] strTemp = new string[10];
try
{
foreach (char ch in chDelimChars)
{
strInput = strInput.Replace(ch, '&');
}
strTemp = strInput.Split('&');
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
return strTemp;
}
Create a StringBuffer and a set of characters.
We iterate throught the StringBuffer character by character and for every character we check the set.
if at any time we find that the character in StringBuffer is present in the set, we replace that character by a space(' ').
we carray on the above step till we reach the end of the StringBuffer.
Here is the Java code:
import java.util.*;
class Delimiter{
static StringBuffer sbf;
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String st = sc.next();
sbf = new StringBuffer(st);
//create Set of the chars
//lets for simplicity I take chars as a d e k you can take it from user or anything
Set<Character> set = new HashSet<Character>();
set.add('a');
set.add('d');
set.add('e');
set.add('k');
for(int i=0;i<st.length();i++)
{
if(set.contains(sbf.charAt(i)))
sbf.setCharAt(i,' ');
}
System.out.println(sbf.toString());
}
}
Pretty much same logic as prolific coder. But in C++
- abhimanipal May 20, 2010//Assumptions 2 null terminated strings. Original string will be destroyed
//Program insert the ' ' instead of the delimiters
void func(char* str, char* str1)
{
map<char,int> map1;
int i=0;
//Insert all delimiters in the map
for(i=0;i<strlen(str1);i++)
map1[str1[i]]++;
// If this char is a delimiter, insert space instead of the char
for(i=0;i<strlen(str);i++)
{
if(map1[str[i]]>0)
str[i]=' ';
}
}
int main(void)
{
char str[]= "abhishekagrawal";
char str1[]="askw";
printf("Before %s %s\n",str,str1);
func(str,str1);
printf("After %s \n",str);
cin.get();
return 0;
}