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]

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

Problem: Given two sorted arrays a (size n) and b (size m) of integers, find the median value. Hint: The time complexity should be O(log (m+n)).

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 words word_start and word_end, find shortest sequence of words from word_start to word_end, such that:
- in each consequitive word only one letter is changed
- all intermediate words exist in the given dictionary

Solution: the find the shortest path we usually use breadth-first-search (or Dijkstra in weighted graph). How do we build a graph? We can precompute neighbors for all words in O(n^2L^2), where L is the maximum length of words. Alternatively, we can create a hash-map, which maps from words with one wildcard to matching words. E.g. *at -> bat, cat.

Problem: Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

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.

List of most asked Programming Interview Questions.

Are you preparing for a coding interview? This tweet is for you. It contains a list of the most asked interview questions from each topic.

Arrays

- How is an array sorted using quicksort?
- How do you reverse an array?
- How do you remove duplicates from an array?
- How do you find the 2nd largest number in an unsorted integer array?

Linked Lists

- How do you find the length of a linked list?
- How do you reverse a linked list?
- How do you find the third node from the end?
- How are duplicate nodes removed in an unsorted linked list?

Strings

- How do you check if a string contains only digits?
- How can a given string be reversed?
- How do you find the first non-repeated character?
- How do you find duplicate characters in strings?

Binary Trees

- How are all leaves of a binary tree printed?
- How do you check if a tree is a binary search tree?
- How is a binary search tree implemented?
- Find the lowest common ancestor in a binary tree?

Graph

- How to detect a cycle in a directed graph?
- How to detect a cycle in an undirected graph?
- Find the total number of strongly connected components?
- Find whether a path exists between two nodes of a graph?
- Find the minimum number of swaps required to sort an array.

Dynamic Programming

1. Find the longest common subsequence?
2. Find the longest common substring?
3. Coin change problem?
4. Box stacking problem?
5. Count the number of ways to cover a distance?

Good websites to Practice Python
👇👇
https://www.hackerrank.com
http://www.practicepython.org/