Coding & Algorithms interview questions

Given a 2D grid (image), a starting point (sr, sc), and a new color, implement flood fill: recolor the starting pixel and all connected pixels of the same color (4-directional).

Write a class for weighted random sampling. The class accepts an array of (item, probability) pairs, and its sample() method returns an item according to that distribution.

Implement weighted random sampling with O(1) query time using the Alias Method.

Implement sampling from a discrete distribution specified by a histogram that may contain floating-point weights. Optimize it to O(log n) per query.

For each number in array B, find the number in array A that maximizes their XOR. Implement a naive solution, then optimize it.

Write a function that, given the mean of five numbers and one of those numbers, returns the mean of the remaining four.

Implement a Bloom filter. Explain how it works and write the code.

A Bloom filter has a false positive rate. How does it depend on parameters (array size m, number of hash functions k, number of elements n)? How to choose optimal parameters?

Compare Bloom filter vs hash set. When is Bloom filter preferable? Give real-world examples.

Given an array of integers and a target value, find two numbers that add up to target and return their indices.

Given a string containing '(', ')', '{', '}', '[', ']', determine if the input string has valid brackets.

Given a sorted and rotated array, find the minimum element in O(log n).

Merge two sorted linked lists into one sorted linked list.

Find the k-th largest element in an unsorted array.

Design and implement an LRU (Least Recently Used) Cache with O(1) get and put.

Given an array of intervals, merge all overlapping intervals.

Find the diameter of a binary tree (longest path between any two nodes).

Given a 2D grid of '1's and '0's, count the number of islands (connected components of 1s).

Implement a Trie (prefix tree) with insert, search, and startsWith operations.

Find the length of the longest increasing subsequence (LIS) in an array.