what is time complexity of following?
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
print(arr[i] + arr[j])
}
}
O(n^2)
n*(n+1)/2.function fn(arr):
left = 0
right = arr.length - 1
while left < right:
// Do some logic here depending on the problem
// Do some more logic here to decide on one of the following:
1. left++
2. right--
3. Both left++ and right--
function fn(arr1, arr2):
i = j = 0
while i < arr1.length AND j < arr2.length:
// Do some logic here depending on the problem
// Do some more logic here to decide on one of the following:
1. i++
2. j++
3. Both i++ and j++
// Step 4: make sure both iterables are exhausted
// Note that only one of these loops would run
while i < arr1.length:
// Do some logic here depending on the problem
i++
while j < arr2.length:
// Do some logic here depending on the problem
j++
while(current>k) current-=arr[left]; left++right - left + 1function fn(arr):
left = 0
for (int right = 0; right < arr.length; right++):
Do some logic to "add" element at arr[right] to window
while WINDOW_IS_INVALID:
Do some logic to "remove" element at arr[left] from window
left++
Do some logic to update the answer
function fn(arr, k):
curr = some data to track the window
// build the first window
for (int i = 0; i < k; i++)
Do something with curr or other variables to build first window
ans = answer variable, probably equal to curr here depending on the problem
for (int i = k; i < arr.length; i++)
Add arr[i] to window
Remove arr[i - k] from window
Update ans
return ans
prefix[j] - prefix[i-1]prefix[j] - prefix[i] + num[i] (if we don't want to deal with out of bound case when i=0)prefix = [nums[0]]
for (int i = 1; i < nums.length; i++)
prefix.append(nums[i] + prefix[i - 1])
[1,2,3,4]
[1,2], [2,3,4][1,3], [1], [3,2,1][1,3], [1], [3,2,1]num%x; final value will be b/w [0, x-1]let map = new Map();
map.set('a', 1);
map.get('a'); // 1
map.has('a'); // true
map.size; // 1
map.delete('a');
let set = new Set();
set.add('a');
set.has('a'); // true
set.size; // 1
set.delete('a');
set -> add
map -> set
let getSum = head => {
let ans = 0;
while (head) {
ans += head.val;
head = head.next;
}
return ans;
}
let addNode = (prevNode, nodeToAdd) => {
nodeToAdd.next = prevNode.next;
prevNode.next = nodeToAdd;
}
let deleteNode = prevNode => {
prevNode.next = prevNode.next.next;
}
let addNode = (node, nodeToAdd) => {
let prevNode = node.prev;
nodeToAdd.next = node;
nodeToAdd.prev = prevNode;
prevNode.next = nodeToAdd;
node.prev = nodeToAdd;
}
let deleteNode = node => {
let prevNode = node.prev;
let nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
function fn(head):
slow = head
fast = head
while fast and fast.next:
// Do something here
slow = slow.next
fast = fast.next.next
stack = []
for num in nums:
while stack.length > 0 AND stack.top >= num:
stack.pop()
// Between the above and below lines, do some logic depending on the problem
stack.push(num)
let dfs = node => {
if (!node) {
return;
}
dfs(node.left);
dfs(node.right);
return;
}
let printAllNodes = (root) => {
let queue = [root]
while (queue.length) {
let nextQueue = []
for (let i = 0; i < queue; i++) {
let node = queue[i]
// do some logic here on the current node
console.log(node.val)
// put the next level onto the queue
if (node.left) {
nextQueue.push(node.left)
}
if (node.right) {
nextQueue.push(node.right)
}
}
queue = nextQueue
}
}
edges = [[0, 1], [1, 2], [2, 0], [2, 3]]let buildGraph = edges => {
let graph = new Map();
for (const [x, y] of edges) {
if (!graph.has(x)) {
graph.set(x, []);
}
graph.get(x).push(y);
// if (!graph.has(y)) {
// graph.set(y, []);
// }
// graph.get(y).push(x);
// uncomment the above lines if the graph is undirected
}
}
graph = [[1], [2], [0, 3], []]graph = [[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1], [0, 0, 0, 0]]function backtrack(curr) {
if (base case) {
Increment or add to answer
return
}
for (iterate over input) {
Modify curr
backtrack(curr)
Undo whatever modification was done to curr
}
}
Given their exponential solution space, it is tricky to ensure that the generated solutions are complete and non-redundant. It is essential to have a clear and easy-to-reason strategy.
There are generally three strategies to do it:
Recursion
Backtracking
Lexicographic generation based on the mapping between binary bitmasks and the corresponding permutations / combinations / subsets.
As one would see later, the third method could be a good candidate for the interview because it simplifies the problem to the generation of binary numbers, therefore it is easy to implement and verify that no solution is missing.
Besides, as a bonus, it generates lexicographically sorted output for the sorted inputs.
var fibonacci = function(n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
/**
* @param {number} n
* @return {number}
*/
var fibonacci = function(n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (memo.has(n)) {
return memo.get(n);
}
memo.set(n, fibonacci(n - 1) + fibonacci(n - 2));
return memo.get(n);
}
let memo = new Map();
/**
* @param {number} n
* @return {number}
*/
var fibonacci = function(n) {
let arr = new Array(n + 1).fill(0);
// base case - the second Fibonacci number is 1
arr[1] = 1;
for (let i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}