I was recommended the book, “Cracking the Coding Interview,” which definitely sufficed in getting my foot in the door with Google. This was a second book that someone recommended. He said, “[this] was highly recommended by several engineers and quite representative of the types of coding questions asked.” (PDF’s available online).
The first two chapters are about getting the interview, while the third prepares the reader for the interview topics to come. Chapters 4-11 deal with programming topics of: Linked Lists, Trees and Graphs, Arrays and Strings, Recursions, Concurrency, OOP, Databases, and “other.” Twelve, Thirteen, and Fourteen deal with non-coding technical problems. Fifteen deals with Nontechnical questions.
What kind of programmer are you?
- Systems or app developer?
- User interfaces?
- Architect or coder?
- Big Company?
- Open source?
- Long or short-term projects?
Knowing the Company
- “Recruiters are honorable people who are very good at what they do; however, their job is to get you to sign with their company as quickly as possible for as little money as possible.
- Always spend a day thinking about the offers
- signing bonus, better pay, or more stock options
- “Thank you for the offer, but I’m having trouble accepting it because it’s not competitive with my other offers.”
- “Thank you again for the offer, but I’m having trouble accepting it because I know from discussions with my peers and from talking with other companies that this offer is below market rates.”
- “I keep all my offers confidential, including yours, and feel that it’s unprofessional to give out that sort of information.
Basic Steps to Interview
- Make sure you understand the problem
- Once you understand the question, try and example
- Focus on algorithm you will use to solve the problem
- After you’ve figured out your algorithm and how you will implement it, explain your solution to the interviewer
- While you code, it’s important to explain what you’re doing
- Ask questions when necessary
- After you’ve written the code for a problem, immediately verify that the code is correct by tracing through it with an example
- Make sure you check your code for all error and special cases. especially boundary conditions
- Big O Analysis
When you get stuck
Usually, there is an elegant answer that you might be missing, but do expect to get stuck.
- Go back to an example
- Try a different data structure
- Consider the less-commonly used or more-advanced aspects of a language
How to do Big O
- Figure out what the input is and what n represents
- Express the number of operations the algorithm performs in terms of n
- Eliminate all but the highest-order terms
- Remove all constant factors
- Singly, Doubly, Circular
- Parent, Child, Descendant, Ancestor, Leaves
- Binary Tree, BST
- Breadth First, Depth First
- Preorder, postorder, inorder traversals
- trees with multiple parents possible
- Unlike a C array, a Java array is an object in and of itself, separate from the data type it holds. A reference to an array is therefore not interchangeable with a reference to an element of the array. As in C, arrays cannot be copied with a simple assignment: If two array references have the same type, assignment of one to the other is allowed, but it results in both symbols referring to the same array.
- Each access to an array index is checked against the current size of the array and an exception is thrown if the index is out of bounds. This makes array access a relatively expensive operation when compared to C/C++ arrays.
- You must construct the objects yourself and assign them to the elements of the array.
- Strings are sequences of characters. However, what constitutes a character depends greatly on the language being used and the settings of the OS on which the application runs.
- Languages such as Java and C# have a built-in Unicode character type.
- Java’s char type holds 16-bit Unicode characters.
- Java strings are immutable: They cannot be changed once the string has been constructed. Methods that appear to modify a string actually return a new string instance.
- The StringBuffer and StringBuilder classes (prior to Java 5 is thread safe) create mutable strings that can be converted to a String instance as necessary. The compiler implicityle uses StringBuffer instances when two String instances are concatenated using the + operator, which is convenient but can lead to inefficient code if you’re not careful.
- Recursion is most useful for tasks that can be defined in terms of similar subtasks.
- Base/Recursive case
- It may be useful to write a separate wrapper routine to do initialization for a complex recursive routine
- Iterative solutions are usually more efficient
- A recursive algorithm can be implemented without recursive calls by using a stack, but it’s usually more trouble than it’s worth
Even today, code you write for an application or Web server tends to be single-threaded, even if the server itself is multithreaded. Why? Because multi-threaded programming (often referred to as concurrency) is hard to do correctly, even when the programming language directly supports it.
- Thread is the fundamental unit of execution within an application: A running application consists of at least one thread. Each thread has its own stack and runs independently from the application’s other threads. Threads share the resources used by the application as it runs, such as file handles or memory, which is why problems can occur.
- On most systems, threads are created and managed by the OS. Sometimes, however, the threads are actually implemented by a software layer above the operating systems, such as the runtime system for a interpreted programming language. Behavior is the same for both. OS: native or kernel level threads
- A system thread is created and managed by the system. The first (main) thread of an application is a system thread, and the application often exits when the first thread terminates. User threads are explicitly created by the application to do tasks that cannot or should not be done by the main thread.
- Applications that display user interfaces must be particularly careful with how they use threads. The main thread in such an application is usually called the event thread, because it waits for and delivers events (such as mouse clicks and key presses) to the application for processing. Generally speaking, causing the event thread to block for any length of time is considered bad programming practice, because it leads to (at best) an unresponsive application or (at worst) a frozen computer. Applications avoid these issues by creating threads to handle time-consuming operations, especially those involving network access.
- In order to avoid data corruption and other problems, applications must control how threads interact with shared resources, referred to as thread synchronization. The two fundamental thread synchronization constructs are monitors and semaphores. Which you use depends on what your system or language supports.
- As soon as two or more threads contend for a shared resource, the possibility of deadlock occurs, which happens when two threads each have a lock on a resource needed by the other thread. Because neither thread can continue running, the threads are said to be deadlocked. Typically, the only way to resolve a deadlock is to forcefully terminate one of the threads, which is not a great solution. The best solution is deadlock avoidance — using careful programming to ensure that deadlock can never occur.
Object Oriented Programming
- Two other important principles are those of inheritance and polymorphism, which are closely related. Inheritance enables a class to provide behavior for a more-specialized version of the class. When class B inherits from class A (Java uses the term extends), class A is B’s parent or base class and class B is A’s subclass. All the behaviors defined by class A are also part of class B, though possibly in a modified form. In fact, an instance of class B can be used wherever an instance of class A is required.
- Polymorphism is the ability to provide multiple implementations of an action and to select the correct implementation based on the surrounding context. For example, a class might define two versions of a method with different parameters. Or the same method might be defined both in a parent class and a subclass, the latter overriding the former for instances of the subclass. Method selection may occur when the code is compiled or when the application is run.
- The classic example of inheritance and polymorphism is a shapes library representing the different shapes in a vector-based drawing application. At the top of the hierarchy is the Shape class, which defines the things that all shapes have in common.
- There are tools available to help you create and manage databases, many of which hide the complexities of the underlying data structures. Ruby on Rails, for example, abstracts all database access and makes most direct access unnecessary, as do component technologies such as Enterprise JavaBeans and many object-oriented frameworks. Still, you need an understanding of how relational databases work to make good design decisions.
- Bit Manipulation
- Brain Teasers
- Graphical and Spatial
Knowledge-based questions generally come from two sources: what you said on your résumé and your answers to questions earlier in the interview.
- What do you want to do?
- What is your favorite programming language?
- What is your work style?
- Tell me about your experience?
- What are your career goals?
- Why are you looking to change jobs?
- How much money do you want to make?
- What is your salary history?
- Why should we hire you?
- Do you have any questions for me?
Technical résumés are written differently than the nontechnical résumés described in most résumé books. Nontechnical jobs generally have some latitude in terms of necessary skills, but technical jobs usually require a very specific skill set. Employers aren’t interested in talking to candidates who don’t have the necessary skills for the job. This means that technical résumés generally require more specific information than nontechnical résumés.