Microsoft Interview Question for Software Engineer in Tests


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

Similar to "find min sub-string in string a that containing all characters of string b". We assume that we use ASCII:
1. Use bool[256] list to record the occurrence of each character of current sub-string.
2. Use int left=0, right =0 to record the edge of current sub-string and int max to record the max length of sub-string with consecutive characters.
3.

for(;right<s.length;right++)
{
    if list[s[right]] is false (which means this character is not in current sub-string)
        list[s[right]]=true; //add this character to current sub-string and expand the right edge
    else
        Calculate the max number of consecutive trues in list and update max variable;
        while(s[left]!=s[right]) //Update the left edge of current sub-string until s[left]=s[right]
            list[s[left++]]=false;
        left++;
}

- g233007 March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I might be missing something, but I don't think the code will work for 'acb' string, it'll report the 'cb' part of it. No? Also s[left]!=s[right] - do we assume that all symbols are unique? or this should read while left != right?
Could you please add details to the code, so it's easier to understand? Thanks!

- just_passing_through March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Sorry that my last posting has something wrong, it needs and int[] list to record the occurrence of each chars. Here is logic:

First we must understand the question. 'the biggest string that has all consecutive characters' implies in this sub-string every character can only appear once and all those characters must be consecutive.
Assuming we have s="acbefcdfg".
At first left=0, right=0 and max=0. Now we are moving right edge of the current sub-string.
(a)cbefcdfg left=0, right=0, list: a(0)
(ac)befcdfg left=0, right=1, list: a(0) c(1)
(acb)efcdfg left=0, right=2, list: a(0) b(2) c(1)
(acbe)fcdfg left=0, right=3, list: a(0) b(2) c(1) e(3)
(acbef)cdfg left=0, right=4, list: a(0) b(2) c(1) e(3) f(4)
(acbefc)dfg left=0, right=5, list: a(0) b(2) c(1) e(3) f(4)

When we set right=5 and find s[5]='c' has already appeared which means the current sub-string has already contained 'c'. Thus the biggest sub-string start with left=0 can only be end with as long as 4 (which is "acbef"). Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number. For this case:
We find first consecutive block a(0) b(2) c(1) and check if numbers in this group is consecutive. To do this we only need to record the min and max in this block and check if max-min+1==length of block. Here we find 2-0+1==3 so max=3.
Continue and we will find another block e(3) f(4) and also 4-3+1==2, but 2<max=3 so the biggest sub-string is acb and length is 3.

So we find the biggest sub-string acb. We update max=3.
Since in "acbefc" (left=0, right=5) 'c' has appeared twice, we can say that all sub-strings with left>0&&left<=index of first 'c'&&right<=5 are illegal (because they all have two 'c'). So we can directly update the left to be the next index of first 'c' which is 2 in this case, letting the current sub-string to be 'befc'. We also update list['c']=5. Now let's start expanding new current sub-string again:
ac(befc)dfg left=2, right=5, list: b(2) c(5) e(3) f(4)
ac(befcd)fg left=2, right=6, list: b(2) c(5) d(6) e(3) f(4)
ac(befcdf)g left=2, right=7, list: b(2) c(5) d(6) e(3) f(4)
We find 'f' twice again. Do the routine as before and you will find the biggest in this case is 'befcd' itself. update max=5 and left=5, right=7. Start over:
acbef(cdf)g left=5, right=7, list: c(5) d(6) f(7)
acbef(cdfg) left=5, right=8, list: c(5) d(6) f(7)g(8)
Now the right comes to the end of s and we need to check again. In this case the biggest sub-string is either 'cd' or 'fg'.

In the end we find the length of biggest string with only consecutive chars is max=5. If the method needs to return the sub-string you just need another two integers maxLeft and maxRight to record the two edge of sub-string.

- g233007 March 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now we can find the biggest string in acbef with all consecutive chars:
To find the biggest sub-string with consecutive chars in "acbef" we just need to check the list and find the biggest block with consecutive number.

you have written an amazing solution, but there is one thing that is still unclear. How exactly did you find the biggest block with consecutive numbers ? It smells of recursion.

An excellent explanation barring this :)

- DCE Coder March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You need to find the biggest string or buggest sub string?

