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

Question: You have two sorted arrays A and B. Array A actually has some empty elements at the end, that would fit B. How to merge A and B together in sorted order?

Solution: typically, when we need to combine multiple sorted sequences into one we use merge sort. However, if we start from the beginning of A and B and store result in A we would have to move elemenets. But we can start merge sort from the end of arrays, thus filling in empty spaces in A.

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