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. 
























43 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 .

steve said...


Thanks for share this POST
ارخص اسعار نقل عفش بالرياض

quickb said...


To setup the email feature within QuickBooks When you choose Edit > Preferences > Send Forms > My Preferences, you may not see Outlook as an option for emailing from QuickBooks.to fix the issue call our Outlook Is Not An Option In QuickBooks Send Forms Preferences department and fix the issue by our technical expert team.

Unknown said...

QuickBooks Enterprise version is one of the most powerful versions of all the three, that is, QuickBooks Pro, Enterprise and Enterprise. This version of QuickBooks software was designed keeping the financial needs of businesses having a large team of accounts in mind. Subscriber of QuickBooks Enterprises version Call the Toll-Free Quickbooks Enterprise Support Phone Number Canada 1888-557-6950 to connect with the USA.

Robin Jack said...

I as of late discovered numerous helpful data in your site particularly this web journal page. Among the bunches of remarks on your articles. A debt of gratitude is in order for sharing. HMRC Tax Investigation Accountants

Manish Packers and Movers Pvt Ltd said...

Manish Packers and Movers Pvt Ltd as a Services providing company can make all the difference to your Home Relocation experience. Indore based Company which offers versatile solutions, Right team that easily reduce the stress associated with a Household Shifting, Vehicle Transportation. we help things run smoothly and reduce breakages and offer you seamless, Affordable, Reliable Shifting Services, Compare Shifting Charges, Visit :
Manish Packers and Movers Ptv Ltd @ https://www.manishpackersmoversindore.in/
Packers and Movers Indore @ https://www.manishpackersmoversindore.in/packers-and-movers-indore.html
Manish Packers Indore @ https://www.manishpackersmoversindore.in/manish-packers-and-movers-indore.html
Packers and Movers Gurgaon @ https://www.manishpackersmoversindore.in/packers-movers-gurgaon.html
Packers and Movers Kolkata @ https://www.manishpackersmoversindore.in/packers-movers-kolkata.html
Packers and Movers Mumbai @ https://www.manishpackersmoversindore.in/packers-movers-mumbai.html
Packers and Movers Bhopal @ https://www.manishpackersmoversindore.in/packers-movers-bhopal.html
Packers and Movers Nagpur @ https://www.manishpackersmoversindore.in/packers-movers-nagpur.html
Packers and Movers Raipur @ https://www.manishpackersmoversindore.in/packers-movers-raipur.html
Packers and Movers Ahmedabad @ https://www.manishpackersmoversindore.in/packers-movers-ahmedabad.html

Manish Packers and Movers Pvt Ltd said...


Packers and Movers Dewas Naka Indore
Packers and Movers Vijay Nagar Indore
Packers and Movers Scheme 54 Indore
Packers and Movers Delhi
Packers and Movers Pune
Packers and Movers Jodhpur
Packers and Movers Kanpur
Packers and Movers Ghaziabad
Packers and Movers Noida
Packers and Movers Navi Mumbai

Manish Packers and Movers Pvt Ltd said...

Best Movers and Packers in India for Moving and Shifting Door to Door Transportation Services to all over India. Visit More :-
Manish Packers and Movers Pvt Ltd Blog
Packers and Movers Bhopal
Packers and Movers Jabalpur
Packers and Movers Vadodara
Packers and Movers Udaipur
Packers and Movers Jaipur
Packers and Movers Chandigarh
Packers and Movers Chennai
Packers and Movers Hyderabad
Packers and Movers in Indore

Manish Packers and Movers Pvt Ltd said...

Hire Manish Packers and Movers Pvt Ltd in India for hassle-free Household Shifting, Office Relocation, Car Transportation, Loading Unloading, packing Unpacking at affordable Price Quotation. Top Rated Safe and Secure Service Providers who can help you with 24x7 and make sure a Untroubled Relocation Services at Cheapest/Lowest Rate. Visit More :-
Manish Packers and Movers Pvt Ltd
Packers and Movers Bangalore
Packers and Movers Gurgaon
Packers and Movers Indore
Packers and Movers Kolkata
Packers and Movers Mumbai
Packers and Movers Nagpur
Packers and Movers Ahmedabad
Manish Packers in Indore
Manish Packers and Movers Pvt Ltd Sitemap

Anas Qureshi said...

I needed to thank you for this fabulous read!! I certainly cherished each and every piece of it. I have you bookmarked your site to look at the new stuff you pos HMRC Tax Enquiry Advice

Anas Qureshi said...

Much obliged to you for such an elegantly composed article. It's brimming with astute data and diverting depictions. Your perspective is the best among numerous. Let Campaign Tax Enquiry

Manish Packers and Movers Pvt Ltd said...

Packers and Movers DLF Gurgaon
Packers and Movers Iffco Chowk Gurgaon
Packers and Movers MG Road Gurgaon
Packers and Movers Palam Vihar Gurgaon
Packers and Movers Udyog Vihar Gurgaon
Packers and Movers Asansol
Packers and Movers Durgapur
Packers and Movers Haldia
Packers and Movers Kharagpur
Packers and Movers Siliguri

Manish Packers and Movers Pvt Ltd said...

Packers and Movers Andheri Mumbai
Packers and Movers Thane Mumbai
Packers and Movers Bandra Mumbai
Packers and Movers Navi Mumbai
Packers and Movers Dadar Mumbai
Packers and Movers Goregaon Mumbai
Packers and Movers Kurla Mumbai
Packers and Movers Mhow
Packers and Movers Pithampur
Packers and Movers Khandwa

Manish Packers and Movers Pvt Ltd said...

Packers and Movers Jamnagar
Packers and Movers Gandhidham
Packers and Movers Nashik
Packers and Movers Gwalior
Packers and Movers Visakhapatnam
Packers and Movers Patna
Packers and Movers Ranchi
Packers and Movers Bilaspur
Packers and Movers Korba
Packers and Movers Raigarh

Manish Packers and Movers Pvt Ltd said...

Packers and Movers Sector 14, 17, 19 Gurgaon
Packers and Movers Sector 23 Gurgaon
Packers and Movers Sector 45, 46, 47 Gurgaon
Packers and Movers Sector 55, 56, 57 Gurgaon