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;
}
