NFT Dashboard Application Development.
Through a wide variety of mobile applications, we’ve developed a unique visual system.
- Client George Wallace
- Date 15 June 2022
- Services Web Application
- Budget $100000+
Xinrui's personal website that shares my work and thoughts
I throw myself down among the tall grass by the stream as Ilie close to the earth.
I throw myself down among the tall grass by the stream as Ilie close to the earth.
Through a wide variety of mobile applications, we’ve developed a unique visual system.
There are always some stocks, which illusively scale lofty heights in a given time period. However, the good show doesn’t last for these overblown toxic stocks as their current price is not justified by their fundamental strength.
A strategy is a general plan to achieve one or more long-term. labore et dolore magna aliqua.
UI/UX Design, Art Direction, A design is a plan or specification for art. which illusively scale lofty heights.
User experience (UX) design is the process design teams use to create products that provide.
Toxic companies are usually characterized by huge debt loads and are vulnerable to external shocks. Accurately identifying such bloated stocks and getting rid of them at the right time can protect your portfolio.
Overpricing of these toxic stocks can be attributed to either an irrational enthusiasm surrounding them or some serious fundamental drawbacks. If you own such bubble stocks for an inordinate period of time, you are bound to see a massive erosion of wealth.
However, if you can precisely spot such toxic stocks, you may gain by resorting to an investing strategy called short selling. This strategy allows one to sell a stock first and then buy it when the price falls.
While short selling excels in bear markets, it typically loses money in bull markets.
So, just like identifying stocks with growth potential, pinpointing toxic stocks and offloading them at the right time is crucial to guard one’s portfolio from big losses or make profits by short selling them. Heska Corporation HSKA, Tandem Diabetes Care, Inc. TNDM, Credit Suisse Group CS,Zalando SE ZLNDY and Las Vegas Sands LVS are a few such toxic stocks.Screening Criteria
Here is a winning strategy that will help you to identify overhyped toxic stocks:
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
Through a wide variety of mobile applications.
Through a wide variety of mobile applications, we’ve developed a unique visual system and strategy that can be applied across the spectrum of available applications.
Through a wide variety of mobile applications, we’ve developed a unique visual system and strategy that can be applied across the spectrum of available applications.
A strategy is a general plan to achieve one or more long-term.
UI/UX Design, Art Direction, A design is a plan or specification for art.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commod viverra maecenas accumsan lacus vel facilisis. ut labore et dolore magna aliqua.
There are always some stocks, which illusively scale lofty heights in a given time period. However, the good show doesn’t last for these overblown toxic stocks as their current price is not justified by their fundamental strength.
Toxic companies are usually characterized by huge debt loads and are vulnerable to external shocks. Accurately identifying such bloated stocks and getting rid of them at the right time can protect your portfolio.
Overpricing of these toxic stocks can be attributed to either an irrational enthusiasm surrounding them or some serious fundamental drawbacks. If you own such bubble stocks for an inordinate period of time, you are bound to see a massive erosion of wealth.
However, if you can precisely spot such toxic stocks, you may gain by resorting to an investing strategy called short selling. This strategy allows one to sell a stock first and then buy it when the price falls.
While short selling excels in bear markets, it typically loses money in bull markets.
So, just like identifying stocks with growth potential, pinpointing toxic stocks and offloading them at the right time is crucial to guard one’s portfolio from big losses or make profits by short selling them. Heska Corporation HSKA, Tandem Diabetes Care, Inc. TNDM, Credit Suisse Group CS,Zalando SE ZLNDY and Las Vegas Sands LVS are a few such toxic stocks.Screening Criteria
Here is a winning strategy that will help you to identify overhyped toxic stocks:
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
Through a wide variety of mobile applications, we’ve developed a unique visual system and strategy that can be applied across the spectrum of available applications.
A strategy is a general plan to achieve one or more long-term.
UI/UX Design, Art Direction, A design is a plan or specification for art.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commod viverra maecenas accumsan lacus vel facilisis. ut labore et dolore magna aliqua.
There are always some stocks, which illusively scale lofty heights in a given time period. However, the good show doesn’t last for these overblown toxic stocks as their current price is not justified by their fundamental strength.
Toxic companies are usually characterized by huge debt loads and are vulnerable to external shocks. Accurately identifying such bloated stocks and getting rid of them at the right time can protect your portfolio.
Overpricing of these toxic stocks can be attributed to either an irrational enthusiasm surrounding them or some serious fundamental drawbacks. If you own such bubble stocks for an inordinate period of time, you are bound to see a massive erosion of wealth.
However, if you can precisely spot such toxic stocks, you may gain by resorting to an investing strategy called short selling. This strategy allows one to sell a stock first and then buy it when the price falls.
While short selling excels in bear markets, it typically loses money in bull markets.
So, just like identifying stocks with growth potential, pinpointing toxic stocks and offloading them at the right time is crucial to guard one’s portfolio from big losses or make profits by short selling them. Heska Corporation HSKA, Tandem Diabetes Care, Inc. TNDM, Credit Suisse Group CS,Zalando SE ZLNDY and Las Vegas Sands LVS are a few such toxic stocks.Screening Criteria
Here is a winning strategy that will help you to identify overhyped toxic stocks:
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
Through a wide variety of mobile applications, we’ve developed a unique visual system and strategy that can be applied across the spectrum of available applications.
A strategy is a general plan to achieve one or more long-term.
UI/UX Design, Art Direction, A design is a plan or specification for art.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commod viverra maecenas accumsan lacus vel facilisis. ut labore et dolore magna aliqua.
There are always some stocks, which illusively scale lofty heights in a given time period. However, the good show doesn’t last for these overblown toxic stocks as their current price is not justified by their fundamental strength.
Toxic companies are usually characterized by huge debt loads and are vulnerable to external shocks. Accurately identifying such bloated stocks and getting rid of them at the right time can protect your portfolio.
Overpricing of these toxic stocks can be attributed to either an irrational enthusiasm surrounding them or some serious fundamental drawbacks. If you own such bubble stocks for an inordinate period of time, you are bound to see a massive erosion of wealth.
However, if you can precisely spot such toxic stocks, you may gain by resorting to an investing strategy called short selling. This strategy allows one to sell a stock first and then buy it when the price falls.
While short selling excels in bear markets, it typically loses money in bull markets.
So, just like identifying stocks with growth potential, pinpointing toxic stocks and offloading them at the right time is crucial to guard one’s portfolio from big losses or make profits by short selling them. Heska Corporation HSKA, Tandem Diabetes Care, Inc. TNDM, Credit Suisse Group CS,Zalando SE ZLNDY and Las Vegas Sands LVS are a few such toxic stocks.Screening Criteria
Here is a winning strategy that will help you to identify overhyped toxic stocks:
Most recent Debt/Equity Ratio greater than the median industry average: High debt/equity ratio implies high leverage. High leverage indicates a huge level of repayment that the company has to make in connection with the debt amount.
The training provided by universities in order to prepare me to work in various sectors of the computer science area.
I get my foundation of CS built here, I learn from the lower level operation system, network, Assembly language to Database, Java and data structure.
Using React, Redux, React Query, Webpack and TypeScript to build AWS IAM Console, integrate with backend APIs, develop a widget system that can plug and play with other AWS Console.
Re-design the Expedia checkout insurance module experience, re-write the jQuery based module to React widgets.
The India economy has grown strongly over recent years, having transformed itself from a producer and innovation-based economy.
App Generator is an all-in-one platform designed for businesses or individuals lacking a development team but wishing to create their own video app. It utilizes technologies such as Angular, Java, and Swift to offer a user-friendly interface where users can select their desired video content and target platform. Ultimately, it generates a customizable app tailored to their needs. Additionally, the platform allows for on-the-fly updates to app content and themes, eliminating the need for frequent app version upgrades.
The AWS IAM Console, ranking as the third most trafficked service on the AWS platform, currently operates on an outdated framework that incorporates a blend of technologies like AngularJS 1.6, Backbone, and Ruby, making it challenging to read and maintain. We are embarking on a complete overhaul of the entire IAM console to enhance usability and maintainability. By adopting modern technologies such as React, Redux, TypeScript, React Query, and REST API, we aim to streamline the architecture while preserving the original user experience.
I spearheaded the frontend segment of the re:Invent project titled "Least Privilege Policy Generator." This tool is designed to analyze a policy over a certain period, identify the services accessed, and refine the policy to limit its scope to only necessary permissions. Consequently, it mitigates the risk associated with granting overly broad policies to unintended recipients.
I have successfully completed scuba diving training and achieved certifications in various disciplines, including PADI Open Water, Advanced Open Water, Enriched Air Diver, and EFR-Primary Care (CPR) & Secondary Care. Additionally, I am an SSI-certified Freediver.
I have developed numerous websites, including e-commerce platforms for companies such as Biovive, Reflexgroup, and WolfTech Studio, showcasing this very site as an example of my work. Leveraging my extensive experience, I also mentor individuals aspiring to learn website development. My expertise spans across all web technologies, from historical methods like modifying HTML/CSS for IE6 compatibility, crafting class-like JavaScript structures before the advent of ES6 and TypeScript, to implementing functionalities traditionally handled by modern frameworks like React and Bootstrap using plain JavaScript/CSS. Furthermore, I am skilled in creating responsive designs with pure CSS, alongside other now less commonly discussed techniques.
I Like many others, I enjoy playing video games, which inspired me to learn how to create them myself. I self-taught various game engines, including Phaser, Unity, and Three.js, and have used these tools to develop games such as Flappy Bird and Ping-Pong, among others.
I write scripts to automate some tasks, mostly using Cypress Integration Test framework.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
The education should be very interactual. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante.
All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary
1 Page with Elementor
Design Customization
Responsive Design
Content Upload
Design Customization
2 Plugins/Extensions
Multipage Elementor
Design Figma
MAintaine Design
Content Upload
Design With XD
8 Plugins/Extensions
All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary
5 Page with Elementor
Design Customization
Responsive Design
Content Upload
Design Customization
5 Plugins/Extensions
Multipage Elementor
Design Figma
MAintaine Design
Content Upload
Design With XD
50 Plugins/Extensions
All the Lorem Ipsum generators on the Internet tend to repeat predefined chunks as necessary
10 Page with Elementor
Design Customization
Responsive Design
Content Upload
Design Customization
20 Plugins/Extensions
Multipage Elementor
Design Figma
MAintaine Design
Content Upload
Design With XD
100 Plugins/Extensions
Today, we’re diving into a classic interview problem, Open the Lock. This problem requires us to use Breadth-First Search (BFS) to find the shortest path by simulating a lock mechanism with four wheels. Let’s walk through the problem step-by-step, analyze the solution, and cover key details in the code.
The problem describes a lock with four rotating wheels, each numbered from 0 to 9. The lock starts at “0000”, and each wheel can be rotated up or down to the next number. For instance, “0” can rotate to “1” or “9”.
We have a list of deadend combinations. If we reach one of these, the lock stops, and we can’t proceed further from that position. Given these constraints, we need to find the minimum number of moves to turn the lock from “0000” to a target combination target
. If it’s impossible, we return -1.
Since we’re trying to find the shortest path to the target, this problem is a perfect candidate for Breadth-First Search (BFS). BFS explores all paths level by level, ensuring we reach the target in the fewest moves possible.
Set
for quick lookup./**
* @param {string[]} deadends - List of dead-end combinations
* @param {string} target - Target combination
* @return {number} - Minimum moves to reach target from "0000", or -1 if impossible
*/
var openLock = function(deadends, target) {
// Initialize a Set for deadends for quick lookup
const seen = new Set(deadends);
// Handle edge cases: if "0000" or target is in deadends, we can't proceed
if (seen.has(target) || seen.has('0000')) return -1;
// If the start is already the target, no moves are needed
if (target === '0000') return 0;
// Initialize BFS queue and moves counter
const queue = ["0000"];
seen.add("0000"); // Mark "0000" as visited
let steps = 0;
// Main BFS loop
while (queue.length > 0) {
// Number of nodes in the current level
let size = queue.length;
// Process each node in the current level
while (size > 0) {
const current = queue.shift(); // Remove the first element in queue
// If we've reached the target, return the steps taken
if (current === target) return steps;
// Generate all possible next moves and add to queue
const comb = generateComb(current);
for (const next of comb) {
if (!seen.has(next)) { // Only add unvisited nodes
queue.push(next); // Add new combination to queue
seen.add(next); // Mark new combination as visited
}
}
size--; // Decrement level size
}
steps++; // Move to the next level (increment moves)
}
// If BFS completes without finding target, return -1
return -1;
};
/**
* generateComb - Generates all possible next moves for a given lock state
* @param {string} input - Current lock state
* @return {string[]} - Returns all possible next moves
*/
var generateComb = function(input) {
const combinations = [];
// Loop through each of the four wheels
for (let i = 0; i < 4; i++) {
// Get the current digit of the wheel
const digit = parseInt(input[i]);
// Roll the digit up by one (wrap around from 9 to 0)
const up = input.slice(0, i) + ((digit + 1) % 10) + input.slice(i + 1);
combinations.push(up); // Add the new combination to the result array
// Roll the digit down by one (wrap around from 0 to 9)
const down = input.slice(0, i) + ((digit - 1 + 10) % 10) + input.slice(i + 1);
combinations.push(down); // Add the new combination to the result array
}
return combinations;
};
openLock
:
seen
set stores all visited states to prevent revisiting deadends and previous combinations.queue
to store each combination and mark “0000” as visited to prevent reprocessing.target
.generateComb
:
steps
to count levels, ensuring that when we reach target
, it’s in the minimum moves.target
, we return -1, as it’s impossible to reach.Consider the case where deadends = ["0201","0101","0102","1212","2002"]
and target = "0202"
:
["0000"]
, steps = 0
This problem is an excellent example of BFS’s utility in finding shortest paths. Key takeaways include:
By practicing with problems like this, you’ll improve your understanding of BFS and how to apply it to real-world scenarios!
用TypeScript写个哈希表——说白了就是“找东西利器”
哈希表这个东西呢,跟生活中找钥匙差不多。想象一下,你每次出门都乱丢钥匙,回家要用半小时才能找到它。如果有个哈希表,那你一秒就能知道钥匙放哪了。所以今天我们来用TypeScript写个哈希表,别担心,跟朋友聊天一样简单。
哈希表就像给你的钥匙分配了个专属抽屉,你把钥匙往哈希表里一丢,它自己找个抽屉放好,等你要用的时候,你直接问它:“我的钥匙在哪呢?” 它马上告诉你在哪个抽屉里,秒找。是不是很方便?那咱现在就来动手写一个。
我们来一步步写哈希表,代码都标注好,解释清楚,放心不会扯得太远。
class HashTable<T> {
// 创建一个桶数组,桶就是个小抽屉,里面装着key-value对
private buckets: Array<Array<[string, T]>>;
// 哈希表的大小,也就是有多少个抽屉
private size: number;
constructor(size: number) {
this.size = size;
// 创建一个指定大小的桶数组,初始每个位置是个空数组
this.buckets = new Array(size).fill(null).map(() => []);
// 为啥要fill(null)?TypeScript不允许你直接在空数组上map,得先填充一波。
}
// 哈希函数,负责把key变成数字,这样才能找到对应的桶
private hash(key: string): number {
let hash = 0;
for (let i = 0; i < key.length; i++) {
// 计算哈希值,用ASCII码+位置的算法,最后取模,得到抽屉位置
hash = (hash + key.charCodeAt(i) * i) % this.size;
}
return hash; // 这个数字就是抽屉的索引
}
// 插入或更新键值对
set(key: string, value: T): void {
const index = this.hash(key); // 通过哈希函数找到抽屉
const bucket = this.buckets[index]; // 拿到对应的抽屉
// 先看看抽屉里有没有相同的key
for (let i = 0; i < bucket.length; i++) {
const pair = bucket[i];
if (pair[0] === key) {
// 找到了,就更新value
pair[1] = value;
return;
}
}
// 没找到?那就直接把新的key-value对扔进去
bucket.push([key, value]);
}
// 查找键值对
get(key: string): T | undefined {
const index = this.hash(key); // 先找到抽屉
const bucket = this.buckets[index]; // 拿出这个抽屉
// 遍历抽屉里的东西,看看有没有这个key
for (const pair of bucket) {
if (pair[0] === key) {
return pair[1]; // 找到了,直接返回value
}
}
return undefined; // 没找到,给你个undefined,你懂的
}
// 删除键值对
remove(key: string): boolean {
const index = this.hash(key); // 一样先找到抽屉
const bucket = this.buckets[index]; // 取出这个抽屉
// 遍历抽屉,找到要删的key
for (let i = 0; i < bucket.length; i++) {
const pair = bucket[i];
if (pair[0] === key) {
bucket.splice(i, 1); // 找到后直接删掉
return true; // 成功删除,返回true
}
}
return false; // 没找到就返回false,删除失败
}
}
fill(null)
?TypeScript不让直接在空数组上 map()
,所以你得先用 fill(null)
把它填满,再通过 map()
每个位置给它创建一个空的抽屉。不这样搞,TypeScript就会给你脸色看(直接报错)。hash()
函数到底干啥。其实它就是把字符串变成一个数字,方便找到你想要的抽屉。这里我们用了每个字符的ASCII码乘以它在字符串里的位置,最后对哈希表的大小取模。简单、暴力、够用!但别想太复杂,咱写这个不是为了拿诺贝尔奖,能用就行。key
哈希到同一个位置就叫冲突。这里我们用了“链地址法”来处理冲突,简单来说就是一个桶可以存多个键值对,每次冲突时就往同一个桶里塞。不过,这种方式容易导致某些桶变得过于拥挤,性能就可能下降。如果你想避免这种情况,可以试试“开放地址法”(Open Addressing)。它的原理是,如果一个桶已经有数据了,哈希表会去找下一个空的桶来放新数据。总的来说,两种方法各有优缺点,你可以根据实际需求选择。好了,你已经有了一个能插入、查找、删除数据的哈希表了。接下来如果你想进一步优化,我们可以聊聊其他的冲突处理方式,比如“开放地址法”——这玩意儿可以让你别再往一个抽屉里塞太多东西。另外呢,像红黑树这种高级结构,也可以用来提升性能,后面有机会我们再详细聊。
Priority queues are essential data structures in computer science, especially when dealing with tasks that require ordering based on priority. In this blog post, we’ll explore how to implement a priority queue in TypeScript, which can help solve problems like LeetCode’s 215. Kth Largest Element in an Array.
A priority queue is a special type of queue where each element is associated with a priority, and elements are served based on their priority. The higher the priority, the sooner the element is dequeued. We’ll implement a min-heap-based priority queue, which ensures that the element with the smallest value (highest priority) is always at the front.
TypeScript adds static typing to JavaScript, providing better tooling and error checking at compile time. This makes our code more robust and maintainable.
First, let’s create a PriorityQueue
class that will hold our heap.
class PriorityQueue<T> {
private heap: T[] = [];
constructor(private comparator: (a: T, b: T) => number) {}
}
We need a method to swap two elements in the heap.
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
Calculate the indices of parent and child nodes.
private parentIndex(index: number): number {
return Math.floor((index - 1) / 2);
}
private leftChildIndex(index: number): number {
return 2 * index + 1;
}
private rightChildIndex(index: number): number {
return 2 * index + 2;
}
Add a new element to the heap and reorder it to maintain the heap property.
push(item: T): void {
this.heap.push(item);
this.heapifyUp();
}
Move the new element up to its correct position.
private heapifyUp(): void {
let index = this.heap.length - 1;
while (
index > 0 &&
this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) < 0
) {
this.swap(index, this.parentIndex(index));
index = this.parentIndex(index);
}
}
Remove and return the element with the highest priority.
pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop();
const item = this.heap[0];
this.heap[0] = this.heap.pop() as T;
this.heapifyDown();
return item;
}
Reorder the heap after removing the root element.
private heapifyDown(): void {
let index = 0;
const length = this.heap.length;
while (this.leftChildIndex(index) < length) {
let smallestChildIndex = this.leftChildIndex(index);
const rightChildIdx = this.rightChildIndex(index);
if (
rightChildIdx < length &&
this.comparator(this.heap[rightChildIdx], this.heap[smallestChildIndex]) < 0
) {
smallestChildIndex = rightChildIdx;
}
if (
this.comparator(this.heap[index], this.heap[smallestChildIndex]) <= 0
) {
break;
}
this.swap(index, smallestChildIndex);
index = smallestChildIndex;
}
}
Get the element with the highest priority without removing it and get the size of the queue.
peek(): T | undefined {
return this.heap[0];
}
size(): number {
return this.heap.length;
}
Now, we’ll implement an update()
method that allows us to update the priority of an element, either by its index or by its value.
updateAt(index: number, newValue: T): void {
if (index < 0 || index >= this.heap.length) {
throw new Error("Index out of bounds");
}
const oldValue = this.heap[index];
this.heap[index] = newValue;
if (this.comparator(newValue, oldValue) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
Explanation: We replace the value at the given index with the new value. Then, depending on how the new value compares to the old value, we either heapify up or heapify down to restore the heap property.
Since updating by value can be inefficient (as it may require searching the entire heap), we’ll implement it cautiously.
update(value: T, newValue: T): void {
const index = this.heap.findIndex((element) => element === value);
if (index === -1) {
throw new Error("Value not found in heap");
}
this.updateAt(index, newValue);
}
Explanation: We find the index of the value in the heap and then call updateAt()
to update it.
public remove(item: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.removeAtIndex(index);
}
private removeAtIndex(index: number): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
if (index === this.heap.length - 1) {
this.heap.pop();
} else {
this.heap[index] = this.heap.pop() as T;
const parentIndex = this.parent(index);
if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
}
We’ll add a heapify()
method to build a heap from an existing array.
heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
Now, let’s use our PriorityQueue
to find the Kth largest element in an array.
Given an integer array nums
and an integer k
, return the kth
largest element in the array.
We’ll use a min-heap (priority queue) to keep track of the largest k
elements.
function findKthLargest(nums: number[], k: number): number {
const pq = new PriorityQueue<number>((a, b) => a - b);
for (const num of nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
return pq.peek() as number;
}
Comparator: (a, b) => a - b
ensures a min-heap.
Logic: Maintain a heap of size k
. The root will be the kth largest element.
Full Code Listing with small changes in variable names
class PriorityQueue<T> {
private heap: T[];
constructor(private compare: (a: T, b: T) => number) {
this.heap = [];
}
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
private parent(i: number): number {
return Math.floor((i - 1) / 2);
}
private left(i: number): number {
return 2 * i + 1;
}
private right(i: number): number {
return 2 * i + 2;
}
private heapifyUp(index: number): void {
while (index > 0 && this.compare(this.heap[index], this.heap[this.parent(index)]) < 0) {
this.swap(index, this.parent(index));
index = this.parent(index);
}
}
private heapifyDown(index: number): void {
const length = this.heap.length;
while (this.left(index) < length) {
let smallest = this.left(index);
const rightIndex = this.right(index);
if (rightIndex < length && this.compare(this.heap[rightIndex], this.heap[smallest]) < 0) {
smallest = rightIndex;
}
if (this.compare(this.heap[index], this.heap[smallest]) < 0) {
break;
}
this.swap(index, smallest);
index = smallest;
}
}
public push(item: T): void {
this.heap.push(item);
this.heapifyUp(this.heap.length - 1);
}
public pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop();
const root = this.heap[0];
this.heap[0] = this.heap.pop() as T;
this.heapifyDown(0);
return root;
}
public peek(): T | undefined {
return this.heap[0];
}
public size(): number {
return this.heap.length;
}
public updateAtIndex(index: number, newItem: T): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
this.heap[index] = newItem;
if (this.compare(newItem, this.heap[this.parent(index)]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
public update(item: T, newItem: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.updateAtIndex(index, newItem);
}
public remove(item: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.removeAtIndex(index);
}
private removeAtIndex(index: number): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
if (index === this.heap.length - 1) {
this.heap.pop();
} else {
this.heap[index] = this.heap.pop() as T;
const parentIndex = this.parent(index);
if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
}
public isEmpty(): boolean {
return this.heap.length === 0;
}
public heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
this.heapifyDown(i);
}
}
}
Let’s test our implementation with an example.
const nums = [3, 2, 1, 5, 6, 4];
const k = 2;
const result = findKthLargest(nums, k);
console.log(`The ${k}th largest element is ${result}`); // Output: 5
heapify()
to Build a Heap from an ArraytypescriptCopy codeconst nums = [3, 2, 1, 5, 6, 4];
const pq = new PriorityQueue<number>((a, b) => a - b);
pq.heapify(nums);
console.log(pq.peek()); // Output: 1
findKthLargest
Function Using heapify()
We can optimize our earlier findKthLargest
function by using heapify()
.
function findKthLargest(nums: number[], k: number): number {
const pq = new PriorityQueue<number>((a, b) => b - a); // Max-heap
pq.heapify(nums);
for (let i = 0; i < k - 1; i++) {
pq.pop();
}
return pq.peek() as number;
}
heapifyDown()
in heapify()
?That’s a great question! In the heapify()
method, we use heapifyDown()
instead of heapifyUp()
because when building a heap from an existing array, we need an efficient way to ensure the heap property is maintained throughout the structure.
When constructing a heap from an unordered array, the most efficient method is to start from the last non-leaf node and move upwards, performing heapifyDown()
on each node. This process is known as the heapify algorithm or build heap.
heapifyDown()
, the overall time complexity of building the heap is O(n). If we were to use heapifyUp()
, the time complexity would increase to O(n log n) in the worst case.heapifyDown()
can fix all violations of the heap property from the current node down to the leaves in one pass, whereas heapifyUp()
might require multiple passes for each node.heapifyDown()
is more appropriate when you need to adjust the heap starting from the internal nodes downwards.heapifyUp()
is typically used when inserting a new element into an already built heap.When building a heap, our goal is to ensure that every parent node satisfies the heap property with respect to its children (for a min-heap, each parent node is less than or equal to its children). To achieve this efficiently, we start from the last non-leaf node because leaf nodes are already valid heaps by themselves.
heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
Math.floor(this.heap.length / 2) - 1
Math.floor(n/2)
to n - 1
are all leaf nodes.heapifyUp()
?
heapifyUp()
is suitable for situations where you’re adding a single new element to the heap and need to adjust its position.heapifyUp()
during the heap construction process would result in higher time complexity because each node might need to be moved up multiple levels.heapifyDown()
can adjust the subtree rooted at a node in one pass.Suppose we have an array [3, 2, 1, 5, 6, 4]
and we want to build a min-heap.
this.heap = [3, 2, 1, 5, 6, 4];
Math.floor(6 / 2) - 1 = 2
.heapifyDown()
on Index 2:
1
, and its children are out of bounds, so no action is needed.heapifyDown()
on Index 1:
2
, with left child 5
and right child 6
.2
is less than its children, no action is needed.heapifyDown()
on Index 0:3
, with left child 2
and right child 1
.The right child 1
is the smallest, so we swap 3
with 1
.[1, 2, 3, 5, 6, 4]
.heapifyDown()
on the Swapped Node:
3
) has a left child 4
, but since 3
is less than 4
, no further action is needed.heapifyDown()
:
heapifyUp()
:
Therefore, in the heapify()
method, we choose heapifyDown()
to efficiently build a valid heap from the bottom up.
heapifyUp()
?
heapifyUp()
on each node starting from the root, each node might have to move up several levels, leading to higher overall time complexity.heapifyDown()
allows us to fix violations of the heap property starting from each internal node down to the leaves in a single pass.heapifyDown()
: Total time complexity is O(n).heapifyUp()
: Total time complexity is O(n log n).We’ve successfully implemented a priority queue in TypeScript using a min-heap and applied it to solve a common algorithm problem. This implementation can be extended or modified for other use cases, such as max-heaps or custom priority criteria.
I am available for freelance work. Connect with me via and call in to my account.
Phone: +01234567890 Email: admin@example.com