- Anonymous March 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We need to find bigest substring
eg::-
abfdegstz
Here the continous jumbled word strings are
ab
fdeg--->(defg)
st

So ans is fdeg as all elements in this string are sorted

- tarun March 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

consider each char in the original string as starting char of the (potentially)longest sub-string containing consecutive chars. Use an array of size 256 and index the chars from the current substring to see if the chars are consecutive. As we index each char into the array update the count of current max consecutive chars seen so far.

- Anonymous March 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that the consecutive string cannot have repeated characters, would this work ?

1. Assume every char can be a part of the longest jumbled consecutive string.
2. Consider a hash map or an array to store 26 alphabets
3. Start with the first char, hast it and make the position, continue hashing until you hit a collision ( basically we have hit a repeated char )
4. Scan the hash map to check if we have a consecutive string. If so store the count and the position of the char. Clear the hash map
5. Repeat Steps 3-4 with all the subsequent chars in the string, replacing the count and position with the longest string found so far.

This is a O(n2) at the very min, assuming we use we can come up with a constant time algorithm to store and count the consecutive chars.

- Anonymous March 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am sorry I am a newbie I didn't got your solution. I tried to scan through your algorithm for a sample string say zkabz.
so the answer here should be ab, but your algo suggests it to be a null string. Please can you explain your algo with a help of an example. also consider example like "azb"

--Hitesh

- hitesh.p.kapoor March 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right Hitesh. I misunderstood the problem. The solution seems pretty simple. I think user 'g233007 ' has given the right solution.

- Anonymous March 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static char[] FindLargestSubArray(char[] input)
        {
            if (input == null || input.Length < 2) return input;
            var len = new int[input.Length];
            int maxLen = 0, maxLenIndex = -1;
            for (int i = input.Length - 1; i >= 0; --i)
            {
                var max = 0;
                for (int j = i + 1; j < input.Length; j++)
                {
                    if (input[j] > input[i] && len[j] > max)
                        max = len[j];
                }
                len[i] = ++max;
                if (max > maxLen)
                {
                    maxLen = max;
                    maxLenIndex = i;
                }
            }
            var runner = 0;
            var output = new char[maxLen];
            for (int j = maxLenIndex; j < len.Length && maxLen > 0; j++)
            {
                if(len[j]==maxLen && input[j] >= input[maxLenIndex])
                {
                    output[runner++] = input[j];
                    maxLen--;
                    maxLenIndex = j;
                }
            }
            return output;
        }

- Artur March 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Seems I did not understand the problem right

- Artur March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

char *max_str(char *str)
{
int len=strlen(str);
int max=0,sub_left,sub_right;
int str_start=0,str_end=0,read_pos=0;
char *lookup=(char *)malloc(sizeof(char)*26); //assume string only contains lower case letters
if (!lookup)
return FALSE;
for (int i=0;i<26;i++)
lookup[i]=0;
while(read_pos<len)
{ while (lookup(str[read_pos]-'a')==0&&read_pos<len){ //find first replicate letters in string
lookup(str[read_pos]-'a')=1;
read_pos++;
}
str_end=read_pos-1;
for (int block_len=str_end-str_start+1;block_len>0;block_len--) // if string length equals the difference
if (max(str(str_start,str_end))-min(sub(str_start,str_end))+1==block_len) // between max letter and min letter in the string
{ // then it is a consecutive sub string
if (max<block_len)
{
sub_left=str_start;sub_righ=str_end; //store the start point and end point of possible
} // maximun continuous substring
str_start+=block_len; // advance to next position after already found consecutive string
break;
}
read_pos=str_start;
for (int i=0;i<26;i++) //clear the lookup table for finding the next replicate letter of start position
lookup[i]=0;
}
free(lookup);
char *sub=(char *)malloc(sizeof(char)*(sub_right-sub_left+1));
while(sub_left<=sub_right)
sub[i++]=str[sub_left++];
sub[i]='0\';
return sub;
}


1. start from the begining of array to find the first duplicate letter
2. find the max possible substring of the first letter
3. advance the start point to the position after the last letter of substing
4. continue with step 1


Example:
"acbefcadfghekop"

1. get the string "acbef"
2. find the max substring with the starting letter 'a' :"acb"
3. start from letter 'e', get the string "efcadfgh"
4. continue the step until reach the end of string.

