Qualcomm Practice — Part 1 Solutions — Arrays, Searching/Sorting, Strings, Bit manipulation¶

Worked solutions for Part 1, categories D–G of the practice list: Arrays, Searching & sorting, Strings (algorithmic), and Bit manipulation. Each entry gives the key idea, clean compilable code, complexity, and the edge case / variant interviewers like to add. Back to the list: practice_questions.md.

All code below was compiled (gcc/g++ -std=c++17) and run against test cases. C is used for array/pointer/bit work; C++ (with std::string/std::vector) for the string algorithms.

Table of contents¶

D. Arrays - D1. Rotate an array by k to the right - D2. Merge two sorted arrays in-place - D3. Find the missing number in 1..n - D4. First and last position in a sorted array - D5. Search in a sorted array of "infinite" size - D6. Count pairs whose sum is divisible by k - D7. N meetings in one room - D8. Minimum number of platforms - D9. Sliding-window maximum - D10. Trapping rain water

E. Searching & sorting - E1. Binary search - E2. Merge sort - E3. Quick sort & pivot impact - E4. Sort a linked list (merge vs quick)

F. Strings (algorithmic) - F1. Reverse the words in a sentence - F2. Longest substring without repeating characters - F3. Longest palindromic substring - F4. Count of palindromic substrings

G. Bit manipulation - G1. Count the number of set bits - G2. Check power of two, O(1) - G3. Flip the kth bit from the right - G4. Reverse the bits of a number - G5. Single Number

D. Arrays¶

D1. Rotate an array by k to the right `[E]`¶

Idea: Three reversals. Reverse the whole array, then reverse the first k and the last n-k. The pieces land in rotated order without extra memory.

Code:

// rotate right by k: [1 2 3 4 5 6 7], k=3 -> [5 6 7 1 2 3 4]
static void reverse(int *a, int l, int r) {
    while (l < r) { int t = a[l]; a[l] = a[r]; a[r] = t; l++; r--; }
}
void rotate(int *a, int n, int k) {
    if (n == 0) return;
    k %= n;                 // k may exceed n
    reverse(a, 0, n - 1);   // whole array
    reverse(a, 0, k - 1);   // first k
    reverse(a, k, n - 1);   // rest
}

Complexity: O(n) time, O(1) space.
Gotcha / variants: Always k %= n first (k can be > n, or 0). Rotate left by k == rotate right by n-k. The naive "shift one at a time k times" is O(n·k) — interviewers want the reversal trick.

D2. Merge two sorted arrays in-place `[M]`¶

Idea: Fill nums1 from the back. The tail of nums1 is free space, so writing the largest elements first never clobbers an unread value.

Code:

// nums1 has m valid + n empty slots at the end; nums2 has n elements.
void merge(int *n1, int m, int *n2, int n) {
    int i = m - 1, j = n - 1, w = m + n - 1; // read m, read n, write tail
    while (j >= 0) {                          // n2 must be fully drained
        if (i >= 0 && n1[i] > n2[j]) n1[w--] = n1[i--];
        else                         n1[w--] = n2[j--];
    }
}

Complexity: O(m+n) time, O(1) space.
Gotcha / variants: Loop on j>=0 (not i): once n2 is empty the remaining n1 items are already in place. Forward-merging in place would overwrite unread n1 values — that's why we go back-to-front.

D3. Find the missing number in 1..n `[E]`¶

Idea: XOR every array element with every value 1..n. Pairs cancel; the lone survivor is the missing number. No overflow, unlike the sum formula.

Code:

// a holds n numbers, a permutation of 1..n+1 with one missing.
int missing(int *a, int n) {        // n = array length
    int x = 0;
    for (int i = 0; i < n; i++) x ^= a[i];
    for (int i = 1; i <= n + 1; i++) x ^= i;
    return x;
}

