Skip to content

Instantly share code, notes, and snippets.

@Shashank-Srivastava2108
Last active November 30, 2023 05:48
Show Gist options
  • Save Shashank-Srivastava2108/22454e1a129401650ee71146950f74e5 to your computer and use it in GitHub Desktop.
Save Shashank-Srivastava2108/22454e1a129401650ee71146950f74e5 to your computer and use it in GitHub Desktop.
End Course Capstone Project (Module Data Structures) - Solution

End Course Capstone Project (Module Data Structures) - Solution

module.exports = { getDecimalValue };
const getDecimalValue = head => {
let val = 0;
while (head) {
val = (val << 1) | head.val;
head = head.next;
}
return val;
};
module.exports = { middleNode };
var middleNode = function(head) {
let slow = head;
let fast = head;
while (fast && fast.next){
fast = fast.next.next;
slow = slow.next;
}
return slow;
};
module.exports = { isPalindrome };
var isPalindrome = function(head) {
let arr = []
while(head) {
arr.push(head.val)
head = head.next
}
return arr.join('') == arr.reverse().join('')
};
module.exports = { reverseList };
var reverseList = function(head) {
let prev = null
while (head !== null) {
let current = head
head = head.next
current.next = prev
prev = current
}
return prev
};
module.exports = { removeElements };
var removeElements = function(head, val) {
let tempHead = head,prev
while (!tempHead){
if (tempHead.val ===val){
if (prev){
head = head.next
tempHead=tempHead.next
}else{
prev.next =tempHead.next
tempHead=tempHead.next
}
}else{
prev=tempHead
tempHead.next = tempHead
}
}
return head
};
module.exports = { countBits };
var countBits = function(num) {
let res = [0]
for(let i=1;i<=num;i++){
const half = i>>1
const odd = i&1
res[i] = res[half] + odd
}
return res
};
module.exports = { sumOfLeftLeaves };
var sumOfLeftLeaves = function(root) {
if(!root) return 0; const { left, right } = root;
let [sumLeft, sumRight] = [sumOfLeftLeaves(left), sumOfLeftLeaves(right)];
if(!sumLeft && left && !left.left && !left.right) sumLeft = left.val;
return Number(sumLeft) + Number(sumRight);
};
module.exports = { diameterOfBinaryTree };
function diameterOfBinaryTree(root) {
let max = 0
function maxDepth(root) {
if (root === null) return 0
let left = maxDepth(root.left)
let right = maxDepth(root.right)
max = Math.max(max, left + right)
return Math.max(left, right) + 1
}
maxDepth(root)
return max
};
module.exports = { preorder };
var preorder = function(root) {
if(!root) return [];
const queue =[root];
const arr = [];
while(queue.length){
const node = queue.shift();
arr.push(node.val);
queue.unshift(...node.children);
}
return arr ;
};
module.exports = ={ mergeTrees };
const mergeTrees = function(root1, root2) {
if (!root1) return root2
if (!root2) return root1
const res = root1
const queue = []
queue.push({v1:res, v2:root2})
while (queue.length) {
const {v1, v2} = queue.shift()
v1.val += v2.val
if (v1.left && v2.left) queue.push({v1:v1.left, v2:v2.left})
if (!v1.left && v2.left) v1.left = v2.left
if (v1.right && v2.right) queue.push({v1:v1.right, v2:v2.right})
if (!v1.right && v2.right) v1.right = v2.right
}
return res
};
module.exports = {minimizeArrayValue };
var minimizeArrayValue = function(nums) {
let max = 0;
for (let i = 1, sum = 0; i <= nums.length; i++)
sum += nums[i - 1], max = Math.max(max, Math.ceil(sum / i));
return max;
};
module.exports = { minimumTime };
function minimumTime(time, totalTrips) {
let left = 1; // minimum time needed to complete all trips
let right = 1e18; // maximum time (for practical purposes)
while (left < right) {
const mid = Math.floor((left + right) / 2); // mid-point of the search range
let tripsCompleted = 0;
for (let i = 0; i < time.length && tripsCompleted < totalTrips; i++) {
tripsCompleted += Math.floor(mid / time[i]); // number of trips completed by this bus in mid time
}
if (tripsCompleted >= totalTrips) {
right = mid; // search the left half of the range
} else {
left = mid + 1; // search the right half of the range
}
}
return left;
}
module.exports = { maxTaxEarnings };
var maxTaxEarnings = function(n, rides) {
const map = new Map();
for (let i = 0; i < rides.length; ++i) {
const [start, end, tips] = rides[i];
if (!map.has(end)) map.set(end, []);
map.get(end).push(i);
}
const dp = new Array(n + 1).fill(0);
for (let point = 1; point <= n; ++point) {
if (!map.has(point)) {
dp[point] = dp[point - 1];
}
else {
dp[point] = dp[point - 1];
const indexes = map.get(point);
for (const idx of indexes) {
const [start, end, tips] = rides[idx];
const currProfit = end - start + tips;
const prevProfit = dp[start];
dp[point] = Math.max(dp[point], prevProfit + currProfit);
}
}
}
return dp[n];
};
module.exports = { mostProfitablePath };
var mostProfitablePath = function(edges, bob, amount) {
const graph = Array.from({ length: edges.length + 1 }, () => []);
for (const [i, j] of edges)
graph[i].push(j), graph[j].push(i);
function aliceMoves(node, parent, time) {
let totalBobTime = node == bob ? 0 : Infinity, newScore = -Infinity;
for (const child of graph[node]) {
if (child == parent) continue;
const [score, bobTime] = aliceMoves(child, node, time + 1);
totalBobTime = Math.min(totalBobTime, bobTime + 1);
newScore = Math.max(newScore, score)
}
if (newScore == -Infinity) newScore = 0;
if (time < totalBobTime) newScore += amount[node];
else if (time == totalBobTime) newScore += amount[node] / 2;
return [newScore, totalBobTime];
}
return aliceMoves(0, -1, 0)[0];
};
module.exports = { edgeScore };
var edgeScore = function(edges) {
let score=Array(edges.length).fill(0);
for(let i=0;i<edges.length;i++){
let neighNode=edges[i];
score[neighNode]+=i;
}
let max=-Infinity;
let index=0;
for(let i=0;i<score.length;i++){
if(score[i]>max){
max=score[i];
index=i;
}
}
return index;
};
module.exports = { addTwoNumbers };
var addTwoNumbers = function(l1, l2, carry) {
if(!l1 && !l2 && !carry) return null;
var total = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + (carry || 0);
carry = parseInt(total / 10);
return new ListNode(total % 10, addTwoNumbers(l1?.next, l2?.next, carry));
};
module.exports = { LRUCache };
class LRUCache {
constructor(capacity) {
this.map = new Map();
this.capacity = capacity;
}
get(key) {
if (!this.map.has(key)) return -1;
const val = this.map.get(key);
this.map.delete(key);
this.map.set(key, val);
return val;
}
put(key, value) {
this.map.delete(key);
this.map.set(key, value);
if (this.map.size > this.capacity) {
const firstItem = this.map.keys().next().value;
this.map.delete(firstItem);
}
}
}
module.exports = { maximumSafenessFactor };
var maximumSafenessFactor = function(grid) {
const n = grid.length;
const isInBound = (r, c) => r >= 0 && r < n && c >= 0 && c < n;
const dist = new Array(n).fill(0).map(() => new Array(n).fill(Infinity));
const queue = [];
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) {
dist[r][c] = 0;
queue.push([r, c]);
}
}
}
while (queue.length) {
const [r, c] = queue.shift();
const neighbors = [
[r + 1, c],
[r - 1, c],
[r, c + 1],
[r, c - 1],
];
for (const [nr, nc] of neighbors) {
if (isInBound(nr, nc) && dist[nr][nc] === Infinity) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
const maxDistance = new Array(n).fill(0).map(() => new Array(n).fill(0));
maxDistance[0][0] = dist[0][0];
queue.push([0, 0]);
while (queue.length) {
const [r, c] = queue.shift();
const neighbors = [
[r + 1, c],
[r - 1, c],
[r, c + 1],
[r, c - 1],
];
for (const [nr, nc] of neighbors) {
if (isInBound(nr, nc)) {
const newDistance = Math.min(maxDistance[r][c], dist[nr][nc]);
if (newDistance > maxDistance[nr][nc]) {
maxDistance[nr][nc] = newDistance;
queue.push([nr, nc]);
}
}
}
}
return maxDistance[n - 1][n - 1];
};
module.exports = { balanceBST };
var balanceBST = function(root) {
const values = toArray(root);
return toBST(values);
function toBST(arr) {
if (arr.length===0) return null;
if (arr.length===1) return new TreeNode(arr[0]);
const mid = Math.floor(arr.length / 2);
const left = toBST(arr.slice(0, mid));
const right = toBST(arr.slice(mid+1));
return new TreeNode(arr[mid], left, right);
}
function toArray(node) {
if (!node) return [];
return [...toArray(node.left), node.val, ...toArray(node.right)];
}
};
module.exports = { cloneGraph };
var cloneGraph = function (node) {
if (!node) return null;
let dfs = (node, visited) => {
if (visited.has(node)) return visited.get(node);
let newNode = new Node(node.val);
visited.set(node, newNode);
for (let neighbor of node.neighbors) {
newNode.neighbors.push(dfs(neighbor, visited));
}
return newNode;
}
return dfs(node, new Map());
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment