Monday, July 8, 2013

Recursive Interview Questions Tutorial (WIP)


The most important thing to learn is how to think recursively. This allows you to solve a large class of problems relatively simply. It's important to know for job interviews. I had interviewed at Google six months ago and because I botched an interview question that could have been solved recursively, the interviewer told the recruiter I "lacked fundamental understanding of computer science". 

To solve a problem recursively:

1)  Think about how to solve the problem for simple cases (base case). 
2)  Determine how to break down larger cases into smaller instances (recursive decomposition).

Remember that every recursive algorithm has two components: the base case and the recursive decomposition. 

Problem #1 Reverse A String
Base Case:  When the string is the empty string is it the same backwards as it is forwards
Recursive Decomposition: For strings, to shrink the string to make forward progress is the same as solving the problem for substrings of the string, and then combining the sub-solutions.


/* Returns the reverse of the indicated string. */
string reverseString(string line) {
 if (line == "")
  return "";
 else
  return reverseString(line.substr(1)) + line[0];
}

Problem #2 Count Spaces in A String
Base Case:  When the string is empty is cannot have a space so the count of spaces is 0.
Recursive Decomposition: Check character by character by working with substrings of the string, and then sum the counts of the strings. 


/* Returns the count of white spaces in a string*/
int countSpaces(string line){
  if (line.length() == 0)
    return 0;
  else
    return ((isspace(line[0]) ? 1 : 0) + countSpaces(line.substr(1)));
}
Problem #3 Find Last Occurrence of Character in String
Base Case: Well if you are at the end of the string and no characters follow, it must be the last occurrence if there is a match. 
Recursive Decomposition: Start at the end of the string and after each call remove the last character. 


/* Return the index of the last occurence of a character in the string */
int find_last_occurence(string line, char character){
  if (line[line.length()-1] == character)
    return (int)line.length();
  else if(line.length() == 0)
    return -1;
  else
    return find_last_occurence(line.substr(0,line.length()-1), character);
}

Spark Notes Article That I Thought Was Useful: http://www.sparknotes.com/cs/recursion/whatisrecursion/section2.rhtml

Problem #4 Traversing a Binary Tree. Inorder, preorder, postorder.

Problem #5 Print all subsets of a set. 

Problem #6 Print all alphanumeric combinations of a phone number. 

These are the slides that I found on the Stanford Engineering Everywhere site that I found useful to learn more about recursion. 
























7 comments :

Kix Mr said...

Tks very much for your post.

Avoid surprises — interviews need preparation. Some questions come up time and time again — usually about you, your experience and the job itself. We've gathered together the most common questions so you can get your preparation off to a flying start.

You also find all interview questions at link at the end of this post.

Source: Interview Questions & Answers:

Best rgs

packers And Movers Bangalore said...

An excellent information provided thanks for all the information i must say great efforts made by you. thanks a lot for all the information you provided.
Packers And Movers Bangalore

Packers Movers Hyderabad said...

i really like your blog, thanks for share...
please visit are website..

Packers And Movers Hyderabad charges

Packers Movers Hyderabad said...

nice post:
Packers And Movers Bangalore to hyderabad

Packers Movers Pune said...

An excellent information provided thanks for all the information i must say great efforts made by you. thanks a lot for all the information you provided.
Packers And Movers Pune

Packers Movers Kolkata said...

Thanks on your marvelous posting! I really enjoyed reading it, you’re a great author.Please visit here:
Packers and Movers Kolkata charges

Packers Movers Jaipur said...

"Enjoyed every bit of your blog article.Really looking forward to read more. Really Cool."
Packers And Movers Jaipur charges