- raj March 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, I'm not sure this implementation will find 'acb' in, say 'sacbrktsbf'. Will it? the 'str()' and 'sub()' calls are undefined, so I don't think I can check the correctness really.
Liked the idea of the property of max(substr) - min(substr) + 1 == len(substr) though.

- just_passing_through March 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's what I got. Does not rely on characters uniqueness as well:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class substr_range {
    char b, e;
    size_t idx;
public:
    substr_range(char c, size_t idx_) : b(c), e(c), idx(idx_) {}
    // returns true, if char was added and false if new range needs to be created
    bool add_char(char c) {
        if(c == b -  1) {
            b = c;
            return true;
        } else if(c == e + 1) {
            e = c;
            return true;
        } else {
            return false;
        }
    }
    // returns true, if two substring ranges were joined and false otherwise
    // the first substring range will have it's range updated and the second one can be ignored
    bool join(const substr_range& other) {
        if(other.b == e + 1) {
            e = other.e;
            return true;
        } else if(other.e == b - 1) {
            b = other.b;
            return true;
        } else {
            return false;
        }
    }

    size_t index() const {return idx;}
    size_t len() const {return e - b + 1;}
};

int main() {
    char str[] = "dabccdfeightdghiv", *s = str;
    vector<substr_range> ranges(1, substr_range(*s, 0));

    while(*(++s)) {
        if(!ranges.back().add_char(*s)) {
            ranges.push_back(substr_range(*s, s - str));
        }
    }

    if(ranges.size() == 1) {
        cout << "hooray, the string's characters are all consecutive" << str;
        return 0;
    }

    bool joined = false;
    do {
        joined = false;
        for(auto i = begin(ranges); i < end(ranges) - 1; ++i) {
            if(i->join(*(i + 1))) {
                ranges.erase(i + 1);
                joined = true;
            }
        }
    } while(joined);

    auto i = begin(ranges);
    size_t maxlen(i->len()), idx(i->index());
    ++i;
    for(; i < end(ranges); ++i) {
        if(i->len() > maxlen) {
            maxlen = i->len();
            idx = i->index();
        }
    }

    cout << "found a substring with " << maxlen << " consecutive characters" << endl
        << "the substring is " << string(str + idx, str + idx + maxlen) << endl;

    return 0;
}

- just_passing_through March 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry can you explain your idea in words, that would be more helpful to read your code

- Anonymous March 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sure, the idea is simple really, you go through the string and you keep track of all substrings, that appear to be consisting of consecutive symbols. For example, say we have string "dabccdfeightdghiv". The algorithm first goes and builds a set of subranges (substrings, that have consecutive characters). So the string "dabccdfeightdghiv" is divided into "d", "abc", "cd", "fe", "i", "gh", "t", "d", "ghi", "v". Now that we have those substrings as subranges we know the min and max character for each substring and we can check if neighboring subranges could be joined. So we go through list of "d", "abc", "cd", "fe", "i", "gh", "t", "d", "ghi", "v" and we join the subranges that would represent a consecutive string. And the list would transform into "dabc", "cdef", "igh", "t", "d", "ghi", "v" and we continue joining neigboring subranges until there's at least one pair that could be joined. This is how you eventually arrive to "cdef" joining with "igh". That's the last pair to be joined, so the process stops after that and the last step is just going through the list of subranges in order to find one with maximum length. Looks plausible?

- just_passing_through March 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if i understood your algo correctly ..
it is being failed on this input:
input : a b e f i j c d g h
step 1:ab ef ij cd gh
it won't reduce after that although the correct answer is
abcdefghij

