Solution: Basically, each rectangle is represented by two segments on X and Y axes. Rectangles overlap if both segments overlap. Then we can compute the coordintates of vertices of the intersection by combining coordinate of left and right points of segment intersections. There is a good explanation of this idea here: https://www.interviewcake.com/question/java/rectangular-love

Solution: The first idea is to enumerate all permutations (either in lexicographical order, or sort them afterwards) and return the k-th one. But this is quite inefficient. Do we really need to generate permutations we don't care about? E.g. what if we need to return the last permutation of a string "abcd" do we need to generate permutations that start with "a"? Probably not, but can we compute what element the k-th permutation will start with? How many permutations will start with the smallest element in the array? The answer is (n-1)! Therefore, we can compute the first element of the permutation we need to compute. But wait, can we do the same for the second character? Yes we can! The number of permutations that start with the fixed first two characters are (n-2)!. So all we need to do is starting with the first character, compute what character will be on each position in the k-th permutation.

Problem: given a sorted array of integers (not necessarily positive) return a sorted array of squares of these integers.

Solution: If the array only contained positive integers the sorted array of squares would have the same order. When we also have negative numbers their squares would interleave with squares of positive numbers. But nevertheless we have the following property: |a_i| < |a_j| => a_i^2 < a_j^2. Therefore, the smallest square would come from the smallest absolute value. We can find zero (or the place where sign of numbers change) in the original array (using binary search) and then maintain two indexes to the current negative and positive candidates. On each step we check which of these numbers have smaller absolute value and add its square to the result, while advancing the corresponding index (backwards for negatives and forward for positives).

Solution: A good first attempt is to realize that whenever we are dealing with sums over segments in array, we can precompute partials sums from 0 to i and then easily compute a sum on any interval as sum[i] - sum[j-1]. Using this approach we can iterate over all possible left ends of the interval and then find the right, which gives the sum closest to the given T. To do this we realize that since we only have positive integers, the sum will only increase as the interval get longer. Thus we can do binary search to find the right end. This gives us O(nlogn) solution. But we can do better. Let's start with some interval and try to grow/shrink it to make its sum closer to T. If the current sum is less than T, we know we need to grow the segment, so we move the right boundary. If the current sum is less than T we increment the left boundary. We can start with a segment that only contains a single left-most element and work our way to the right by constantly shifting either left or right end of the segment.

Solution: In linear time we could simply do merge sort until we reach the median elements. But when we need to achieve log-time we usually start thinking about divide and conquer type of strategies. Let's take a longer array and choose it's middle element. Let's search for it in the other array using binary search. Let position of the first element that is greater than the given number be pos. Then we can see that in total in both arrays there are mid + pos elements, that are less than or equals to the given element. Is it less than (n + m) / 2? If it's, than the median lies somewhere either to the right of mid and pos in the first and second arrays correspondingly. Otherwise, it's to the left of mid and pos correspondingly and we can simply repeat the process. On each such iteration we are eliminating at least n/2 elements by taking middle of a larger array, thus we achieve log-time complexity.

Problem: Given an array a of n integers, find all such elements a[i], a[j], a[k], and a[l], such that a[i] + a[j] + a[k] + a[l] = target? Output all unique quadruples.

