Find the first substring in C++

Years ago, I interviewed for a summer internship, and I got a coding question along the lines of: "Implement a function that finds a substring within a string. If that substring is found, return the index of the found substring."

I fumbled through the question. Eventually I got a working solution, but it was a clumsy process getting there. Why was such a simple question so difficult to implement on the spot?

In hindsight, I think this is a good interview question for a few reasons. The problem is deceivingly simple; just about anybody is capable of doing this correctly, but it's difficult to do it well and efficiently, especially on the spot. Because the problem is so simple, the focus of evaluation lies in your style and thought process. Do you clutter your code with unnecessary variables? Is your code verbose or terse? How many functions do you compose, and why? Is your style sloppy or bug-prone? I didn't get that particular internship, because my code was definitely sloppy and bug-prone.

I think there's one more aspect of this question that causes applicants to freeze: strings. In C++ and Java, people tend to use the std::string/String classes, which have lots of utility functions built in. In day-to-day programming, you would rarely iterate over a string manually, and you might also avoid using pointers of type char*.

In this particular example, I think it's actually easier to use pointers than integer indices; this way you have fewer local variables to keep track of. To some extent, having fewer variables means fewer opportunities to introduce a bug.

In my version, I like splitting it up into two functions. The primary function simply iterates over the outer string, and searches each substring for the sought string. Heres' the code:

bool matched(char* sought, char* sent){
    //utility function
    while (*sought!='\0'){
        if (*sent=='\0') //sought is longer than sent
            return false;
        if (*sent!=*sought) //The characters don't match
            return false;
        sent++; sought++; //Check next character
    }
    return true;
}

int substring(char* sought, char* sentence){
    //primary function
    char* iter=sentence; //iterate over string
    while (*iter!='\0'){        
        if (matched(sought, iter)){
                return iter-sentence;
        }        
        iter++;
    }
    return -1;
}

As you can see, the pointers can reduce clutter in the code, because they already are indices in an array of characters.

Pallindromes in C++

Sometimes you come across puzzles or interview questions along the lines of "Find the longest palindrome in a string." To be honest, I've never looked for palindromes in my work, but I think it's a good exercise nonetheless. For one thing, the "best practices" strategies can be applied to other problems. For another, the search for symmetric subsets in datasets of all types definitely does come up.

So, we might start this exercise by first writing a function to classify a string as a palindrome or not. A nice way to do this is to start with a pointer at either end of the string, and iterate them inwards, checking the lower and upper characters against each other at each stage.  For example, if the first and last characters are equal, we iterate inwards. If not, we can return "false" immmediately. The following snippet shows this function.

 bool is_pallindrome(string input){  
      int lower=0;  
      int upper=input.length()-1;  
      while (upper>lower){  
           if (input[upper]!=input[lower]) //If we find differing characters, not a pallindrome  
                return false;  
           upper--;  
           lower++;  
      }  
      return true;  
 }  

So now, to find the longest palindrome in a string, we could just iterate over the string, looking at all substrings, and calling is_pallindrome() [notice my typo in the function name]. That sounds pretty straight-forward, but searching all substrings becomes O(N^2), kind of cumbersome.

A nice way to use the is_pallindrome() function is to think about strings that are centered at index i. So, we have a pointer that searches left from i, and a pointer that searches right from i, and we stop iterating when input[lower]!=input[upper]. This is very similar to the is_pallindrome() function.

There's another approach that's more efficient than the above. Sometimes a good way to think about such a problem is to find the desired subset that ends at index i. If I'm searching for a palindrome that ends at index i, I can store the longest palindrome that ended at index i-1. Then I simply have to look at the first index of that palindrome, and the character that precedes it in the input string.

The storage/caching can be implemented with a hashmap, so we store the longest palindrome that ends at each index, and then we can look it up at the next step. This means, each additional step only features two more comparisons. The following snippet implements this approach:

 string longest_pallindrome_map(string input){  
      map<int, string> pal; //hashmap from index to longest pallindrome that *ends* at index  
      int max_length=0; int max_index=0;  
      for (int i=0; i<input.size(); i++){  
           int prev_index=i-pal[i-1].length()-1;            
           if (pal[i-1][0]==input[i]) //Looking for consecutive duplicate letters  
                pal[i]=pal[i-1]+input[i];            
           else if (input[i]==input[prev_index])  
                pal[i]=input[prev_index]+pal[i-1]+input[i]; //Looking at the character prior to previous pallindrome  
           else  
                pal[i]=string(input.begin()+i, input.begin()+i+1); //Longest pallindrome is current character  
   
           if (pal[i].length()>max_length){  
                max_index=i;  
                max_length=pal[i].length();            
           }            
      }  
      return pal[max_index];  
 }  