Complexity: O(n) time, O(1) space.
Gotcha / variants: Sum formula n(n+1)/2 - sum also works but can overflow for large n; XOR is overflow-safe. If the range is 0..n (LC268), XOR i over 0..n instead.

D4. First and last position in a sorted array `[M]`¶

Idea: Two binary searches: lower_bound finds the first index >= target; upper_bound finds the first > target. First occurrence = lower_bound; last = upper_bound − 1.

Code:

// first index where a[i] >= t  (insertion point)
static int lower_bound(const int *a, int n, int t) {
    int lo = 0, hi = n;                  // half-open [lo, hi)
    while (lo < hi) { int m = lo + (hi - lo) / 2; if (a[m] < t) lo = m + 1; else hi = m; }
    return lo;
}
static int upper_bound(const int *a, int n, int t) {
    int lo = 0, hi = n;
    while (lo < hi) { int m = lo + (hi - lo) / 2; if (a[m] <= t) lo = m + 1; else hi = m; }
    return lo;
}
// returns {first, last}; {-1,-1} if absent
void firstLast(const int *a, int n, int t, int *first, int *last) {
    int lo = lower_bound(a, n, t);
    if (lo == n || a[lo] != t) { *first = *last = -1; return; }
    *first = lo;
    *last  = upper_bound(a, n, t) - 1;
}

Complexity: O(log n) time, O(1) space.
Gotcha / variants: Validate lo == n || a[lo] != t before trusting the result — lower_bound returns a valid index even when the target is absent. < vs <= is the only difference between the two searches.

D5. Search in a sorted array of "infinite" size `[M]`¶

Idea: You can't pass n. Exponentially grow the high bound (1, 2, 4, 8, …) until a[hi] >= target, then binary-search the bracket [lo, hi]. Doubling reaches a position p in O(log p) probes.

Code:

// Conceptually a[] is unbounded; reads past the end return a sentinel (INT_MAX
// here for the test). n is only for the simulation.
int searchInfinite(const int *a, int n, int t) {
    int lo = 0, hi = 1;
    while (hi < n && a[hi] < t) { lo = hi; hi *= 2; }  // expand the window
    if (hi >= n) hi = n - 1;
    while (lo <= hi) {                                  // standard binary search
        int m = lo + (hi - lo) / 2;
        if (a[m] == t) return m;
        if (a[m] < t)  lo = m + 1; else hi = m - 1;
    }
    return -1;
}

Complexity: O(log p) time where p is the target's index, O(1) space.
Gotcha / variants: Out-of-range reads must return a value > target (sentinel / "infinity") so the doubling loop terminates. This is the "find position in infinite sorted stream" GfG variant.

D6. Count pairs whose sum is divisible by k `[M]`¶

Idea: Bucket elements by remainder mod k. A pair sums to a multiple of k iff their remainders are 0&0 or r & k-r. Count pairs within/between buckets — no O(n²) scan.

Code:

// counts (i<j) with (a[i]+a[j]) % k == 0
long countPairsDivByK(const int *a, int n, int k) {
    long *cnt = calloc(k, sizeof(long));
    for (int i = 0; i < n; i++) cnt[((a[i] % k) + k) % k]++;  // handles negatives
    long res = cnt[0] * (cnt[0] - 1) / 2;                     // both remainder 0
    for (int r = 1; r <= k / 2; r++) {
        if (r == k - r) res += cnt[r] * (cnt[r] - 1) / 2;     // r == k/2 (k even)
        else            res += cnt[r] * cnt[k - r];
    }
    free(cnt);
    return res;
}

Complexity: O(n + k) time, O(k) space.
Gotcha / variants: Two traps: (1) the r == k-r middle bucket (k even) must use the n-choose-2 formula, not a product; (2) ((x%k)+k)%k to keep remainders non-negative. Use a long accumulator — pair counts overflow int fast.

D7. N meetings in one room `[M]`¶

