Top ten programming interview questions visited
Today I found a list of problems discussed as the most often asked interview questions and could not resist bringing them up here albeit briefly:
They are:
Evaluate Reverse Polish Notation, Longest Palindromic Substring, Word Break,
Word Ladder, Median of Two Sorted Arrays, Regular Expression Matching, Merge Intervals, Insert
Interval, Two Sum, 3Sum, String to Integer, Merge Sorted Array, Valid Parentheses, Implement
strStr()(), Set Matrix Zeroes.
SetMatrixZeroes - Given a m * n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Hint: Use the first row and first column to mark the zero row and column. We only need to remember what the final states for first row and column should be, then we can use the markings there to flip the values.
Implement strStr() Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Hint: Use O(N^2) naive implementation or a pattern matching algorithm such as KMP or the matchHere() method discussed earlier in this blog.
Valid Parentheses: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. Hint: Use a map with key-values as opening and closing brackets respectively and a stack for the occurrences pushing the opening and checking the values.
Merge sorted array - There are two sorted arrays that need to be merged into one. If you order the arrays by their lengths, you can have fewer instructions for your code.
StringToInteger Here the first character could be + or - aside from the edge cases. The regular representation can then multiply the result by 10 and add the next character.
3Sum - Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Hint: Use combinations that are 3 integers long and then select the ones that sum to zero.
2Sum - This does not involves generating combinations because the complement of the current number can be found as O(N^2).
InsertInterval - Insert into non-overlapping ranges, merge if necessary. Hint: By insertion we handle the cases when an overlap with the current range. If there are more than one range that has overlap with the new, we split the new range at the point where the start of an existing range occurs in the new.
void Merge(Tuple<int, int> current, Tuple<int, int> new)
{
assert (previous.overlap(new));
var insert = new Tuple<int,int>{ Math.min(previous.first, new.first, previous.), Math.max(previous.second, math.second))}
return insert;
}
MergeIntervals - Given a collection of intervals, merge all overlapping intervals.
This does not involve O(N^2). We could do it linear if we keep the ranges sorted with a comparator that checks the start of each element. Then we can find out the ends that overlap and merge as above.
Regular Expression Matching - There is a LeetCode solution for this that handles the pattern lengths 0 and 1 separately and case as follows:
int len = s.length();
int i = -1;
while(i<len&& (I < 0 || p.charAt(0) == '.' || p.CharAt(0) == s.charAt(I))){
if (isMatch(s.substring(I+1), p.substring(2)))
return true;
i++;
}
return false;
Median of two sorted arrays - This was already discussed in the previous post.
WordLadder: Given a dictionary find the minimum of one-letter substitution transformations between one word to another. Breadthfirst traversal will help with the tree search to get from one node to another.
wordbreak - this was already discussed. The Leetcode solution suggests a dynamic approach with
Define an array t[s.length+1] such that t[i]==true => 0-(i-1) can be segmented using dictionary
Initial state t[0] == true
for(int i=0; i<s.length(); i++){
//should continue from match position
if(!t[i])
continue;
for(String a: dict){
int len = a.length();
int end = i + len;
if(end > s.length())
continue;
if(t[end]) continue;
if(s.substring(i, end).equals(a)){
t[end] = true;
}
}
}
return t[s.length()];
Longest Palindromic substring already covered in previous post
Reverse polish notation - Here we use a stack and push the numerals. When we encounter an operator, we pop the stack and apply the operation.
Today I found a list of problems discussed as the most often asked interview questions and could not resist bringing them up here albeit briefly:
They are:
Evaluate Reverse Polish Notation, Longest Palindromic Substring, Word Break,
Word Ladder, Median of Two Sorted Arrays, Regular Expression Matching, Merge Intervals, Insert
Interval, Two Sum, 3Sum, String to Integer, Merge Sorted Array, Valid Parentheses, Implement
strStr()(), Set Matrix Zeroes.
SetMatrixZeroes - Given a m * n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Hint: Use the first row and first column to mark the zero row and column. We only need to remember what the final states for first row and column should be, then we can use the markings there to flip the values.
Implement strStr() Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Hint: Use O(N^2) naive implementation or a pattern matching algorithm such as KMP or the matchHere() method discussed earlier in this blog.
Valid Parentheses: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. Hint: Use a map with key-values as opening and closing brackets respectively and a stack for the occurrences pushing the opening and checking the values.
Merge sorted array - There are two sorted arrays that need to be merged into one. If you order the arrays by their lengths, you can have fewer instructions for your code.
StringToInteger Here the first character could be + or - aside from the edge cases. The regular representation can then multiply the result by 10 and add the next character.
3Sum - Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Hint: Use combinations that are 3 integers long and then select the ones that sum to zero.
2Sum - This does not involves generating combinations because the complement of the current number can be found as O(N^2).
InsertInterval - Insert into non-overlapping ranges, merge if necessary. Hint: By insertion we handle the cases when an overlap with the current range. If there are more than one range that has overlap with the new, we split the new range at the point where the start of an existing range occurs in the new.
void Merge(Tuple<int, int> current, Tuple<int, int> new)
{
assert (previous.overlap(new));
var insert = new Tuple<int,int>{ Math.min(previous.first, new.first, previous.), Math.max(previous.second, math.second))}
return insert;
}
MergeIntervals - Given a collection of intervals, merge all overlapping intervals.
This does not involve O(N^2). We could do it linear if we keep the ranges sorted with a comparator that checks the start of each element. Then we can find out the ends that overlap and merge as above.
Regular Expression Matching - There is a LeetCode solution for this that handles the pattern lengths 0 and 1 separately and case as follows:
int len = s.length();
int i = -1;
while(i<len&& (I < 0 || p.charAt(0) == '.' || p.CharAt(0) == s.charAt(I))){
if (isMatch(s.substring(I+1), p.substring(2)))
return true;
i++;
}
return false;
Median of two sorted arrays - This was already discussed in the previous post.
WordLadder: Given a dictionary find the minimum of one-letter substitution transformations between one word to another. Breadthfirst traversal will help with the tree search to get from one node to another.
wordbreak - this was already discussed. The Leetcode solution suggests a dynamic approach with
Define an array t[s.length+1] such that t[i]==true => 0-(i-1) can be segmented using dictionary
Initial state t[0] == true
for(int i=0; i<s.length(); i++){
//should continue from match position
if(!t[i])
continue;
for(String a: dict){
int len = a.length();
int end = i + len;
if(end > s.length())
continue;
if(t[end]) continue;
if(s.substring(i, end).equals(a)){
t[end] = true;
}
}
}
return t[s.length()];
Longest Palindromic substring already covered in previous post
Reverse polish notation - Here we use a stack and push the numerals. When we encounter an operator, we pop the stack and apply the operation.
