Algorithms for Coding Interviews in C++/

...

/

Solution: Sparse Search

Solution: Sparse Search

In this review lesson, we give a detailed analysis of the solutions to solve the sparse search problem.

We'll cover the following...

Solution #1: Brute Force

Press + to interact
int searchForString(string array[], int size, string target) {
  for (int i = 0; i < size; i++) {
    if (array[i] == target) {
      return i;
    }
  }
  return -1;
}
int main() {
  int size = 12;
  string array[size] = {"", "educative", "", "", 
                        "",  "hello", "", "learning", 
                        "world", "", "", ""};
  
  string targetArray[2] = {"educative", "learning"};
  
  for(int i = 0; i < 2; i++) {
    cout << targetArray[i] << ": " << searchForString(array, size, targetArray[i]) << endl;
  }
  return 0;
}

In this solution we traverse the entire array of strings and stop only if we find the target string or reach the end of array.

Time Complexity

The time complexity is the time it takes to traverse the entire array, i.e. ...

Access this course and 1400+ top-rated courses and projects.