Idea: Classic activity selection — greedy. Sort by finish time, then keep every meeting that starts after the last selected one ends. Earliest-finishing choices leave the most room.

Code:

typedef struct { int s, e; } Meeting;
static int cmpFinish(const void *x, const void *y) {
    return ((const Meeting*)x)->e - ((const Meeting*)y)->e;
}
int maxMeetings(Meeting *m, int n) {
    if (n == 0) return 0;
    qsort(m, n, sizeof(Meeting), cmpFinish);
    int count = 1, lastEnd = m[0].e;
    for (int i = 1; i < n; i++)
        if (m[i].s > lastEnd) { count++; lastEnd = m[i].e; }
    return count;
}

Complexity: O(n log n) time (the sort), O(1) extra space.
Gotcha / variants: Sort by finish, not start — sorting by start is wrong. Decide whether start == lastEnd counts as a conflict (here > means back-to-back is disallowed; use >= to allow it).

D8. Minimum number of platforms `[M]`¶

Idea: Sort arrivals and departures separately. Sweep both like a merge: a train arriving before the next departure needs a new platform (++), a departure frees one (--). Track the peak.

Code:

static int cmpInt(const void *x, const void *y){ return *(const int*)x - *(const int*)y; }
int minPlatforms(int *arr, int *dep, int n) {
    qsort(arr, n, sizeof(int), cmpInt);
    qsort(dep, n, sizeof(int), cmpInt);
    int i = 1, j = 0, plat = 1, peak = 1;       // first arrival already on a platform
    while (i < n && j < n) {
        if (arr[i] <= dep[j]) { plat++; i++; }  // overlap -> need another platform
        else                  { plat--; j++; }  // a train left -> free one
        if (plat > peak) peak = plat;
    }
    return peak;
}

Complexity: O(n log n) time, O(1) extra space.
Gotcha / variants: arr[i] <= dep[j] (not <): a train arriving exactly when another departs still needs its own platform in the usual interpretation. The arrival/departure arrays get decoupled by sorting — that's intentional, you don't pair them per-train.

D9. Sliding-window maximum `[H]`¶

Idea: Monotonic deque of indices, kept decreasing by value. The front is always the current window's max. Pop stale indices off the front, pop smaller values off the back before pushing.

Code:

// out[] gets the max of every window of size k; out has n-k+1 entries.
void slidingWindowMax(const int *a, int n, int k, int *out) {
    int *dq = malloc(n * sizeof(int));   // deque of indices, front=head
    int head = 0, tail = 0, oi = 0;
    for (int i = 0; i < n; i++) {
        if (tail > head && dq[head] <= i - k) head++;          // drop out-of-window
        while (tail > head && a[dq[tail-1]] <= a[i]) tail--;    // drop smaller tails
        dq[tail++] = i;
        if (i >= k - 1) out[oi++] = a[dq[head]];                // window complete
    }
    free(dq);
}

Complexity: O(n) time (each index pushed/popped once), O(k) space.
Gotcha / variants: Store indices, not values, so you can detect when the max scrolls out of the window. A naive max-per-window is O(n·k); a max-heap is O(n log k). The deque is the optimal O(n).

D10. Trapping rain water `[H]`¶

Idea: Two pointers. Water above a bar is bounded by the smaller of the tallest walls on its left and right. Move the pointer on the shorter side; the running max on that side is a valid bound.

Code:

int trap(const int *h, int n) {
    int l = 0, r = n - 1, leftMax = 0, rightMax = 0, water = 0;
    while (l < r) {
        if (h[l] < h[r]) {                       // left wall is the limiter
            if (h[l] >= leftMax) leftMax = h[l];
            else water += leftMax - h[l];
            l++;
        } else {                                 // right wall is the limiter
            if (h[r] >= rightMax) rightMax = h[r];
            else water += rightMax - h[r];
            r--;
        }
    }
    return water;
}

