Microsoft Interview Question Software Engineers
Country: United States
public string convertStringToSum(string s){
s = convertStringToNumberString();
if(string.IsNullOrWhiteSpace(s)){
return string.empty;
}
int result = 0;
bool isMinus = false;
int currnum = 0;
for(int i=0; i<s.Length; i++){
if(s[i] == '-'){
// a number has ended. add num to result
if(isMinus) {result -= currnum;} else {result += currnum}
isMinus=true;
currnum=0;
} else if(s[i] == '+'){
if(isMinus) {result -= currnum;} else {result += currnum}
isMinus=false;
currnum=0;
} else {
currnum *= 10 + Int32.ParseInt(s[i]);
}
}
if(isMinus) {result -= currnum;} else {result += currnum}
return result;
}
private string convertStringToNumberString(string s){
if(string.IsNullOrWhiteSpace(s)){
return string.empty;
}
Trie trie = createTrie("zero","one","two",...,"nine","minus"); OR USE A MAP. Trie is more efficient in both space and time.
Map<string,string> map = new Map<string,string>();map.Add("zero","0"); map.Add("minus","-");
string result = string.empty;
int lastEndIndex = -1;
for(int i=0; i<s.Length-2; i++){ // length varies from 3 to 5
// for each character, check if it is a start of a number
// length varies from 3 to 5
for(int len = 3; len<=5 && s.Length<=(i+len); len++){
string possnum = s.Substring(i,len);
if(map.ContainsKey(possnum)){ // number is found,
if(lastEndIndex == i-1){ // continuous
result = result + map[possnum];
} else if (map[possnum] == "-"){
result = result + map[possnum];
} else {
result = result + "+" + map[possnum];
}
lastEndIndex = i+len-1;
}
}
}
return result;
}
Create a trie with all the key words one two three and so on .
Trie should have these functions Trie.isMatchPartial(key)
Trie.isMatchFull(key)
Trie.payload(key)
The payload would return the integer 0-9 or -1 when minus is seen.
Now we can loop through the string pattern as long as there is partial match. If full match then get payload and add it to the sum.
If partial match fails move the pointer on the pattern string by as many elements as matched and repeat again.
Create a trie and match the string pattern till as long as there is is partial match. If full match we can lookup the value and add it to sum. Since there could be multiple integers together we will have to continue till we have no full matches.
If partial match fails then we can increment by the amount matched and move ahead and start partial match again.
Minus can be handles as well by returning -1 and set a flag negative state. Subsequent integer
KEYWORDS = {
'zero': '0',
'one': '1',
'two': '2',
'three': '3',
'four': '4',
'five': '5',
'six': '6',
'seven': '7',
'eight': '8',
'nine': '9',
'minus': '-',
}
def is_keyword(string, i):
for kw in KEYWORDS:
j = i
for char in kw:
if char != string[j]:
break
j += 1
if len(kw) == (j - i):
return kw
return False
def sum_string(string: str) -> int:
digits = []
sum, i = 0, 0
while i < len(string):
kw = is_keyword(string, i)
if kw:
digits.append(KEYWORDS[kw])
i += len(kw)
else:
if len(digits):
sum += int(''.join(digits))
digits = []
i += 1
if len(digits):
sum += int(''.join(digits))
return sum
KEYWORDS = {
'zero': '0',
'one': '1',
'two': '2',
'three': '3',
'four': '4',
'five': '5',
'six': '6',
'seven': '7',
'eight': '8',
'nine': '9',
'minus': '-',
}
def is_keyword(string, i):
for kw in KEYWORDS:
j = i
for char in kw:
if char != string[j]:
break
j += 1
if len(kw) == (j - i):
return kw
return False
def sum_string(string: str) -> int:
digits = []
sum, i = 0, 0
while i < len(string):
kw = is_keyword(string, i)
if kw:
digits.append(KEYWORDS[kw])
i += len(kw)
else:
if len(digits):
sum += int(''.join(digits))
digits = []
i += 1
if len(digits):
sum += int(''.join(digits))
return sum
assert sum_string('xyzonexyztwothreeeabrminusseven') == 17
public static int ConvertStringToNumber(String input)
{
Dictionary<string, string> dict = new Dictionary<string, string>();
string result = string.Empty;
dict.Add("zero", "0");
dict.Add("one", "1");
dict.Add("two", "2");
dict.Add("three", "3");
dict.Add("four", "4");
dict.Add("five", "5");
dict.Add("six", "6");
dict.Add("seven", "7");
dict.Add("eight", "8");
dict.Add("nine", "9");
dict.Add("minus", "-");
StringBuilder strB = new StringBuilder();
StringBuilder strB1 = new StringBuilder();
for (int i = 0; i <= input.Length - 1; i++)
{
strB.Append(input[i]);
if (strB.Length >= 3)
{
if (dict.ContainsKey(strB.ToString().ToLower()))
{
strB1.Append(dict[strB.ToString().ToLower()]);
strB = new StringBuilder();
}
else if (strB.Length > 5)
{
strB1.Append("+");
strB = new StringBuilder();
i = i - 3;
}
}
}
Console.WriteLine(strB1.ToString());
DataTable dt = new DataTable();
return (int)dt.Compute(strB1.ToString(), "");
}
}
public static int ConvertStringToNumber(String input)
{
Dictionary<string, string> dict = new Dictionary<string, string>();
string result = string.Empty;
dict.Add("zero", "0");
dict.Add("one", "1");
dict.Add("two", "2");
dict.Add("three", "3");
dict.Add("four", "4");
dict.Add("five", "5");
dict.Add("six", "6");
dict.Add("seven", "7");
dict.Add("eight", "8");
dict.Add("nine", "9");
dict.Add("minus", "-");
StringBuilder strB = new StringBuilder();
StringBuilder strB1 = new StringBuilder();
for (int i = 0; i <= input.Length - 1; i++)
{
strB.Append(input[i]);
if (strB.Length >= 3)
{
if (dict.ContainsKey(strB.ToString().ToLower()))
{
strB1.Append(dict[strB.ToString().ToLower()]);
strB = new StringBuilder();
}
else if (strB.Length > 5)
{
strB1.Append("+");
strB = new StringBuilder();
i = i - 3;
}
}
}
DataTable dt = new DataTable();
return (int)dt.Compute(strB1.ToString(), "");
}
}
public static int ConvertStringToNumber(String input)
{
Dictionary<string, string> dict = new Dictionary<string, string>();
string result = string.Empty;
dict.Add("zero", "0");
dict.Add("one", "1");
dict.Add("two", "2");
dict.Add("three", "3");
dict.Add("four", "4");
dict.Add("five", "5");
dict.Add("six", "6");
dict.Add("seven", "7");
dict.Add("eight", "8");
dict.Add("nine", "9");
dict.Add("minus", "-");
StringBuilder strB = new StringBuilder();
StringBuilder strB1 = new StringBuilder();
for (int i = 0; i <= input.Length - 1; i++)
{
strB.Append(input[i]);
if (strB.Length >= 3)
{
if (dict.ContainsKey(strB.ToString().ToLower()))
{
strB1.Append(dict[strB.ToString().ToLower()]);
strB = new StringBuilder();
}
else if (strB.Length > 5)
{
strB1.Append("+");
strB = new StringBuilder();
i = i - 3;
}
}
}
Console.WriteLine(strB1.ToString());
DataTable dt = new DataTable();
return (int)dt.Compute(strB1.ToString(), "");
String inputStr = "xyzonexyztwothreeeabrminussevenskdjjtwozerodfs";
int i=0, sum=0;
String currString = "";
inputStr =inputStr.replace("one", "1");
inputStr =inputStr.replace("two", "2");
inputStr =inputStr.replace("three", "3");
inputStr =inputStr.replace("four", "4");
inputStr =inputStr.replace("five", "5");
inputStr =inputStr.replace("six", "6");
inputStr =inputStr.replace("seven", "7");
inputStr =inputStr.replace("eight", "8");
inputStr =inputStr.replace("nine", "9");
inputStr =inputStr.replace("zero", "0");
inputStr =inputStr.replace("minus", "-");
while(i<inputStr.length())
{
if(inputStr.charAt(i) >= '0' && inputStr.charAt(i) <= '9' || inputStr.charAt(i) == '-' )
{
currString = currString + inputStr.charAt(i);
i++;
}
else
{
if(currString != "")
{
sum = sum + Integer.parseInt(currString);
currString = "";
}
i++;
}
}
if(currString != "")
sum = sum + Integer.parseInt(currString);
System.out.println(sum);
String inputStr = "xyzonexyztwothreeeabrminusseven";
int i=0, sum=0;
String currString = "";
inputStr =inputStr.replace("one", "1");
inputStr =inputStr.replace("two", "2");
inputStr =inputStr.replace("three", "3");
inputStr =inputStr.replace("four", "4");
inputStr =inputStr.replace("five", "5");
inputStr =inputStr.replace("six", "6");
inputStr =inputStr.replace("seven", "7");
inputStr =inputStr.replace("eight", "8");
inputStr =inputStr.replace("nine", "9");
inputStr =inputStr.replace("zero", "0");
inputStr =inputStr.replace("minus", "-");
while(i<inputStr.length())
{
if(inputStr.charAt(i) >= '0' && inputStr.charAt(i) <= '9' || inputStr.charAt(i) == '-' )
{
currString = currString + inputStr.charAt(i);
i++;
}
else
{
if(currString != "")
{
sum = sum + Integer.parseInt(currString);
currString = "";
}
i++;
}
}
if(currString != "")
sum = sum + Integer.parseInt(currString);
System.out.println(sum);
A C# solution
public class q1
{
public int input { get; set; }
public Dictionary<string,string> keywords { set; get; }
public q1()
{
keywords = new Dictionary<string, string>();
keywords.Add("one", "1");
keywords.Add("two", "2");
keywords.Add("three", "3");
keywords.Add("four", "4");
keywords.Add("five", "5");
keywords.Add("six", "6");
keywords.Add("seven", "7");
keywords.Add("eight", "8");
keywords.Add("nine", "9");
keywords.Add("zero", "0");
keywords.Add("minus", "-");
}
public int Calcuate(string input)
{
int sum = 0,k;
string temp = "";
bool f = false;
List<int> numbers = new List<int>();
foreach(var itm in this.keywords)
{
input = input.Replace(itm.Key, itm.Value);
}
foreach(char c in input)
{
if (keywords.ContainsValue(c.ToString()))
{
temp += c.ToString();
f = true;
}
else
{
if (f)
{
numbers.Add(int.Parse(temp));
temp = "";
f = false;
}
}
}
if (temp != "")
{
numbers.Add(int.Parse(temp));
}
foreach(int i in numbers)
{
sum += i;
}
return sum;
}
public static void test()
{
Console.WriteLine("input:");
string input = Console.ReadLine();
q1 q = new q1();
int sum = q.Calcuate(input);
Console.WriteLine($"sume is {sum}");
Console.Read();
}
}
import java.util.*;
public class SumOfAllNumbers
{
public static void main(String args[])
{
Trie root = new Trie();
Map<String, String> dict = new HashMap<>();
dict.put("zero", "0");
root.addWord("zero");
dict.put("one", "1");
root.addWord("one");
dict.put("two", "2");
root.addWord("two");
dict.put("three", "3");
root.addWord("three");
dict.put("four", "4");
root.addWord("four");
dict.put("five", "5");
root.addWord("five");
dict.put("six", "6");
root.addWord("six");
dict.put("seven", "7");
root.addWord("seven");
dict.put("eight", "8");
root.addWord("eight");
dict.put("nine", "9");
root.addWord("nine");
root.addWord("minus");
System.out.println(root.findWord("one"));
System.out.println(root.findWord("two"));
System.out.println(root.findWord("ones"));
SumOfAllNumbers a = new SumOfAllNumbers();
String s = "xyzonexyztwothreeeabrminusseven";
System.out.println(a.findSum(s, root, dict));
}
public int findSum(String s, Trie trie, Map<String, String> dict)
{
TrieNode node = trie.root;
StringBuilder sb = new StringBuilder();
//int sum = 0;
boolean negative = false;
StringBuilder res = new StringBuilder();
for(int i = 0;i<s.length();i++)
{
char c = s.charAt(i);
TrieNode child = node.getChild(c);
if(child==null)
{
i = i - sb.length();
sb = new StringBuilder();
node = trie.root;
res.append(" ");
continue;
}
else
{
sb.append(child.getVal());
node = child;
if(child.isWord())
{
if("minus".equals(sb.toString()))
negative = true;
else
{
String n = dict.get(sb.toString());
if(negative)
n = "-"+n;
res.append(n);
negative = false;
node = trie.root;
sb = new StringBuilder();
}
}
}
}
String[] nums = res.toString().split("\\s+");
int sum = 0;
for(String n : nums)
{
if(!n.isEmpty())
sum += Integer.parseInt(n);
}
return sum;
}
}
class Trie
{
TrieNode root;
public Trie()
{
this.root = new TrieNode(' ');
}
public void addWord(String s)
{
TrieNode node = this.root;
for(char c : s.toCharArray())
{
TrieNode temp = node.getChild(c);
if(temp == null)
{
TrieNode child = new TrieNode(c);
node.getChildren().add(child);
node = child;
}
else
{
node = temp;
}
}
node.setWord(true);
}
public boolean findWord(String s)
{
TrieNode node = this.root;
for(char c : s.toCharArray())
{
TrieNode temp = node.getChild(c);
if(temp == null)
{
return false;
}
else
{
node = temp;
}
}
return node.isWord();
}
}
class TrieNode
{
private char val;
private List<TrieNode> children;
private boolean word;
TrieNode(char val)
{
this.val = val;
this.children = new ArrayList<>();
this.word = false;
}
public List<TrieNode> getChildren()
{
return this.children;
}
public TrieNode getChild(char c)
{
for(TrieNode child : this.children)
{
if(child.val == c)
return child;
}
return null;
}
public void setWord(boolean flag)
{
this.word = flag;
}
public boolean isWord()
{
return this.word;
}
public char getVal()
{
return this.val;
}
}
import java.util.*;
public class SumOfAllNumbers
{
public static void main(String args[])
{
Trie root = new Trie();
Map<String, String> dict = new HashMap<>();
dict.put("zero", "0");
root.addWord("zero");
dict.put("one", "1");
root.addWord("one");
dict.put("two", "2");
root.addWord("two");
dict.put("three", "3");
root.addWord("three");
dict.put("four", "4");
root.addWord("four");
dict.put("five", "5");
root.addWord("five");
dict.put("six", "6");
root.addWord("six");
dict.put("seven", "7");
root.addWord("seven");
dict.put("eight", "8");
root.addWord("eight");
dict.put("nine", "9");
root.addWord("nine");
root.addWord("minus");
System.out.println(root.findWord("one"));
System.out.println(root.findWord("two"));
System.out.println(root.findWord("ones"));
SumOfAllNumbers a = new SumOfAllNumbers();
String s = "xyzonexyztwothreeeabrminusseven";
System.out.println(a.findSum(s, root, dict));
}
public int findSum(String s, Trie trie, Map<String, String> dict)
{
TrieNode node = trie.root;
StringBuilder sb = new StringBuilder();
//int sum = 0;
boolean negative = false;
StringBuilder res = new StringBuilder();
for(int i = 0;i<s.length();i++)
{
char c = s.charAt(i);
TrieNode child = node.getChild(c);
if(child==null)
{
i = i - sb.length();
sb = new StringBuilder();
node = trie.root;
res.append(" ");
continue;
}
else
{
sb.append(child.getVal());
node = child;
if(child.isWord())
{
if("minus".equals(sb.toString()))
negative = true;
else
{
String n = dict.get(sb.toString());
if(negative)
n = "-"+n;
res.append(n);
negative = false;
node = trie.root;
sb = new StringBuilder();
}
}
}
}
String[] nums = res.toString().split("\\s+");
int sum = 0;
for(String n : nums)
{
if(!n.isEmpty())
sum += Integer.parseInt(n);
}
return sum;
}
}
class Trie
{
TrieNode root;
public Trie()
{
this.root = new TrieNode(' ');
}
public void addWord(String s)
{
TrieNode node = this.root;
for(char c : s.toCharArray())
{
TrieNode temp = node.getChild(c);
if(temp == null)
{
TrieNode child = new TrieNode(c);
node.getChildren().add(child);
node = child;
}
else
{
node = temp;
}
}
node.setWord(true);
}
public boolean findWord(String s)
{
TrieNode node = this.root;
for(char c : s.toCharArray())
{
TrieNode temp = node.getChild(c);
if(temp == null)
{
return false;
}
else
{
node = temp;
}
}
return node.isWord();
}
}
class TrieNode
{
private char val;
private List<TrieNode> children;
private boolean word;
TrieNode(char val)
{
this.val = val;
this.children = new ArrayList<>();
this.word = false;
}
public List<TrieNode> getChildren()
{
return this.children;
}
public TrieNode getChild(char c)
{
for(TrieNode child : this.children)
{
if(child.val == c)
return child;
}
return null;
}
public void setWord(boolean flag)
{
this.word = flag;
}
public boolean isWord()
{
return this.word;
}
public char getVal()
{
return this.val;
}
}
Here is the basic idea. Yes, you can optimize, but... well.. that would mean amazingly bad - undebuggable code.
- NoOne June 07, 2017// create a name lookup table _names_ = { 'zero' : 0 , 'one' : 1 , 'two' : 2 , 'three' : 3 , 'four' : 4 , 'five' : 5 , 'six' : 6 ,'seven' : 7 ,'eight' : 8 , 'nine' : 9 } // a regex like zero|nine|six|four|one|seven|two|three|five|eight _int_pattern_ = str( _names_.keys , '|' ) -> { $.o } // regex (minus)?(zero|nine|six|four|one|seven|two|three|five|eight)+ _base_pattern_ = '(minus)?(' + _int_pattern_ +')+' // convert the word into integer def convert_int( word ){ sign_num = 1 // if the word starts with minus then if ( word #^ 'minus' ){ sign_num = -1 // change sign word = word[5:-1] // substring } // extracts digits by simple mapper - when a word match a digit digits = tokens( word , _int_pattern_ ) -> { _names_[$.o] } // convert the digits into integer and multiply by sign int( str(digits,'') ) * sign_num } // the actual function def count_nums_as_words_in_string( string ){ // sum of generated integers out of matched tokens sum( tokens( string, _base_pattern_ ) -> { convert_int($.o) }) } input = "xyzonexyztwothreeeabrminusseven" println( count_nums_as_words_in_string( input ) )