← Back to DSA Course | Chapter 18: Interview Preparation | Lesson 1 of 4

Top Array और String समस्याएँ

Top array और string problems classic warm-up puzzles जैसी हैं जो interviewers को पसंद हैं, जैसे दो numbers ढूंढना जो एक target तक add होते हैं।

Two Sum

Two Sum आपसे किसी array में दो numbers ढूंढने को कहता है जो एक दिए target तक add होते हैं — naive approach हर pair O(n²) में जांचती है, लेकिन scan करते समय seen values को एक hash map में store करना इसे एक single O(n) pass तक लाता है।

उदाहरण: Two Sum

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int arr[] = {2,7,11,15}, target = 9;
	unordered_map<int,int> seen;
	for (int i = 0; i < 4; i++) {
		if (seen.count(target - arr[i])) { cout << "Indices: " << seen[target-arr[i]] << "," << i; break; }
		seen[arr[i]] = i;
	}
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {2,7,11,15};
		int target = 9;
		Map<Integer,Integer> seen = new HashMap<>();
		for (int i = 0; i < 4; i++) {
			if (seen.containsKey(target - arr[i])) { System.out.println("Indices: " + seen.get(target-arr[i]) + "," + i); break; }
			seen.put(arr[i], i);
		}
	}
}
arr = [2,7,11,15]
target = 9
seen = {}
for i, x in enumerate(arr):
    if target - x in seen:
        print(f"Indices: {seen[target-x]},{i}")
        break
    seen[x] = i
#include <stdio.h>
int main() {
	int arr[] = {2,7,11,15}, target = 9;
	for (int i = 0; i < 4; i++)
		for (int j = i+1; j < 4; j++)
			if (arr[i]+arr[j] == target) { printf("Indices: %d,%d", i, j); return 0; }
	return 0;
}

Maximum and Minimum

किसी array में maximum या minimum value ढूंढने के लिए सिर्फ एक linear scan चाहिए, अब तक देखी गई best value track करते हुए और जब भी एक ज़्यादा extreme value दिखे इसे update करते हुए — किसी sorting या extra data structure की ज़रूरत नहीं।

उदाहरण: Maximum and Minimum

#include <iostream>
using namespace std;
int main() {
	int arr[] = {3,7,1,9,4};
	int mx = arr[0], mn = arr[0];
	for (int i = 1; i < 5; i++) { if (arr[i] > mx) mx = arr[i]; if (arr[i] < mn) mn = arr[i]; }
	cout << "Max: " << mx << " Min: " << mn;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {3,7,1,9,4};
		int mx = arr[0], mn = arr[0];
		for (int i = 1; i < 5; i++) { if (arr[i] > mx) mx = arr[i]; if (arr[i] < mn) mn = arr[i]; }
		System.out.println("Max: " + mx + " Min: " + mn);
	}
}
arr = [3,7,1,9,4]
mx = mn = arr[0]
for x in arr[1:]:
    if x > mx: mx = x
    if x < mn: mn = x
print("Max:", mx, "Min:", mn)
#include <stdio.h>
int main() {
	int arr[] = {3,7,1,9,4};
	int mx = arr[0], mn = arr[0];
	for (int i = 1; i < 5; i++) { if (arr[i] > mx) mx = arr[i]; if (arr[i] < mn) mn = arr[i]; }
	printf("Max: %d Min: %d", mx, mn);
	return 0;
}

Array Search

Linear search हर element को order में जांचता है जब तक यह एक match न ढूंढे या आखिर तक न पहुंचे, जो simple है और हमेशा correct है लेकिन O(n) time लेता है — binary search के O(log n) से एक strong contrast, जिसे पहले data sorted चाहिए।

उदाहरण: Array Search

#include <iostream>
using namespace std;
int main() {
	int arr[] = {5,3,8,1,9}, target = 8;
	for (int i = 0; i < 5; i++) if (arr[i] == target) { cout << "Found at index " << i << " in O(n)"; break; }
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {5,3,8,1,9};
		int target = 8;
		for (int i = 0; i < 5; i++) if (arr[i] == target) { System.out.println("Found at index " + i + " in O(n)"); break; }
	}
}
arr = [5,3,8,1,9]
target = 8
for i, x in enumerate(arr):
    if x == target:
        print(f"Found at index {i} in O(n)")
        break
#include <stdio.h>
int main() {
	int arr[] = {5,3,8,1,9}, target = 8;
	for (int i = 0; i < 5; i++) if (arr[i] == target) { printf("Found at index %d in O(n)", i); break; }
	return 0;
}

String Thinking

कई string problems यह count करने तक reduce होती हैं कि हर character कितनी बार दिखता है (एक fixed-size array या hash map उपयोग करके), फिर उन counts को scan या compare करते हुए — यह single technique anagram checks, character-frequency puzzles, और ज़्यादा के पीछे है।

उदाहरण: String Thinking

#include <iostream>
using namespace std;
int main() {
	string s1 = "listen", s2 = "silent";
	int freq[26] = {0};
	for (char c : s1) freq[c-'a']++;
	for (char c : s2) freq[c-'a']--;
	bool isAnagram = true;
	for (int i = 0; i < 26; i++) if (freq[i] != 0) isAnagram = false;
	cout << "'" << s1 << "' and '" << s2 << "' are anagrams: " << isAnagram;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		String s1 = "listen", s2 = "silent";
		int[] freq = new int[26];
		for (char c : s1.toCharArray()) freq[c-'a']++;
		for (char c : s2.toCharArray()) freq[c-'a']--;
		boolean isAnagram = true;
		for (int f : freq) if (f != 0) isAnagram = false;
		System.out.println("'" + s1 + "' and '" + s2 + "' are anagrams: " + isAnagram);
	}
}
from collections import Counter
s1, s2 = "listen", "silent"
print(f"'{s1}' and '{s2}' are anagrams: {Counter(s1) == Counter(s2)}")
#include <stdio.h>
int main() {
	char s1[] = "listen", s2[] = "silent";
	int freq[26] = {0};
	for (int i = 0; s1[i]; i++) freq[s1[i]-'a']++;
	for (int i = 0; s2[i]; i++) freq[s2[i]-'a']--;
	int isAnagram = 1;
	for (int i = 0; i < 26; i++) if (freq[i] != 0) isAnagram = 0;
	printf("'%s' and '%s' are anagrams: %s", s1, s2, isAnagram ? "true" : "false");
	return 0;
}

Interview Practice

एक आम interview strategy पहले एक brute-force solution को काम में लाना है ताकि आपके पास test करने के लिए कुछ correct हो, फिर repeated work या अनावश्यक comparisons ढूंढना जिन्हें एक बेहतर data structure या single pass eliminate कर सके।

उदाहरण: Interview Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Get brute force working first, then look for repeated work a better approach can eliminate";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Get brute force working first, then look for repeated work a better approach can eliminate");
	}
}
print("Get brute force working first, then look for repeated work a better approach can eliminate")
#include <stdio.h>
int main() {
	printf("Get brute force working first, then look for repeated work a better approach can eliminate");
	return 0;
}
Related Topics
{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. i == j के साथ एक pair जांचना, Two Sum में उसी element को दो बार उपयोग करते हुए।
  2. Max और min को arr[0] के बजाय 0 पर शुरू करना, इसलिए negative numbers गलत results देते हैं।
  3. arr[0] पढ़ने से पहले एक empty array handle करना भूल जाना।
🔒

Chapter Quiz — Complete all 4 topics to unlock

0/4 topics done

Complete these topics first:

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.