Microsoft Microsoft Interview Question
Software Engineer in TestsTeam: Office
Country: United States
Interview Type: In-Person
In the else part we can do potential_start = i+1, since two adjacent characters of non matching blocks will always return false. Does not really affect complexity though
public int indexOfRepeatedBlock(char[] word){
if(word == null || word.length == 0){
return -1;
}
int length = word.length -1;
int finalIndex = 0;
int maxCount = 0;
int startIndex = 0;
int iterator = 1;
while (iterator <= length){
int count = 1;
startIndex = iterator-1;
while (iterator <= length && (word[iterator-1] == word[iterator])){
iterator++;
count++;
}
if(count > maxCount){
maxCount = count;
finalIndex = startIndex;
}
iterator++;
}
return finalIndex;
}
public static int LargeBlock(String str)
{
if(str==null || str.length()==0)
return null;
int start=0,i,largecount,count,length=str.length();
i=1,largecount=1,count=1,temp=str.charAt(0);
while(i<length)
{
if(str.charAt(i)==str.charAt(i-1)&&str.charAt(i)!=" ")
{
count++;
}
else
{
if(largecount<count)
{
largecount=count;
start=i-count;
}
count=1;
}
i++;
}
return start;
}
Haven't tested it, could have some bugs.
public class LargestBlockRepeated {
public static int repeated(String str) {
int count = 0;
int largeCount = 0;
int position = 0;
int repeatedStartPosition = 0;
int runner = 1;
while (runner <str.length()-1 && position<str.length()-1) {
if (str.charAt(position) == str.charAt(runner)) {
runner++;
count++;
if (largeCount <= count) {
largeCount = count+1;
repeatedStartPosition = position;
}
} else {
if (runner == str.length()-1) {
position++;
} else {
count=0;
position = runner;
runner++;
}
}
}
return repeatedStartPosition;
}
public static void main(String args[]) {
System.out.println(" " + repeated("abeeeeefeegkkkkkkkk"));
}
}
a slightly more elegant solution:
public class FindLargestRepeated {
public static int repeated(String str) {
char [] c = str.toCharArray();
int runner = 1;
int position = 0;
int counter = 1;
int oldpos = 0;
int f = 1;
while(runner < c.length -1) {
if (c[position] == c[runner] ) {
counter++;
} else {
if (f < counter) {
f = counter;
oldpos = position;
}
counter = 1;
position = runner;
}
runner++;
}
//return (f < counter) ? counter: f;
return oldpos;
}
public static void main(String args[]) {
System.out.println(" " + repeated("abeeeeefeeeeeeeeeegkk"));
}
}
int GetRep( char *s)
{
char c = *s;
int n =0;
while ( c == *s)
{
s++; n++;
}
return n;
}
pair<int, int>LargestBlock( char * s)
{
int nTmpPos = 0;
int nTmpSize = GetRep( s+nTmpPos);;
int nLPos = nTmpPos;
int nLSize = nTmpSize;
while(true)
{
nTmpPos += nTmpSize;
nTmpSize = GetRep( s+nTmpPos);
if (nTmpSize > nLSize)
{
nLPos = nTmpPos ;
nLSize = nTmpSize;
}
if (!s[nTmpPos + nTmpSize])
{
pair<int , int> pRtn;
pRtn.first = nLPos;
pRtn.second = nTmpSize;
return pRtn;
}
};
char * p = "aaaaabbbbbbbbbbbbbbefxsscc";
int len = strlen(p);
cout << len << endl;
int idx = 0;
int maxRep = 0;
int maxIdx = 0;
while (idx < len)
{
int nRep = 1;
int idx2 = idx + 1;
while (idx2 < len && p[idx2] == p[idx])
{
idx2 ++;
nRep ++;
}
if (nRep > maxRep)
{
maxRep = nRep;
maxIdx = idx;
}
idx = idx2;
}
cout << "maxRep:" << maxRep << " maxIdx:" << maxIdx << endl;
char * p = "aaaaabbbbbbbbbbbbbbefxsscc";
int len = strlen(p);
cout << len << endl;
int idx = 0;
int maxRep = 0;
int maxIdx = 0;
while (idx < len)
{
int nRep = 1;
int idx2 = idx + 1;
while (idx2 < len && p[idx2] == p[idx])
{
idx2 ++;
nRep ++;
}
if (nRep > maxRep)
{
maxRep = nRep;
maxIdx = idx;
}
idx = idx2;
}
cout << "maxRep:" << maxRep << " maxIdx:" << maxIdx << endl;
In Java :
public int largestBlock(String s) {
int block = 0;
int prevblock = 0;
int blockidx = 0;
char[] schars = s.toCharArray();
int i=0,j=1;
for(;j<schars.length-1;i++,j++){
if(schars[i] == schars[j]){
block++;
continue;
}
if(block > prevblock){
prevblock = block;
blockidx = i - block;
}
block=0;
}
if(block > prevblock){
blockidx = i - block;
}
return blockidx;
}
public class LargestBlock {
public static void main(String[] args){
String target = "abcdddddddddddeeeeeefsddeeeeeeeeeeee";
int max = 0;
int maxindex = 0;
int index=0;
while(index < target.length()-1){
int counter = 0;
int subindex = index +1;
while(target.charAt(index)==target.charAt(subindex)){
counter++;
subindex++;
if(subindex == target.length()){
break;
}
}
if(counter > max){ // compare the counter with the previous max
max = counter;
maxindex = index;
}
index++;
}
System.out.println(maxindex);
}
}
<pre>
int get_max_sequential_start_index(const char *c) {
if (NULL == c) return -1;
int current_start = 0;
int max_start = 0;
int current_len = 0;
int max_len = 0;
int i = 0;
int len = strlen(c);
for (i = 1; i < len; i++) {
if (c[current_start] == c[i]) {
current_len++;
if (current_len > max_len) {
max_start = current_start;
max_len = current_len;
}
} else {
current_start = i;
current_len = 1;
}
}
return max_start;
}
</pre>
import java.util.Scanner;
//given a string, find the start position of the largest block of repeated
//chars
//
public class LargestCharBlocks{
public static int getStart(String s){
//never forget to check the null...
if(s == null || s.length() == 0)
return -1;
int tempStartRecord = 0;
int startRecord = 0;
char previousChar;
int maxLength = 0;
int tempLength = 0;
char[] string = s.toCharArray();
previousChar = string[0];
startRecord = 0;
maxLength = 1;
tempLength = 1;
for(int i = 1; i < string.length; i ++){
if(string[i] == previousChar){
tempLength ++;
}
else if(string[i] != previousChar){
if(tempLength > maxLength){
maxLength = tempLength;
startRecord = tempStartRecord;
}
tempStartRecord = i;
tempLength = 1;
previousChar = string[i];
}
}
return startRecord;
}
public static void main(String[] args){
Scanner s = new Scanner(System.in);
String string = s.next();
System.out.println(LargestCharBlocks.getStart(string));
return;
}
}
public static int LargestBlockOfrepeatedCharacters(String s)
{
int length = s.Length;
int largest = 0, Count=1, i=0;
if (s.Length == 0 || s == null)
{
Console.WriteLine("Invalid string");
}
else
{
while (i < s.Length-1)
{
if (s[i] == s[i + 1])
{
Count++;
}
else
{
if (Count > largest)
{
largest = Count;
}
}
i++;
}
}
return largest;
}
def maxRepeatStrIndex(data):
if (len(data)<1 or (data==" ")):
print("Blank string")
return -1
maxVal = 1
chStart=0
i = 0
cnt=1
while(i<len(data)-1):
i=i+1
if (data[i-1] == data[i]):
cnt=cnt+1
if ((i==len(data)-1) and (cnt > maxVal)):
maxVal=cnt
chStart = i-maxVal+1
else:
if (maxVal<cnt):
maxVal=cnt
chStart = i-maxVal
cnt=1
# it will return Max count, character and start position
return maxVal,data[chStart],chStart
#Here are few test cases and I tested it works fine
class TestStr(unittest.TestCase):
def test_end(self):
val = maxRepeatStrIndex("nddaaa")
#print(val)
assert val==(3, 'a', 3)
def test_start(self):
val = maxRepeatStrIndex("aaanaaa")
assert val==(3, 'a', 0)
def test_long(self):
val = maxRepeatStrIndex("aaanbbbbbbbbbbbbbbbbbcccccccccddddddddddaaa")
assert val==(18, 'c', 22)
if __name__ == '__main__':
unittest.main()
#include <stdio.h>
int main(int charc, char **argv)
{
char *string = argv[1];
int i = 0, mcount = 0, count = 0, start = 0;
char prevch, currch;
while(string[i] != '\0')
{
currch = string[i];
if(i == 0)
{
prevch = currch;
i++;
count++;
if(count > mcount)
{
mcount = count;
start = i - count;
}
continue;
}
if(prevch == currch)
{
i++;count++;
if(count > mcount)
{
mcount = count;
start = i - count;
}
prevch = currch;
continue;
}else{
i++;count = 1;
if(count > mcount)
{
mcount = count;
start = i - count;
}
prevch = currch;
continue;
}
}
if(count > mcount)
{
mcount = count;
start = i - count;
}
printf("largest block of repeating chars starts at %d and has %d chars\n", start, mcount);
return 0;
}
Test cases:
input : output
null : -1
a : 0
ab : 0
aa : 0
bba : 0
abb : 1
aba : 0
aabb : 0
aabbbaa : 2
class IQ {
public IQ() {}
/*
* ============================
*
* FIND START POSITION OF
* LONGEST BLOCK OF CHARS.
*
* ===========================
*/
public int maxRepeatedCharIndex(String s) {
if(s==null) return -1;
int length = s.length();
if(length==0) return -1;
if(length==1) return 0;
char[] chars = s.toCharArray();
int max = 0;
int maxIndex = 0;
int count;
int currIndex;
int i = 0;
//[aabc]
while(i < length) {
currIndex = i;
count=1;
while(i+1 < length && chars[i] == chars[i+1]) {
count++;
if(count > max) {
max = count;
maxIndex = currIndex;
}
i++;
}
i++;
}
System.out.println("maxIndex of "+s+ " is: "+maxIndex);
return maxIndex;
}
public void testMaxRepeatedCharIndex(String[] strs) {
for(String s : strs)
maxRepeatedCharIndex(s);
}
public static void main(String[] args) {
IQ iq = new IQ();
iq.testMaxRepeatedCharIndex(new String[] {null, "", "a", "ab", "aabb", "aba", "aa", "aabbb", "bbbaa", "aabbbaaa"});
}
}
#include <stdio.h>
void block_Size(char *);
void main()
{
char *str="dhdhdhddddhdhdhdhdhegeegeev";
block_Size(str);
}
void block_Size(char *a)
{
int c=1,pos=-1,j=0,count=0;
char ch;
ch=a[j];
j++;
while(a[j]!='\0')
{
if(ch==a[j])
{
c++;
}
else
{
if(c>count)
{
count=c;
pos=j-c;
}
ch=a[j];
c=1;
}
j++;
}
if(c>count)
{
count=c;
pos=j-c;
}
printf("character=%c\tposition=%d",a[pos],pos);
}
int LargestRepeatedBlock(const std::string& str)
{
if (str.length() == 0)
return -1;
unsigned int largestIndex = 0;
bool inBlock = false;
unsigned int largestBlockCount = 1;
unsigned int index = 0;
unsigned int blockCount = 1;
for (unsigned int i = 0; i < str.length() - 1; ++i)
{
if (str[i] == str[i + 1])
{
if (!inBlock)
{
inBlock = true;
index = i;
}
++blockCount;
}
else
{
if (inBlock)
{
if (blockCount > largestBlockCount)
{
largestIndex = index;
largestBlockCount = blockCount;
}
blockCount = 1;
index = 0;
inBlock = false;
}
}
}
if (blockCount > largestBlockCount)
{
largestIndex = index;
largestBlockCount = blockCount;
}
return largestIndex;
}
static string GetLongestSubString(string input)
{
if (string.IsNullOrEmpty(input))
return string.Empty;
//Return the sub string
string retstring = string.Empty;
//Max Length of dup chars
int stringLength = 0;
//Start Position
int startIndex = 0;
for (int i = 0; i < input.Length; i++)
{
int repeatLength = 1;
for (int j = i + 1; j < input.Length; j++)
{
if (input[j] == input[i])
repeatLength++;
else
break;
}
if (repeatLength > stringLength)
{
stringLength = repeatLength;
startIndex = i;
}
}
retstring = new string(input.ToCharArray(), startIndex, stringLength);
return retstring;
}
public int GetStartPosOfLargestRepChar(string str)
{
Dictionary<char, int> dic = new Dictionary<char, int>();
int max = 0;
char maxChar = ' ';
int pos = -1;
for (int i = 0; i < str.Length; i++)
{
if (dic.ContainsKey(str[i]))
{
dic[str[i]]++;
if (dic[str[i]] > max)
{
max = dic[str[i]];
maxChar = str[i];
pos = i;
}
}
else
dic.Add(str[i], 1);
}
for (int k = 0; k < str.Length; k++)
if (str[k] == maxChar)
{
pos = k;
break;
}
return pos;
}
void highest_occurence(const string& str)
{
int max = INT_MIN;
char maxChar = 0;
int count = 0;
char ch = 0;
for(int i = 0; i < str.length(); ++i)
{
if(i == str.length() - 1 || str[i] != str[i + 1])
{
if(count > max)
{
max = count;
maxChar = ch;
}
count = 0;
ch = str[i + 1];
}
else
{
++count;
}
}
cout << "Max occurence char is " << maxChar;
}
private static void largest(String string) {
//null check
if(string.length()==0)
System.out.println(-1);
//works with left, right and center largest repeat letters
int counter =1;
int largest =1;
char letter = ' ';
for(int i =0 ; i< string.length()-1; i++)
{
if(string.charAt(i+1)==string.charAt(i))
{
counter++;
if(largest < counter)
{
largest = counter;
letter = string.charAt(i+1);
}
}
else
{
counter=1;
}
}
if (largest!=1)
{
System.out.println(letter + " " + largest);
}
}
private static void largest(String string) {
//null check
if(string.length()==0)
System.out.println(-1);
//works with left, right and center largest repeat letters
int counter =1;
int largest =1;
char letter = ' ';
for(int i =0 ; i< string.length()-1; i++)
{
if(string.charAt(i+1)==string.charAt(i))
{
counter++;
if(largest < counter)
{
largest = counter;
letter = string.charAt(i+1);
}
}
else
{
counter=1;
}
}
if (largest!=1)
{
System.out.println(letter + " " + largest);
}
}
static int RepeatedChar(char[] a, int length)
{
int count = 1, max = 1, pos = 0;
for (int i = 0; i < length; i++)
{
if (i == length - 1)
{
if (a[i] == a[i - 1])
{
if (max < count)
{
max = count;
pos = i - count + 1;
}
count = 1;
}
}
else if (a[i] != a[i + 1])
{
if (max < count)
{
max = count;
pos = i - count + 1;
}
count = 1;
}
else
{
count++;
}
}
return pos;
}
Hi,
Was the question to return the starting point of a largest block of single repeated character?
meaning...in following string: "abcdddeeeeeefsddeee" , the return location should be : 6 (0 start index)..as "eeeeee" is the largest set of repeated character "e"
or
they want to return positon "3" because from that position..the largest set of repeated characters d and e i.e "dddeeeeeee" begins? The second set of repeate ddeee is smaller compared to first one.
This is the code I have ..
My understanding is: in a string aaeeeddbddddda ... The biggest block is ddddd so answer is 5.
#include<iostream>
#include<string>
#include<map>
using namespace std;
void main()
{
string input;
getline(cin,input);
map<char,int> mymap;
mymap[input[0]]=1;
int i,chk=0;
int count=1;
int max=0;
for(i=1;i<input.length();i++)
{
if(input[i]==input[chk])
count++;
else if(mymap.find(input[chk])==mymap.end())
{
mymap[input[chk]]=count;
chk=i;
if(count>max)
max=count;
count=1;
}
else if(count>mymap[input[chk]])
{
mymap[input[chk]]=count;
chk=i;
if(count>max)
max=count;
count=1;
}
}
cout<<max;
system("pause");
}
case1: null (return -1)
case2: ""(empty) (return -1)
case3: "aaabbbbbbcddccc" (return 3)
case4: "vfdaaafgggbbb" (same largest block, return start position of first block)
- Kevin February 28, 2013