Complexity: O(n) time, O(1) space.
Gotcha / variants: The insight: when h[l] < h[r], the left side is guaranteed bounded by leftMax regardless of bars in between, so it's safe to compute the left side now. The O(n)-space version precomputes leftMax[]/rightMax[] arrays — same idea, easier to explain if pointers feel slippery.

E. Searching & sorting¶

E1. Binary search `[E]`¶

Idea: On a sorted array, compare the middle; discard the half that can't contain the target. Each step halves the range → O(log n).

Code:

// returns index of t, or -1. Array must be sorted ascending.
int binarySearch(const int *a, int n, int t) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int m = lo + (hi - lo) / 2;   // NOT (lo+hi)/2 -> avoids int overflow
        if (a[m] == t) return m;
        if (a[m] < t)  lo = m + 1;
        else           hi = m - 1;
    }
    return -1;
}

Pseudocode: lo=0, hi=n-1; while lo<=hi: m=(lo+hi)/2; if a[m]==t return m; if a[m]<t lo=m+1 else hi=m-1; return -1.

Complexity: Time best O(1) (hit at first mid), avg/worst O(log n); space O(1) iterative, O(log n) recursive (call stack).
Gotcha / variants: mid = lo + (hi-lo)/2 to dodge overflow on large indices. Requires sorted + random access (so not on a plain linked list). Variants: first/last position (D4), rotated array, infinite array (D5).

E2. Merge sort `[M]`¶

Idea: Divide & conquer — split in half, sort each recursively, merge the two sorted halves. log n levels × O(n) merge = O(n log n) in all cases; stable.

Code:

static void merge(int *a, int l, int mid, int r, int *tmp) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= keeps it stable
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int x = l; x <= r; x++) a[x] = tmp[x];
}
static void msort(int *a, int l, int r, int *tmp) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    msort(a, l, m, tmp);
    msort(a, m + 1, r, tmp);
    merge(a, l, m, r, tmp);
}
void mergeSort(int *a, int n) {
    int *tmp = malloc(n * sizeof(int));   // one shared buffer, allocated once
    msort(a, 0, n - 1, tmp);
    free(tmp);
}

Complexity: O(n log n) time (best = avg = worst), O(n) extra space; O(log n) recursion depth.
Gotcha / variants: <= in the merge makes it stable. The O(n) buffer is the price; allocate it once and reuse, not per recursion. Preferred over quicksort when you need a worst-case guarantee, stability, or you're sorting a linked list (E4).

E3. Quick sort & pivot impact `[M]`¶

Idea: Pick a pivot, partition so smaller elements go left and larger go right, recurse on each side. In-place, fast in practice — but the pivot choice decides whether you get O(n log n) or O(n²).

Code:

// Lomuto partition with last element as pivot.
static int partition(int *a, int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { i++; int t = a[i]; a[i] = a[j]; a[j] = t; }
    int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;   // pivot to its final spot
    return i + 1;
}
static void qs(int *a, int lo, int hi) {
    if (lo < hi) { int p = partition(a, lo, hi); qs(a, lo, p - 1); qs(a, p + 1, hi); }
}
void quickSort(int *a, int n) { qs(a, 0, n - 1); }

Complexity: Time avg O(n log n), worst O(n²); space O(log n) avg recursion (O(n) worst).
Gotcha / variants: Pivot impact (the asked question): a fixed end-pivot on an already-sorted or reverse-sorted array makes every partition split 1-vs-(n−1) → O(n²). Fixes: median-of-three or a random pivot make worst case astronomically unlikely. Recurse into the smaller partition first (tail-call the larger) to bound stack to O(log n). Quicksort is in-place and cache-friendly but not stable.

E4. Sort a linked list (merge vs quick) `[H]`¶

Idea: Use merge sort on lists: find the middle with slow/fast pointers, split, sort each half, merge. No random access needed — the natural fit for linked lists.

Code:

struct Node { int val; Node *next; };

