Skip to content

Latest commit

 

History

History
50 lines (44 loc) · 3.72 KB

programming.md

File metadata and controls

50 lines (44 loc) · 3.72 KB
Raw

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

  • Recursive programming (sol in code)

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

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

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

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

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

  • Greedy

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?

  • sort then select the highest and the lowest 2.5%

8. When can parallelism make your algorithms run faster?

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

9. What are the different types of joins? What are the differences between them?

  • (INNER) JOIN: Returns records that have matching values in both tables LEFT (OUTER) JOIN: Return all records from the left table, and the matched records from the right table RIGHT (OUTER) JOIN: Return all records from the right table, and the matched records from the left table FULL (OUTER) JOIN: Return all records when there is a match in either left or right table

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

  • Change the subquery to a join.

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

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

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?

  • 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

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.

  • select id, average(click) from (select count(click) as click from IMPRESSIONS group by id,month(date)) group by id

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

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