Algorithms In My Projects

# kNN cosine similarity — the core of LandAI city-twin matching
import numpy as np

def find_twin_cities(features: np.ndarray, query_idx: int, k: int = 5):
    """
    Brute-force cosine kNN: O(n * d) per query.
    features: (n_cities, n_features), L2-normalized
    Returns indices of k most similar cities (excluding self)
    """
    query = features[query_idx]                          # O(d)
    scores = features @ query                            # O(n * d) — dot product = cosine on L2-normalized
    scores[query_idx] = -1                               # exclude self
    top_k = np.argpartition(scores, -k)[-k:]            # O(n) quickselect
    return top_k[np.argsort(scores[top_k])[::-1]]       # sorted top-k

# Sliding window EMA — the core of StockVision technical indicators
def compute_ema(prices: list, window: int) -> list:
    """Exponential moving average — O(n), O(1) incremental update"""
    alpha = 2 / (window + 1)  # smoothing factor
    ema = []
    for i, price in enumerate(prices):
        if i == 0:
            ema.append(price)
        else:
            ema.append(alpha * price + (1 - alpha) * ema[-1])  # O(1) per step
    return ema

# Leaderboard update — skip list logic (conceptual, implemented via Redis ZSET)
# Redis: ZADD leaderboard <score> <user_id>  → O(log n)
# Redis: ZREVRANGE leaderboard 0 9           → O(log n + k) for top 10

// XGBoost-style tree traversal (simplified — what you explain in interviews)
public class DecisionTree {
    // Inference: walk from root to leaf — O(depth) per tree
    public double predict(TreeNode root, double[] features) {
        TreeNode current = root;
        while (current.left != null || current.right != null) {
            // At each node: check feature threshold and go left or right
            if (features[current.featureIndex] <= current.threshold) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return current.leafValue;  // leaf = prediction contribution
    }
    // Ensemble: sum of all trees' predictions — O(#trees * depth)
    public double predictEnsemble(TreeNode[] trees, double[] features) {
        double total = 0;
        for (TreeNode tree : trees) {
            total += predict(tree, features);  // each tree: O(depth)
        }
        return total;  // gradient boosting: sum of residual corrections
    }
}

// Grid BFS for urban morphology — same as "Number of Islands"
// Used in LandAI's morphological analysis of urban footprint grids
#include <vector>
#include <queue>
using namespace std;

int countConnectedComponents(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1) {  // unvisited land cell
                count++;
                // BFS flood fill — O(pixels) total across all components
                queue<pair<int,int>> q;
                q.push({r, c});
                grid[r][c] = 0;  // mark visited
                int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
                while (!q.empty()) {
                    auto [row, col] = q.front(); q.pop();
                    for (auto& d : dirs) {
                        int nr = row + d[0], nc = col + d[1];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                            && grid[nr][nc] == 1) {
                            grid[nr][nc] = 0;
                            q.push({nr, nc});
                        }
                    }
                }
            }
        }
    }
    return count;
}