Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

---

Examples

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

---

Constraints

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Implement Secure Password Storage

Passwords should never be stored in plain text. If a database is compromised, an attacker can see all user passwords. To prevent this, passwords must be hashed using a one-way cryptographic hash function.

However, simple hashing (like MD5 or SHA-1) is not enough because attackers can use rainbow tables or brute-force attacks. To make storage secure, we use:

1. Salt: A unique, random string added to each password before hashing to ensure that users with the same password have different hashes.
2. Key Stretching: Using algorithms like Argon2, bcrypt, or PBKDF2 that are intentionally slow to compute, making brute-force attacks impractical.

Task:

Implement a class PasswordManager with two methods:

• hash_password(password: string): string: Takes a plain text password and returns a hashed version including a salt.
• verify_password(password: string, hashed_password: string): boolean: Returns true if the plain text password matches the hashed version, otherwise false.

For this challenge, implement a simplified version of PBKDF2 (Password-Based Key Derivation Function 2) logic or use a standard pattern.

Example:

const pm = new PasswordManager();
const hash = pm.hash_password("mySecretPassword");
// hash might look like "pbkdf2$1000$randomSalt$encryptedHash"

console.log(pm.verify_password("mySecretPassword", hash)); // true
console.log(pm.verify_password("wrongPassword", hash)); // false

Constraints:

• password.length >= 8
• The hash must be unique even for the same password if called multiple times.

Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1] Output: 1

Example 2:

Input: nums = [4,1,2,1,2] Output: 4

Example 3:

Input: nums = [1] Output: 1

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Each element in the array appears twice except for one element which appears only once.

Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

---

Examples

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

---

Constraints

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

Follow Up:

If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Encode and Decode Strings

Design an algorithm to encode a list of strings to a single string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Please implement encode and decode methods.

---

Examples

Example 1:

Input: ["lint","code","love","you"]
Output: ["lint","code","love","you"]
Explanation:
One possible encode method is: "4#lint4#code4#love3#you".

Example 2:

Input: ["we", "say", ":", "yes"]
Output: ["we", "say", ":", "yes"]
Explanation:
One possible encode method is: "2#we3#say1#:3#yes"

---

Constraints

• 0 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] contains any possible characters out of 256 valid ascii characters.
• Note: There are no dedicated constraints on the intermediate string length.

Implement Linear Regression from Scratch

Problem Description

Implement a Linear Regression model from scratch using gradient descent optimization. Your implementation should be able to fit a linear model to training data and make predictions on new data.

Linear regression models the relationship between features X and target y as:

y = X * w + b

where w is the weight vector and b is the bias term.

Requirements

1. Fit: Train the model using gradient descent to minimize Mean Squared Error (MSE)
2. Predict: Use learned weights and bias to predict on new data
3. Return: The predictions, learned weights, and bias

Function Signature

function linearRegression(
  X_train: number[][],
  y_train: number[],
  X_test: number[][],
  learningRate?: number,
  epochs?: number
): { predictions: number[]; weights: number[]; bias: number }

Parameters

• X_train: 2D array of training features (n_samples x n_features)
• y_train: 1D array of target values
• X_test: 2D array of test features
• learningRate: Learning rate for gradient descent (default: 0.01)
• epochs: Number of training iterations (default: 1000)

Example

Input:
  X_train = [[1], [2], [3], [4]]
  y_train = [2, 4, 6, 8]
  X_test = [[5], [6]]

Output:
  predictions = [10, 12]
  weights = [2]
  bias = 0

Constraints

• 1 <= n_samples <= 10,000
• 1 <= n_features <= 100
• Learning rate > 0
• Values are finite numbers

Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

---

Examples

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

---

Constraints

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999