الفصل 3: الخوارزميات وهياكل البيانات
تغطي هذه التمارين الأسئلة الكلاسيكية للخوارزميات المطروحة في مقابلات جافا. تتضمن كل حل تعقيد الوقت/المكان وعبارة رئيسية لقولها في المقابلة.
التمرين 1 — عداد تكرار الكلمات (HashMap)
"احسب تكرار كل كلمة في سلسلة نصية."
الحل الإمبراطوري
public Map<String, Integer> wordCount(String text) {
Map<String, Integer> freq = new HashMap<>();
for (String word : text.toLowerCase().split("\\s+")) {
freq.merge(word, 1, Integer::sum);
}
return freq;
}
الحل باستخدام Streams
public Map<String, Long> wordCountStream(String text) {
return Arrays.stream(text.toLowerCase().split("\\s+"))
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
اختبار : "hello world hello java" → {hello=2, world=1, java=1}
"I used merge() for the imperative approach and groupingBy for the stream approach. Both are O(n)."
التمرين 2 — التحقق من الأقواس الصحيحة (Stack)
"تحقق مما إذا كانت سلسلة الأقواس صحيحة: (), [], "
الحل
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) {
stack.push(c);
} else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
}
}
return stack.isEmpty();
}
اختبارات :
"({[]})" → true
"({[}])" → false
"(((" → false
"" → true
التعقيد : O(n) وقت، O(n) مساحة.
"Classic stack problem. O(n) time, O(n) space. I used ArrayDeque instead of the legacy Stack class because it's faster and recommended by the Java documentation."
التمرين 3 — عكس قائمة مرتبطة
"اعكس قائمة مرتبطة بسيطة (singly linked list)."
الحل
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // sauvegarder le suivant
curr.next = prev; // inverser le pointeur
prev = curr; // avancer prev
curr = next; // avancer curr
}
return prev;
}
التصور :
Avant : 1 → 2 → 3 → null
Après : 3 → 2 → 1 → null
التعقيد : O(n) وقت، O(1) مساحة.
"Three pointers: prev, curr, next. O(n) time, O(1) space. This is a classic that tests pointer manipulation."
التمرين 4 — البحث الثنائي (Binary Search)
"قم بتنفيذ بحث ثنائي على مصفوفة مرتبة."
الحل
public int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // évite le dépassement d'entier
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // non trouvé
}
اختبار : [1, 3, 5, 7, 9, 11], target = 7 → يعود 3 (الفهرس)
التعقيد : O(log n) وقت، O(1) مساحة.
لماذا lo + (hi - lo) / 2 بدلاً من (lo + hi) / 2 ؟
لأن lo + hi يمكن أن يتجاوز Integer.MAX_VALUE إذا كانت القيمتان كبيرتين. إنه تفصيل يحبه المقابلون.
"I use lo + (hi - lo) / 2 instead of (lo + hi) / 2 to avoid integer overflow. Classic O(log n) search on sorted data."
التمرين 5 — Two Sum (رقمان يحققان مجموعاً)
"اعثر على رقمين في مصفوفة يكون مجموعهما مساوياً لهدف."
الحل O(n) باستخدام HashMap
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[] { seen.get(complement), i };
}
seen.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
اختبار : [2, 7, 11, 15], target = 9 → يعود [0, 1] (لأن 2 + 7 = 9)
التعقيد : O(n) وقت، O(n) مساحة.
الفكرة
لكل رقم x، نبحث إذا كان target - x قد تم رؤيته بالفعل. تتيح لنا HashMap القيام بهذا البحث في O(1).
"Single-pass HashMap solution. For each number, I check if the complement exists in the map. O(n) time instead of the brute-force O(n²)."
التمرين 6 — FizzBuzz (الكلاسيكي)
"اطبع الأرقام من 1 إلى n. للمضاعفات 3: 'Fizz'. للمضاعفات 5: 'Buzz'. لكليهما: 'FizzBuzz'."
الحل النظيف
public List<String> fizzBuzz(int n) {
List<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) result.add("FizzBuzz");
else if (i % 3 == 0) result.add("Fizz");
else if (i % 5 == 0) result.add("Buzz");
else result.add(String.valueOf(i));
}
return result;
}
الحل القابل للتوسيع (إذا أضاف المقابل قواعد)
public List<String> fizzBuzz(int n) {
record Rule(int divisor, String word) {}
List<Rule> rules = List.of(
new Rule(3, "Fizz"),
new Rule(5, "Buzz"),
new Rule(7, "Jazz") // facile à ajouter !
);
List<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
final int num = i;
String s = rules.stream()
.filter(r -> num % r.divisor() == 0)
.map(Rule::word)
.collect(Collectors.joining());
result.add(s.isEmpty() ? String.valueOf(i) : s);
}
return result;
}
"I start with the simple version, but if the interviewer asks for extensibility, I switch to a rule-based approach. Adding a new rule is just one line."
التمرين 7 — العثور على أول تكرار
"اعثر على أول عنصر مكرر في مصفوفة."
الحل
public int firstDuplicate(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
if (!seen.add(num)) return num;
}
return -1; // pas de doublon
}
نصيحة : Set.add() يعود false إذا كان العنصر موجودًا بالفعل — لا حاجة إلى contains() منفصل.
اختبار : [2, 1, 3, 5, 3, 2] → يعود 3 (أول تكرار تم مواجهته)
التعقيد : O(n) وقت، O(n) مساحة.
التمرين 8 — التحقق مما إذا كانت سلسلتان هما أناغرام
"تحقق مما إذا كانت سلسلتان هما أناغرام."
الحل
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
اختبار : "listen", "silent" → true
التعقيد : O(n) وقت، O(1) مساحة (جدول ثابت من 26).
"I use a frequency counter array instead of sorting (O(n log n)). Single pass, O(n) time, O(1) space since the alphabet is fixed."
ملخص التعقيدات
| التمرين | الوقت | المساحة | الهيكل الرئيسي |
|---|---|---|---|
| تكرار الكلمات | O(n) | O(n) | HashMap |
| الأقواس الصحيحة | O(n) | O(n) | Stack (ArrayDeque) |
| عكس linked list | O(n) | O(1) | 3 مؤشرات |
| البحث الثنائي | O(log n) | O(1) | القسمة على 2 |
| Two Sum | O(n) | O(n) | HashMap (المكمل) |
| FizzBuzz | O(n) | O(n) | Modulo |
| أول تكرار | O(n) | O(n) | HashSet |
| أناغرام | O(n) | O(1) | جدول الترددات |