Two Sigma Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class RegExpDemo {
public static void main(String[] args) {
String word = "abcd";
String[] regex = {"a?c","a*?c","\'*","\\?c"};
for(String str: regex){
Pattern pattern = Pattern.compile(str);
Matcher match = pattern.matcher(word);
System.out.println(match.find());
}
}
}
import unittest
def regex_match(st, reg):
i = 0
j = 0
reg_len = len(reg)
while i < len(st) and j < reg_len:
if reg[j].isalpha():
if st[i] != reg[j]:
return False
i = i + 1
j = j + 1
elif reg[j] == '?':
i = i + 1
j = j + 1
elif reg[j] == '*':
if j == reg_len - 1:
i = i + 1
else:
j = j + 1
return True
class Test(unittest.TestCase):
in_out = [['abc', 'a?c', True], ['abc', 'a*?c', True], ['abc', '*', True], ['abc', '?c', False], ['abc', 'a*', True]]
def test_regex_match(self):
for st, reg, out in self.in_out:
output = regex_match(st, reg)
self.assertEqual(output, out)
if __name__ == '__main__':
unittest.main()
import unittest
def regex_match(st, reg):
i = 0
j = 0
reg_len = len(reg)
while i < len(st) and j < reg_len:
if reg[j].isalpha():
if st[i] != reg[j]:
return False
i = i + 1
j = j + 1
elif reg[j] == '?':
i = i + 1
j = j + 1
elif reg[j] == '*':
if j == reg_len - 1:
i = i + 1
else:
j = j + 1
return True
class Test(unittest.TestCase):
in_out = [['abc', 'a?c', True], ['abc', 'a*?c', True], ['abc', '*', True], ['abc', '?c', False], ['abc', 'a*', True]]
def test_regex_match(self):
for st, reg, out in self.in_out:
output = regex_match(st, reg)
self.assertEqual(output, out)
if __name__ == '__main__':
unittest.main()
import unittest
def regex_match(st, reg):
i = 0
j = 0
reg_len = len(reg)
while i < len(st) and j < reg_len:
if reg[j].isalpha():
if st[i] != reg[j]:
return False
i = i + 1
j = j + 1
elif reg[j] == '?':
i = i + 1
j = j + 1
elif reg[j] == '*':
if j == reg_len - 1:
i = i + 1
else:
j = j + 1
return True
class Test(unittest.TestCase):
in_out = [['abc', 'a?c', True], ['abc', 'a*?c', True], ['abc', '*', True], ['abc', '?c', False], ['abc', 'a*', True]]
def test_regex_match(self):
for st, reg, out in self.in_out:
output = regex_match(st, reg)
self.assertEqual(output, out)
if __name__ == '__main__':
unittest.main()
import unittest
def regex_match(st, reg):
i = 0
j = 0
reg_len = len(reg)
while i < len(st) and j < reg_len:
if reg[j].isalpha():
if st[i] != reg[j]:
return False
i = i + 1
j = j + 1
elif reg[j] == '?':
i = i + 1
j = j + 1
elif reg[j] == '*':
if j == reg_len - 1:
i = i + 1
else:
j = j + 1
return True
class Test(unittest.TestCase):
in_out = [['abc', 'a?c', True], ['abc', 'a*?c', True], ['abc', '*', True], ['abc', '?c', False], ['abc', 'a*', True]]
def test_regex_match(self):
for st, reg, out in self.in_out:
output = regex_match(st, reg)
self.assertEqual(output, out)
if __name__ == '__main__':
unittest.main()
public class StringMatch {
public static void main(String[] args) {
System.out.println(isMatch("abc", "a*?c"));
System.out.println(isMatch("abc", "a*c"));
System.out.println(isMatch("abc", "a?c"));
System.out.println(isMatch("abc", "*"));
System.out.println(isMatch("abc", "?c"));
System.out.println(isMatch("adfjhfdnbkdsfhjjsk", "a*j?k"));
System.out.println(isMatch("abcacbcd", "a*cd"));
}
private static boolean isMatch(String s, String m) {
boolean match = isMatch(s, m, 0, 0);
System.out.println(s + " match " + m + " is " + match);
return match;
}
private static boolean isMatch(String s, String m, int ms, int ss) {
if (ms > 0 && ms >= m.length()) {
return true;
}
char mChar = m.charAt(ms);
if (mChar == '?') {
return isMatch(s, m, ms + 1, ss + 1);
}
if (mChar != '*') {
if (s.charAt(ss) == mChar) {
return isMatch(s, m, ms + 1, ss + 1);
}
return false;
}
return isMatch(s, m, ms + 1, s.length() - (m.length() - ms) + 1);
}
}
- Basu May 09, 2017