This is actually quite a bit more efficient in the searching, more like pseudo-linear instead of quadratic search. [Again notice my mispelling of palindrome.]  The only thing is, we are storing a bunch of strings in this hashmap. We don't actually need to do this.

Instead, we can just store the indices or pointers that begin the palindromes that ends at each index in the input string. The following function does this.

 string longest_pallindrome(string input){       
      map<int, int> pal; //hashmap from current index, to the begin-index of the longest pallindrome that *ends* here  
      int max_length=0;  
      int max_ind=0;  
      for (int i=0; i<input.size(); i++){                           
           int prev_index=pal[i-1];                                
           if (input[i]==input[prev_index]){ //Looking for consecutive duplicate characters  
                pal[i]=prev_index;  
           }  
           else if (input[i]==input[prev_index-1]) //Looking at the index prior to the last pallindrome  
                pal[i]=prev_index-1;  
           else  
                pal[i]=i; //Longest pallindrome is simply the current character  
           if ((i-pal[i])>max_length){ //Finding the longest one along the way  
                max_ind=i;  
                max_length=i-pal[i];  
           }                           
      }            
      return string(input.begin()+pal[max_ind], input.begin()+max_ind+1);  
 }  

So now we have, via dynamic programming, a pseudo-linear search, in that we basically have a linear search over the input string, but we have to store O(N) indices.

Did I really need the hashmap? Not necessarily; I could have used a regular old array, and had some code to check_bounds. On the other hand, the hashmap approach is generalizable to other problems, where the key values might not be simple ordinal numbers.

Reversing C-Style Strings With Pointers

It's a common interview question to ask an applicant to reverse a c-style string, without using string utility functions. In practice, this is something you almost never do, as modern programming languages have nice, safe string classes and interfaces, most likely complete with their own string::reverse() methods.

However, the test has some value. Depending on how the applicant approaches the task, you can gauge his comfort level with pointers. You can get a feel for the applicant's efficiency with memory and operations. Do they reverse the string in place, or allocate new memory?

In particular, swapping the values of two variables, is an interesting sub-test. Can the applicant do this correctly? How do they choose to do it? They can do it in a separate function, with pointers, with references, etc.

Finally, testing. Does the applicant simply write an answer and say "tada"? Or do they try to walk through the code and test what it does, maybe catching mistakes or corner-cases?

As long as the applicant can correctly complete the task, there are no wrong answers. This test really elucidates their style and thought process.

Even though a person might scoff at such a "trivial" test that "doesn't prove anything," it turns out that the test is not so trivial for most programmers. Notably, most applicants cannot correctly complete this task the first time.

Now to the code:

1:  void reverse_str(char* str){  
2:       //Receive a c-style string, meaning a pointer to an array of type char,  
3:       //Reverse in place  
4:       char* lower=str;  
5:       char* upper=lower;            
6:       while (*upper!='\0')     //Searching for the end of a null-terminated string       
7:            upper++;       
8:       upper--;          //Decrement it; we want the last non-null element  
9:       while (upper>lower){       
10:            char temp=*lower;  
11:            *lower=*upper;  
12:            *upper=temp;                                          
13:            upper--;  
14:            lower++;  
15:       }  
16:  }  

In this example, I've used pointers. To find the length of the string, I iterate the pointer [upper] until I find the null-character. I then decrement this pointer, to the last non-null character.

Then, I swap the values of the lower and upper pointers, incrementing the lower and decrementing the upper, until they meet in the middle. And that's it.

If I wanted to be a little more elegant with my swapping, I might write a separate function to swap the values of the pointers. How might I do that?

1:  template<class T>  
2:  void swap(T* a, T* b){  
3:       //Swap the values of two pointers  
4:       T temp=*a;  
5:       *a=*b;  
6:       *b=temp;  
7:  }  

In this case, I've chosen to swap using pointers. So, lines 10-12 in reverse_str() would change to:

1:  swap(lower,upper);  

One other option could be to swap using references. It's actually pretty important that an applicant understands references in C++, as this is a common and integral feature of the language. [Maybe I'll do a follow-up entry on this at some point]. Here's a swap with references:

