Scribd
Upload
63 views3 pages

Core Algorithms Techniques

The document outlines several core algorithms and techniques useful for interviews, including the Sweep Line Algorithm, Two Pointers, Sliding Window, Monotonic Stack, Topological Sort, Union Find, and Binary Search. Each technique is described with its usage, underlying idea, time complexity, and a code snippet for implementation. These algorithms are commonly applied in various problem-solving scenarios in computer science.

Uploaded by

bingmschandler
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
63 views3 pages

Core Algorithms Techniques

The document outlines several core algorithms and techniques useful for interviews, including the Sweep Line Algorithm, Two Pointers, Sliding Window, Monotonic Stack, Topological Sort, Union Find, and Binary Search. Each technique is described with its usage, underlying idea, time complexity, and a code snippet for implementation. These algorithms are commonly applied in various problem-solving scenarios in computer science.

Uploaded by

bingmschandler
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Core Algorithms and Techniques for

Interviews
Sweep Line Algorithm
**Usage**: Geometry, scheduling, calendar, skyline.

**Idea**: Convert objects into events (start/end), sort by position, and process left to right.

**Time Complexity**: O(n log n)

Code Snippet:

List<Event> events = ...; // start + end


Collections.sort(events, (a, b) -> a.x != b.x ? a.x - b.x : a.height -
b.height);
TreeMap<Integer, Integer> activeHeights = new TreeMap<>();

Two Pointers
**Usage**: Array scan from both ends or fast/slow pointer.

**Idea**: Compare values while moving inward or skipping duplicates.

**Time Complexity**: O(n)

Code Snippet:

int left = 0, right = arr.length - 1;


while (left < right) {
// compare arr[left] and arr[right]
left++;
right--;
}

Sliding Window
**Usage**: Optimal subarrays/substrings.

**Idea**: Expand window to right, shrink from left when invalid.

**Time Complexity**: O(n)

Code Snippet:
int left = 0;
Map<Character, Integer> freq = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
freq.put(s.charAt(right), freq.getOrDefault(s.charAt(right), 0) +
1);
while (freq.size() > k) {
freq.put(s.charAt(left), freq.get(s.charAt(left)) - 1);
left++;
}
}

Monotonic Stack
**Usage**: Next greater/smaller element.

**Idea**: Maintain increasing or decreasing stack.

**Time Complexity**: O(n)

Code Snippet:

Stack<Integer> stack = new Stack<>();


for (int i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
stack.pop();
}
stack.push(i);
}

Topological Sort
**Usage**: Task scheduling with dependencies (DAG).

**Idea**: Use indegree array + BFS (Kahn's Algorithm).

**Time Complexity**: O(V + E)

Code Snippet:

Queue<Integer> q = new LinkedList<>();


int[] indegree = new int[n];
for (...) indegree[neighbor]++;
for (int i = 0; i < n; i++) if (indegree[i] == 0) q.add(i);
while (!q.isEmpty()) {
int node = q.poll();
for (int next : graph[node]) {
if (--indegree[next] == 0) q.add(next);
}
}

Union Find (Disjoint Set)


**Usage**: Connected components, merging sets.

**Idea**: Use parent array with path compression.

**Time Complexity**: O(α(n)) ≈ O(1)

Code Snippet:

int[] parent = new int[n];


for (int i = 0; i < n; i++) parent[i] = i;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union(int x, int y) {
parent[find(x)] = find(y);
}

Binary Search (Answer Space)


**Usage**: Find optimal number under constraints.

**Idea**: Search value space instead of index space.

**Time Complexity**: O(log(range) * check)

Code Snippet:

int left = 1, right = 1_000_000_000;


while (left < right) {
int mid = (left + right) / 2;
if (canShip(mid)) right = mid;
else left = mid + 1;
}

You might also like