- Anonymous March 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You're right! Thanks for being thorough :). So I failed to come up with an algorithm with a 'decent' complexity, all I can think of now is extending raj's (see above) approach for all possible substrings really. (The code example below does not work for strings with repetitive chars, please see raj's code for how to streamline this (trivial)).

struct consec_substr {
    char const *start;
    size_t len;
    consec_substr(char const * const start_, size_t const len_) : start(start_), len(len_) {}
};

void update_results_if_better(consec_substr &final_result, const consec_substr& curr_result) {
    if(curr_result.len > final_result.len) {
        final_result = curr_result;
    }
}

void find_consec_substring2(char const * const str) {
    const size_t len = strlen(str);
    consec_substr final_result(str, 0);

    for(size_t start = 0; start < len - 1; ++start) {
        // if remaining substring is smaller than the result already obtained, no need to look further
        if(len - start <= final_result.len) break;

        for(size_t end = len; end > start; --end) {

            unsigned char maxC = str[start], minC = str[start];

            for(size_t i = start; i < end; ++i) {
                if(str[i] > maxC) maxC = str[i];
                if(str[i] < minC) minC = str[i];
            }

            if(maxC - minC == end - start - 1) {
                update_results_if_better(final_result, consec_substr(str + start, end - start));
                break;
            }
        }
    }

    cout << string(str) << " - " << string(final_result.start, final_result.start + final_result.len) << endl;
}

int main() {
    char str[] = "dabcfeightv";
    char str2[] = "abefijcdgh";
    char str3[] = "bdcapfgehikjvml";
    char str4[] = "dbapclemfojnhkig";
    char str5[] = "clebajnkd";

    find_consec_substring2(str);
    find_consec_substring2(str2);
    find_consec_substring2(str3);
    find_consec_substring2(str4);
    find_consec_substring2(str5);

    return 0;
}

- just_passing_through March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Interesting to see no one has given time complexity for their algorithms. The way I solved this was using "Math".

1. Be it whatever way the first "n" distinct numbers are arranged, the sum of these numbers = n*(n+1)/2.
2. Use two loops - 1 to go, over each position in the string and the 2nd for variable length.
3. Find the localized minimum in the loop for the given range.
4. Do the Math - check and set your flags

I wrote a program for this but I do not want to distribute code. This algorithm runs in O(n^2) and can be optimized a little. Brute force would take O(n^3).

Any better algo's? I was also thinking of doing something XOR's but gave up.

- RiTZ April 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please explain the use of two loops clearly. Or may be you can do a dryrun of your algo with any suitable input.

- bytecode April 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the pseudo code/idea.
I have a function called normalize which basically takes the current character and finds the difference with the current minimum. So, for example if the current min is "b" and current character is "d", normalize would return 2.

This code is written in C# and must work out of the box.

//Initialize the currentMax
int currentMax = int.MinValue;
//Pointers to left and right if we find continuous string
int left=-1, right=-1;
//The string to store the final result
String finalResult;
char[] str = value.ToLower().ToCharArray();

// THE MAIN LOGIC - FOR EACH CHAR IN THE STRING
for (int i = 0; i < str.Length && (str.Length - i > currentMax); i++)
{
//Find the min and store in localMin
    char localMin = str[i];
//At the same time find the sum
    int localSum = normalize(str[i], localMin);

//Use a hashSet to keep track of what characters have been visited
    HashSet<char> visited = new HashSet<char>();
    visited.Add(str[i]);

    for (int j = i + 1; j < str.Length; j++)
    {
//The Math part that I was talking about - for "n" numbers sum is n*(n+1)/2
        int n = j - i + 1;

        if(visited.Contains(str[j]))
            break;
        else
        {
            visited.Add(str[j]);
        }
                    
        if (localMin > str[j])
        {
            //Find the difference
            int diff = localMin - str[j];
            localMin = str[j];
//Add the difference (j-i) times
//Why are we doing this? Fox example - If our localMin was 3 and NOW our localMin changed to 1, then we need to add (j-i) times the difference to sum
            localSum += ((j - i)*diff);
        }
        localSum += normalize(str[j], localMin);
                    
        if (localSum == (n * (n + 1)) / 2)
        {
            //Means we have a match
            if (currentMax < (j - i + 1))
            {
                currentMax = j - i + 1;
                left = i;
                right = j;
            }
        }
    }
}

if (currentMax == int.MinValue)
    return "";

return new String(str,left,right-left+1);

Let me know if you need more clarification. I hope this gives a good idea of how to deal with the problem. Also, please let me know if you have any other better solutions.

- RiTZ April 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I also ran this through a bunch of test cases and it works. Please let me know if you find something wrong so that I can correct this algo or make it more efficient.

- RiTZ April 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey, so here was what I came up with. This was written in C#

private string LongestConsecutiveSubString(string aString)
		{
			if (aString == null)
			{
				return null;
			}
			bool[] hits = new bool[256];
			// Currently the first character alone as a substring of aString is currently the largest continuous substring
			int longestConsecutiveCount = 1;
			int startIndex = 0;
			// Starting point of substring
			for (int subStringStart = 0; subStringStart < aString.Length - 1; subStringStart++)
			{
				// Ending point of substring
				for (int subStringEnd = subStringStart; subStringEnd < aString.Length; subStringEnd++)
				{
					// If there is a repeated character, break out of loop
					if (hits[aString[subStringEnd]])
					{
						break;
					}
					// Continually build up hit array hits within inner loop
					hits[aString[subStringEnd]] = true;
					int tempHitIndexStart = aString[subStringStart];
					int tempHitIndexEnd = aString[subStringStart];
					// Get the starting position of the potential continuous substring
					while (hits[tempHitIndexStart] && tempHitIndexStart >= 0)
					{
						tempHitIndexStart--;
					}
					tempHitIndexStart++;
					// Get the ending position of the potential continuous substring
					while (hits[tempHitIndexEnd] && tempHitIndexEnd < hits.Length)
					{
						tempHitIndexEnd++;
					}
					// If the substring is larger than the current longest substring, and the hit array is continuous
					if ((tempHitIndexEnd - tempHitIndexStart) > longestConsecutiveCount && IsConsecutive(hits, tempHitIndexStart, tempHitIndexEnd))
					{
						longestConsecutiveCount = tempHitIndexEnd - tempHitIndexStart;
						startIndex = subStringStart;
					}
				}
				// Reset hits array
				for (int hit = 0; hit < hits.Length; hit++)
				{
					hits[hit] = false;
				}
			}
			return aString.Substring(startIndex, longestConsecutiveCount);
		}

		// Check to see if hit array is continuous excluding the partial array of startPositionExclude to endPositionExclude
		// The partial array is the potential continuous char array
		private bool IsConsecutive(bool[] hitArray, int startPositionExclude, int endPositionExclude)
		{
			for (int hit = 0; hit < startPositionExclude; hit++)
			{
				if (hitArray[hit])
				{
					return false;
				}
			}
			for (int hit = endPositionExclude + 1; hit < hitArray.Length; hit++)
			{
				if (hitArray[hit])
				{
					return false;
				}
			}
			return true;
		}

- Neil April 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Neil, can you explain your algo by words please.

- RiTZ April 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Got it :)

