Programming

Question 1

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).

Answer 1

Recursive programming (sol in code)

Question 2

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

Answer 2

Store all the hashtags in a dictionary and get the top 10 values

Question 3

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

Answer 3

Greedy solution (add the best v/w as much as possible and move on to the next)

Question 4

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

Answer 4

Greedy

Question 5

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?

Answer 5

https://en.wikipedia.org/wiki/Reservoir_sampling

Question 6

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

Answer 6

https://www.quora.com/What-is-the-method-to-calculate-a-square-root-by-hand?redirected_qid=664405

Question 7

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

Answer 7

sort then select the highest and the lowest 2.5%

Question 8

8. When can parallelism make your algorithms run faster?

Answer 8

When could it make your algorithms run slower?

Ask someone for more details.
compute in parallel when communication cost < computation cost
ensemble trees
minibatch
cross validation
forward propagation
minibatch
not suitable for online learning

Question 9

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

Answer 9

Change the subquery to a join.

Question 10

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

Answer 10

Primary keys are columns whose value combinations must be unique in a specific table so that each row can be referenced uniquely. Foreign keys are columns that references columns (often primary keys) in other tables.

Question 11

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?

Answer 11

select faculty_name from faculty_id c join (select faculty_id from (select course_id from COURSES where course_name=xxx) as a join COURSE_FACULTY b on a.course_id = b.course_id) d on c.faculty_id = d.faculty_id

Question 12

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.

Answer 12

select ad_id, average(click) from IMPRESSIONS group by ad_id, month(date)

Question 13

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

Answer 13

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

select Dept_Name, count(1) from DEPTS a right join EMPLOYEE_DEPT b on a.Dept_id = b.Dept_id group by Dept_Name