NYU Bootcamp 2020: Python

Series 1. General exercises and numpy

1. Generate a list with random integers. Then remove all the elements in that list that are located at a position corresponding to a prime. Recall that a prime is a number that is divisible only by 1 and by itself.

2. We want to write a function that computes the square root of a number (without relying on the )

3. When considering a subspace of vectors $x_1, \ldots, x_n$ of $\mathbb{R}^n$, one can construct an orthonormal basis for the subspace by relying on the Gram Schmidt

4. Generate a $10\times 10$ matrix with random entries, compute the determinant of the matrix and if this determinant is non zero, generate a random vector b of dimension $n$ and solve the system $Ax = b$.

5. Using a for loop, generate the first 50 elements of the recursion x[3] = 3sin(x[2] ) + 2x[1] + x[0]. Starting from x[0] = 1.1, x[1] = 0.9 and x[2] = 1.2

Series 2. Data structures

Data types in python can be grouped in about 7 groups

  • Text Type (incl. str)
  • Numeric Types (incl. int, float, complex)
  • Sequence Types (incl. list, tuple, range)
  • Mapping Type (dict)
  • Set Types (incl. set, frozenset)
  • Boolean Type (bool)
  • Binary Types (incl. bytes, bytearray, memoryview)

1. Build a dictionnary that encode the first 20 prime numbers

2. Consider the list ['Plato', 'Aristotle', 'Socrates', 'Descartes', 'Leibnitz', 'Joyce', 'Locke']. Use the .remove function to get rid of the entry which should not be there.

3. We consider the dictionnary D = {'Alphabet' : {'stock' : 1526, 'number Employees': 127498, 'Headquarter': 'MontainView'}, 'Facebook' : {'stock' : 268.09, 'number Employees': 52534, 'Headquarter': 'Menlo Park'}, 'Amazon' : {'stock' : 3175, 'number Employees': 1000000, 'Headquarter': 'Seattle'}}. Use the methods 'get()' and 'pop()' on this dictionnary. What do those methods do? Then try the method 'values()'

4. Build a dictionnary of depth 5 in which the keys at each level are numbered 1 to 5 and each encode a dictionnary with 5 keys. Set the all the elements in the last level to 0.

5.Generate a dictionnary of length 100 in which the keys are strings corresponding to the numbers from 0 to 99 and the entries are the actual numbers from 0 to 99.

6. (linuxtopia) There are 36 possible combinations of two dice. A sim→ple pair of loops over range(6)+1 will enumerate all combinations. The sum of the two dice is more interesting than the actual combination. Create a dict of all combinations, using the sum of the two dice as the key. Each value in the dict should be a list of tuples; each tuple has the value of two dice. The general outline is something like the following:

Series 3. Functions

Answer the following questions by defining a function

1. Write a function which takes a date (format dd/mm/yyyy) as input and return the corresponding number of the day in the year (we assume a classical (i.e. 365 days) year)

2. Rewrite the function dot which takes two matrices A and B as input and returns the product of those matrices.

3. implement the step function defined below as function of the argument x.

