This summer i spent most of my time preparing for coding interview for my placements, during this time i came across some of the great problems for which thinking the solution was really interesting and fun. So i have picked a few of them and discussed how i approached for the solution.
1.Majority element
Given an array you have to find the element(s) which appears more than n/2 times
This question is fairly easy as there are many methods to solve this.
The first thing that should come to your mind is how many such elements can be there.
The answer is only 1 because, suppose we have 2 elements which occurs more than n/2 times where n is the total number of elements in array then the size of array will become (n/2+x) + (n/2+y)=n+(x+y) which is greater than n (where x and y are both greater than or equal to 1) hence it is not possible to have more than 1 element as the majority element.
since we figured out what output we have to give now the question is how to find this output element, one approach is simply the brute force method where we pick every element one by one and count the number of occurrence in the array and if it is greater than the n/2 we will return it but this is not a good solution if we consider the time complexity, another approach is to use hashmap to keep the count of every element in the array for which we have to first traverse the array and add the key value pair as the array element and it's frequency so far and then traverse the map to find the required element whose value is greater than n/2. This will solve the problem in O(n) but another interesting way to solve this is by using stack which only require one loop traversal in which we add the first element to the stack and start traversing for the rest of the element and apply condition that if top of the stack is not equal to the current element of the array then pop the top element from stack else we push the current element to the stack. After we are done with the traversal of the array, the element at top of the stack is our required majority element because suppose we have length of array as 10 and our array looks like this {2,1,2,2,2,4,2,2,6,2} now apply the above approach and after you are done with the array traversal you will find the top of the stack has element '2' which is our final required answer.
2.Binary Tree Maximum Path Sum
Given a binary tree we have to find the path having the maximum sum where sum is the addition of the values at all the nodes through that path.
A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
This question seems hard at first but once you start thinking about the solution you will realize that it's not that tough of a question. The only catch in this question is that you should be able to figure out that a maximum path of a node can be a single node itself, the node plus it's left sub tree, the node plus it's right sub tree or node plus it's left sub tree plus it's right sub tree hence the solution is nothing but to apply the recursion to every node and keep track of the maximum value
Once you will see the code you will understand everything:
int findPath(Node* root,int &res)
{
if(!root) return 0;
int l=findPath(root->left);
int r=findPath(root->right);
int local_max=max(l,r);
local_max=max(local_max,0);
local_max=local_max + root->val;
res=max(res,local_max);
res=max(res,root->val+l+r);
return local_max;
}
// Main function which return the maximum path sum given the root
int findMaxSum(Node *root)
{
int res=INT_MIN;
findPath(root,res);
return res;
}
3.Minimum Window Substring
Given 2 strings S and T find the minimum window in S having all letters of string T in O(n).
It is quiet clear from the question what we have to do. Let's say S="ADDBECODEBANC and T="ABC" then we have to return a string as "BANC" as it is the smallest substring in S having all the letters of T.
In this i am going to tell my approach through a series of steps:
First, i defined a string 'ans' which we will return and contains the substring of 'S' with minimum window size.
Now,
1) Define an empty array and initialize it with 0;
2) Traverse the string 'T' and increment the count for the respective character in the array.
3) Initialize 4 variables: 'left=0' which will point to the first letter of 'S', 'count=0' which we will increment every time we find a letter in 'S' which is there in 'T' as well, 'min=INT_MAX' which will store the minimum value of the window and finally 'len=T.size()' which will store the length of 'T'.
4) Now we loop through 'S' and every time we encounter a letter in 'S' which is there in 'T' we will increment the count variable by 1
5) After this in the same loop we will compare if the count is equal to len, if yes then we find the length of minimum window as (i-left+1) where i is the current index we are at while traversing 'S' and if it is less than min, we will update min by that minimum length and update ans with substring which begins from 'left' till the 'min' length.
6) Now we increment the left value by 1 and before we do that we have to see if (arr[left]+1>0), if yes than the value at S[left] is also there in 'T' hence decrease the count value by 1 since we will encounter that character again as we move forward in 'S'.
In this way once we complete our traversal of 'S' we will have the minimum window size in variable 'min' and required string in variable 'ans'. The below code will explain all the steps that i mentioned. The time complexity is O(n) where n is the size of string 'S'.
 |
| Minimum Window Substring |
So these 3 were the some of the amazing question i came across, there were many good questions but i randomly picked these 3. I hope it will be helpful and if you didn't understand any part of the code, logic/approach you can comment down below.
Note: There is one more question which i think you should know as this question was asked like 5 to 6 times either in online coding tests or in coding interview. In fact it was even asked in the latest and the final interview which i gave, the question is given an array of numbers and a target value you have to find all pairs of number in the array whose sum is equal to target in O(n).
Try this as this also has many solutions and the best approach will test some of your basic data structure knowledge ;)
