Interview Questions

Short Questions

General Programming

• Reverse a singly linked list

Data structures

• Implement a simple array backed hashtable
• Tree serialization/deserialization (depth-first, breadth-first, preorder, postorder)
• Implement a simple array backed min or max heap
• Name some different data structures that exist. Can you name some advantages of those data structures compared to others?

Javascript

• What are some differences between classical and prototypical inheritance?
• How do you create a javascript object? Private methods? Static methods?
• Write a function that takes any number of arguments (assumed to be numbers) and returns the sum of those number?

Python

• Mutable default keyword arguments (e.g. def x(arg=[]):)

Django

• ?

SQL

• Join question?

Security

• Quickly analyze this sample blog web application: http://pastebin.com/JFsay8Ux. It is vulnerable to the following:
• SQL injection
• Cross Site Scripting
• Cross Site Request Forgery
• Application Exception Output
• Known Vulnerable Output: Name, Comment, "Add blog for" title
• HTML injection
• This code was adapted from Mutillidae.

Detailed Questions

Question: You have a list of N+1 integers between 1 and N. There is at least one duplicate, but there might be more. Print out a number that appears in the list more than once.
Source: http://www.quora.com/Programming-Interviews/What-are-the-best-programming-interview-questions-youve-ever-asked-or-been-asked Details: If N=3, your list might be 3, 1, 1, 3 or it might be 1, 3, 2, 2. In the first example, you can print '1' or '3' -- you don't have to print both. Answers:

• O(n^2) time, O(1) space:
  • Compare every number in the list to every other number until you find a duplicate.
• O(n) time, O(n) space:
  • Iterate through the list and use a boolean array using the integer values as indices.
  • Can be generalized using hashes if not using integers
• O(n*log n) time, O(1) space:
  • Sort the numbers and compare adjacent pairs (if using something like in-place mergesort)
• O(n*log n) time, O(1) space (constraint: can't manipulate original list):
  • Binary search for a duplicated number. Go through the list and count the number of integers between 1 and N/2. If the count is greater than the number of possible integers in that range, there is a duplicate in that range. Otherwise, a duplicate must exist in the range of N/2 + 1 to N. Recurse and binary search in the half with the duplicate and keep repeating the process until the duplicate number is found.

Question: You are given two eggs, and access to a 100-storey building. Find the highest floor from which an egg will not break in the least number of drops.
Source: http://www.datagenetics.com/blog/july22012/index.html
Details: Both eggs are identical. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that's it for that egg.
Answers:

• One egg solutions (illustrative)
  • At most 100 drops - Linear search
• Many egg solutions (illustrative)
  • At most 7 drops - Binary search
• Two eggs
  • At most 100 drops - Linear search
  • At most 50 drops - Binary search until egg breaks, then linear search
  • At most 19 drops - Check every ten floors until one egg breaks, then linear search
  • At most 14 drops - Minimize maximal regret
    • Drop the egg from floor n. If it doesn't break, check floor n + (n - 1)
    • n + (n - 1) + (n - 2) + ... + 1 >= 100 -> n (n+1) / 2 >= 100
    • Solving for n, n=13.651~=14. Drop at floor 14, 27, etc.

Question: At Willet we like rock climbing. One day we stopped for lunch after climbing to the top of a tall cliff. While eating lunch a rather mischievous marmot chewed through our ropes creating N segments of varying lengths. To get home we needed to rappel down the cliff of height H but none of the individual lengths of rope were long enough. We can tie shorter segments of rope together but each time we encounter a knot we need to unclip from the rope to pass the knot through our belay devices.

Your task is to write a function that minimizes number of knots that need to be passed and returns the lengths of the rope segments to use to create a length of exactly H.

public int[] minimizeKnots(int[] segments, int H) {

}

Design Questions

• How would you design an analytics system like Google Analytics (backend / frontend)?