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. 
























29 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

Packers Movers Chennai 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 Chennai

rdsraftaar said...

QuickBooks Support Phone Number
QuickBooks Technical Support Phone Number
QuickBooks Tech Support Phone Number
QuickBooks 24/7 Support Phone Number
QuickBooks PRO Support Phone Number
QuickBooks Support Number

Ankit Kumar said...

QuickBooks Support Phone Number
QuickBooks Technical Support Phone Number
QuickBooks Tech Support Phone Number
QuickBooks 24/7 Support Phone Number
QuickBooks PRO Support Phone Number
QuickBooks Support Number

Mathew said...

QuickBooks Support Phone Number

QuickBooks Technical Support Phone Number

QuickBooks 24/7 Support Phone Number

QuickBooks PRO Support Phone Number

QuickBooks Support Number

QuickBooks Tech Support Phone Number

rdsraftaar said...

QuickBooks Support Phone Number

QuickBooks Tech Support Phone Number

QuickBooks Payroll Support Phone Number

QuickBooks Payroll Tech Support Phone Number

QuickBooks Payroll Phone Number

Ankit Kumar said...

QuickBooks Support Phone Number
QuickBooks 24/7 Support Phone Number
QuickBooks Technical Support Phone Number
QuickBooks Tech Support Phone Number
QuickBooks Support Number

Mathew said...

Quickbooks made accounting easy for beginners and provide a helping hand to complete the task before the time for standard users. It is an easy way to navigate the financial reports as a result of getting to know about the business transactions and cash in and outflows.


Quickbooks Support Phone Number

QuickBooks Support Number

QuickBooks Tech Support Phone Number

QuickBooks Technical Support Phone Number

QuickBooks Customer Service Phone Number

Mathew said...

Are You Facing Problem in your Quickbooks? Call us today at QuickBooks Tech Support Phone Number +1-888-396-0208 for QuickBooks upgrades, updates, company file repair and data recovery services. 24 hours service delivery guaranteed. QuickBooks Technical Support Call use for QuickBooks error resolution and any kind of technical support. Call us Now.

Ankit Kumar said...

That was a great read. I really like your writing style and how you explain certain things. I will be back to read more from you.We also provide Technical Support for QuickBooks Payroll , if you face any problem with your QuickBooks Payroll you can just click here. Or dial 1888-567-1159.

rdsraftaar said...

Were you just searching for Intuit QuickBooks Payroll for Mac ?QuickBooks software for Mac users does not have a built-in payroll service like the Windows version. You need to click on the Payroll link that will direct you to an external website for processing employee checks. As QuickBooks fails to accord built-in method for manually tracking payroll, the employers who wish to track payroll for employees in QuickBooks must subscribe and pay a monthly fee to access the online QuickBooks Payroll for Mac service.

Ankit Kumar said...

QuickBooks Payroll Tech Support Number is a capable programming composed by Intuit. It is utilized for Small and medium size business to keep up records of working representatives bookkeeping data, pay including all the duties and exchanges are finished with them.

Pankaj Ahuja said...

The enterprise solution streamlines all the critical tasks in such a way that you find accounting and financial transactions easier. The software suite keeps track of all information and documents in a single space. And that's why, the enterprise solution is best recommended for small and mid-sized industries. For more Details you can contact QuickBooks Enterprise Support 1888-396-0208.

Robert Elfed said...

Having problems with sending or receiving your W2's ? QuickBooks Support Phone Number.This software can keep the record of all the transactions and produce reports for various needs.
Call on 1888-567-1159 and have a conversation with one of our experts now.

rdsraftaar said...

QuickBooks Technical Support Phone Number Support Phone Number for Technical Support & Customer Service , working 24*7 Just dial ++1800-291-2485 (Toll Free) for any requirement including set-up, purchase , installation , bookkeeping, and many more. Simply Dial and Feel Secure.

Ankit Kumar said...

Presently you can undoubtedly get to any sort of data without much problem to make a report. With the choice of pursuit and channel now you can tweak the reports according to your benefit and preference. New Customers of Quickbooks can Call Quickbook Tech Support Phone Number 1888-396-0208 and get in touch with us .

Pankaj Ahuja said...

QuickBooks Support Phone Number 1888-396-0208 services offer you qualified experts who have a sufficient experience in the relevant field. If you come across an issue with the software, the experts make sure to resolve your issue instantly. They assist in downloading the QuickBooks, setting up and creating the data files of the company in windows and Mac systems.

rdsraftaar said...

To get the customized online answer for all QuickBooks Enterprise Users. Our support benefit is open to Windows and Mac PC clients to settle the issue according to the similarity of their PC framework. It works for Mac and different gadgets utilizing QuickBooks Enterprise however having an issue while utilizing or introducing this product. The Operating System (OS) master group of nerds to determine such issues with finish security and protection.QuickBooks Enterprise Support Phone Number

Mathew said...

POS Support 1800-291-2485 is proposed to influence skilled client to profit and to make customers chipper. It tracks the stock and customer's information and passes on various features to hold them returning. Also, moreover with this product; you can in like manner know customer's necessity for a particular thing and what stamp they get a kick out of the opportunity to shop.

Mathew said...

The Enterprise Support 1800-291-2485 Has Many Professional Technicians Who Are Expert And Provides Instant Solution Of The Problems You Are Facing. Side By Side The Quickbooks Enterprise Support Is Equipped With Many Certified Technicians Who Can Handle All Kind Of Issues Related To Your Quickbooks Issues At The Same Time.

lucky said...


This product can keep the record of the considerable number of exchanges and deliver reports for different requirements. In any case, such profoundly appraised programming can likewise demonstrate the issue however QuickBooks Payroll Phone Number is accessible here.

Unknown said...

We give proficient help and specialized help for QuickBooks clients on QuickBooks Support Number 1800-291-2485. Our group comprise of affirmed QuickBooks ProAdvisors. With the assistance of devoted 24×7 supports framework and superb client benefit, 247 QuickBooks gives your bookkeeping a fix.

Pankaj Ahuja said...

QuickBooks accounting software is one of the most recommended bookkeeping solutions. Though, it is considered as an outstanding software, there are certain occasions where you might come across certain errors that may hamper your work. One such error is QuickBooks License Error. The License error in QuickBooks is also known as the QuickBooks Error 3371 .