Microsoft Interview Question
Software DevelopersTeam: Bing
Country: United Kingdom
Interview Type: Written Test
static public List<String> subString(String str){
List<String> lst = new LinkedList<>();
outer : for(int outer_index = 0; outer_index < str.length(); outer_index++){
int start_index = str.charAt(outer_index);
for(int inner_index = outer_index+1; inner_index < str.length(); inner_index++){
if(start_index < str.charAt(inner_index)){
lst.add(str.substring(outer_index, inner_index + 1));
start_index = str.charAt(inner_index);
}else{
continue outer;
}
}
}
return lst;
}
//Scala code for the above
def listIncreasingSubstring(str : String): List[String] = {
def loop(start : Int, end : Int, result : List[String]) : List[String] = {
val sub = str.substring(start,end+1)
//See if this substring is strictly increasing
val correctStart = everyCharIsGreaterThanLast(str,start,end)
//Add the substring if it is increasing
val newResult = if(correctStart) sub :: result else result
//further loop conditions
if(end == str.length - 1 && start == str.length - 2) newResult
//checking correctStart here so that if a substring is not increasing from a fixed start there is no point in checking further from that start
else if (end == str.length - 1 || !correctStart) loop(start+1,start+2,newResult)
else loop(start,end+1,newResult)
}
loop(0,1,Nil)
}
def everyCharIsGreaterThanLast(str: String, start : Int, end: Int) : Boolean = {
if (start == end) true
else if(str.charAt(start) >= str.charAt(start+1)) false
else everyCharIsGreaterThanLast(str,start+1,end)
}
public static List<String> count(String str) {
if(str == null || str.length() == 0) return null;
List<String> ans = new ArrayList<>();
for(int i=0; i<str.length(); i++){
StringBuilder sb = new StringBuilder();
sb.append(str.charAt(i));
for(int j=i+1; j<str.length(); j++){
sb.append(str.charAt(j));
if(str.charAt(j-1) < str.charAt(j))
//ans.add(str.substring(i,j+1));
ans.add(sb.toString());
else // If subarray arr[i..j] is not strictly increasing, then subarrays after it , i.e.,
// arr[i..j+1], arr[i..j+2], .... cannot be strictly increasing
break;
}
}
return ans;
public static List<String> count(String str) {
if(str == null || str.length() == 0) return null;
List<String> ans = new ArrayList<>();
for(int i=0; i<str.length(); i++){
StringBuilder sb = new StringBuilder();
sb.append(str.charAt(i));
for(int j=i+1; j<str.length(); j++){
sb.append(str.charAt(j));
if(str.charAt(j-1) < str.charAt(j))
//ans.add(str.substring(i,j+1));
ans.add(sb.toString());
else // If subarray arr[i..j] is not strictly increasing, then subarrays after it , i.e.,
// arr[i..j+1], arr[i..j+2], .... cannot be strictly increasing
break;
}
}
return ans;
public static List<string> getConsecutiveLettersinString(string s)
{
List<string> cs = new List<string>();
for (int i = 0; i < s.Length; i++)
{
int k = i;
for (int j = i + 1; j < s.Length; j++)
{
if (s[k] < s[j])
{
cs.Add(s.Substring(i, j - i + 1));
k++;
}
else
{
break;
}
}
}
return cs;
}
public static void ReturnSubstringGreaterThanTwo(string myString)
{
char[] myChar = myString.ToArray();
List<char> lstChar = new List<char>();
List<string> lst = new List<string>();
for (int i = 0; i < myChar.Count() - 1; i++)
{
lstChar.Add(myChar[i]);
for (int j = i+1; j < myChar.Count(); j++)
{
if (myChar[j-1] != myChar[j])
{
lstChar.Add(myChar[j]);
lst.Add(new string(lstChar.ToArray()));
}
else
{
break;
}
}
lstChar.Clear();
}
lst.ForEach(s => Console.WriteLine(s));
}
int getLongest( string & orig, int start, set<string>& ans)
{
int consec = 1;
for ( int i=start; i < orig.length() -1 ; i++ )
{
if ( orig[i+1] == orig[i]+1 )
{
consec++;
if ( consec > 1 )
ans.insert(orig.substr(start,consec));
}
else
break;
}
return consec;
}
set<string> consecutiveChars(string orig)
{
set<string> consecutive;
int start=0;
while( start < orig.size() )
{
start+=getLongest(orig, start,consecutive);
}
return consecutive;
}
v = "abcdefghijklmnopqrstuvwxyz"
v = {char:i for char,i in zip(v,range(26))}
#print v
def printStr(s):
st = s[0]
for i in range(1,len(s)):
if v[s[i]] - v[st[-1]] == 1:
st += s[i]
else:
for j in range(2,len(st)+1):
for k in range(0,len(st)-j+1):
print st[k:k+j],
st = s[i]
for j in range(2,len(st)+1):
for k in range(0,len(st)-j+1):
print st[k:k+j],
return
v = "abcdefghijklmnopqrstuvwxyz"
v = {char:i for char,i in zip(v,range(26))}
#print v
def printStr(s):
st = s[0]
for i in range(1,len(s)):
if v[s[i]] - v[st[-1]] == 1:
st += s[i]
else:
for j in range(2,len(st)+1):
for k in range(0,len(st)-j+1):
print st[k:k+j],
st = s[i]
for j in range(2,len(st)+1):
for k in range(0,len(st)-j+1):
print st[k:k+j],
return
v = "abcdefghijklmnopqrstuvwxyz"
v = {char:i for char,i in zip(v,range(26))}
#print v
def printStr(s):
st = s[0]
for i in range(1,len(s)):
if v[s[i]] - v[st[-1]] == 1:
st += s[i]
else:
for j in range(2,len(st)+1):
for k in range(0,len(st)-j+1):
print st[k:k+j],
st = s[i]
for j in range(2,len(st)+1):
for k in range(0,len(st)-j+1):
print st[k:k+j],
return
public static List<string> GetSubString(string inputString)
{
List<string> subString = new List<string>();
for (int i = 0; i <inputString.Length; i++)
{
int k = i;
for (int j = i + 1; j < inputString.Length; j++)
{
if (inputString[k] < inputString[j])
{
if (j >= 2)
{
if (inputString[j] <= inputString[j - 1])
{
break;
}
}
subString.Add(inputString.Substring(i,j-i+1));
}
else
{
break;
}
}
}
return subString;
}
Input --> BCCDDEEFG
Output --> BC, CD, DE, EF, EFG, FG
I have few question what about CC? BCC? why where those skipped? does the substring be unique characters?
- Gear March 05, 2017