Coding Interview Resources

💥 All Company Placement Materials 💥 🔗 Google Drive Download link : https://drive.google.com/open?id=1oLvYU3uj23fumRNF9IL8yIE4vYIVvvSz

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.

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

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

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.

How to get job as python fresher? 1. Get Your Python Fundamentals Strong You should have a clear understanding of Python syntax, statements, variables & operators, control structures, functions & modules, OOP concepts, exception handling, and various other concepts before going out for a Python interview. 2. Learn Python Frameworks As a beginner, you’re recommended to start with Django as it is considered the standard framework for Python by many developers. An adequate amount of experience with frameworks will not only help you to dive deeper into the Python world but will also help you to stand out among other Python freshers. 3. Build Some Relevant Projects You can start it by building several minor projects such as Number guessing game, Hangman Game, Website Blocker, and many others. Also, you can opt to build few advanced-level projects once you’ll learn several Python web frameworks and other trending technologies. @crackingthecodinginterview 4. Get Exposure to Trending Technologies Using Python. Python is being used with almost every latest tech trend whether it be Artificial Intelligence, Internet of Things (IOT), Cloud Computing, or any other. And getting exposure to these upcoming technologies using Python will not only make you industry-ready but will also give you an edge over others during a career opportunity. 5. Do an Internship & Grow Your Network. You need to connect with those professionals who are already working in the same industry in which you are aspiring to get into such as Data Science, Machine learning, Web Development, etc.

How to get job as python fresher? 1. Get Your Python Fundamentals Strong You should have a clear understanding of Python syntax, statements, variables & operators, control structures, functions & modules, OOP concepts, exception handling, and various other concepts before going out for a Python interview. 2. Learn Python Frameworks As a beginner, you’re recommended to start with Django as it is considered the standard framework for Python by many developers. An adequate amount of experience with frameworks will not only help you to dive deeper into the Python world but will also help you to stand out among other Python freshers. 3. Build Some Relevant Projects You can start it by building several minor projects such as Number guessing game, Hangman Game, Website Blocker, and many others. Also, you can opt to build few advanced-level projects once you’ll learn several Python web frameworks and other trending technologies. @crackingthecodinginterview 4. Get Exposure to Trending Technologies Using Python. Python is being used with almost every latest tech trend whether it be Artificial Intelligence, Internet of Things (IOT), Cloud Computing, or any other. And getting exposure to these upcoming technologies using Python will not only make you industry-ready but will also give you an edge over others during a career opportunity. 5. Do an Internship & Grow Your Network. You need to connect with those professionals who are already working in the same industry in which you are aspiring to get into such as Data Science, Machine learning, Web Development, etc.

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

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

Join this channel to learn Programming and hacking for Free 👇👇 @codingwithsagar

List of most asked Programming Interview Questions. 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?