Wednesday, April 4, 2012

A trivial problem

I recently had a job interview for a company in NYC. The interview seemed to have gone really well, however I kinda choked on a very simple programming question. If I think about it now I feel like I should have done much better. The question was to write a function that given a string would return the character corresponding to the longest sub-string. E.g., the character corresponding to the longest sub-string in "aabbbakk" is 'b', since the longest sub-string is "bbb". The solution is assumed to be unique, i.e., "aabbbcc" is legal, but "aaabbbxxx" is not. Trivial problem, somehow tricky to solve when under pressure. Here's a simple solution in C:
 #include <cstring>  
 char findCharFromMaximumSubstring(char *s){  
      int stringLength = strlen(s);  
      char previous = ' ', maxChar = ' ';  
      int length = 0, maxLength = 0;  
      for(int i=0; i<stringLength; i++){  
           char current = s[i];  
           if (previous == current) {  
                // still working on the same substring  
           } else {  
                // new substring, length is 1  
                length = 1;  
                // store the previous character for the next iteration  
                previous = current;  
           // check if we have found a longer substring and store its length  
           // and the corresponding character  
           if (length > maxLength) {  
                maxLength = length;  
                maxChar = current;  
      return maxChar;  

No comments:

Post a Comment