- RiTZ April 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

cant we first sort this and start looking for max consecutive strings.
Complexity will be O(nlogn) for sorting and 1 loop for finding the max consecutive strings.
total complexity = O(nlogn)

I am only pasting the code for finding the max consecutive string considering the string is in sorted form after applying suitable sorting algorithm takes O(nlogn) time complexity.

void longRepeatConscString(char *str)
{
     int i, count = 0, start = 0, nextstart = 0;
     for(i = 1; i <= strlen(str); i++)
     {
           if(str[i] != str[i - 1] + 1)
           {   
                if((i - nextstart - 1) > count)
                {
                      
                      count = i - nextstart - 1;
                      start = nextstart;
                      nextstart = i;
                }
           }
     }
     for(i = start; i <= start + count; i++)
           printf("%c", str[i]);
           
     printf("\n\n");
}

- akashj April 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

some changes in the code to include no consecutive strings also.

void longRepeatConscString(char *str)
{
     int i, count = 0, start = 0, nextstart = 0;
     for(i = 1; i <= strlen(str); i++)
     {
           if(str[i] != str[i - 1] + 1)
           {   
                if((i - nextstart - 1) > count)
                {
                      
                      count = i - nextstart - 1;
                      start = nextstart;
                      nextstart = i;
                }
                else
                {
                    nextstart = i;
                }
           }
     }
     if(count)
              for(i = start; i <= start + count; i++)
                    printf("%c", str[i]);
     else
         printf("No consecutive substring found \n");
           
     printf("\n\n");
}

- akashj April 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@RiTZ...can u plz write your code in c or c++ or jst paste the dry run..........i cant understand the c#

- Anonymous May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a java code for those who are interested

public class MaxContiguousPattern 
{
	String str;
	int length;
	int startindex = 0;
	int endindex = 0;
	int maxlength = 0;
		