static Node* middle(Node *h) {                  // slow ends at mid (left of two)
    Node *slow = h, *fast = h->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    return slow;
}
static Node* mergeLists(Node *a, Node *b) {
    Node dummy{0, nullptr}, *t = &dummy;
    while (a && b) {
        if (a->val <= b->val) { t->next = a; a = a->next; }
        else                  { t->next = b; b = b->next; }
        t = t->next;
    }
    t->next = a ? a : b;                         // attach the leftover run
    return dummy.next;
}
Node* sortList(Node *h) {
    if (!h || !h->next) return h;                // 0 or 1 node
    Node *mid = middle(h), *right = mid->next;
    mid->next = nullptr;                         // cut into two halves
    return mergeLists(sortList(h), sortList(right));
}

Complexity: O(n log n) time; O(log n) stack space (no O(n) buffer — the merge just relinks nodes).
Gotcha / variants: Merge sort > quick sort for lists: merge needs only sequential access and relinks pointers (no element copies, no extra array), while quicksort on a list loses its cache and in-place advantages because lists have no random access for partitioning. Split fast = h->next so a 2-node list splits evenly and won't infinite-loop.

F. Strings (algorithmic)¶

F1. Reverse the words in a sentence `[M]`¶

Idea: Scan word by word; prepend each word to the result (or: reverse the whole string, then reverse each word in place). Skip runs of spaces so extra whitespace collapses.

Code:

// "the sky is blue" -> "blue is sky the"; collapses extra spaces.
string reverseWords(const string &s) {
    string res;
    int n = s.size(), i = 0;
    while (i < n) {
        while (i < n && s[i] == ' ') i++;            // skip leading spaces
        if (i >= n) break;
        int j = i;
        while (j < n && s[j] != ' ') j++;            // [i, j) is one word
        string w = s.substr(i, j - i);
        res = res.empty() ? w : w + " " + res;       // prepend
        i = j;
    }
    return res;
}

Complexity: O(n) passes; O(n²) here from repeated prepend — for strict O(n) build the result left-to-right into a reversed word list, or do the in-place double-reverse on a char[].
Gotcha / variants: Handle leading/trailing/multiple spaces. In-place char[] version (true O(1) extra space): reverse the entire buffer, then reverse each word back. Reverse only odd-positioned words: keep a word counter and reverse the characters of words at odd indices instead.

F2. Longest substring without repeating characters `[M]`¶

Idea: Sliding window. Track the last index seen for each character; when a repeat falls inside the window, jump the window start past it. Window length is the candidate answer.

Code:

int lengthOfLongestSubstring(const string &s) {
    int last[256];
    for (int i = 0; i < 256; i++) last[i] = -1;   // last position of each char
    int best = 0, start = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        unsigned char c = s[i];
        if (last[c] >= start) start = last[c] + 1; // shrink window past the dup
        last[c] = i;
        if (i - start + 1 > best) best = i - start + 1;
    }
    return best;
}

Complexity: O(n) time, O(1) space (fixed 256-entry table / O(charset)).
Gotcha / variants: The last[c] >= start check matters — only jump if the previous occurrence is inside the current window, otherwise an old duplicate would wrongly shrink it. Empty string → 0.

F3. Longest palindromic substring `[M]`¶

Idea: Expand around centers. Every palindrome has a center; there are 2n−1 of them (each char, and each gap). Expand outward while characters match, track the longest.

Code:

string longestPalindrome(const string &s) {
    if (s.empty()) return "";
    int bestStart = 0, bestLen = 1;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
        int len = r - l - 1;                      // after the loop overshoots by 1
        if (len > bestLen) { bestLen = len; bestStart = l + 1; }
    };
    for (int i = 0; i < (int)s.size(); i++) {
        expand(i, i);       // odd-length center
        expand(i, i + 1);   // even-length center
    }
    return s.substr(bestStart, bestLen);
}

