Questions Day 09 Challenges: Challenge 1: write a program that finds all nonsingle letter substrings that are palindromes. For instance: Challenge 2: there is a sorting algorithm called Quick Sort...

python


Questions Day 09 Challenges: Challenge 1: write a program that finds all nonsingle letter substrings that are palindromes. For instance: Challenge 2: there is a sorting algorithm called Quick Sort that used a recursive method. Learn how that works. Challenge 3: create a tic-tac-toe game that its output is like this: If the user enters a repeated cell it says: If the user enters an already taken cell, it passes the turn to the next player and gives the following message: And at the end it says the result: Day 10 Challenges: Challenge 1: The above module can be used to compare the big file sizes. For example, if you want to see if your 5 TB file is same as the one that your colleague has, you can check their message digest. Try to solve this problem. You can get some idea by looking at the code in this link but do not use md5 and also do not use the file I/O methods that is suggested in this code (https://stackoverflow.com/questions/36873485/compare-md5-hashes-of-two-files-in-python) Challenge 2: Please read this link (https://leons.im/posts/a-python-implementation-of-simhash-algorithm/) and install simhash and test it with two files that are similar together and prove that you can find similar contents. Challenge 3: use the information you have gained so far to create a program that asks the user for a topic and search the https://icanhazdadjoke.com and if it finds more than one jokes, then it randomly chooses one of those and shows it to the user. If it finds one, it shows: If it does not find any joke it says: Challenge 4: Write a program to count a number of files for each extension in the given directory. The program should take a directory name as argument and print count and extension for each available file extension. For example, the output would be something like this: python counter.py \yourpathhere 14 py 4 txt 1 csv Challenge 5: familiarize yourself with the “re” module (https://docs.python.org/3/library/re.html). It is an abbreviation for the Regular Expression. They are used to find a string with a specific pattern. For example, the phone numbers in Toronto have 10 digits and they have this format xxx-yyy-wwww Use the re module to check if the user has entered a valid phone number that follows the above-mentioned pattern. Day 10 LRU Implement an LRU (least recently used) cache (30 Marks): The LRU is a common caching strategy which defines policy to evict elements from a cache to make room for the new elements when the cache is full, i.e., discards the least recently used items first. To solve this question, you should assume your cache has a specific size. You will need to implement insert to cache and eviction from cache as part of your implementation. Solution Approach: Let’s assume your cache size=4. The first four values are stored in the cache one after another. 1 2 3 4 When it is time to store the 5th value, one of them has to evicted to open room for the 5th element. In this case element “1” is the least recently used (since it was the first stored element in the cache). After the eviction, the cache has the following elements: 5 2 3 4 Now if the element “2” is accessed, its timestamp also changed to one of the recently accessed elements: 5 2 3 4 If we need to store a new element “6”, the least recently element would be “3” since the “5”, “2” and “4” elements are accessed /stored after “3”: 5 2 6 4 Hint: You need to implement two data structures to solve this problem. The first one implements the cache itself and the second one keeps track of last access times for each element in the first data structure. The eviction function searches inside the second data structure to find the qualified item and update the first data structure with the new element. After insertion, the second data structure has to be updated with a new timestamp for the inserted item. Give us instructions in your code (in the form of comments) how to test your code. 1- Merging Intervals (40 Marks): You are given a task to calculate the overall time for execution of a task, given the intervals of subtasks. In the other word, given the list of intervals as input where each interval has a start and end timestamps, you are required to merge the overlapping intervals and return the output list. The input is “sorted” by starting timestamps. For example, consider the input list of intervals (1, 5), (3, 7), (4, 6), (6, 8). When your program runs against this list, it merges the interval to a bigger interval (1, 8). Similarly, intervals (10, 12) and (12, 15) are also overlapping intervals and is merged to (10, 15). Sample input: lst = [pair(2,10),pair(4, 12), pair(13,16), pair(19,20), pair(20,24)] Sample output: (2,24) Give us instructions in your code (in the form of comments) how to test your code. 2- Finding the meeting point (30 Marks): Given N people on MxM grid, find the point that requires the least total distance covered by all the people to meet at that point. For example, consider a 5x5 grid with three people at P(1,2), Q(3,3) and R(4,2). X is the horizontal axis, and Y is the vertical axis: 1 2 3 4 5 1 2 P R 3 Q 4 5 We need to find the meeting point(x,y) for these people where the total distance covered by all three is the minimum. They can travel in all directions, i.e., horizontally, vertically and diagonally. Hint: For small grids, a brute force approach works. In the brute force approach, we select each empty cell and then find the Euclidean distance ( ) between each empty cell with occupied cells. Then we find the minimum of those distances. However, for big grids that would not work. The reasons are A) there are many cells for distance calculation and B) intuitively we know that the meet point is somewhere close to the occupied points but still in brute force, we calculate the distance for all the empty cells (for example, why should we calculate the distance to cell (5,5)? We know that it cannot be an answer in our case). A better solution uses the 'centroid' to find the minimum distance traveled point. The centroid of a two-dimensional region is the arithmetic mean or average position of all the points. We can calculate the centroid of all the points with people on the grid, and that will be the minimum distance traveled point. It can be calculated as follows: centroid=(​x1+x2+x3+...+xn/n​​, ​​y1+y2+y3+...+yn/n​​) You should also be aware that there are scenarios that the meet point is one of the people points. Give us instructions in your code (in the form of comments) how to test your code.