Solution: of course one way would be to just use 4 nested loops to iterate over all possible quadruples, but this is quite slow O(n^4). Another way is to iterate over all triples, put the sums into a set and then in another pass over elements a[i] check if we have any triple with sum (T - a[i]). This would give us O(n^3), and we need to keep track of which elements gave us the required sums. Another step is to iterate over all pairs and put results into a map from integer to indexes of elements, which produce this sum. Then in another pass over this map we can see if we can get a sum of T using two different values from the map (and they shouldn't be using the same element twice). This approach has time complexity O(n^2).

Top 10 Sites to review your resume for free:

1. Zety Resume Builder
2. Resumonk
3. Free Resume Builder
4. VisualCV
5. Cvmaker
6. ResumUP
7. Resume Genius
8. Resumebuilder
9. Resume Baking
10. Enhancv

Coding is tricky. Coding in interviews feels even harder. It’s intimidating, uncertain and hard to prepare. Here are 4 ways to do it!

1. Interview Cake: I think it is some of the best prep available and it is targeted toward weaknesses many data scientists have in algorithms and data structures: https://www.interviewcake.com/

2. Leetcode: While developed for software engineering interviews, it has a LOT of useful content for learning algorithms. For data science, I'd suggest focusing on Easy/Medium: https://leetcode.com/

3. Cracking the Coding Interview: Amazing book, sometimes referred to as CTCI. A classic and one you should have: https://cin.ufpe.br/~fbma/Crack/Cracking%20the%20Coding%20Interview%20189%20Programming%20Questions%20and%20Solutions.pdf

4. Daily Coding Problem: The book and the website are awesome. Work on a daily problem. This was my go to resource for when I was looking to stay sharp: https://www.dailycodingproblem.com/

Student Program that will help you lot :

1. Microsoft Learn Student Ambassadors :
https://studentambassadors.microsoft.com/

2 .Facebook Developer Circles :
https://developers.facebook.com/developercircles/join/

3.Pie and AI Student Ambassador (deeplearning.ai) :
https://docs.google.com/forms/d/e/1FAIpQLSdyztghL5bLnktJLP6YG2GU65E8IEpGR_o937CxEwxdemNcHA/viewform

4.Agora :
https://docs.google.com/forms/d/e/1FAIpQLSck0MBbicJF4NoqF8r0vfK6F8A_HnMwwTN-SFQjKl1ppXZ6MA/viewform


5.GeeksForGeeks Campus Mantri :
https://www.geeksforgeeks.org/campus-ambassador-program-by-geeksforgeeks/

6.Intel Student Innovator :
https://devmesh.intel.com/member-programs/intel-software-innovator-program

Solution: Every pair of points on a plane define a line that passes through them. One approach is to iterate over each pair of points, find a line that passes through them and check how many of the other points lie on this line. This solution will be O(n^3). We can do better if we reformulate our approach a little bit. Let's say we found lines that pass through every pair of points. Some of them might be the same. E.g. if there is a line that passes through 3 points a,b,c, than lines that pass through a-b, b-c and a-c will coincide. So, we can count how many lines coincide and calculate the number of points that this line pass through. To find lines, that coincide, we can put them in hash map. The only problem is numeric instability, i.e. when dealing with floating point numbers it's likely we won't get lines, whose coefficients match exactly. One way to solve it is to use buckets of size \epsilon. Then we need to iterate over lines that are inside a bucket and check how many of them are actually the same.

Best suited IDE's for programming languages:

1. JavaScript => VSCode
2. Python => PyCharm
3. C# => Visual Studio
4. Java => IntelliJ IDEA
5. Ruby => Ruby Mine
6. C & C++ => CLion

DSA INTERVIEW QUESTIONS AND ANSWERS

1. What is the difference between file structure and storage structure?
The difference lies in the memory area accessed. Storage structure refers to the data structure in the memory of the computer system,
whereas file structure represents the storage structure in the auxiliary memory.

2. Are linked lists considered linear or non-linear Data Structures?
Linked lists are considered both linear and non-linear data structures depending upon the application they are used for. When used for
access strategies, it is considered as a linear data-structure. When used for data storage, it is considered a non-linear data structure.

3. How do you reference all of the elements in a one-dimension array?
All of the elements in a one-dimension array can be referenced using an indexed loop as the array subscript so that the counter runs
from 0 to the array size minus one.

4. What are dynamic Data Structures? Name a few.
They are collections of data in memory that expand and contract to grow or shrink in size as a program runs. This enables the programmer
to control exactly how much memory is to be utilized.Examples are the dynamic array, linked list, stack, queue, and heap.

5. What is a Dequeue?
It is a double-ended queue, or a data structure, where the elements can be inserted or deleted at both ends (FRONT and REAR).

6. What operations can be performed on queues?
enqueue() adds an element to the end of the queue
dequeue() removes an element from the front of the queue
init() is used for initializing the queue
isEmpty tests for whether or not the queue is empty
The front is used to get the value of the first data item but does not remove it
The rear is used to get the last item from a queue.

7. What is the merge sort? How does it work?
Merge sort is a divide-and-conquer algorithm for sorting the data. It works by merging and sorting adjacent data to create bigger sorted
lists, which are then merged recursively to form even bigger sorted lists until you have one single sorted list.

8.How does the Selection sort work?
Selection sort works by repeatedly picking the smallest number in ascending order from the list and placing it at the beginning. This process is repeated moving toward the end of the list or sorted subarray.

Scan all items and find the smallest. Switch over the position as the first item. Repeat the selection sort on the remaining N-1 items. We always iterate forward (i from 0 to N-1) and swap with the smallest element (always i).

Time complexity: best case O(n2); worst O(n2)

Space complexity: worst O(1)

9. What are the applications of graph Data Structure?
Transport grids where stations are represented as vertices and routes as the edges of the graph
Utility graphs of power or water, where vertices are connection points and edge the wires or pipes connecting them
Social network graphs to determine the flow of information and hotspots (edges and vertices)
Neural networks where vertices represent neurons and edge the synapses between them

10. What is an AVL tree?
An AVL (Adelson, Velskii, and Landi) tree is a height balancing binary search tree in which the difference of heights of the left
and right subtrees of any node is less than or equal to one. This controls the height of the binary search tree by not letting
it get skewed. This is used when working with a large data set, with continual pruning through insertion and deletion of data.

11. Differentiate NULL and VOID ?
Null is a value, whereas Void is a data type identifier
Null indicates an empty value for a variable, whereas void indicates pointers that have no initial size
Null means it never existed; Void means it existed but is not in effect

You can check these resources for Coding interview Preparation

Credits: https://t.me/free4unow_backup

All the best 👍👍

Problem: Given an array a of n integers, find all such elements a[i], a[j], a[k], and a[l], such that a[i] + a[j] + a[k] + a[l] = target? Output all unique quadruples.

[Answer will be posted within one hour]