Complexity: O(n²) time, O(1) space.
Gotcha / variants: Run expand twice per index — once for odd centers, once for even — or you'll miss palindromes like "bb". After the while-loop, the real length is r - l - 1 because both pointers overshot by one. Manacher's algorithm does this in O(n) but is rarely expected.

F4. Count of palindromic substrings `[M]`¶

Idea: Same expand-around-center as F3, but count every match instead of tracking the longest. Each successful expansion is one more palindromic substring.

Code:

int countSubstrings(const string &s) {
    int count = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { count++; l--; r++; }
    };
    for (int i = 0; i < (int)s.size(); i++) {
        expand(i, i);       // odd-length palindromes
        expand(i, i + 1);   // even-length palindromes
    }
    return count;
}

Complexity: O(n²) time, O(1) space.
Gotcha / variants: Single characters count ("abc" → 3). Each count++ inside the loop is the trick — every widening that still matches is a distinct palindrome. DP table (dp[i][j] = s[i]==s[j] && dp[i+1][j-1]) is the alternative, O(n²) time and space.

G. Bit manipulation¶

G1. Count the number of set bits `[E]`¶

Idea: Brian Kernighan's trick: n & (n-1) clears the lowest set bit. Loop until n is 0; iterations = number of set bits. Runs once per set bit, not per bit.

Code:

int countSetBits(unsigned n) {
    int count = 0;
    while (n) { n &= (n - 1); count++; }   // clear lowest set bit each step
    return count;
}