$$\text{step}(x) =\left\{\begin{array}{ll} +1 & x>0\\ 0 & x\leq 0 \end{array}\right.$$

4. we consider the repetition of the function $f(x) = 1$ if $-1\leq x\leq 1$ and $0$ on $[-1.5, -1]$ and $[1,1.5]$. In other words, this function is an infinite repetition of a 'square' signal. For any real number x, code the function which returns the value $f(x)$.

Series 4. Object oriented programming

1. We want to describe a code that describes the NYU Students. Write a general class "NYU students". This class should contain an initialization function From this class we want to define 4 additional classes through inheritance. The first one "NYU Paris Students" should inherit from "NYU Students" but should also contain specific function an attributes (see below). The last three "NYU Paris CS", "NYU Paris Math" and "NYU Paris Other" should inherit from the class "NYU Paris Students" again with their own specific features.

  • Objects from the "NYU students" class should have the following attributes: A dictionnary "GPA" (containing a list of course and the associated grades obtained), a variable, "Major", a list "courseList" initialized to an empty list. They should contain an initialization function which sets the variable GPA to 0 and the Major to None. The class should also contain a function 'grade(course)' which takes as input a particular course and returns two parameters: a binary value if the student took the course and the corresponding GPA from the list GPA

  • Objects from the "NYU Paris Students" Class should contain a variable "Residence" that will be set to either of the two NYU Paris residences (Maison de l’Ile-de-France vs Fondation des Etats- Unis), it should contain a French Citizenship which takes a binary 0/1 value. It should also contain a list "ParisCourseList" used to encode the courses taken in Paris.

  • Objects from the classes "CS", "Math" and "Other" should respectively contain variables "numCScourses", "numMathCourse" and "numOthers" variables. They should also contain variables "GPAMath", "GPACS" and "GPAOthers"

2. (my-courses.net) Write a Rectangle class in Python language, allowing you to build a rectangle with length and width attributes.

  • Create a Perimeter() method to calculate the perimeter of the rectangle and a Area() method to calculate the area of the rectangle.
  • Create a method display() that display the length, width, perimeter and area of an object created using an instantiation on rectangle class.
  • Create a Parallelepipede child class inheriting from the Rectangle class and with a height attribute and another Volume() method to calculate the volume of the Parallelepiped

3. (Institut pasteur) Write the definition of a Point class. Objects from this class should have a

a method show to display the coordinates of the point a method move to change these coordinates. a method dist that computes the distance between 2 points.

e.g. p1.move(10, -10) updates the coordinates by adding 10 and -10 p2.show() display the coordinates and p1.dist(p2) computes the distance between p1 and p2.

Series 5. Algorithms and graphs

1. Many algorithms in Theoretical Computer Science are described in terms of their properties on graphs and in particular trees. There are two easy approaches at generating random trees. The first one is to start from a node and generate its children with fixed probabilities, lets says p(x has one child) = p_1, p(x has two child) = p_2,... This first approach is known as Galton Watson. The alternative is to rely on the notion of Prufer sequence. A tree with n nodes can be uniquely expressed by a sequence of n-2 integer numbers (in the range of [0, n-1]). You can generate such a sequence at random. The sequence can be used to generate a tree (see for example here)

Implement each approach and display the resulting tree using plot or scatter (hint: compute the set a distance between children nodes at level 1, then divide the distance from the previous level by 2 in order to get the coorinates of the nodes from the next level).

2. Dijkstra's algorithm's is a very popular algorithm for finding the shortest path between two vertices in a graph. The algorithm can be found here. graphs can be represented by an adjacency matrix $\mathbf{A}$ whose (i,j) entry is $1$ if there is an edge between

3. Write a function that takes an integer (in decimal notation) as input an return the corresponding string of bits encoding that number in base 2. Then write a function that takes two strings of bits and return the integer corresponding to the multiplication of the two numbers

Series 6. Interview questions (Answer those questions in python)

The following questions are gathered from a variety of online sources. The source is indicated under brackets followed buy the claim regarding the companies at which that question is supposed to haev been asked.

1. (interviewbit, Bloomberg, Google, DE Shaw,Amazon,Flipkart) Given two integer arrays A and B of size N. There are N gas stations along a circular route, where the amount of gas at station i is A[i]. You have a car with an unlimited gas tank and it costs B[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the minimum starting gas station’s index if you can travel around the circuit once, otherwise return -1. You can only travel in one direction. i to i+1, i+2,...n-1, 0, 1, 2.. Completing the circuit means starting at i and ending up at i again.

2. (interviewbit, Google, Microsoft) Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area. Bonus if you can solve it in O(n^2) or less.

3. (interviewbit, Google, Microsoft) The majority elements in an array are the elements that appear more than $\lfloor n/2\rfloor$ times. Given a 1D array, return the majority elements from the array.

4. (interviewbit, Google, Yahoo) Given three strings S1, S2 and S3, find whether C is formed by the interleaving of A and B.

5. (interviewbit, Google Facebook, Microsoft) Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

    int isMatch(const char *s, const char *p)

Examples include

  • isMatch('aa', '.a') gives 1
  • isMatch("aaa","aa") gives 0
  • isMatch("ab", ".*") gives 1
  • isMatch("aab", "cab") gives 1

6. (interviewbit, IBM, Google) Given a string A and a dictionary of words B, determine if A can be segmented into a space-separated sequence of one or more dictionary words.

7. (interviewbit, IBM, Google) Given a string A, partition A such that every substring of the partition is a palindrome. Examples of what the function should return are

8. (interviewbit, Google) Given two sequences A, B, count number of unique ways in sequence A, to form a subsequence that is identical to the sequence B.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Example: A = "rabbbit" B = "rabbit", output = 3 since we can take A = "ra_bbit" (removing one character), A = "rab_bit" (removing the middle character) and A = "rabb_it" (removing the last b). Another example, A = 'abc', B = 'abc' output: 1 since the only way to make B from A is to take the whole sequence.

9. (interviewbit, Amazon, Ebay,Google) Given an array of non-negative integers, A, of length N, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Return the minimum number of jumps required to reach the last index. If it is not possible to reach the last index, return -1.