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]
[Answer will be posted within one hour]
👍2❤1
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).
👍4
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
- 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?
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?
👍7🥰1
10 Ways to Speed Up Your Python Code
1. List Comprehensions
numbers = [x**2 for x in range(100000) if x % 2 == 0]
instead of
numbers = []
for x in range(100000):
if x % 2 == 0:
numbers.append(x**2)
2. Use the Built-In Functions
Many of Python’s built-in functions are written in C, which makes them much faster than a pure python solution.
3. Function Calls Are Expensive
Function calls are expensive in Python. While it is often good practice to separate code into functions, there are times where you should be cautious about calling functions from inside of a loop. It is better to iterate inside a function than to iterate and call a function each iteration.
4. Lazy Module Importing
If you want to use the time.sleep() function in your code, you don't necessarily need to import the entire time package. Instead, you can just do from time import sleep and avoid the overhead of loading basically everything.
5. Take Advantage of Numpy
Numpy is a highly optimized library built with C. It is almost always faster to offload complex math to Numpy rather than relying on the Python interpreter.
6. Try Multiprocessing
Multiprocessing can bring large performance increases to a Python script, but it can be difficult to implement properly compared to other methods mentioned in this post.
7. Be Careful with Bulky Libraries
One of the advantages Python has over other programming languages is the rich selection of third-party libraries available to developers. But, what we may not always consider is the size of the library we are using as a dependency, which could actually decrease the performance of your Python code.
8. Avoid Global Variables
Python is slightly faster at retrieving local variables than global ones. It is simply best to avoid global variables when possible.
9. Try Multiple Solutions
Being able to solve a problem in multiple ways is nice. But, there is often a solution that is faster than the rest and sometimes it comes down to just using a different method or data structure.
10. Think About Your Data Structures
Searching a dictionary or set is insanely fast, but lists take time proportional to the length of the list. However, sets and dictionaries do not maintain order. If you care about the order of your data, you can’t make use of dictionaries or sets.
1. List Comprehensions
numbers = [x**2 for x in range(100000) if x % 2 == 0]
instead of
numbers = []
for x in range(100000):
if x % 2 == 0:
numbers.append(x**2)
2. Use the Built-In Functions
Many of Python’s built-in functions are written in C, which makes them much faster than a pure python solution.
3. Function Calls Are Expensive
Function calls are expensive in Python. While it is often good practice to separate code into functions, there are times where you should be cautious about calling functions from inside of a loop. It is better to iterate inside a function than to iterate and call a function each iteration.
4. Lazy Module Importing
If you want to use the time.sleep() function in your code, you don't necessarily need to import the entire time package. Instead, you can just do from time import sleep and avoid the overhead of loading basically everything.
5. Take Advantage of Numpy
Numpy is a highly optimized library built with C. It is almost always faster to offload complex math to Numpy rather than relying on the Python interpreter.
6. Try Multiprocessing
Multiprocessing can bring large performance increases to a Python script, but it can be difficult to implement properly compared to other methods mentioned in this post.
7. Be Careful with Bulky Libraries
One of the advantages Python has over other programming languages is the rich selection of third-party libraries available to developers. But, what we may not always consider is the size of the library we are using as a dependency, which could actually decrease the performance of your Python code.
8. Avoid Global Variables
Python is slightly faster at retrieving local variables than global ones. It is simply best to avoid global variables when possible.
9. Try Multiple Solutions
Being able to solve a problem in multiple ways is nice. But, there is often a solution that is faster than the rest and sometimes it comes down to just using a different method or data structure.
10. Think About Your Data Structures
Searching a dictionary or set is insanely fast, but lists take time proportional to the length of the list. However, sets and dictionaries do not maintain order. If you care about the order of your data, you can’t make use of dictionaries or sets.
👍2❤1
Python interview questions 😍😍
What is Python?
Python is an interpreted, object-oriented, high-level programming language with dynamic semantics, automatic memory management.
What's the difference between a tuple and a list?
Both tuples and lists are data structures in Python and hold a list of values. Unlike lists, tuples are immutable - they can't be changed.
What is a dict and what's its most important limitation?
A dict is a structure akin a hash map. It stores key-value pairs, where keys are unique and it has O(1) access time. The most important limitation for a dict is that the keys must be hashable/immutable. Meaning, we can use a tuple as a key, but not a list.
What is pickling/unpickling?
Pickling is converting an object to a string representation in python. Generally used for caching and transferring objects between hosts/processes.
Is Python a Scripting Language?
Python is capable of scripting, but it is more than that. It is considered as a general-purpose programming language.
What is Python?
Python is an interpreted, object-oriented, high-level programming language with dynamic semantics, automatic memory management.
What's the difference between a tuple and a list?
Both tuples and lists are data structures in Python and hold a list of values. Unlike lists, tuples are immutable - they can't be changed.
What is a dict and what's its most important limitation?
A dict is a structure akin a hash map. It stores key-value pairs, where keys are unique and it has O(1) access time. The most important limitation for a dict is that the keys must be hashable/immutable. Meaning, we can use a tuple as a key, but not a list.
What is pickling/unpickling?
Pickling is converting an object to a string representation in python. Generally used for caching and transferring objects between hosts/processes.
Is Python a Scripting Language?
Python is capable of scripting, but it is more than that. It is considered as a general-purpose programming language.
👍2
Explain the features of Python / Say something about the benefits of using Python?
Python is a MUST for students and working professionals to become a great Software Engineer specially when they are working in Web Development Domain. I will list down some of the key advantages of learning Python:
○ Simple and easy to learn:
* Learning python programming language is easy and fun.
* Compared to other language, like, Java or C++, its syntax is a way lot easier.
* You also don’t have to worry about the missing semicolons (;) in the end!
* It is more expressive means that it is more understandable and readable.
* Python is a great language for the beginner-level programmers.
* It supports the development of a wide range of applications from simple text processing to WWW browsers to games.
* Easy-to-learn − Python has few keywords, simple structure, and a clearly defined syntax. This makes it easy for Beginners to pick up the language quickly.
* Easy-to-read − Python code is more clearly defined and readable. It's almost like plain and simple English.
* Easy-to-maintain − Python's source code is fairly easy-to-maintain.
Features of Python
○ Python is Interpreted −
* Python is processed at runtime by the interpreter.
* You do not need to compile your program before executing it. This is similar to PERL and PHP.
○ Python is Interactive −
* Python has support for an interactive mode which allows interactive testing and debugging of snippets of code.
* You can open the interactive terminal also referred to as Python prompt and interact with the interpreter directly to write your programs.
○ Python is Object-Oriented −
* Python not only supports functional and structured programming methods, but Object Oriented Principles.
○ Scripting Language —
* Python can be used as a scripting language or it can be compliled to byte-code for building large applications.
○ Dynammic language —
* It provides very high-level dynamic data types and supports dynamic type checking.
○ Garbage collection —
* Garbage collection is a process where the objects that are no longer reachable are freed from memory.
* Memory management is very important while writing programs and python supports automatic garbage collection, which is one of the main problems in writing programs using C & C++.
○ Large Open Source Community —
* Python has a large open source community and which is one of its main strength.
* And its libraries, from open source 118 thousand plus and counting.
* If you are stuck with an issue, you don’t have to worry at all because python has a huge community for help. So, if you have any queries, you can directly seek help from millions of python community members.
* A broad standard library − Python's bulk of the library is very portable and cross-platform compatible on UNIX, Windows, and Macintosh.
* Extendable − You can add low-level modules to the Python interpreter. These modules enable programmers to add to or customize their tools to be more efficient.
○ Cross-platform Language —
* Python is a Cross-platform language or Portable language.
* Python can run on a wide variety of hardware platforms and has the same interface on all platforms.
* Python can run on different platforms such as Windows, Linux, Unix and Macintosh etc.
👍5
PYTHON INTERVIEW QUESTIONS
1 what is python ?
2 why python ?
3 what are advantage of python ?
4 what is pep 8 ?
5. What do you mean by literal ?
6 explain python function ?
7 what is use of break statement ?
8 what is tuple ?
9 python libraries /module ?
10. What is an in operator in python ?
11 why python interpreted ?
12 how is memory managed in python ?
13 python decorator ?
14 global variable / local variable ?
15 what is iterators in python ?
16 what is slicing in python ?
17 what is a dictionary in python ?
18 what is pass in python ?
19 what isinit ?
20 what is self in python ?
Most important for Technical round interview.
1 what is python ?
2 why python ?
3 what are advantage of python ?
4 what is pep 8 ?
5. What do you mean by literal ?
6 explain python function ?
7 what is use of break statement ?
8 what is tuple ?
9 python libraries /module ?
10. What is an in operator in python ?
11 why python interpreted ?
12 how is memory managed in python ?
13 python decorator ?
14 global variable / local variable ?
15 what is iterators in python ?
16 what is slicing in python ?
17 what is a dictionary in python ?
18 what is pass in python ?
19 what isinit ?
20 what is self in python ?
Most important for Technical round interview.
👍4
This is an amazing opportunity to test your coding skills
Try to be in Top 1000 to claim amazing Rewards 👍👍
Try to be in Top 1000 to claim amazing Rewards 👍👍
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.
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.
PREPARING FOR AN ONLINE INTERVIEW?
10 basic tips to consider when invited/preparing for an online interview:
1. Get to know the online technology that the interviewer(s) will use. Is it a phone call, WhatsApp, Skype or Zoom interview? If not clear, ask.
2. Familiarize yourself with the online tools that you’ll be using. Understand how Zoom/Skype works and test it well in advance. Test the sound and video quality.
3. Ensure that your internet connection is stable. If using mobile data, make sure it’s adequate to sustain the call to the end.
4. Ensure the lighting and the background is good. Remove background clutter. Isolate yourself in a place where you’ll not have any noise distractions.
5. For Zoom/Skype calls, use your desktop or laptop instead of your phone. They’re more stable especially for video calls.
6. Mute all notifications on your computer/phone to avoid unnecessary distractions.
7. Ensure that your posture is right. Just because it’s a remote interview does not mean you slouch on your couch. Maintain an upright posture.
8. Prepare on the other job specifics just like you would for a face-to-face interview
9. Dress up like you would for a face-to-face interview.
10. Be all set at least 10 minutes to the start of interview.
10 basic tips to consider when invited/preparing for an online interview:
1. Get to know the online technology that the interviewer(s) will use. Is it a phone call, WhatsApp, Skype or Zoom interview? If not clear, ask.
2. Familiarize yourself with the online tools that you’ll be using. Understand how Zoom/Skype works and test it well in advance. Test the sound and video quality.
3. Ensure that your internet connection is stable. If using mobile data, make sure it’s adequate to sustain the call to the end.
4. Ensure the lighting and the background is good. Remove background clutter. Isolate yourself in a place where you’ll not have any noise distractions.
5. For Zoom/Skype calls, use your desktop or laptop instead of your phone. They’re more stable especially for video calls.
6. Mute all notifications on your computer/phone to avoid unnecessary distractions.
7. Ensure that your posture is right. Just because it’s a remote interview does not mean you slouch on your couch. Maintain an upright posture.
8. Prepare on the other job specifics just like you would for a face-to-face interview
9. Dress up like you would for a face-to-face interview.
10. Be all set at least 10 minutes to the start of interview.
👍2
How long are coding interviews?
The phone screen portion of the coding interview typically lasts up to one hour. The second, more technical part of the interview can take multiple hours.
Where can I practice coding?
There are many ways to practice coding and prepare for your coding interview. LeetCode provides practice opportunities in more than 14 languages and more than 1,500 sample problems. Applicants can also practice their coding skills and interview prep with HackerRank.
How do I know if my coding interview went well?
There are a variety of indicators that your coding interview went well. These may include going over the allotted time, being introduced to additional team members, and receiving a quick response to your thank you email.
The phone screen portion of the coding interview typically lasts up to one hour. The second, more technical part of the interview can take multiple hours.
Where can I practice coding?
There are many ways to practice coding and prepare for your coding interview. LeetCode provides practice opportunities in more than 14 languages and more than 1,500 sample problems. Applicants can also practice their coding skills and interview prep with HackerRank.
How do I know if my coding interview went well?
There are a variety of indicators that your coding interview went well. These may include going over the allotted time, being introduced to additional team members, and receiving a quick response to your thank you email.
👍5