Complexity: O(popcount) time ≤ O(bits), O(1) space.
Gotcha / variants: Use unsigned so right-shifts / n-1 behave on the high bit. The naive n & 1 then n >>= 1 is O(#bits) (always 32/64 iters); Kernighan only loops for set bits. Builtins: __builtin_popcount(n).

G2. Check power of two, O(1) `[E]`¶

Idea: A power of two has exactly one set bit, so n & (n-1) is 0 — and we must exclude n == 0, which also satisfies that.

Code:

int isPowerOfTwo(unsigned n) {
    return n != 0 && (n & (n - 1)) == 0;
}

Complexity: O(1) time, O(1) space.
Gotcha / variants: The n != 0 guard is essential — 0 & -1 == 0 would otherwise falsely report 0 as a power of two. Works for unsigned; for signed inputs, negatives must return false (the unsigned parameter handles that). No pow/log2 (those have float rounding bugs).

G3. Flip the kth bit from the right `[E]`¶

Idea: XOR with a mask that has only bit k set. XOR toggles: 0→1, 1→0, leaving other bits untouched. (k is 0-indexed.)

Code:

unsigned flipKthBit(unsigned n, int k) {
    return n ^ (1u << k);          // toggle bit k (0-indexed from the right)
}
// Related one-liners:
unsigned setKthBit  (unsigned n, int k) { return n |  (1u << k); }  // force to 1
unsigned clearKthBit(unsigned n, int k) { return n & ~(1u << k); }  // force to 0
int      testKthBit (unsigned n, int k) { return (n >> k) & 1; }    // read it

Complexity: O(1) time, O(1) space.
Gotcha / variants: Use 1u << k (unsigned literal) — 1 << 31 on a signed int is UB. Mind the indexing convention: bit 0 is the LSB. Set / clear / test are the sibling operations interviewers ask alongside flip.

G4. Reverse the bits of a number `[M]`¶

Idea: Pull bits off the low end of the input and push them onto the low end of the result, which shifts earlier bits up. After 32 steps the order is reversed.

Code:

#include <stdint.h>
uint32_t reverseBits(uint32_t n) {
    uint32_t r = 0;
    for (int i = 0; i < 32; i++) {
        r = (r << 1) | (n & 1);   // append n's lowest bit to r
        n >>= 1;
    }
    return r;
}

Complexity: O(1) (fixed 32 iterations), O(1) space.
Gotcha / variants: Fix the width (32 here) — the answer depends on it; reversing within 8 vs 32 bits gives different results. Follow-up ("then count set bits"): reversal preserves the number of 1s, so countSetBits(reverseBits(n)) == countSetBits(n) — point that out. A divide-and-conquer swap (swap halves, then bytes, then nibbles…) does it in O(log bits) operations.

G5. Single Number `[M]`¶

Idea: XOR all elements. Every value that appears twice cancels itself to 0; the one unique value survives. x ^ x = 0, x ^ 0 = x.

Code:

// every element appears twice except one; return that one.
int singleNumber(const int *a, int n) {
    int x = 0;
    for (int i = 0; i < n; i++) x ^= a[i];
    return x;
}

Complexity: O(n) time, O(1) space.
Gotcha / variants: Order doesn't matter (XOR is commutative/associative). Variants: if every element appears three times except one (LC137), XOR no longer works — use per-bit counts mod 3, or the ones/twos bitmask trick. "Two unique numbers" (LC260): XOR everything to get a^b, isolate a differing bit (x & -x), partition by it, XOR each group.

Covers Part 1 categories D–G. For the source list and the other categories (linked lists, trees, concurrency, etc.) see practice_questions.md. All snippets compile clean under gcc -Wall / g++ -std=c++17 -Wall and were run against sample inputs.

Qualcomm Practice — Part 1 Solutions — Arrays, Searching/Sorting, Strings, Bit manipulation¶

Table of contents¶

D. Arrays¶

D1. Rotate an array by k to the right [E]¶

D2. Merge two sorted arrays in-place [M]¶

D3. Find the missing number in 1..n [E]¶

D4. First and last position in a sorted array [M]¶

D5. Search in a sorted array of "infinite" size [M]¶

D6. Count pairs whose sum is divisible by k [M]¶

D7. N meetings in one room [M]¶

D8. Minimum number of platforms [M]¶

D9. Sliding-window maximum [H]¶

D10. Trapping rain water [H]¶

E. Searching & sorting¶

E1. Binary search [E]¶

E2. Merge sort [M]¶

E3. Quick sort & pivot impact [M]¶

E4. Sort a linked list (merge vs quick) [H]¶

F. Strings (algorithmic)¶

F1. Reverse the words in a sentence [M]¶

F2. Longest substring without repeating characters [M]¶

F3. Longest palindromic substring [M]¶

F4. Count of palindromic substrings [M]¶

G. Bit manipulation¶

G1. Count the number of set bits [E]¶

G2. Check power of two, O(1) [E]¶

G3. Flip the kth bit from the right [E]¶

G4. Reverse the bits of a number [M]¶

G5. Single Number [M]¶

D1. Rotate an array by k to the right `[E]`¶

D2. Merge two sorted arrays in-place `[M]`¶

D3. Find the missing number in 1..n `[E]`¶

D4. First and last position in a sorted array `[M]`¶

D5. Search in a sorted array of "infinite" size `[M]`¶

D6. Count pairs whose sum is divisible by k `[M]`¶

D7. N meetings in one room `[M]`¶

D8. Minimum number of platforms `[M]`¶

D9. Sliding-window maximum `[H]`¶

D10. Trapping rain water `[H]`¶

E1. Binary search `[E]`¶

E2. Merge sort `[M]`¶

E3. Quick sort & pivot impact `[M]`¶

E4. Sort a linked list (merge vs quick) `[H]`¶

F1. Reverse the words in a sentence `[M]`¶

F2. Longest substring without repeating characters `[M]`¶

F3. Longest palindromic substring `[M]`¶

F4. Count of palindromic substrings `[M]`¶

G1. Count the number of set bits `[E]`¶

G2. Check power of two, O(1) `[E]`¶

G3. Flip the kth bit from the right `[E]`¶

G4. Reverse the bits of a number `[M]`¶

G5. Single Number `[M]`¶