Algorithms and Problem Solving with Java
Practice and Assessment
You are viewing a free preview lesson.
Module Overview
এই module-এ আমরা Java ব্যবহার করে algorithmic problem solving-এর foundation তৈরি করেছি।
আমরা শিখেছি:
Big-O
Linear Search
Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Java sorting APIs
Comparable
Comparator
Stack
Queue
Deque
Heap
PriorityQueue
HashMap
HashSet
Binary Search Tree
Tree traversal
এই assessment-এর লক্ষ্য শুধু definitions মনে আছে কি না তা দেখা নয়।
আপনি যেন একটি problem দেখে reason করতে পারেন:
কোন data structure fit করে?
কোন algorithm fit করে?
Expected complexity কী?
কোথায় hidden expensive operation আছে?
Standard Java API কখন ব্যবহার করা উচিত?
Part 1 — Big-O Review
নিচের code snippets-এর time complexity identify করুন।
Assume called operations are O(1) unless otherwise mentioned।
Question 1
static int first(
int[] values
) {
return values[0];
}
Answer
O(1)
Input যত বড়ই হোক, একটি fixed index access করা হচ্ছে।
Question 2
static int sum(
int[] values
) {
int total =
0;
for (
int value
: values
) {
total +=
value;
}
return total;
}
Answer
O(n)
প্রতিটি element একবার process করা হচ্ছে।
Question 3
for (
int first
: values
) {
for (
int second
: values
) {
process(
first,
second
);
}
}
Answer
O(n²)
Question 4
for (
int value
: values
) {
process(
value
);
}
for (
int value
: values
) {
save(
value
);
}
Answer
O(n)
Because:
O(n + n)
=
O(2n)
=
O(n)
Question 5
int value =
n;
while (
value > 1
) {
value /=
2;
}
Answer
O(log n)
Question 6
for (
int i = 0;
i < learners.size();
i++
) {
if (
enrolledLearners.contains(
learners.get(
i
)
)
) {
...
}
}
Assume:
enrolledLearners
is an ArrayList with size proportional to n।
Answer
O(n²)
Outer loop:
O(n)
ArrayList.contains():
O(n)
Combined:
O(n × n)
=
O(n²)
Question 7
If enrolledLearners becomes:
HashSet<Learner>
and hash operations behave normally, expected complexity becomes:
Answer
O(n)
because each membership check is average expected:
O(1)
Part 2 — Choose the Correct Data Structure
For each requirement, choose the most appropriate starting point।
Options may include:
List
Set
HashSet
Map
HashMap
Queue
Deque as Stack
PriorityQueue
Sorted array + Binary Search
TreeMap
Scenario 1
Need:
Unique course codes
Answer
HashSet<String>
if ordering is not required।
Scenario 2
Need:
CourseCode → Course
with frequent exact lookup।
Answer
HashMap<CourseCode, Course>
Scenario 3
Need tasks processed in arrival order।
Answer
Queue<Task>
with a common implementation:
ArrayDeque<Task>
Scenario 4
Need most recent action undone first।
Answer
Deque<Action>
used as a Stack।
Scenario 5
Need most urgent task processed first।
Answer
PriorityQueue<Task>
with an appropriate Comparator।
Scenario 6
Need keys maintained in sorted order।
Answer
TreeMap<K, V>
if map semantics are required।
Scenario 7
Need one lookup in a small unsorted array।
Answer
Usually:
Linear Search
Scenario 8
Need thousands of lookups in a large already-sorted array।
Answer
Binary Search
Part 3 — Linear Search
Implement:
static int indexOf(
int[] values,
int target
)
Return:
matching index
or:
-1
Solution
static int indexOf(
int[] values,
int target
) {
for (
int i = 0;
i < values.length;
i++
) {
if (
values[i]
== target
) {
return i;
}
}
return -1;
}
Worst-case time:
O(n)
Extra space:
O(1)
Part 4 — Binary Search
Implement Binary Search for a sorted integer array।
Solution
static int binarySearch(
int[] sorted,
int target
) {
int left =
0;
int right =
sorted.length - 1;
while (
left <= right
) {
int middle =
left
+ (
right - left
) / 2;
if (
sorted[middle]
== target
) {
return middle;
}
if (
sorted[middle]
< target
) {
left =
middle + 1;
} else {
right =
middle - 1;
}
}
return -1;
}
Worst-case:
O(log n)
Requirement:
Input must be sorted.
Binary Search Debugging
What is wrong here?
if (
sorted[middle]
< target
) {
left =
middle;
}
Answer
The already-checked middle remains inside the search range।
In some cases the algorithm can repeatedly calculate the same middle index and never terminate।
Correct:
left =
middle + 1;
Likewise:
right =
middle - 1;
when moving left।
Part 5 — Search Strategy Reasoning
Suppose you have:
2,000,000 unsorted IDs
and need exactly:
one lookup
Would you:
A. Sort then Binary Search
B. Linear Search
Answer
Usually:
B. Linear Search
One linear scan:
O(n)
is asymptotically cheaper than:
sorting O(n log n)
+
searching O(log n)
for a single lookup।
Repeated Lookup Variation
Now suppose those two million IDs are loaded once and checked millions of times।
A strong alternative is:
HashSet<Long>
Build:
expected O(n)
Then each exact membership lookup:
average expected O(1)
Part 6 — Simple Sorting
Given:
[5, 3, 4, 1]
answer the following।
Bubble Sort
After the first full pass:
Answer
3 4 1 5
The largest value reaches the end।
Selection Sort
Which value is placed at index 0 after the first round?
Answer
1
Insertion Sort
After processing:
5
3
4
the sorted prefix becomes:
Answer
3 4 5
Simple Sort Complexity Review
| Algorithm | Best | Worst | Extra Space |
|---|---|---|---|
| Bubble Sort, optimized | O(n) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(1) |
Part 7 — Implement Insertion Sort
Implement ascending Insertion Sort।
Solution
static void insertionSort(
int[] values
) {
for (
int i = 1;
i < values.length;
i++
) {
int current =
values[i];
int position =
i - 1;
while (
position >= 0
&& values[position]
> current
) {
values[position + 1] =
values[position];
position--;
}
values[position + 1] =
current;
}
}
Why Save current?
Because shifting values may overwrite:
values[i]
So the value being inserted must be preserved first।
Part 8 — Merge Sort Reasoning
Explain Merge Sort using three steps।
Answer
1. Split the range into halves.
2. Recursively sort both halves.
3. Merge the sorted halves.
Merge Sort Complexity
Time
O(n log n)
for:
best
average
worst
in the standard implementation studied।
Extra array space
O(n)
Why O(n log n)?
Because:
log n recursive levels
and approximately:
n work per merge level
So:
n × log n
=
O(n log n)
Part 9 — Quick Sort Reasoning
What are the main stages?
Answer
1. Choose a pivot.
2. Partition the range around the pivot.
3. Recursively sort the left region.
4. Recursively sort the right region.
Quick Sort Complexity
Typical average:
O(n log n)
Textbook worst case:
O(n²)
Poor Pivot Scenario
Using the last value as pivot on:
1 2 3 4 5 6 7
can repeatedly create partitions like:
n - 1
and
0
This produces a highly unbalanced recursion tree।
Part 10 — Standard Java Sorting
Production code needs to sort:
int[] values
What should normally be used?
Answer
Arrays.sort(
values
);
not a handwritten Bubble Sort, Merge Sort, or Quick Sort unless there is a specific reason।
Sort a Mutable List
List<String> names =
new ArrayList<>(
List.of(
"Sumu",
"Nur",
"Sakib"
)
);
Natural order:
names.sort(
Comparator.naturalOrder()
);
Part 11 — Comparator Assessment
Given:
record Course(
String code,
String title,
long priceInPaisa
) {
}
Sort by price ascending।
Solution
courses.sort(
Comparator.comparingLong(
Course::priceInPaisa
)
);
Price Descending
courses.sort(
Comparator.comparingLong(
Course::priceInPaisa
).reversed()
);
Price Ascending, Then Title
courses.sort(
Comparator.comparingLong(
Course::priceInPaisa
).thenComparing(
Course::title
)
);
Score Descending, Name Ascending
Given:
record Learner(
String name,
int score
) {
}
Solution
Comparator<Learner> ranking =
Comparator.comparingInt(
Learner::score
)
.reversed()
.thenComparing(
Learner::name
);
Comparator Bug
What is wrong with:
return first.score()
- second.score();
Answer
Integer subtraction can overflow।
Prefer:
Integer.compare(
first.score(),
second.score()
);
or:
Comparator.comparingInt(
Learner::score
);
Part 12 — Sorting and Binary Search
Suppose:
Comparator<Course> byCode =
Comparator.comparing(
Course::code
);
You sort:
courses.sort(
byCode
);
Then you perform Binary Search।
What comparator must be used?
Answer
The same ordering:
byCode
or another comparator defining exactly the same ordering semantics।
Binary Search requires the data to be sorted according to the search comparison rule।
Part 13 — Stack Assessment
Implement bracket validation for:
()
[]
{}
Solution
static boolean isBalanced(
String value
) {
Deque<Character> stack =
new ArrayDeque<>();
for (
int i = 0;
i < value.length();
i++
) {
char current =
value.charAt(
i
);
if (
current == '('
|| current == '['
|| current == '{'
) {
stack.push(
current
);
continue;
}
if (
current == ')'
|| current == ']'
|| current == '}'
) {
if (
stack.isEmpty()
) {
return false;
}
char opening =
stack.pop();
if (
!matches(
opening,
current
)
) {
return false;
}
}
}
return stack.isEmpty();
}
static boolean matches(
char opening,
char closing
) {
return opening == '('
&& closing == ')'
|| opening == '['
&& closing == ']'
|| opening == '{'
&& closing == '}';
}
Time:
O(n)
Worst-case extra space:
O(n)
Why Stack?
Because the most recently opened bracket must close first।
That is:
LIFO
Part 14 — Queue Assessment
Tasks arrive:
A
B
C
and must be processed in that exact arrival order।
Implementation:
Queue<String> tasks =
new ArrayDeque<>();
tasks.offer(
"A"
);
tasks.offer(
"B"
);
tasks.offer(
"C"
);
Repeated:
poll()
returns:
A
B
C
This is:
FIFO
Part 15 — BFS vs DFS
Given:
A
/ \
B C
/ \
D E
Breadth-first order:
Answer
A
B
C
D
E
Typical worklist:
Queue
One Possible Depth-First Order
Answer
A
B
D
E
C
Typical iterative worklist:
Stack
implemented using:
Deque<Node>
Why Push Right First?
To process left before right using a Stack:
stack.push(
right
);
stack.push(
left
);
Because:
Last pushed
→ first popped
Part 16 — PriorityQueue Assessment
Given:
PriorityQueue<Integer> values =
new PriorityQueue<>();
values.offer(
40
);
values.offer(
10
);
values.offer(
30
);
values.offer(
20
);
What is poll order?
Answer
10
20
30
40
Default integer PriorityQueue behaves as a min-priority queue।
Max PriorityQueue
Create one where largest value comes first।
Solution
PriorityQueue<Integer> values =
new PriorityQueue<>(
Comparator.reverseOrder()
);
PriorityQueue Complexity
Typical binary-heap operations:
peek()
→ O(1)
offer()
→ O(log n)
poll()
→ O(log n)
PriorityQueue Iteration Question
Does:
for (
int value
: queue
)
guarantee sorted order?
Answer
No।
The heap guarantees priority behavior for:
peek()
poll()
not globally sorted iteration।
Part 17 — Top-K Problem
You receive millions of numbers and need only the:
10 largest
Should you necessarily sort everything?
Answer
No।
Maintain a:
Min Heap of size 10
For each value:
heap.offer(
value
);
if (
heap.size() > 10
) {
heap.poll();
}
Expected complexity:
O(n log k)
where:
k = 10
Extra space:
O(k)
Why Min Heap for Largest K?
Because the smallest member of the current top K should be available for fast removal।
The root represents:
the weakest current candidate
Part 18 — HashSet Assessment
Implement duplicate detection।
Solution
static boolean hasDuplicate(
String[] values
) {
Set<String> seen =
new HashSet<>();
for (
String value
: values
) {
if (
!seen.add(
value
)
) {
return true;
}
}
return false;
}
Expected time:
O(n)
Extra space:
O(n)
Compare with Nested Loops
Pairwise duplicate checking:
O(n²)
HashSet version:
expected O(n)
This is a classic example of trading:
more memory
for:
faster expected execution
Part 19 — HashMap Frequency Counter
Implement:
word → count
Solution
static Map<String, Integer> frequencies(
List<String> words
) {
Map<String, Integer> counts =
new HashMap<>();
for (
String word
: words
) {
counts.merge(
word,
1,
Integer::sum
);
}
return counts;
}
Alternative
for (
String word
: words
) {
int count =
counts.getOrDefault(
word,
0
);
counts.put(
word,
count + 1
);
}
Both express the same basic algorithm।
Part 20 — equals() and hashCode()
Complete the sentence:
If two objects are equal according to equals(),
__________________________________________.
Answer
they must have the same hash code.
Does the Reverse Hold?
If:
a.hashCode()
==
b.hashCode()
must:
a.equals(
b
)
be true?
Answer
No।
That may simply be a:
hash collision
Mutable Key Problem
Why is this dangerous?
Map<UserKey, User> users =
new HashMap<>();
users.put(
key,
user
);
key.setEmail(
"changed@example.com"
);
Assume email participates in:
equals()
hashCode()
Answer
The key's hash can change after it was placed into the map।
Future lookup may search a different bucket than the one where the entry was originally stored।
Use stable or immutable hash keys।
Part 21 — HashMap as an Index
Suppose:
List<Learner> learners
contains one million learners।
You repeatedly need:
Learner by ID
Naive repeated Linear Search:
O(n)
per lookup
Build:
Map<Long, Learner> byId
once।
Then expected lookup:
O(1)
Build the Index
static Map<Long, Learner> indexById(
List<Learner> learners
) {
Map<Long, Learner> byId =
new HashMap<>();
for (
Learner learner
: learners
) {
byId.put(
learner.id(),
learner
);
}
return byId;
}
Index construction:
expected O(n)
Space:
O(n)
Part 22 — BST Terminology
Given:
40
/ \
20 60
/ \ /
10 30 50
Identify:
Root
Leaves
Children of 20
Sibling of 20
Answer
Root:
40
Leaves:
10, 30, 50
Children of 20:
10, 30
Sibling of 20:
60
Part 23 — Validate BST
Is this a valid BST?
40
/ \
20 60
/
30
Answer
No।
Although:
30 < 60
it is inside the right subtree of 40।
Every value in that subtree must also satisfy:
value > 40
The BST rule applies to entire subtrees, not just direct parent-child pairs।
Part 24 — BST Search
Implement iterative search।
Solution
static boolean contains(
Node root,
int target
) {
Node current =
root;
while (
current != null
) {
if (
target == current.value()
) {
return true;
}
if (
target < current.value()
) {
current =
current.left();
} else {
current =
current.right();
}
}
return false;
}
Complexity:
O(h)
where:
h = tree height
Balanced:
O(log n)
Worst skewed:
O(n)
Part 25 — BST Insert
Implement recursive insert with no duplicates।
Solution
static Node insert(
Node node,
int value
) {
if (
node == null
) {
return new Node(
value
);
}
if (
value < node.value()
) {
node.setLeft(
insert(
node.left(),
value
)
);
} else if (
value > node.value()
) {
node.setRight(
insert(
node.right(),
value
)
);
}
return node;
}
Part 26 — Tree Traversal
Tree:
40
/ \
20 60
/ \ / \
10 30 50 70
In-Order
Left
Node
Right
Result:
10
20
30
40
50
60
70
Pre-Order
Node
Left
Right
Result:
40
20
10
30
60
50
70
Post-Order
Left
Right
Node
Result:
10
30
20
50
70
60
40
Why In-Order Matters for BST
In-order traversal of a valid BST produces:
sorted order
because:
Left subtree
<
Node
<
Right subtree
Part 27 — Balanced vs Unbalanced BST
Insert:
10
20
30
40
50
into a simple BST in that order।
Result:
10
\
20
\
30
\
40
\
50
This is:
highly unbalanced
Search can degrade to:
O(n)
Why Production Trees Balance Themselves
Structures such as:
TreeMap
TreeSet
use more sophisticated self-balancing tree strategies।
Purpose:
Keep height near O(log n)
so ordered operations remain predictably efficient।
Part 28 — Data Structure Comparison
Match each structure to its main strength।
ArrayList
Fast index access
Ordered sequence
HashSet
Fast expected exact membership
Uniqueness
HashMap
Fast expected key-value lookup
ArrayDeque
Efficient Queue / Stack / Deque behavior
PriorityQueue
Efficient access to highest-priority element
Balanced Tree
Ordered lookup and navigation
Part 29 — Algorithm Choice Case Study
Suppose LiveKlass has:
2 million course enrollment records
and a process must repeatedly answer:
Has learner X already enrolled in course Y?
A naive structure is:
List<Enrollment>
with repeated scans।
Each lookup:
O(n)
This can become expensive।
Better Lookup Key
We could model a lookup key:
record EnrollmentKey(
long learnerId,
String courseCode
) {
}
and build:
Set<EnrollmentKey> enrollmentIndex =
new HashSet<>();
Then membership:
enrollmentIndex.contains(
new EnrollmentKey(
learnerId,
courseCode
)
);
is expected average:
O(1)
Engineering Tradeoff
We gain:
Fast lookup
but pay:
Additional memory
Index maintenance
Consistency responsibility
This is exactly the type of tradeoff algorithmic thinking should reveal।
Part 30 — Performance Review Exercise
Consider:
static List<Course> findCourses(
List<Course> courses,
List<String> requestedCodes
) {
List<Course> result =
new ArrayList<>();
for (
String code
: requestedCodes
) {
for (
Course course
: courses
) {
if (
course.code()
.equals(
code
)
) {
result.add(
course
);
break;
}
}
}
return result;
}
Let:
n = number of courses
m = requested codes
Worst-case complexity:
O(n × m)
Improve It with HashMap
Build an index:
Map<String, Course> byCode =
new HashMap<>();
for (
Course course
: courses
) {
byCode.put(
course.code(),
course
);
}
Then:
for (
String code
: requestedCodes
) {
Course course =
byCode.get(
code
);
if (
course != null
) {
result.add(
course
);
}
}
Expected complexity:
Build index:
O(n)
Requested lookups:
O(m)
Total expected:
O(n + m)
Extra space:
O(n)
This Is the Core of Algorithmic Engineering
The important improvement was not:
write a cleverer loop
It was:
change the data structure
This is one of the most important lessons in the module।
Part 31 — Code Review Questions
For each piece of algorithmic code you write, ask:
What is the input size?
How does work grow with input?
Are there nested scans?
Are expensive method calls hidden inside loops?
What data structure is being used?
Would Set or Map avoid repeated searching?
Does ordering matter?
Does priority matter?
Is recursion depth safe?
How much additional memory is used?
Is there already a Java standard-library API for this?
Part 32 — Short Answer Assessment
Answer without looking back if possible।
Question 1
What is the difference between O(n) and O(log n)?
Answer
O(n) work grows proportionally with input size, while O(log n) grows much more slowly because the remaining problem is repeatedly reduced by a factor।
Question 2
What requirement does Binary Search have?
Answer
The input must be sorted according to the same ordering used by the search।
Question 3
What is the worst-case complexity of Bubble Sort?
Answer
O(n²)
Question 4
What is Merge Sort's worst-case complexity?
Answer
O(n log n)
Question 5
What is textbook Quick Sort's worst-case complexity?
Answer
O(n²)
Question 6
What data structure naturally supports BFS?
Answer
Queue
Question 7
What data structure naturally supports iterative DFS?
Answer
Stack
usually implemented with:
Deque
Question 8
What is PriorityQueue.peek() complexity?
Answer
Typically:
O(1)
Question 9
What is heap insertion complexity?
Answer
O(log n)
Question 10
What is typical HashMap.get() complexity?
Answer
Average expected:
O(1)
Question 11
If two objects are equal, what must be true?
Answer
Their hash codes must be equal।
Question 12
What traversal produces sorted values from a BST?
Answer
In-order traversal
Part 33 — True or False
- Big-O measures exact milliseconds.
- Linear Search works on unsorted data.
- Binary Search works correctly on arbitrary unsorted data.
- Binary Search is
O(log n). - Bubble Sort worst case is
O(n²). - Merge Sort worst case is
O(n log n). - Textbook Quick Sort can degrade to
O(n²). - Java application code should normally use standard sorting APIs.
Comparatorallows multiple orderings for the same type.- Queue follows FIFO.
- Stack follows LIFO.
- PriorityQueue guarantees FIFO for equal priority.
- A Heap is globally sorted.
- Heap insertion is
O(log n). - HashMap guarantees worst-case
O(1). - HashSet is useful for duplicate detection.
- Equal objects must have equal hash codes.
- Equal hash codes mean objects must be equal.
- A plain BST is always balanced.
- In-order BST traversal produces sorted values.
Answers
1. False
2. True
3. False
4. True
5. True
6. True
7. True
8. True
9. True
10. True
11. True
12. False
13. False
14. True
15. False
16. True
17. True
18. False
19. False
20. True
Part 34 — Final Practical Challenge
Build a small:
Course Ranking and Lookup Analyzer
The program should:
- Store courses.
- Build fast lookup by course code.
- Detect duplicate course codes.
- Sort courses by popularity descending.
- Use a
PriorityQueueto retrieve the top three courses. - Search a sorted popularity array using Binary Search.
- Print basic complexity reasoning.
Domain Model
record Course(
String code,
String title,
int popularity
) {
}
Complete Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
public class Main {
public static void main(String[] args) {
List<Course> courses =
List.of(
new Course(
"JAVA",
"Java Foundation",
92
),
new Course(
"BACKEND",
"Backend Development",
97
),
new Course(
"ALGORITHMS",
"Algorithms",
88
),
new Course(
"SYSTEM-DESIGN",
"System Design",
95
),
new Course(
"AGENTS",
"Agent Engineering",
90
)
);
validateUniqueCodes(
courses
);
Map<String, Course> byCode =
indexByCode(
courses
);
Course javaCourse =
byCode.get(
"JAVA"
);
System.out.println(
"Lookup: "
+ javaCourse
);
List<Course> ranked =
new ArrayList<>(
courses
);
ranked.sort(
Comparator.comparingInt(
Course::popularity
).reversed()
);
System.out.println(
"\nRanking:"
);
for (
Course course
: ranked
) {
System.out.println(
course.title()
+ " - "
+ course.popularity()
);
}
System.out.println(
"\nTop 3:"
);
List<Course> topThree =
topCourses(
courses,
3
);
for (
Course course
: topThree
) {
System.out.println(
course.title()
+ " - "
+ course.popularity()
);
}
int[] popularity =
courses.stream()
.mapToInt(
Course::popularity
)
.toArray();
Arrays.sort(
popularity
);
int target =
95;
int index =
Arrays.binarySearch(
popularity,
target
);
System.out.println(
"\nPopularity "
+ target
+ " found: "
+ (
index >= 0
)
);
}
static void validateUniqueCodes(
List<Course> courses
) {
Set<String> codes =
new HashSet<>();
for (
Course course
: courses
) {
if (
!codes.add(
course.code()
)
) {
throw new IllegalArgumentException(
"Duplicate course code: "
+ course.code()
);
}
}
}
static Map<String, Course> indexByCode(
List<Course> courses
) {
Map<String, Course> result =
new HashMap<>();
for (
Course course
: courses
) {
result.put(
course.code(),
course
);
}
return result;
}
static List<Course> topCourses(
List<Course> courses,
int limit
) {
if (
limit <= 0
) {
throw new IllegalArgumentException(
"Limit must be positive."
);
}
PriorityQueue<Course> heap =
new PriorityQueue<>(
Comparator.comparingInt(
Course::popularity
)
);
for (
Course course
: courses
) {
heap.offer(
course
);
if (
heap.size()
> limit
) {
heap.poll();
}
}
List<Course> result =
new ArrayList<>();
while (
!heap.isEmpty()
) {
result.add(
heap.poll()
);
}
result.sort(
Comparator.comparingInt(
Course::popularity
).reversed()
);
return result;
}
record Course(
String code,
String title,
int popularity
) {
}
}
Note About the Stream in the Final Challenge
This line:
courses.stream()
uses the Stream API, which we have not formally studied yet।
It is included only as a small preview of Modern Java।
The same popularity array can be built using a normal loop:
int[] popularity =
new int[
courses.size()
];
for (
int i = 0;
i < courses.size();
i++
) {
popularity[i] =
courses.get(
i
).popularity();
}
If Streams have not yet been introduced in your learning path, use the loop version।
Challenge Complexity Review
Duplicate validation
Each code inserted into HashSet once:
Expected O(n)
Space:
O(n)
Build code index
Each course inserted into HashMap once:
Expected O(n)
Space:
O(n)
Lookup by code
byCode.get(
"JAVA"
);
Expected:
O(1)
Full ranking
General sorting:
O(n log n)
Top K
With bounded heap:
O(n log k)
Space:
O(k)
Binary Search
After sorting:
O(log n)
The preceding sort itself costs roughly:
O(n log n)
Final Assessment Checklist
Before completing Module 6, you should be able to explain:
Why Big-O matters
Difference between O(1), O(log n), O(n), O(n log n), O(n²)
When Linear Search is appropriate
Why Binary Search requires sorted data
How Bubble, Selection, and Insertion Sort differ
Why Merge Sort is O(n log n)
Why Quick Sort can degrade to O(n²)
Why standard Java sorting APIs should usually be preferred
Difference between Comparable and Comparator
Why Queue creates BFS-style processing
Why Stack creates DFS-style processing
How a Heap supports PriorityQueue
Why PriorityQueue is not fully sorted
How Top-K can use a bounded heap
How hashing provides fast expected lookup
How equals() and hashCode() work together
Why mutable hash keys are dangerous
How a BST search follows ordering
Why tree height determines BST performance
Why a balanced tree is different from a naive BST
Module Completion Summary
এই module-এর সবচেয়ে গুরুত্বপূর্ণ takeaway কোনো একটি algorithm নয়।
এটি হলো:
Data structure
+
Algorithm
+
Access pattern
+
Scale
এই চারটি একসঙ্গে reason করা।
A problem may initially look like:
"How do I write this loop?"
but the better question may be:
"Am I using the right data structure?"
For example:
Repeated List scanning
→ maybe HashMap
Arrival-order work
→ Queue
Most recent first
→ Stack
Priority first
→ PriorityQueue
Ordered exact search
→ Binary Search
Dynamic ordered data
→ balanced tree structure
Algorithmic thinking means শুধু clever code লেখা নয়।
It means choosing structures that make the required operation naturally efficient।
Module 6 Complete
You have completed:
1. Understanding Algorithmic Complexity and Big-O
2. Linear Search and Binary Search
3. Simple Sorting Algorithms
4. Merge Sort and Quick Sort
5. Java's Built-In Sorting and Searching APIs
6. Using Stacks, Queues, and Deques in Algorithms
7. Heaps and PriorityQueue
8. Hashing and Fast Lookup
9. Trees and Binary Search Tree Fundamentals
10. Module Practice and Assessment
Next Module
পরবর্তী module:
Module 7 — Modern Java
প্রথম lesson:
Lambda Expressions
আমরা শিখব:
- Why lambdas exist
- Behavior as a value
- Lambda syntax
- Single-parameter lambdas
- Multiple parameters
- Expression lambdas
- Block lambdas
- Type inference
- Variable capture
- Effectively final variables
- Lambdas with collections
- Lambdas with Comparator
- When lambdas improve code
- When a normal method is clearer