Geico interview question prep.
Sample Medium-Level Coding Problems:
Pathfinding/DP: "Minimum
Path Sum" (grid traversal), often with constraints on moves (right/down).
Solved
Medium
Topics
Companies
Given a m x
n grid filled with non-negative numbers, find a path from top left to
bottom right, which minimizes the sum of all numbers along its path.
Note: You can only
move either down or right at any point in time.
Example 1:
class Solution {
public int
minPathSum(int[][] grid) {
int m = grid.length;
int n
= grid[0].length;
int[]
dp = new int[n];
dp[0]
= grid[0][0];
//
First row
for
(int j = 1; j < n; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
//
Remaining rows
for
(int i = 1; i < m; i++) {
dp[0] += grid[i][0]; // first column
for (int j = 1; j < n; j++) {
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
}
}
return
dp[n - 1];
}
}
Even simpler case:
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++)
dp[i][0] = dp[i-1][0] + grid[i][0];
for (int j = 1; j < n; j++)
dp[0][j] = dp[0][j-1] + grid[0][j];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] +
Math.min(dp[i-1][j],
dp[i][j-1]);
}
}
return dp[m-1][n-1];
Strings/Sliding Window: "Longest
Substring Without Repeating Characters," "First Unique
Character," "String to Integer (atoi)".
Longest
Substring Without Repeating Characters - LeetCode
1st attempt, I tried this way:
class Solution {
public int lengthOfLongestSubstring(String s)
{
HashSet<Character> hs =
new HashSet<Character>();
for (int i = 0; i <
s.length(); i++) {
hs.add(s.charAt(i));
}
return hs.size();
}
}
but this works only if the question were without repeating
the charector>
✅ Optimal Approach: Sliding
Window (O(n))
Idea (simple):
Use two pointers: left and right
Maintain a HashSet of characters in the current window
Expand right
If duplicate found → shrink from left
Track max window size
class Solution {
public int
lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<>();
int left = 0,
maxLen = 0;
for (int right
= 0; right < s.length(); right++) {
while
(set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
maxLen =
Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
- Linked
Lists: "Detect Cycle in Linked List," "Merge Two
Sorted Lists," "Reverse Linked List" (use dummy
nodes/two-pointers).
- Heaps/Priority
Queues: Finding the top K elements, or complex sorting
scenarios.
Staff Engineer Focus Areas:
- System
Design: Scalable backend, API structuring (Spring Boot), database
management (PostgreSQL), AWS services, fault tolerance, service
decoupling.
- Advanced
Algorithm Application: Handling large strings with limited
memory, optimizing database queries, ensuring scalability.
- Leadership/Behavioral: Project
leadership, conflict resolution with teammates, technical choices (e.g.,
why Rust vs. Python), resolving project challenges (STAR method).
Preparation Tips:
- Master
standard templates for sliding windows, two-pointers, and
heap/priority queues.
- Practice
explaining your thought process and runtime complexity (Big O) for
optimizations.
- Be
ready to pivot from coding to system design and behavioral questions
seamlessly.
·
Roman to int and time complexity
·
Technical - Integer to Roman Leetcode
question
·
Leetcode, mainly greedy and dynamic programming
medium questions.
·
Knapsack questions were common
·
Design an auto complete, track the length
·
Graph and greedy question System design
Detect Cycle in Linked List,
Given head, the head of a linked list, determine if the
linked list has a cycle in it.
There is a cycle in a linked list if there is some node in
the list that can be reached again by continuously following
the next pointer. Internally, pos is used to denote the
index of the node that tail's next pointer is connected
to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked
list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list,
where the tail connects to the 1st node (0-indexed).
Solution:
Detect
Cycle in Linked List - GeeksforGeeks
class GfG {
static boolean
detectLoop(Node head) {
// Fast and
slow pointers initially points to the head
Node slow =
head, fast = head;
// Loop that
runs while fast and slow pointer are not
// null and
not equal
while (slow !=
null && fast != null && fast.next != null) {
slow =
slow.next;
fast =
fast.next.next;
// If fast
and slow pointer points to the same node,
// then
the cycle is detected
if (slow
== fast) {
return
true;
}
}
return false;
}
[Expected Approach] Using Floyd's Cycle-Finding Algorithm
This idea is to use Floyd's
Cycle-Finding Algorithm to find a loop in a linked list. It uses two
pointers slow and fast, fast pointer move two steps ahead and slow will move
one step ahead at a time.
You are given the heads of two sorted linked
lists list1 and list2.
Merge the two lists into one sorted list.
The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
class Solution {
public ListNode mergeTwoLists(ListNode list1,
ListNode list2) {
ListNode finalNode=null;
// Dummy node to simplify logic
ListNode dummy = new
ListNode(-1);
ListNode finallist = dummy;
while (list1 != null &&
list2 != null) {
if (list1.val
<= list2.val) {
finallist.next = list1;
list1 = list1.next;
} else {
finallist.next = list2;
list2 = list2.next;
}
finallist =
finallist.next;
}
// Attach remaining nodes
if (list1 != null) {
finallist.next =
list1;
} else {
finallist.next =
list2;
}
return dummy.next;
}
}
Reverse
Linked List - LeetCode
Given the head of a singly linked list, reverse
the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp
= curr.next; // store next
curr.next = prev;
// reverse link
prev = curr;
// move prev
curr = nextTemp;
// move curr
}
return prev; // new head
}
}
dffasdfasdfafsadf
Question:
1st OA was leetcode fix maximum potholes in a road. Second
OA was something about removing certain characters from a string and
interviewer followed ups with how to handle a very large string on device with
limited memory. Behavioral was typical STAR stuff.
Max pathhole.
Problem Description (Common Version)
You are given a string road consisting of:
- '.' →
smooth road
- 'x' →
pothole
You can fix potholes using one repair operation,
which:
- Fixes exactly
one pothole
- Cannot
be applied to adjacent potholes
Goal
Return the maximum number of potholes that can be
fixed.
Example
Input
road = "x..xx...xxx"
Breakdown
|
Segment |
Length |
Fixable |
|
x |
1 |
1 |
|
xx |
2 |
1 |
|
xxx |
3 |
2 |
Output
4
Java Solution (LeetCode Style)
class Solution {
public int
maximumPotholes(String road) {
int count = 0;
int i = 0;
int n =
road.length();
while (i <
n) {
if
(road.charAt(i) == 'x') {
int
len = 0;
//
count consecutive potholes
while
(i < n && road.charAt(i) == 'x') {
len++;
i++;
}
//
each repair fixes 3 potholes
count
+= (len / 3) * 3;
} else {
i++;
}
}
return count;
}
}Time & Space Complexity
- Time:
O(n)
- Space:
O(1)
·
Example Walkthrough 🚶♂️
·
Input
·
road = "x..xx...xxx"
·
Segments
|
Segment |
Length |
Fixes |
|
x |
1 |
1 |
|
xx |
2 |
1 |
|
xxx |
3 |
2 |
·
Total
·
1 + 1 + 2 = 4
Other way:
public class Solution {
public int
maximumPotholes(String road) {
int count = 0;
int i = 0;
while (i <
road.length()) {
if
(road.charAt(i) == 'x') {
count++; // fix this pothole
i +=
2; // skip next to avoid adjacency
} else {
i++;
}
}
return count;
}
}
Why This Works 🧠
Example:
road = "xxx..xx"
Walkthrough:
i=0 → 'x' → fix → count=1 → i=2
i=2 → 'x' → fix → count=2 → i=4
i=4 → '.' → skip → i=5
i=5 → 'x' → fix → count=3 → i=7 (end)
Design an auto complete, track the length JAVA
1. Problem Understanding
Functional requirement
Design an auto-complete system that:
- Stores
words (dictionary)
- Returns
suggestions for a given letter you typed so far
- Tracks
prefix length (how many characters typed so far)
- Works
efficiently as the user types character by character
Non functional requirement:
Mutiple user
2. High-Level Design
Core Operations
- insert(word)
- search(prefix)
- getSuggestions(prefix)
- trackLength(prefix)
→ return length
3. Data Structure Choice: Trie (Prefix Tree)
Why Trie?
- Optimized
for prefix queries
- Prefix
length is depth of traversal
- Easy
to generate suggestions
4. Trie Node Design (Java)
class TrieNode {
TrieNode[]
children = new TrieNode[26];
boolean isEnd;
int
prefixCount; // tracks how many words
share this prefix
}
Integer
to roman
✅ Corrected Version (Minimal
Change to Your Code)
class Solution {
public String
intToRoman(int num) {
int[] value =
{
1000, 900,
500, 400,
100, 90,
50, 40,
10, 9, 5,
4, 1
};
String[]
symbol = {
"M", "CM", "D", "CD",
"C", "XC", "L", "XL",
"X", "IX", "V", "IV",
"I"
};
StringBuilder
b = new StringBuilder();
for (int j =
0; j < value.length; j++) {
while (num
>= value[j]) {
num -=
value[j];
b.append(symbol[j]);
}
}
return
b.toString();
}
}
⏱ Time Complexity
Key Observation
- The
value array has a constant size (13).
- Each
iteration of while reduces num.
- Maximum
Roman numeral length for 3999 is 15 characters (MMMCMXCIX).
Analysis
- Outer
loop → 13 iterations (constant)
- Inner
loop → runs at most 15 times total
✅ Time Complexity = O(1)
(constant time)
Even though there is a nested loop, the total number of
operations is bounded by a constant, not by input size.
💾 Space Complexity
Extra Space Used
- StringBuilder
→ max ~15 characters
- value[]
and symbol[] → fixed size
✅ Space Complexity = O(1)
(constant space)
Number
to roman:
class Solution {
public int romanToInt(String s) {
int[] value = {
1000, 900, 500,
400,
100, 90, 50, 40,
10, 9, 5, 4, 1
};
String[] symbol = {
"M",
"CM", "D", "CD",
"C",
"XC", "L", "XL",
"X",
"IX", "V", "IV", "I"
};
int number = 0;
int i = 0;
while (i < s.length()) {
for (int j = 0; j
< symbol.length; j++) {
if
(s.startsWith(symbol[j], i)) {
number += value[j];
i += symbol[j].length();
break;
}
}
}
return number;
}
}
Alternate:
class Solution {
private int
value(char c) {
switch (c) {
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
default:
return 0;
}
}
public int
romanToInt(String s) {
int result =
0;
for (int i =
0; i < s.length(); i++) {
int curr =
value(s.charAt(i));
if (i + 1
< s.length() && curr < value(s.charAt(i + 1))) {
result
-= curr;
} else {
result
+= curr;
}
}
return result;
}
}
Final Summary
|
Problem |
Time |
Space |
|
Roman → Integer |
O(n) |
O(1) |
|
Integer → Roman |
O(1) |
O(1) |
class Solution {
public int
romanToInt(String s) {
Map<Character, Integer> map = new HashMap<>();
map.put('I',
1);
map.put('V',
5);
map.put('X',
10);
map.put('L',
50);
map.put('C',
100);
map.put('D',
500);
map.put('M',
1000);
int result =
0;
for (int i =
0; i < s.length(); i++) {
int curr =
map.get(s.charAt(i));
if (i + 1
< s.length() && curr < map.get(s.charAt(i + 1))) {
result
-= curr;
} else {
result
+= curr;
}
}
return result;
}
Assume you are an awesome parent and want to give your
children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which
is the minimum size of a cookie that the child will be content with; and each
cookie j has a size s[j]. If s[j] >= g[i], we can assign
the cookie j to the child i, and the child i will be
content. Your goal is to maximize the number of your content children and
output the maximum number.
Example 1:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The
greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both
1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The
greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify
all of the children,
You need to output 2.
class Solution {
public int findContentChildren(int[] g, int[]
s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int i = 0;
while (i < s.length
&& count < g.length) {
if (s[i] >= g[count])
{
count++;
}
i++;
}
return count;
}
}
Valid
parenthesis
Given a string s containing just the
characters '(', ')', '{', '}', '[' and ']',
determine if the input string is valid.
An input string is valid if:
- Open
brackets must be closed by the same type of brackets.
- Open
brackets must be closed in the correct order.
- Every
close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
class Solution {
public boolean
isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i =
0; i < s.length(); i++) {
char c =
s.charAt(i);
if (c ==
'(' || c == '{' || c == '[') {
stack.push(c);
} else {
if
(stack.isEmpty()) return false;
if ((c
== ')' && stack.peek() == '(') ||
(c
== '}' && stack.peek() == '{') ||
(c
== ']' && stack.peek() == '[')) {
stack.pop();
} else
{
return false;
}
}
}
return
stack.isEmpty();
}
}
interview
preparation for greedy algorithm - Google Search
Given a string s containing only three types of
characters: '(', ')' and '*', return true if s is valid.
The following rules define a valid string:
- Any
left parenthesis '(' must have a corresponding right
parenthesis ')'.
- Any
right parenthesis ')' must have a corresponding left
parenthesis '('.
- Left
parenthesis '(' must go before the corresponding right
parenthesis ')'.
- '*' could
be treated as a single right parenthesis ')' or a single left
parenthesis '(' or an empty string "".
class Solution {
public boolean
checkValidString(String s) {
Stack<Integer> openStack = new Stack<>();
Stack<Integer> starStack = new Stack<>();
// First pass
for (int i =
0; i < s.length(); i++) {
char c =
s.charAt(i);
if (c ==
'(') {
openStack.push(i);
} else if
(c == '*') {
starStack.push(i);
} else {
// c == ')'
if
(!openStack.isEmpty()) {
openStack.pop();
} else
if (!starStack.isEmpty()) {
starStack.pop();
} else
{
return false;
}
}
}
// Match
remaining '(' with '*'
while
(!openStack.isEmpty() && !starStack.isEmpty()) {
if
(openStack.peek() > starStack.peek()) {
return
false;
}
openStack.pop();
starStack.pop();
}
return
openStack.isEmpty();
}
}
🔍 Example Walkthrough
Input:
"(*)"
- ( →
push index to openStack
- * →
push index to starStack
- ) →
pop from openStack
✅ Valid
Input:
"(*))"
- ( →
openStack
- * →
starStack
- ) →
match (
- ) →
match *
✅ Valid
Fractional Knapsack problem:
Fractional Knapsack
Problem using Greedy Method | Example | Data structures and algorithms
Fractional
Knapsack - GeeksforGeeks
[Approach] Selecting Items by value/weight Ratio -
O(nlogn) Time and O(n) Space
The idea is to always pick items greedily based on their value-to-weight
ratio. Take the item with the highest ratio first, then the next highest,
and so on, until the knapsack is full. If any item doesn’t fully fit, then take
its fractional part according to the remaining capacity.
Steps to solve the problem:
- Calculate
the ratio (value/weight) for each item.
- Sort
all the items in decreasing order of the ratio.
- Iterate
through items:
if the current item fully fits, add its full value and decrease capacity otherwise, take the fractional part that fits and add proportional value.
- Stop
once the capacity becomes zero.
import java.util.*;
class Item {
int value;
int weight;
Item(int value,
int weight) {
this.value =
value;
this.weight =
weight;
}
}
class Solution {
public static
double fractionalKnapsack(int W, Item[] items) {
// Sort items
by value/weight ratio (descending)
Arrays.sort(items, (a, b) ->
Double.compare((double)b.value / b.weight,
(double)a.value / a.weight)
);
double
totalValue = 0.0;
int
remainingCapacity = W;
for (Item item
: items) {
if
(remainingCapacity == 0) break;
if
(item.weight <= remainingCapacity) {
//
Take full item
remainingCapacity -= item.weight;
totalValue += item.value;
} else {
//
Take fractional part
double
fraction = (double) remainingCapacity / item.weight;
totalValue += item.value * fraction;
remainingCapacity = 0;
}
}
return
totalValue;
}
// Driver Code
public static void
main(String[] args) {
int W = 50;
Item[] items =
{
new
Item(60, 10),
new
Item(100, 20),
new
Item(120, 30)
};
System.out.println(fractionalKnapsack(W, items));
}
}
⏱️ Time & Space Complexity
|
Metric |
Complexity |
|
Sorting |
O(n log n) |
|
Selection |
O(n) |
|
Space |
O(1) |
Two pointer problem
|
|
6.13
Dijkstra Algorithm | Single Sourc99ik e Shortest Path| Greedy Method
Dijkstra's algorithm is often considered to be the most
straightforward algorithm for solving the shortest path problem.
Dijkstra's algorithm is used for solving single-source
shortest path problems for directed or undirected paths. Single-source means
that one vertex is chosen to be the start, and the algorithm will find the
shortest path from that vertex to all other vertices.
Dijkstra's algorithm does not work for graphs with negative
edges. For graphs with negative edges, the Bellman-Ford algorithm that is
described on the next page, can be used instead.
How it works:
- Set
initial distances for all vertices: 0 for the source vertex, and infinity
for all the other.
- Choose
the unvisited vertex with the shortest distance from the start to be the
current vertex. So the algorithm will always start with the source as the
current vertex.
- For
each of the current vertex's unvisited neighbor vertices, calculate the
distance from the source and update the distance if the new, calculated,
distance is lower.
- We
are now done with the current vertex, so we mark it as visited. A visited
vertex is not checked again.
- Go
back to step 2 to choose a new current vertex, and keep repeating these
steps until all vertices are visited.
- In
the end we are left with the shortest path from the source vertex to every
other vertex in the graph.
`
https://www.w3schools.com/dsa/dsa_algo_graphs_dijkstra.php check the simulation from here.
public class Main {
static class Graph
{
private
int[][] adjMatrix;
private
String[] vertexData;
private int
size;
public
Graph(int size) {
this.size
= size;
this.adjMatrix = new int[size][size];
this.vertexData = new String[size];
}
public void
addEdge(int u, int v, int weight) {
if (u
>= 0 && u < size && v >= 0 && v < size) {
adjMatrix[u][v] = weight;
adjMatrix[v][u] = weight; // For
undirected graph
}
}
public void
addVertexData(int vertex, String data) {
if (vertex
>= 0 && vertex < size) {
vertexData[vertex] = data;
}
}
public int[]
dijkstra(String startVertexData) {
int
startVertex = findIndex(startVertexData);
int[]
distances = new int[size];
boolean[]
visited = new boolean[size];
for (int i
= 0; i < size; i++) {
distances[i] = Integer.MAX_VALUE;
}
distances[startVertex] = 0;
for (int i
= 0; i < size; i++) {
int u
= minDistance(distances, visited);
if (u
== -1) break;
visited[u] = true;
for
(int v = 0; v < size; v++) {
if
(!visited[v] && adjMatrix[u][v] != 0 && distances[u] !=
Integer.MAX_VALUE) {
int newDist = distances[u] + adjMatrix[u][v];
if (newDist < distances[v]) {
distances[v] = newDist;
}
}
}
}
return
distances;
}
private int
findIndex(String data) {
for (int i
= 0; i < size; i++) {
if
(vertexData[i].equals(data)) {
return i;
}
}
return -1;
}
private int
minDistance(int[] distances, boolean[] visited) {
int min =
Integer.MAX_VALUE, minIndex = -1;
for (int v
= 0; v < size; v++) {
if
(!visited[v] && distances[v] <= min) {
min = distances[v];
minIndex = v;
}
}
return
minIndex;
}
}
public static void
main(String[] args) {
Graph g = new
Graph(7);
g.addVertexData(0, "A");
g.addVertexData(1, "B");
g.addVertexData(2, "C");
g.addVertexData(3, "D");
g.addVertexData(4, "E");
g.addVertexData(5, "F");
g.addVertexData(6, "G");
g.addEdge(3,
0, 4); // D - A, weight 4
g.addEdge(3,
4, 2); // D - E, weight 2
g.addEdge(0,
2, 3); // A - C, weight 3
g.addEdge(0,
4, 4); // A - E, weight 4
g.addEdge(4,
2, 4); // E - C, weight 4
g.addEdge(4,
6, 5); // E - G, weight 5
g.addEdge(2,
5, 5); // C - F, weight 5
g.addEdge(2,
1, 2); // C - B, weight 2
g.addEdge(1,
5, 2); // B - F, weight 2
g.addEdge(6,
5, 5); // G - F, weight 5
// Dijkstra's
algorithm from D to all vertices
System.out.println("Dijkstra's Algorithm starting from vertex
D:\n");
int[]
distances = g.dijkstra("D");
for (int i =
0; i < distances.length; i++) {
System.out.println("Shortest distance from D to " +
g.vertexData[i] + ": " + distances[i]);
}
}
}
//Java
The Bellman-Ford Algorithm
The Bellman-Ford algorithm is best suited to find the
shortest paths in a directed graph, with one or more negative edge weights,
from the source vertex to all other vertices.
The Bellman-Ford algorithm can also be used for graphs with
positive edges (both directed and undirected), like we can with Dijkstra's
algorithm, but Dijkstra's algorithm is preferred in such cases because it is
faster.
Using the Bellman-Ford algorithm on a graph with negative
cycles will not produce a result of shortest paths because in a negative cycle
we can always go one more round and get a shorter path.
A negative cycle is a path we can follow in circles, where
the sum of the edge weights is negative.
Luckily, the Bellman-Ford algorithm can be implemented to
safely detect and report the presence of negative cycles.
How it works:
- Set
initial distance to zero for the source vertex, and set initial distances
to infinity for all other vertices.
- For
each edge, check if a shorter distance can be calculated, and update the
distance if the calculated distance is shorter.
- Check
all edges (step 2) V−1 times. This is as many times as there are
vertices (V), minus one.
- Optional:
Check for negative cycles. This will be explained in better detail later.
The Euclidean Algorithm
The Euclidean algorithm finds the greatest common divisor (gcd) of
two numbers a and b.
Here 21 is the common gretest divisior.
Euclidean
Algorithm - An example ← Number Theory
How it works:
- Start
with the two initial numbers a and b.
- Do a
division with remainder: a=q0⋅b+r0
- Use
the remainder (r0) and the divisor (b) from the last calculation to set up
the next calculation: b=q1⋅r0+r1
- Repeat
steps 2 and 3 until the remainder is 0.
- The
second last remainder calculated is the greatest common divisor.
Find
Greatest Common Divisor of Array - LeetCode
GCD
of Odd and Even Sums - LeetCode
class Solution {
public int
findGCD(int[] nums) {
Arrays.sort(nums);
int
min=nums[0];
int
max=nums[nums.length-1];
int rem=1;
do{
rem=max%min;
max=min;
min=rem;
// System.out.println("min"+ min+
"max"+max "rem"+ rem);
}
while (rem!=0);
return max;
}
}
Huffman Coding
Huffman Coding is an algorithm used for lossless data
compression.
Huffman Coding is also used as a component in many different
compression algorithms. It is used as a component in lossless compressions such
as zip, gzip, and png, and even as part of lossy compression algorithms like
mp3 and jpeg.
Use the animation below to see how a text can be compressed
using Huffman Coding.
The Huffman code is 22% of the original size.
The animation shows how the letters in a text are normally
stored using UTF-8,
and how Huffman Coding makes it possible to store the same text with fewer
bits.
How it works:
- Count
how often each piece of data occurs.
- Build
a binary
tree, starting with the nodes with the lowest count. The new parent
node has the combined count of its child nodes.
- The
edge from a parent gets '0' for the left child, and '1' for the edge to
the right child.
- In
the finished binary tree, follow the edges from the root node, adding '0'
or '1' for each branch, to find the new Huffman code for each piece of
data.
- Create
the Huffman code by converting the data, piece-by-piece, into a binary
code using the binary tree.
Huffman
coding step-by-step example
The Traveling Salesman Problem
The Traveling Salesman Problem states that you are a
salesperson and you must visit a number of cities or towns.
The Traveling Salesman Problem
Rules: Visit every city only once, then return back
to the city you started in.
Goal: Find the shortest possible route.
Checking All Routes to Solve The Traveling Salesman Problem
To find the optimal solution to The Traveling Salesman
Problem, we will check all possible routes, and every time we find a shorter
route, we will store it, so that in the end we will have the shortest route.
Good: Finds the overall shortest route.
Bad: Requires an awful lot of calculation,
especially for a large amount of cities, which means it is very time consuming.
How it works:
- Check
the length of every possible route, one route at a time.
- Is
the current route shorter than the shortest route found so far? If so,
store the new shortest route.
- After
checking all routes, the stored route is the shortest one.
Such a way of finding the solution to a problem is
called brute force.
Brute force is not really an algorithm, it just means
finding the solution by checking all possibilities, usually because of a lack
of a better way to do it.
https://www.geeksforgeeks.org/dsa/travelling-salesman-problem-implementation-using-backtracking/
Traveling
Salesman Problem using Dynamic Programming | DAA -explained.
Gas code problem
Gas
Station - LeetCode
https://leetcode.com/problems/add-two-numbers/
You are given two non-empty linked lists
representing two non-negative integers. The digits are stored in reverse
order, and each of their nodes contains a single digit. Add the two numbers
and return the sum as a linked list.
You may assume the two numbers do not contain any leading
zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
class Solution {
public ListNode addTwoNumbers(ListNode l1,
ListNode l2) {
ListNode dummy = new
ListNode(0);
ListNode curr = dummy;
int rem = 0;
while (l1 != null || l2 != null
|| rem != 0) {
int sum = rem;
if (l1 != null) {
sum
+= l1.val;
l1 =
l1.next;
}
if (l2 != null) {
sum
+= l2.val;
l2 =
l2.next;
}
rem = sum / 10;
curr.next = new
ListNode(sum % 10);
curr = curr.next;
}
return dummy.next;
}
}
Maximum
Depth of Binary Tree - LeetCode
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return
1+Math.max(maxDepth(root.right), maxDepth(root.left));
}
Minimum
Depth of Binary Tree - LeetCode
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left,
TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
if (root.left == null
&& root.right == null)
return 1;
if (root.left == null)
return 1 +
minDepth(root.right);
if (root.right == null)
return 1 +
minDepth(root.left);
return 1+
Math.min(minDepth(root.left), minDepth(root.right));
}
}
Merge
Two Binary Trees - LeetCode
class Solution {
public TreeNode mergeTrees(TreeNode root1,
TreeNode root2) {
TreeNode root= new TreeNode();
if (root1 == null) return root2;
if (root2 == null) return root1;
root.val =root1.val+ root2.val;
root.left =
mergeTrees(root1.left, root2.left);
root.right =
mergeTrees(root1.right, root2.right);
return root;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int
targetSum) {
if (root == null) return false;
// if it's a leaf node
if (root.left == null &&
root.right == null) {
return targetSum
== root.val;
}
return hasPathSum(root.left,
targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
}
Binary
Tree Level Order Traversal - LeetCode
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left,
TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>>
levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
levelOrderRec(root, 0, res);
return res;
}
public void levelOrderRec(TreeNode root, int
level,
List<List<Integer>> res)
{
// Base case
if (root == null)
return;
// Add a new level to the result
if needed
if (res.size() <= level)
res.add(new
ArrayList<>());
// Add current node's data to
its corresponding
// level
res.get(level).add(root.val);
// Recur for left and right
children
levelOrderRec(root.left, level +
1, res);
levelOrderRec(root.right, level
+ 1, res);
}
}
Alternate solution:
class Solution {
public
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root ==
null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while
(!queue.isEmpty()) {
int size =
queue.size(); // nodes at
current level
List<Integer> level = new ArrayList<>();
for (int i
= 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if
(node.left != null) queue.offer(node.left);
if
(node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
}
Binary
Tree Zigzag Level Order Traversal - LeetCode
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left,
TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>>
zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
levelOrderRec(root, 0, res);
return res;
}
public void levelOrderRec(TreeNode root, int
level,
List<List<Integer>> res)
{
// Base case
if (root == null)
return;
// Add a new level to the result
if needed
if (res.size() <= level)
res.add(new
ArrayList<>());
// 🔥 zigzag logic
if (level % 2 == 0) {
res.get(level).add(root.val); // left → right
} else {
res.get(level).add(0, root.val); // right → left
}
// Recur for left and right
children
levelOrderRec(root.left, level +
1, res);
levelOrderRec(root.right, level
+ 1, res);
}
}
Validate
Binary Search Tree - LeetCode
class Solution {
public boolean isValidBST(TreeNode root) {
return check(root, null, null);
}
private boolean check(TreeNode node, Integer
min, Integer max) {
if (node == null) return true;
if ((min != null &&
node.val <= min) ||
(max != null
&& node.val >= max))
return false;
return check(node.left, min,
node.val) &&
check(node.right, node.val, max);
}
}
Move zeros:
Move
Zeroes - LeetCode
class Solution {
public void moveZeroes(int[] nums) {
int count = 0;
for (int i = 0; i <
nums.length; i++) {
if (nums[i] != 0)
{
nums[count] = nums[i];
count++;
}
}
for (int i = count; i <
nums.length; i++) {
nums[i] = 0;
}
}
}
Longest
Increasing Subsequence - LeetCode
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j
< i; j++) {
if
(nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max =
Math.max(max, dp[i]);
}
return max;
}
}
Zigzag
Conversion - LeetCode (more than medium, it’s a complex solution)
Tree Terminology and Rules
Learn words used to describe the tree data structure by
using the interactive tree visualization below.
The first node in a tree is called the root node.
A link connecting one node to another is called an edge.
A parent node has links to its child nodes.
Another word for a parent node is internal node.
A node can have zero, one, or many child nodes.
A node can only have one parent node.
Nodes without links to other child nodes are called leaves,
or leaf nodes.
The tree height is the maximum number of
edges from the root node to a leaf node. The height of the tree above is 2.
The height of a node is the maximum number
of edges between the node and a leaf node.
The tree size is the number of nodes in the
tree.
Types of Trees
Trees are a fundamental data structure in computer science,
used to represent hierarchical relationships. This tutorial covers several key
types of trees.
Binary Trees: Each node has up to two children,
the left child node and the right child node. This structure is the foundation
for more complex tree types like Binay Search Trees and AVL Trees.
Binary Search Trees (BSTs): A type of Binary
Tree where for each node, the left child node has a lower value, and the right
child node has a higher value.
AVL Trees: A type of Binary Search Tree that
self-balances so that for every node, the difference in height between the left
and right subtrees is at most one. This balance is maintained through rotations
when nodes are inserted or deleted.
Binary Trees vs Arrays and Linked Lists
Benefits of Binary Trees over Arrays and Linked Lists:
- Arrays are
fast when you want to access an element directly, like element number 700
in an array of 1000 elements for example. But inserting and deleting
elements require other elements to shift in memory to make place for the
new element, or to take the deleted elements place, and that is time
consuming.
- Linked
Lists are fast when inserting or deleting nodes, no memory
shifting needed, but to access an element inside the list, the list must
be traversed, and that takes time.
- Binary
Trees, such as Binary Search Trees and AVL Trees, are great compared
to Arrays and Linked Lists because they are BOTH fast at accessing a node,
AND fast when it comes to deleting or inserting a node, with no shifts in
memory needed.
A balanced Binary Tree has at most 1 in
difference between its left and right subtree heights, for each node in the
tree.
A complete Binary Tree has all levels full
of nodes, except the last level, which is can also be full, or filled from left
to right. The properties of a complete Binary Tree means it is also balanced.
A full Binary Tree is a kind of tree where
each node has either 0 or 2 child nodes.
A perfect Binary Tree has all leaf nodes on
the same level, which means that all levels are full of nodes, and all internal
nodes have two child nodes.The properties of a perfect Binary Tree means it is
also full, balanced, and complete.
There are two main categories of Tree traversal methods:
Breadth First Search (BFS) is when the nodes on
the same level are visited before going to the next level in the tree. This
means that the tree is explored in a more sideways direction.
Depth First Search (DFS) is when the traversal
moves down the tree all the way to the leaf nodes, exploring the tree branch by
branch in a downwards direction.
There are three different types of DFS traversals:
pre-order
public static void
preOrderTraversal(TreeNode node) {
if (node ==
null) {
return;
}
System.out.print(node.data + ", ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
Inorder
public static void
inOrderTraversal(TreeNode node) {
if (node ==
null) {
return;
}
inOrderTraversal(node.left);
System.out.print(node.data + ", ");
inOrderTraversal(node.right);
}
Post order
public static void postOrderTraversal(TreeNode node) {
if (node ==
null) {
return;
}
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.data + ", ");
}
Complete implementation:
public class Main {
public static
class TreeNode {
String data;
TreeNode left;
TreeNode
right;
public
TreeNode(String data) {
this.data
= data;
this.left
= null;
this.right
= null;
}
}
public static void
preOrderTraversal(TreeNode node) {
if (node ==
null) {
return;
}
System.out.print(node.data + ", ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
public static void
main(String[] args) {
TreeNode root
= new TreeNode("R");
TreeNode nodeA
= new TreeNode("A");
TreeNode nodeB
= new TreeNode("B");
TreeNode nodeC
= new TreeNode("C");
TreeNode nodeD
= new TreeNode("D");
TreeNode nodeE
= new TreeNode("E");
TreeNode nodeF
= new TreeNode("F");
TreeNode nodeG
= new TreeNode("G");
root.left =
nodeA;
root.right =
nodeB;
nodeA.left =
nodeC;
nodeA.right =
nodeD;
nodeB.left =
nodeE;
nodeB.right =
nodeF;
nodeF.left =
nodeG;
// Traverse
preOrderTraversal(root);
}
}
DFS
traversal of a Tree - GeeksforGeeks
BFS traversal using
primary and queue approaches:
Level
Order Traversal (Breadth First Search) of Binary Tree - GeeksforGeeks
Binary
Tree Level Order Traversal II - LeetCode
The below code will give you Output for this tree:
[[3],[9],[20],[15],[7]]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left,
TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>>
levelOrderBottom(TreeNode root) {
List<List<Integer>>
arr = new ArrayList<>();
bfsTravel(root, arr);
return arr;
}
void bfsTravel(TreeNode
node,List<List<Integer>> arr ){
if(node==null){
return ;
}
//maintain a level, without
level its not possible
ArrayList<Integer> arr1=new
ArrayList<>();
arr1.add(node.val);
arr.add(arr1);
bfsTravel(node.left, arr);
bfsTravel(node.right, arr);
}
}
We can input the level, if you want to add the node in
different nodes.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left,
TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>>
levelOrderBottom(TreeNode root) {
List<List<Integer>>
arr = new ArrayList<>();
bfsTravel(root, arr, 0);
return arr;
}
void bfsTravel(TreeNode
node,List<List<Integer>> arr, int level ){
if(node==null){
return ;
}
//maintain a level, without
level its not possible
System.out.println(level
+":"+node.val);
if (arr.size() <= level)
arr.add(new
ArrayList<>());
arr.get(level).add(node.val);
bfsTravel(node.left, arr, level+1);
bfsTravel(node.right, arr, level+1);
}
}
Binary
Tree Level Order Traversal II - LeetCode
class Solution {
public List<List<Integer>>
levelOrderBottom(TreeNode root) {
List<List<Integer>>
arr = new ArrayList<>();
bfsTravel(root, arr, 0);
//return arr;
List<List<Integer>> returnList = new ArrayList<>();
for(int i=arr.size()-1;
i>=0;i--){
returnList.add(arr.get(i));
}
return returnList;
}
void bfsTravel(TreeNode
node,List<List<Integer>> arr, int level ){
if(node==null){
return ;
}
//maintain a level, without
level its not possible
System.out.println(level
+":"+node.val);
if (arr.size() <= level)
arr.add(new
ArrayList<>());
arr.get(level).add(node.val);
bfsTravel(node.left, arr, level+1);
bfsTravel(node.right, arr, level+1);
}
Graphs
A Graph is a non-linear data structure that consists of
vertices (nodes) and edges.
A vertex, also called a node, is a point or an object in the
Graph, and an edge is used to connect two vertices with each other.
Graphs are non-linear because the data structure allows us
to have different paths to get from one vertex to another, unlike with linear
data structures like Arrays or Linked Lists.
A weighted Graph is a Graph where the edges
have values. The weight value of an edge can represent things like distance,
capacity, time, or probability.
A connected Graph is when all the vertices
are connected through edges somehow. A Graph that is not connected, is a Graph
with isolated (disjoint) subgraphs, or single isolated vertices.
A directed Graph, also known as a digraph,
is when the edges between the vertex pairs have a direction. The direction of
an edge can represent things like hierarchy or flow.
A cyclic Graph is defined differently depending on whether
it is directed or not:
- A directed
cyclic Graph is when you can follow a path along the directed
edges that goes in circles. Removing the directed edge from F to G in the
animation above makes the directed Graph not cyclic anymore.
- An undirected
cyclic Graph is when you can come back to the same vertex you
started at without using the same edge more than once. The undirected
Graph above is cyclic because we can start and end up in vertes C without
using the same edge twice.
A loop, also called a self-loop, is an edge that
begins and ends on the same vertex. A loop is a cycle that only consists of one
edge. By adding the loop on vertex A in the animation above, the Graph becomes
cyclic.
Adjacency Matrix Graph Representation
Adjacency Matrix is the Graph representation (structure) we
will use for this tutorial.
How to implement an Adjacency Matrix is shown on the next
page.
The Adjacency Matrix is a 2D array (matrix) where each cell
on index (i,j) stores information about the edge from
vertex i to vertex j.
Below is a Graph with the Adjacency Matrix representation
next to it.
public void
addEdge(int u, int v) {
if (u >= 0
&& u < size && v >= 0 && v < size) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1;
}
}
class Graph {
private int[][]
adjMatrix;
private char[]
vertexData;
private int size;
public Graph(int
size) {
this.size =
size;
this.adjMatrix
= new int[size][size];
this.vertexData = new char[size];
}
public void
addEdge(int u, int v) {
if (u >= 0
&& u < size && v >= 0 && v < size) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1;
}
}
public void
addVertexData(int vertex, char data) {
if (vertex
>= 0 && vertex < size) {
vertexData[vertex] = data;
}
}
public void
printGraph() {
System.out.println("Adjacency Matrix:");
for (int i =
0; i < size; i++) {
for (int j
= 0; j < size; j++) {
System.out.print(adjMatrix[i][j] + " ");
}
System.out.println();
}
System.out.println("\nVertex Data:");
for (int i =
0; i < size; i++) {
System.out.println("Vertex " + i + ": " +
vertexData[i]);
}
}
}
public class Main {
public static void
main(String[] args) {
Graph g = new
Graph(4);
g.addVertexData(0, 'A');
g.addVertexData(1, 'B');
g.addVertexData(2, 'C');
g.addVertexData(3, 'D');
g.addEdge(0,
1); // A - B
g.addEdge(0,
2); // A - C
g.addEdge(0,
3); // A - D
g.addEdge(1,
2); // B - C
g.printGraph();
}
}
//Java
Graph traversal:
Breadth First Search Traversal (queue)
Breadth First Search visits all adjacent vertices of a
vertex before visiting neighboring vertices to the adjacent vertices. This
means that vertices with the same distance from the starting vertex are visited
before vertices further away from the starting vertex are visited.
How it works:
- Put
the starting vertex into the queue.
- For
each vertex taken from the queue, visit the vertex, then put all unvisited
adjacent vertices into the queue.
- Continue
as long as there are vertices in the queue.
Depth First Search Traversal (stack)
Depth First Search is said to go "deep" because it
visits a vertex, then an adjacent vertex, and then that vertex' adjacent
vertex, and so on, and in this way the distance from the starting vertex
increases for each recursive iteration.
How it works:
- Start
DFS traversal on a vertex.
- Do a
recursive DFS traversal on each of the adjacent vertices as long as they
are not already visited.
Linear search algorithms:
Linear
Search Algorithm - GeeksforGeeks
Binary search;
class GFG {
static int
binarySearch(int arr[], int x) {
int low = 0,
high = arr.length - 1;
while (low
<= high) {
int mid =
low + (high - low) / 2;
// Check
if x is present at mid
if
(arr[mid] == x)
return
mid;
// If x
greater, ignore left half
if
(arr[mid] < x)
low =
mid + 1;
// If x is
smaller, ignore right half
else
high =
mid - 1;
}
// If we reach
here, then element was
// not present
return -1;
}
public static void
main(String args[]) {
int arr[] = {
2, 3, 4, 10, 40 };
int x = 10;
int result =
binarySearch(arr, x);
if (result ==
-1)
System.out.println(
"Element is not present in array");
else
System.out.println("Element is present at "
+ "index
" + result);
}
}
Interpolation search:
Interpolation
Search Algorithm
Jump search Algorithm:
Design Question:
Geico
System Design Interview: The Complete Guide
Functional and Non Functional requirements.
Design amazon prime:
System
Design Interview: Design Amazon Prime Video 
Course:
Software Architecture & System Design Practical Case Studies | Udemy
Business
Design a tiny url:
System
Design : Scalable URL shortener service like TinyURL | by Sandeep Verma |
Medium
Conversation we can start with like:
How long a tiny url would be ? Will it ever expire ?
Assume once a url created it will remain forever in system.
Then we need to store in database.
Can a customer create a tiny url of his/her choice or
will it always be service generated ? If user is allowed to create customer
shortened links, what would be the maximum size of custom url ?
Yes user can create a tiny url of his/her choice. Assume
maximum character limit to be 16.
How many url shortening request expected per month ?
Assume 100 million new URL shortenings per month
Do we expect service to provide metrics like most visited
links ?
Yes. Service should also aggregate metrics like number of
URL redirections per day and other analytics for targeted advertisements.
3. System Design goals
Functional Requirements:
- Service
should be able to create shortened url/links against a long url
- Click
to the short URL should redirect the user to the original long URL
- Shortened
link should be as small as possible
- Users
can create custom url with maximum character limit of 16
- Service
should collect metrics like most clicked links
- Once
a shortened link is generated it should stay in system for lifetime
Non-Functional Requirements:
- Service
should be up and running all the time
- URL
redirection should be fast and should not degrade at any point of time
(Even during peak loads)
- Service
should expose REST API’s so that it can be integrated with third party
applications
4. Traffic and System Capacity
Traffic
Assuming 200:1 read/write ratio
Number of unique
shortened links generated per month = 100 million
Number of unique
shortened links generated per seconds = 100 million /(30 days * 24 hours * 3600
seconds ) ~ 40 URLs/second
With 200:1 read/write
ratio, number of redirections = 40 URLs/s * 200 = 8000 URLs/s
Storage
Assuming lifetime of
service to be 100 years and with 100 million shortened links creation per
month, total number of data points/objects in system will be = 100
million/month * 100 (years) * 12 (months) = 120 billion
Assuming size of each
data object (Short url, long
url, created date etc.) to be 500 bytes long, then total
require storage = 120 billion * 500 bytes =60TB
Memory
Following Pareto
Principle, better known as the 80:20 rule for caching. (80% requests are for
20% data)
Since we get 8000
read/redirection requests per second, we will be getting 700 million requests
per day:
8000/s * 86400 seconds
=~700 million
To cache 20% of these
requests, we will need ~70GB of memory.
0.2 * 700 million * 500
bytes = ~70GB
Estimates
Shortened URLs generated : 40/s
Shortened URLs generated in 100 years : 120
billion
Total URL requests/redirections : 8000/s
Storage for 100 years : 60TB
Cache memory : 70GB
5. High Level Design
Following is high level design of our URL service. This is a
rudimentary design. We will optimise this further as we move along.
Press enter or click to view image in full size
Fig. 1 A Rudimentary design for URL service
Problems with above design :
- There
is only one WebServer which is single point of failure (SPOF)
- System
is not scalable
- There
is only single database which might not be sufficient for 60 TB of storage
and high load of 8000/s read requests
To cater above limitations we :
- Added
a load balancer in front of WebServers
- Sharded
the database to handle huge object data
- Added
cache system to reduce load on the database.
4.
5.
6. Algorithm REST Endpoints
Let’s starts by making two functions accessible through REST
API:
create( long_url, api_key, custom_url)
POST
Tinyrl : POST : https://tinyurl.com/app/api/create
Request Body: {url=long_url}
Return OK (200), with the generated short_url in data
long_url: A long URL that needs to be shortened.
api_key: A unique API key provided to each user, to protect
from the spammers, access, and resource control for the user, etc.
custom_url(optional): The custom short link URL, user
want to use.
Return Value: The short Url generated, or error
code in case of the inappropriate parameter.
Technique 1 —Short url from random numbers:
Technique 2 — Short urls from base conversion:
Let’s number each of our 62 numerals, like so:
0: 0,
1: 1,
2: 2,
3: 3,
...
10: a,
11: b,
12: c,
...
36: A,
37: B,
38: C,
...
61: Z
Technique 3 — MD5 hash :
The MD5 message-digest algorithm is a
widely used hash function producing a 128-bit hash
value(or 32 hexadecimal digits). We can use these 32 hexadecimal
digit for generating 7 characters long tiny url.
- Encode
the long URL using the MD5 algorithm and take only the first 7 characters
to generate TinyURL.
- The
first 7 characters could be the same for different long URLs so check the
DB to verify that TinyURL is not used already
- Try
next 7 characters of previous choice of 7 characters already exist in DB
and continue until you find a unique value
9. Cache
We can cache URLs that are frequently accessed. We can use some
off-the-shelf solution like Memcached, which can store full URLs with their respective hashes. Before
hitting backend storage, the application servers can quickly check if the cache
has the desired URL.
How much cache memory should we have? We can start with 20% of daily traffic and, based on clients’
usage patterns, we can adjust how many cache servers we need. As estimated
above, we need 70GB memory to cache 20% of daily traffic. Since a modern-day
server can have 256GB memory, we can easily fit all the cache into one machine.
Alternatively, we can use a couple of smaller servers to store all these hot
URLs.
10. Load Balancer (LB)
We can add a Load balancing layer at three places in our
system:
- Between
Clients and Application servers
- Between
Application Servers and database servers
- Between
Application Servers and Cache servers
Design
Dropbox - A System Design Interview Question - GeeksforGeeks
Design patterns:
Top
30 Java Design Patterns Interview Question - GeeksforGeeks
This looks like the Codility problem: build a string
using A times 'a' and B times 'b' such that no three consecutive characters
are the same.
Your current code has multiple issues:
- You
reduce A by 2 even when appending only one "a"
- It
can create "aaa" / "bbb"
- It
doesn’t append remaining characters safely
- Loop
condition and equality case are wrong
class Solution {
public String
solution(int A, int B) {
StringBuilder
result = new StringBuilder();
while (A >
0 || B > 0) {
int len =
result.length();
// Check
last two characters
boolean
lastTwoA = len >= 2 &&
result.charAt(len - 1) == 'a' &&
result.charAt(len - 2) == 'a';
boolean
lastTwoB = len >= 2 &&
result.charAt(len - 1) == 'b' &&
result.charAt(len - 2) == 'b';
if ((A
>= B && !lastTwoA) || lastTwoB) {
result.append('a');
A--;
} else {
result.append('b');
B--;
}
}
return
result.toString();
}
}
Codility Question:
🧱 StoneWall (Codility)
🧩 Problem Summary
You are given an array H[] where:
- H[i]
= height of wall at position i
- You
can build the wall using rectangular blocks
- Each
block has a fixed height and width
- Goal:
minimum number of blocks
🧠 Key Insight
- When
height increases → need a new block
- When
height decreases → previous blocks end
- When
height stays the same → reuse block
This is a classic stack problem.
StoneWall
coding task - Learn to Code - Codility
🔍 Example Input
H = [8, 8, 5, 7, 9, 8, 7, 4, 8]
📦 Step-by-Step Execution
Initialize
stack = []
blocks = 0
i = 0 → height = 8
- Stack
empty → push 8
stack = [8]
blocks = 1
i = 1 → height = 8
- Same
as top → do nothing
stack = [8]
blocks = 1
i = 2 → height = 5
- Pop
while stack top > 5
pop 8
- Stack
empty → push 5
stack = [5]
blocks = 2
i = 3 → height = 7
- 7
> 5 → push
stack = [5, 7]
blocks = 3
i = 4 → height = 9
- 9
> 7 → push
stack = [5, 7, 9]
blocks = 4
i = 5 → height = 8
- Pop
while > 8
pop 9
- 8
> 7 → push
stack = [5, 7, 8]
blocks = 5
i = 6 → height = 7
- Pop
while > 7
pop 8
- Same
as top → do nothing
stack = [5, 7]
blocks = 5
i = 7 → height = 4
- Pop
while > 4
pop 7
pop 5
- Stack
empty → push
stack = [4]
blocks = 6
i = 8 → height = 8
- 8
> 4 → push
stack = [4, 8]
blocks = 7
✅ Final Answer
Minimum blocks = 7
💻 Java Solution
(Interview-Ready)
import java.util.Stack;
class Solution {
public int
solution(int[] H) {
Stack<Integer> stack = new Stack<>();
int blocks =
0;
for (int
height : H) {
while
(!stack.isEmpty() && stack.peek() > height) {
stack.pop();
}
if
(stack.isEmpty() || stack.peek() < height) {
stack.push(height);
blocks++;
}
}
return blocks;
}
}
⏱ Complexity
- Time:
O(N)
- Space:
O(N)
TOP 5 To Practice First (GEICO Priority)
- Fish
- StoneWall
- NumberOfDiscIntersections
- MaxCounters
- EquiLeader
Comments
Post a Comment