programming.md

Programming (14 questions)

1. Write a function to calculate all possible assignment vectors of 2n users, where n users are assigned to group 0 (control), and n users are assigned to group 1 (treatment).

2. Given a list of tweets, determine the top 10 most used hashtags.

3. Program an algorithm to find the best approximate solution to the knapsack problem1 in a given time.

4. Program an algorithm to find the best approximate solution to the travelling salesman problem2 in a given time.

5. You have a stream of data coming in of size n, but you don’t know what n is ahead of time. Write an algorithm that will take a random sample of k elements. Can you write one that takes O(k) space?

6. Write an algorithm that can calculate the square root of a number.

7. Given a list of numbers, can you return the outliers?

8. When can parallelism make your algorithms run faster?

9. What are the di erent types of joins? What are the di er- ences between them?

10. Why might a join on a subquery be slow? How might you speed it up?

11. Describe the difference between primary keys and foreign keys in a SQL database.

12. Given a COURSES table with columns course_id and course_name, a FACULTY table with columns faculty_id and faculty_name, and a COURSE_FACULTY table with columns faculty_id and course_id, how would you return a list of faculty who teach a course given the name of a course?

13. Given a IMPRESSIONS table with ad_id, click (an indicator that the ad was clicked), and date, write a SQL query that will tell me the click-through-rate of each ad by month.

14. Write a query that returns the name of each department and a count of the number of employees in each:

EMPLOYEES containing: Emp_ID (Primary key) and Emp_Name
EMPLOYEE_DEPT containing: Emp_ID (Foreign key) and Dept_ID (Foreign key)
DEPTS containing: Dept_ID (Primary key) and Dept_Name