Coding Questions Flashcards
Product of Array Except Self
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
Trick is to create two arrays with left product and right product, where left product of an element at ith position in the array will contain product of elements from 0 to i-1. Similarly right will contain n to i+1.
Then multiple left and right array and result will contain answer
TrieNode
class TrieNode {
TrieNode[] children;
String word;
TrieNode() {
children = new TrieNode[26];
}
}Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Sort by start and check if overlaps with next and change end time
Missed cases could be - if the current intervals end time is greater than next intervals end time
public int[][] merge(int[][] intervals) {
if(intervals == null || intervals.length == 0) return intervals;
Queue queue = new PriorityQueue<>( (a,b) -> {
return a[0] - b[0];
});
for(int [] interval : intervals) {
queue.add(interval);
}
List list = new ArrayList<>();
int[] curr = queue.remove();
while(!queue.isEmpty()) {
int[] next = queue.remove();
if(curr[1] >= next[0]) {
curr[1] = Math.max(curr[1],next[1]);
} else {
list.add(curr);
curr = next;
}
}
list.add(curr);
int[][] result = new int[list.size()][2];
for(int i=0; i
Trick for solving linked list
Create a dummy node and use it to point to head
Task Scheduler
Finding the idle timeout will determine the total time required. For example if there is one task to be executed thrice and the cool down period is 5 then total time required for the CPU to finish would be 13 (1+5+1+5+1).
Therefore idle time = 10
If there were another task to be executed twice then idle time would be 10-2 = 8, which is 13 (1+1+4+1+1+4+1)
Meeting rooms II, find how minimum meeting rooms required, give the meeting intervals
First approach -
Sort by start time and put the end time in the heap, for every interval check if the start is greater then the last end time. If there is then we can reuse the room or else we need a new room and put the new endtime in the heap.
Second Approach -
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0;
int endsItr = 0;
for(int i=0; i
Car pooling with capacity
public boolean carPooling(int[][] trips, int capacity) {
Map m = new TreeMap<>();
for (int[] t : trips) {
m.put(t[1], m.getOrDefault(t[1], 0) + t[0]);
m.put(t[2], m.getOrDefault(t[2], 0) - t[0]);
}
for (int v : m.values()) {
capacity -= v;
System.out.println(capacity);
if (capacity < 0) {
return false;
}
}
return true;
}
}Find Kth largest number in an array
quickSelect(arr, l, r, kSmallest) {
if(l == r) return arr[l];
int pivot_index = getRandomPivot(l,r);
pi = partition(arr, l, r, pivot_index); if(pi == ksmallest) return arr[pi]; else if(ksmallest < pi) return quick_select(arr, l, pi-1, kSmallest); else return quick_select(arr, pi+1, r, kSmallest); }
int partition(arr, l, r, pi) {
int pivot = arr[pi];
swap(pi, r);
int index = l;
for(int i=l; i<=r; i++) {
if(arr[i] < pivot) {
swap(i, index);
index++;
}
}
swap(index, r)
return index;
Interval Search Tree
Build a BST with start time as the node key and at every node remember the max end interval.
Minimum Remove to Make Valid Parentheses
Needs two iteration one from back and one from start that way in first iteration remove invalid open parentheses if starting from back and in second iteration remove invalid open parentheses from start. Remember to use stack and then stringbuilder to respond
Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Example 1:
Input: “()())()”
Output: [”()()()”, “(())()”]
Example 2:
Input: “(a)())()”
Output: [“(a)()()”, “(a())()”]
Example 3:
Input: “)(“
Output: [””]
1) There is no straight forward DP solution, this needs to be solved in exponential complexity
2) Find the open and close paratheses to remove
3) Keep count of open and close during recursion and verify while inserting into result whether open count is equal to close count
4) While excluding make sure to exclude only if open remaining and close remaining are valid
5) Remember to use set as while recursion you might end up adding same expression multiple times
Graph problems Dijkstra’s - Network Delay Time
There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
public int networkDelayTime(int[][] times, int N, int K) {
Map> map = new HashMap<>();
for(int[] time : times) {
List list = map.getOrDefault(time[0], new ArrayList<>());
list.add(new int[] { time[1], time[2] });
map.put(time[0], list);
}
Map dist = new HashMap<>();
Queue queue = new PriorityQueue<>((a,b) -> {
// sort by weights
return a[1] - b[1];
});
queue.add(new int[] {K, 0});
while(!queue.isEmpty()) {
int[] node = queue.remove();
int u = node[0];
int w = node[1];
if(!dist.containsKey(u)) {
dist.put(u, w);
if(map.containsKey(u)) {
for(int[] edge : map.get(u)) {
int v = edge[0];
int w2 = edge[1];
if(!dist.containsKey(v)) {
queue.add(new int[] {v, w+w2});
}
}
}
}
}
if(dist.size() != N) {
return -1;
}
int max = 0;
for(int w : dist.values()) {
max = Math.max(max, w);
}
return max;
}
Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
“abba”
This is the most important test case, make sure to only consider an index which is found later, in the above case when index of ‘a’ is calculated it becomes to be higher, but ‘b’ appears in between and that needs to be considered.
Remember to add +1 as we are calculating difference between two relative indexes.
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
Longest Palindromic Substring
Medium
6371
508
Add to List
Share
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
You can do better than O(n2), but that is Manchester algorithm, which is difficult to understand and not expected.
Remember to return indices properly, in the below while condition the start and end are one additional left and right to the index, end is fine as when substring is called, it excludes the end character.
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
// throw exception
return "";
}
int max = 0;
int start = 0;
int end = 0;
for(int i=0; i len2 && len1 > max) {
start = i1[0];
end = i1[1];
max = len1;
} else if(len2 > max) {
start = i2[0];
end = i2[1];
max = len2;
}
}
return s.substring(start, end);
}
private int[] expand(String s, int l, int r) {
int start = l;
int end = r;
while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
start--;
end++;
}
return new int[] {start+1, end};
}
Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
The main thing to identify here is the boundary conditions of where to move left or right based on the mid value
public int search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while (start <= end){
int mid = (start + end) / 2;
if (nums[mid] == target)
return mid;
if (nums[start] <= nums[mid]){
if (target < nums[mid] && target >= nums[start])
end = mid - 1;
else
start = mid + 1;
}
if (nums[mid] <= nums[end]){
if (target > nums[mid] && target <= nums[end])
start = mid + 1;
else
end = mid - 1;
}
}
return -1;
}
Course Schedule II, solution is different than question below
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Key point to note, add to queue only if there are no in degree left and decrement in degree as and when encountered
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map> map = new HashMap<>();
int[] indegree = new int[numCourses];
for (int i=0; i list = map.getOrDefault(u, new ArrayList());
list.add(v);
map.put(u, list);
}
Queue queue = new LinkedList();
for (int i=0; i stack = new Stack<>();
while (!queue.isEmpty()) {
int u = queue.poll();
stack.push(u);
if(map.containsKey(u)) {
for(int v : map.get(u)) {
if (--indegree[v] == 0) {
queue.add(v);
}
}
}
}
if(stack.size() != numCourses) {
return new int[]{};
}
int[] result = new int[stack.size()];
int i=0;
while(!stack.isEmpty()) {
result[i++] = stack.pop();
}
return result; }
General approach to backtracking solutions
https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ],
rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ] Example 2:
Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ],
rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]
The obvious idea would be to transpose the matrix first and then reverse each row. This simple approach already demonstrates the best possible time complexity O(N^2)
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// transpose matrix
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int tmp = matrix[j][i];
matrix[j][i] = matrix[i][j];
matrix[i][j] = tmp;
}
}
// reverse each row
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = tmp;
}
}
}
}
Group Anagrams
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note:
All inputs will be in lowercase.
The order of your output does not matter.
Use the count approach where we can create a array of size 26 and we don’t need to sort and form hash by appending some special character after every count
In Java, the hashable representation of our count will be a string delimited with ‘#’ characters. For example, abbccc will be #1#2#3#0#0#0…#0 where there are 26 entries total. In python, the representation will be a tuple of the counts. For example, abbccc will be (1, 2, 3, 0, 0, …, 0), where again there are 26 entries total.
public List> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map ans = new HashMap();
int[] count = new int[26];
for (String s : strs) {
Arrays.fill(count, 0);
for (char c : s.toCharArray()) count[c - 'a']++;
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < 26; i++) {
sb.append('#');
sb.append(count[i]);
}
String key = sb.toString();
if (!ans.containsKey(key)) ans.put(key, new ArrayList());
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
Maximum Product Subarray
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Requires to use there variables
current_max, current_min and max
temp = current_max;
current_max = Math.max(Math.max(current_max*nums[i], current_min * nums[i]), nums[i]);
current_max = Math.min(Math.min(temp*nums[i], current_min * nums[i]), nums[i]);
max = Math.max(max, current_max);
Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5] Example 2:
Input: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] Output: [1,2,3,4,8,12,11,10,9,5,6,7]
public List < Integer > spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0)
return ans;
int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
if (r1 < r2 && c1 < c2) {
for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
}
r1++;
r2--;
c1++;
c2--;
}
return ans;
}Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
public int jump(int[] nums) {
int n = nums.length;
if (n < 2) return 0;
// max position one could reach
// starting from index <= i
int maxPos = nums[0];
// max number of steps one could do
// inside this jump
int maxSteps = nums[0];
int jumps = 1;
for (int i = 1; i < n; ++i) {
// if to reach this point
// one needs one more jump
if (maxSteps < i) {
\++jumps;
maxSteps = maxPos;
}
maxPos = Math.max(maxPos, nums[i] + i);
}
return jumps;
}
Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
This is tricky because we need to cover various test cases -
1) If new interval is before the 1st interval or after last interval
2) If it overlaps with more than one intervals, this boils down to merge interval problem
3) Interval list is empty, this needs to be the only interval which needs to be added
public int[][] insert(int[][] intervals, int[] newInterval) {
if(intervals == null || intervals.length == 0) {
return new int[][]{newInterval};
}
List list = new ArrayList<>();
boolean inserted = false;
int ns = newInterval[0];
int ne = newInterval[1];
for(int[] interval : intervals) {
int s = interval[0];
int e = interval[1];
if(!inserted) {
// new interval is after this interval
if(ns > e) {
list.add(interval);
continue;
}
// new interval is before this interval
if(ne < s) {
list.add(newInterval);
list.add(interval);
inserted = true;
continue;
}
// new interval overlaps with this
interval[0] = Math.min(s, ns);
interval[1] = Math.max(e, ne);
list.add(interval);
inserted = true;
} else {
int[] prev = list.get(list.size()-1);
if(prev[1] >= s) {
prev[1] = Math.max(prev[1], e);
} else {
list.add(interval);
}
}
}
if(!inserted) {
list.add(newInterval);
}
int[][] result = new int[list.size()][2];
for(int i=0; i
Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ] Example 2:
Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ] Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
There is no better solution iterating loop twice, overall complexity is O(mn)
Efficient solution is to make first row and first column for storing zeros (place holder) and in the second iteration set the row, column to zero
public void setZeroes(int[][] matrix) {
Boolean isCol = false;
int R = matrix.length;
int C = matrix[0].length;
for (int i = 0; i < R; i++) {
// Since first cell for both first row and first column is the same i.e. matrix[0][0]
// We can use an additional variable for either the first row/column.
// For this solution we are using an additional variable for the first column
// and using matrix[0][0] for the first row.
if (matrix[i][0] == 0) {
isCol = true;
}
for (int j = 1; j < C; j++) {
// If an element is zero, we set the first element of the corresponding row and column to 0
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// Iterate over the array once again and using the first row and first column, update the elements.
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// See if the first row needs to be set to zero as well
if (matrix[0][0] == 0) {
for (int j = 0; j < C; j++) {
matrix[0][j] = 0;
}
}
// See if the first column needs to be set to zero as well
if (isCol) {
for (int i = 0; i < R; i++) {
matrix[i][0] = 0;
}
}
}