1:  template<class T>  
2:  void swap(T& a, T& b){  
3:       //Swap the values of two variables  
4:       T temp=a;  
5:       a=b;  
6:       b=temp;  
7:  }  

In this case, lines 10-12 of reverse_str() would need the pointers to be dereferenced:

1:  swap(*lower,*upper);  

So yeah, there you go. There are myriads of other ways to approach this problem. For such a seemingly simple task, you get a lot of mileage and information about a software engineer.

Binary Search With Pointers, C++

Today I'm posting my version of binary search, using pointers in C++. Binary search is a fundamental algorithm, which searches for an element in a sorted array. It is considered the mother of all divide-and-conquer algorithms, and executes in log(N) time, where N is the size of the array. The log is taken with respect to base 2 [binary].

Implementing Binary Search with pointers is a nice exercise that brings together a few concepts.

1. While binary search is an important algorithm from a conceptual standpoint, it's also highly practical and has come up in my research and work. Consider captured data that is indexed by its timestamp, e.g.

                timestamp :  value 1, value 2,....value N
             
The most efficient way to search for the values at a particular timestamp is binary search. In reality, we may want the nearest timestamp to a given reference, but that's a minor adjustment to the algorithm.

2. Implementing binary search with pointers helps to reinforce understanding of pointers, a concept which tends to trip up many C++ programmers.

3. Despite the fact that binary search is a fundamental algorithm, very few job applicants are able to code it correctly on a whiteboard. In short, it's good practice.

In our example, we initialize an array with random elements, then sort it. First we demonstrate how we find an element in the array. Second, we demonstrate how the function behaves when we search for an unknown element. Now, to the code:

 #include <iostream> //For std::cout  
 #include <algorithm> //For std::sort  
 #include <stdlib.h> //For srand, rand   
 #include <time.h>  //For time   
   
 template<class T> //template class means we can accept arguments of different classes: int, float, double, etc.  
 int binarysearch(T* arr /*pointer to beginning of array*/, T* low, T* high, T searchkey /*seeking this value in array*/){  
      int index=-1; //Default value, if we don't find searchkey  
      if (*low>*high) //Double-checking that the array's actually sorted  
           return index;  
      if (low>high) //At this point, we've searched the whole array  
           return index;  
   
      T* mid=(high-low)/2+low; //The array index midway between high and low  
      if (*mid==searchkey)   //We've found the searchkey  
           return mid-arr;  
      if (searchkey<*mid)  
           return binarysearch(arr,low,mid-1,searchkey); //Recursive call to search the lower half of the array  
      else if (searchkey>*mid)  
           return binarysearch(arr,mid+1,high,searchkey); //Recursive call to search the upper half of the array  
   
      return index;  
 }  
   
 int main(int argc, char* argv[]){  
      //Using srand to initialize rand() with time()  
      srand (time(NULL));  
   
      //Size of our array will be 15  
      int size=15;   
      int* arr=new int [size]; //Note that arr is the array, and is also a pointer. It points to a memory block of 15 integers.  
      for (int i=0; i<size; i++){            
           arr[i]=rand()%100; //Randomly initialize the elements of the array, integers between 0 and 100  
           std::cout<<arr[i]<<",";  
      }  
      std::cout<<"\n";                 
      std::sort(arr,arr+size); //Sort the array  
      for (int i=0; i<size; i++)  
           std::cout<<arr[i]<<",";  
      std::cout<<"\n";  
   
      //Finding element in array.   
      int to_find=arr[rand()%size]; //Choosing an element at random from the array to search using binary search  
      int found_index=binarysearch(arr,arr,arr+size-1,to_find);  
      if (found_index>-1)  
           std::cout<<"Found "<<to_find<<" at location "<<found_index<<"\n\n";  
      else  
           std::cout<<"Couldn't find "<<to_find<<" in array\n\n";  
   
      //Finding unknown element  
      to_find=100; //We initialized the array with elements strictly smaller than 100  
      found_index=binarysearch(arr,arr,arr+size-1,to_find);  
      if (found_index>-1)  
           std::cout<<"Found "<<to_find<<" at location "<<found_index<<"\n";  
      else  
           std::cout<<"Couldn't find "<<to_find<<" in array\n";  
   
      delete [] arr; //Clean up dynamically allocated memory  
      return 0;  
 }