This document was used by Kevin Owocki in his Summer 2013 Job Hunt to prep for technical interviews. Enjoy, and feel free to edit! If you have any questions, my contact information is on owocki.com
- General Knowledge
- Data Structures
- Bit Manipulation
- Brain Teasers
- Object Oriented Design
- Recursion and Dynamic Programming
- Scalability and Memory Limits
- Sorting and Searching
- Design Patterns
- Testing
- Threads and Locks
- Security
- Supplemental Resources
- Behavioral Interview Checklist
Q: Describe everything that happens from the time you hit enter, to the time your browser receives a response.
Roughly,
The hardware sends an interupt to the web browser application for each key pressed.
The browser resolves the hostname (unless its an IP already) to an IP address.
- DNS Lookup, but may also be cached.
The browser sends a GET request to that IP via HTTP protocol.
- This involves some parsing of the URL (assuming it's even HTTP and not a search query)
- Under the surface, this is TCP.
- Socket Stream
- TLS handshake
The server finds the correct file via URI* requested.
- Usually an apache server, sometimes not. Ngnix, etc.
- Bridge between web server and application environemnt. Apache/PHP, Ngnix/Unicorn/Rails.
- If there's a dynamic environment on server, manipulation of data structures will occur, maybe even some reads from files, redis, or a ACID database.
The server returns the HTML (we hope it's HTML, it could be one of serveral content-types, but assume HTML for now).
The file is sent to you, again through HTTP.
Your browser displays it.
- Probably some more memory is allocated at this point. The previous page may also be destroyed, but a referene to it will be placed in history.
- DOM parsing
- CSS interpretation
- page rendering, this can go down to the GPU
Browser fetches asset files (CSS/JS/Images).
- Repeat steps 2 - 6.
*URI - Uniform Resource Identifier
See also, this attempt to answer this question as broadly as possible!
Q: What is the w3c?
The World Wide Web Consortium (W3C) is the main international standards organization for the World Wide Web (abbreviated WWW or W3).
Q: Explain MVC in simple terms
MVC is a methodology in programming that is widely used for the ground works, we’re asking them to explain it in simple language because we also we also want a developer to be able to speak to non-technical people. We’ll give you 2 examples of simple explanations:
M (Model) stands for the part of the code that knows things.
V (View) is the part of the code that shows the things the Model knows.
C (Controller) is the part of the code that gets commands from the user and tells the View what to show and the Model what to know.
Q: Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz.| For numbers which are multiples of both three and five print “FizzBuzz.”
Public Sub fizzbuzz()
For n = 1 To 100
Select Case 0
Case n Mod 15
f = "FizzBuzz"
Case n Mod 3
f = "Fizz"
Case n Mod 5
f = "Buzz"
Case Else
f = n
End Select
Debug.Print f
Next n
End Sub
Q: What is REST?
REST (REpresentational State Transfer) is a simple stateless architecture that generally runs over HTTP. REST is an "architectural style" that basically exploits the existing technology and protocols of the Web. There are generally 4 actions on a RESTful service:
* Create
* Read
* Update
* Delete
Q: Explain ways to improve a page load speed or user experience.
See Front End Performance Checklist On the backend,
- Caching
- Solid Architecture
- Horizontal Scalability
Q: Explain a number of HTTP status codes (except maybe 404 and 500).
Q: What is a closure in JavaScript?
A method and properties that outlive the scope of their original function
Q: What is the maximum value of a 32bit integer?
Unsigned? 2^32= 4.2 billion
Signed? 2^(32-1)= 2.1 billion
Q: How many bytes are in a 32bit integer?
32/8 = 4 bytes
Q: Number of times 7 appears in the list of number 1 - 100?
In the range 1 - 100, the digit 7 appears ten times in the second decimals place, and ten times in the first decimals place, for a total of twenty appearances.
Q: Discuss pros/cons of OOP, Procedural, Functional, Event-Driven, programming.
- Imperative programming – defines computation as statements that change a program state
- Procedural programming, structured programming – specifies the steps the program must take to reach the desired state.
- Declarative programming – defines computation logic without defining its control flow.
- Functional programming – treats computation as the evaluation of mathematical functions and avoids state and mutable data
- Object-oriented programming (OOP) – organizes programs as objects: data structures consisting of datafields and methods together with their interactions.
- Event-driven programming – the flow of the program is determined by events, such as sensor outputs or user actions (mouse clicks, key presses) or messages from other programs or threads.
- Automata-based programming – a program, or part, is treated as a model of a finite state machine or any other formal automata
#!TODO
An array is data structure (type of memory layout) that stores a collection of individual values that are of the same data type. All of the items placed into an array are automatically stored in adjacent memory location.
An ArrayList is a dynamically resizing array. It doubles in size each time the array is full. Doubling is O(n), but lookups are O(1).
A StrinbBuffer is an array of strings. Storing the strings as an array allows you to avoid the O(xn^2) problem of concatenating n strings.
Q: Implement an algorithm to determine if a string has all unique characters.
Q: Implement a function void reverse(char * str) in C, C++ which reverses a null terminated string.
Q: Given two strings, write a method to decide if one is a permutation of the other
Q: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aacccccaaa would become a2b1c5a3. If the compressed string is not shorter than the original string, then return the original string.
Q: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Bonus points: do this in place.
Q: Assuming you have a method isSubstring() which checks if one string is a substring of another, write code to check if s2 is a rotation of s1 using only one call to isSubstring(). ex: pineapple is a rotation of apppinele.
A singly linked list contains nodes which have a data field as well as a next field, which points to the next node in the linked list. It is often used as a stack (or last in first out queue (LIFO)) because adding a new first element, removing the existing first element, and examining the first element are very fast O(1) operations.
A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes
Q: How can you find a 'cycle' in a singly linked list?
- Use Memory Allocation Information. - Keep track of the minimum or maximum memory addresses seen. If more nodes have been seen than can fit in the address space then some node must have been a cycle.
- Two iterators - Go through the list one by one (with a slow iterator) and by twos (fast iterator). If the fast iterator laps the slow iterator, the linked list has a 'cycle.
Q: Write an algo to remove duplicates from an unsorted linked list.
Q: Implement an algorithm to find the n-th element of a singly linked list.
Q: Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
Q: Implement an algorithm to partition a linked list around value z. All nodes less than z come before all nodes greater than or equal to z.
Q: Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
Q: Implement an algorithm to check if a linked list is a palindrome.
Q: Implement a 'Hash table'.
A stack is a data structure which contains a list of elements with LIFO (last in first out) ordering. The most recent item added (push()ed) to the stack is the first item to be removed (pop()ed).
A queue is a FIFO (first in, first out) data structure. The most recent item added (enqueu()ed) is the last item to be removed from the queue (dequeu()ed).
Q: Implement a stack. Implement a queue.
Q: How would you use a single array to implement three stacks?
Q: Design a stack that has a method min() which returns the minimum element in O(1) time.
Q: Implement a data structure SetOfStacks which contains several stacks and will create a new stack when a stack in the set exceeds a certain capacity (positive integer). Implement SetOfStacks.push() and SetOfStacks.pop().
Q: Write an algorithm that solves the Towers of Hanoi problem using stacks.
Q: Implement a Queue class which implements a queue using two stacks.
Q: An animal shelter holds only dogs and cats, and operates on a strictly “first in, first out” basis. People must adopt either the “oldest” (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat. You may use the built-in LinkedList data structure (has “addLast” method to insert an element at the end of the list, “poll” method to pop the first element of the list and “peek” method to get the first element).
Q: Write an array-based implementation of a queue that uses a circular array to represent the items in the queue. It should have two array indexes - front and rear - where front should point to the front of the queue and rear should point to the back of the queue. Use variable MAX_QUEUE to indicate the maximum number of elements that could be stored in the queue. Obtain the wrap around effect by using modulo arithmetic (the JAVA % operator).
!TODO answers
A Binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. A tree which does not have any node other than root node is called a null tree. In a binary tree, a degree of every node is maximum two. A tree with n nodes has exactly n−1 branches or degree.
Binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:[1] ** The left subtree of a node contains only nodes with keys less than the node's key. ** The right subtree of a node contains only nodes with keys greater than the node's key. ** The left and right subtree must each also be a binary search tree. ** There must be no duplicate nodes.
A tree is 'unbalanced' if the depth of the subtrees varies by more than a certain amount.
A tree is 'full' or 'complete' if all leaves are at the bottom of the tree and all non-leaf nodes have exactly two children.
A hash map is a data structure used to implement an associative array. A hash table uses a hash function to compute an index into an array of slots, from which the correct value can be found.
The hash function (ideally) assigns each possible key to a unique bucket, but there are, in practice, hash collisions.
There are several strategies to collision resolution.
- Seperate chaining - Each bucket has a list of entries.
- Open addressing - All entry records are stored in teh bucket itself.
- Hopscotch hashing - define a 'neighborhood' of buckets near the original hased bucket, and then search limited to that neighborhood. If all buckets in that neighborhood are taken, iterate across array.
& - bitwise and
| - bitwise or
^ - bitwise xor
~ - bitwise not
<< - bitwise shift left
>> - bitwise shift right
Bit Hack #1. Check if the integer is even or odd.
if ((x & 1) == 0) {
x is even
}
else {
x is odd
}
Bit Hack #2. Test if the n-th bit is set.
if (x & (1<<n)) {
n-th bit is set
}
else {
n-th bit is not set
}
Bit Hack #3. Set the n-th bit.
y = x | (1<<n)
Bit Hack #4. Unset the n-th bit.
y = x & ~(1<<n)
Bit Hack #5. Toggle the n-th bit.
y = x ^ (1<<n)
Bit Hack #6. Turn off the rightmost 1-bit.
y = x & (x-1)
Bit Hack #7. Isolate the rightmost 1-bit.
y = x & (-x)
If you get asked a problem solving question in an interview, remember that they are NOT looking for the RIGHT answer. They are evaluating the approach you use to think out and solve the problem. A strong candidate demonstrates the following:
- Evaluates and understands the scope of the problem
- Communicates assumptions
- Demonstrates quantitative analytical skills
- Answers the question that has been asked. You’d be surprised how many candidates get lost in the analysis and solve for a different question than what was asked.
- Examplify - Write out specific examples of the problem and see if you can derive a general rule.
- Pattern Matching - Consider problems that the algorithm is similar to and try to modify the solution to the related problem.
- Simply and Generalize - Change a constraint in a way that allows you to simplify problem. Once you have an algorithm for a simplified problem, generalize the problem to the complex version.
- Base Case and Build - Solve the problem first for a base case (ex: n = 1) Then solve for n =2, 3, and onwards.
- Data Structure Brainstorm - Run through a list of data structures and apply each one.
- __Bubble sort __ -
- __Selection sort __ -
- __Insertion sort __ -
- __Shell sort __ -
- __Comb sort __ -
- __Merge sort __ -
- __Heapsort __ -
- __Quicksort __ -
- __Counting sort __ -
- __Bucket sort __ -
- __Radix sort __ -
- __Distribution sort __ -
TODO Definitions here
- Abstract Factory groups object factories that have a common theme.
- Builder constructs complex objects by separating construction and representation.
- Factory Method creates objects without specifying the exact class to create.
- Prototype creates objects by cloning an existing object.
- Singleton restricts object creation for a class to only one instance.
- Adapter allows classes with incompatible interfaces to work together by wrapping its own interface around that of an already existing class.
- Bridge decouples an abstraction from its implementation so that the two can vary independently.
- Composite composes zero-or-more similar objects so that they can be manipulated as one object.
- Decorator dynamically adds/overrides behaviour in an existing method of an object.
- Facade provides a simplified interface to a large body of code.
- Flyweight reduces the cost of creating and manipulating a large number of similar objects.
- Proxy provides a placeholder for another object to control access, reduce cost, and reduce complexity.
- Chain of responsibility delegates commands to a chain of processing objects.
- Command creates objects which encapsulate actions and parameters.
- Interpreter implements a specialized language.
- Iterator accesses the elements of an object sequentially without exposing its underlying representation.
- Mediator allows loose coupling between classes by being the only class that has detailed knowledge of their methods.
- Memento provides the ability to restore an object to its previous state (undo).
- Observer is a publish/subscribe pattern which allows a number of observer objects to see an event.
- State allows an object to alter its behavior when its internal state changes.
- Strategy allows one of a family of algorithms to be selected on-the-fly at runtime.
- Template method defines the skeleton of an algorithm as an abstract class, allowing its subclasses to provide concrete behavior.
- Visitor separates an algorithm from an object structure by moving the hierarchy of methods into one object.
XSS
SQL Injection
CSRF
Man in the middle
| Name | Description | Comments |
|---|---|---|
| Clojure | TODO | |
| Django | TODO | |
| Go | TODO | |
| Lisp | TODO | |
| Node | TODO | |
| PHP | TODO | |
| Python | TODO | |
| R | TODO | |
| Ruby / Rails | TODO | |
| Java | TODO | |
| Scala | TODO |
| Name | Description | Comments |
|---|---|---|
| Angular | TODO | |
| Backbone | TODO | |
| Javascript/jQuery | TODO | |
| HTML5 | TODO | |
| CSS3 | TODO |
| Name | Description | Comments |
|---|---|---|
| BerkeleyDB | TODO | |
| Cassandra | TODO | |
| CouchDB | TODO | |
| Redis | TODO | |
| Hadoop | TODO | |
| ElasticSearch | TODO | |
| Memcache | TODO | |
| MemcacheDB | TODO | |
| MongoDB | TODO | |
| MariaDB | TODO | |
| PostegresSQL | TODO | |
| MySQL | TODO | |
| SQLLite | TODO | |
| Graph Databases | TODO |
| Name | Description | Comments |
|---|---|---|
| Analytics (MixPanel, KISSMetrics) | TODO | |
| TODO | ||
| TODO | ||
| TODO | ||
| Android | TODO | |
| iOS | TODO | |
| Mailing Clients (Sendgrid, Sailthru,MailChimp) | TODO | |
| Messaging Queues | TODO | |
| Firebase | TODO | |
| Graphite | TODO |
| Name | Description | Comments |
|---|---|---|
| Amazon | TODO | |
| Rackspace | TODO | |
| TODO | ||
| Azure | TODO | |
| Managed Hosts (EngingeYard, etc) | TODO |
| Name | Description | Comments |
|---|---|---|
| Braintree | TODO | |
| Authorize.net | TODO | |
| Stripe | TODO | |
| Paypal | TODO |
- Why do you want to work for X?
- Why should we hire you at X?
- What is your greatest weakness?
- What is your biggest strength?
- Do you have any questions for me?
- Where do you see yourself in 5 years?
- Why are you leaving your current company?
- What blogs do you read? How do you keep up with tech news?
Often on these questions, interviewers are looking for three things (be succinct):
- Situation: outline the situation
- Action: what action did you take?
- Response: What was the result?
- What was the most technically challenging part of (last project)?
- What'd you learn the most from (last project)?
- What was the most interesting part of (last project)?
- What was the hardest bug?
- What'd you enjoy the most?
- Give me an example of a conflict with a past teammate.
- Give me an example of a decision you made that was unpopular.
- Look @ Glassdoor Reviews.
- Look @ Recent press & fundraise announcements.
- Who are the founders? What are their backgrounds?
- Research interviewer