	public MaxContiguousPattern(String str)
	{
		this.str = str;
		this.length = str.length();
	}
	
	public String findString()
	{		
		String st2;
		for(int i=0; i<length;i++)
		{
			for(int j = i+1 ; j<=length;j++)
			{
				st2 = str.substring(i, j);
				if (isContiguous(st2))
				{
					if( (j - i) > maxlength )
					{
						maxlength = j - i;
						startindex = i;
						endindex = j;
					}					
				}				
			}
		}		
		
		return str.substring(startindex , endindex);		
	}
		
	public boolean isContiguous(String str2)
	{
		char [] x = sortChars(str2.toCharArray());
		int len = x.length;
		
		for(int i=0; i < len-1;i++ )
		{
			if(x[i+1] - x[i] > 1)
			{
				return false;
			}
		}
		return true;
	}
	
	public char [] sortChars(char [] toSort)
	{
		int len = toSort.length;
		char buffer;
		for(int i=0;i<len;i++)
		{
			for(int j=i+1;j<len;j++)
			{
				if (toSort[i] > toSort[j])
				{
					buffer = toSort[i];
					toSort[i] = toSort[j];
					toSort[j] = buffer;
				}
			}
		}		
		return toSort;
	}
	
	
}

- Shrikant June 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you put down whats the algo?

- Srishti June 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I request everyone to write algorithm rather than code. It's much easier and faster to read.
Here is my proposed solution. It's O(n*n) time. O(n*n) space.

Let in any substring, the minimum value be n, maximum value be m, sum of all values be s.
For the condition to be true in this substring the following condition should be satisfied
s = m * ( m + 1 ) / 2 - ( n - 1) * n / 2

Let us find the m, n and s for each possible substring
We can formulate a dynamic programming to calculate this
I would leave it as an exercise to calculare these.
This can be done O(n*n)
s[i,j] = sum of all values in from char i to char j ( i <= j )
m[i,j] = max of all values in from char i to char j ( i <= j )
n[i,j] = min of all values in from char i to char j ( i <= j )

Define two variables iMaxRange, jMaxRange

Loop through each value in our 2-D arrays to check if condition is satisfied. ( s = m * ( m + 1 ) / 2 - ( n - 1) * n / 2 )

If condition is satisfied
{
if( j - i > jMaxRange - iMaxRange)
{
iMaxRange = i
jMaxRange = j
}
}

At the end iMaxRange and jMaxRange should give you the answer.

Please let me know if this is not satisfiying any scenario.

- DarkKnight July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Build an index array for each character, say if index[a]=3,9,10 then character 'a' is present as 3rd, 9th and 10th character in the given string.
2) Now sort the given string
3) Scan the given string and whenever you encounter a sequence then use recursion to see even if their indexes can be consecutive. If yes then keep track of the largest interval.

Recursive procedure to check if indexes are consecutive:
1) Use recursion to build various combination of indexes of each character. Say we are looking at indices of characters 'a','b','c','d', then we build a set of 4 indices where each element is taken from index[a], index[b], index[c], index[d]
2) Now sort this set. If it contains consecutive numbers (indices) then return true

- IntwPrep December 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i guess a new approach would be to take character by character from string and set a bit vector (size 26) index to 1 for every character untill there is a repitition of charac in string ......... and as soon as a repition is found do two things :a) print the charac corresponding to which bit vector has consec 1
b) reset entire bit vector to 0

complexity - O(n^2)
code is as follows :

#include<stdio.h>
int main(){
  char a[]="hllsacefgdbdf";
  int no[26];
  int i=0;
  int j,t;
  for(j=0;j<26;j++)
  no[j]=0;
  while(i!=13)
  {  printf("\n");;
    if(no[a[i]-97]==0)
    no[a[i]-97]=1;
    else{
      for(j=0;j<26;j=j+2){
        if(no[j]==1 && no[j+1]==1)
        {printf("%c%c",(j+97),(j+1)+97);
    t=j+1;
    }
      }
      printf("%c",(t+1+97));
      printf("\n");
      for(j=0;j<26;j++)
      no[j]=0;
    }
    i+=1;
  }
  printf("\n");
  return 0;
}

- healer0994 June 03, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More