Study Guides for your Next Technical Interview

I get commissions for purchases made through some links in this post. The recommendations are my own, and are not sponsored (*).

Over the last couple of years, I have been creating some Interview Study Guides that have helped both improve my coding/technical skills and prepare for interviews in top tech companies. Since I believe these guides might be useful for others I have decided to publish them.

All the guides are free and released under CC-Attribution-ShareAlike License.

All the guides are a work in progress and open for improvements. You can download all the guides from here.

NEW: if you prefer video over text, then don't miss my Youtube Playlist "Before the technical interview" where I cover all the topics presented on these guides (and many others).

Below is a brief summary of each of the guides.

Computer Science Fundamentals

As the name implies, this guide provides a summary of Computer Science Fundamentals, including:

• Data Structures
• Algorithms
• Complexity Analysis
• Mathematics and Probability
• Regular Expressions
• Threads and Locks

The sources range from online resources like Wikipedia, GeeksForGeeks and StackOverflow to formal books including (*):

• The Algorithm Design Manual
• Programming Interviews Exposed
• Cracking the Coding Interview

I find it useful to quickly review different algorithms and as cheatsheet for different CS courses, and most of the interviews at Google, Facebook, LinkedIn, Amazon, and other big tech companies, will make a big emphasis on these topics.

You can download this guide clicking here.

This guide will help you have the concept to solve typical problems like Finding the largest BST in a tree.

Software Development and Architecture

This guide compiles higher level topics like:

• Object Oriented Design
• Service Oriented Architectures (SOAP and REST)
• Scalability and Networking
• Front End Development
• How do browsers work
• How to speed up websites
• ...and more!
• Frameworks (specifically Spring)
• Databases

This guide is a bit less polished than CS Fundamentals, but also includes a wide range of sources from different websites and books including (*):

• Cracking the Coding Interview.
• Head's First Object Oriented Analysis and Design.
• Java Web Services Up and Running.
• Java SOA Cookbook.

You can download this guide clicking here.

Code Snippets

This guide is the shortest. It includes short descriptions and code snippets from programming languages I have had some experience with (even if only during a course in college). The code snippets are commented with syntax explanation. The languages in the guide include:

• Ruby
• Javascript
• PHP
• Prolog
• Haskell
• C/C++

You can download this guide clicking here.

Additional Resources

There are a lot of free resources on the Internet you can learn from:

• Here's a summary of most Software Development topics that you learn in college, and works great as quick refresher:https://github.com/jwasham/coding-interview-university
• A list of sites where you can practice coding: http://programmingzen.com/15-sites-for-programming-exercises/ 

Disclaimer

I (Christian Vielma) have personally created these guides for personal use, to be used as a reference for technical interviews, work, and study. Since I believe these documents might provide value to others, I have decided to make them public.

Most of the contents on these documents have been added from different sources, from freely available resources on the Internet, to books, with additional added content from me. I made my best effort to provide full credit to the original sources, and in no way I'm trying to take advantage of improper quotations. If you believe I have made an invalid reference to a resource, please let me know and I'll fix it.
 
I provide these guides as-is, with no additional guarantees. I'm also releasing it under CC-Atribution-ShareAlike License, so you are free to extend it and update it with proper attribution.

Enjoy!

(*) Disclaimer 2:
As an Amazon Associate I earn from qualifying purchases. Links referring to Amazon are still books that I personally recommend (not sponsored) but I might receive money based on clicks  or purchases. There might also be some ads on the sides or between posts are those are placed by Google based on their recommendations (not endorsed by me).

Big-Oh Computer Science English Interviews Java Programming Study

Find Largest Binary Search Tree in a Tree: Java Solution

The question is simple and fair common:

Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree. (From: GeeksForGeeks)

Additionally, I'll be returning the root node for the BST. In this case the BST would have to include all its children (i.e.: it must be a BST from a specific node to the leaves).

Algorithm

To find the largest BST in a tree there are different options to traverse the tree: we could take an top-down approach or a bottom-up.

Top-Down

The top-down approach require us to check at each node from the root if the tree starting at that node is a BST. This makes us traverse multiple times the tree to find the bst. Although it stops as soon as it find a BST because it will be the largest. This solution has a time complexity of O(n^2) in worst-case (degenerated tree into list) or O(nLogn) (balanced tree)

 where n is the number of nodes in the tree.

Bottom-Up

A better approach will be bottom-up where we check from the bottom of the tree the nodes to check if the trees created are BST. This makes the evaluation of a BST in O(1) for each node, although we still have to traverse the tree completely, so this approach has a time complexity of O(n) (in fact we have to traverse the tree twice because to get to the bottom nodes we must traverse from the root and then again from the bottom to the top).

Given the implementation is recursive, this has a space complexity of O(n). 

Implementation

Below is my Java proposed solution. For a complete solution (including testing, full comments and printing) check this.

If you are preparing for a tech interview, don't forget to check the Interview Study Guides.

Big-Oh English Java Programming