Skip to main content

​
Introduction

This section contains coding exercises commonly asked in technical interviews, based on real interview experiences from companies like Alibaba, Meituan, Pinduoduo, and ByteDance.
For each problem, try to solve it yourself first before looking at the solution. Understanding the problem-solving process is more important than memorizing solutions.

​
String & Array Problems

​
Problem 1: Adjacent Character Substring (Aliyun)

Description:Given a string, find the number of continuous substrings where no two adjacent characters are the same.Input:
  • First line: positive integer n (string length, max 200,000)
  • Second line: string of lowercase letters
Output:
  • Number of valid continuous substrings
Example:Input:
3
bee
Output:
5
Explanation:
  • Empty string (length 0): 1
  • Length 1: “b”, “e”, “e” → 3 valid
  • Length 2: “be” → 1 valid (“ee” is invalid)
  • Length 3: “bee” → 0 valid
  • Total: 1 + 3 + 1 = 5
Strategy:
  1. Count substrings of each valid length
  2. For each position, find the longest valid substring starting there
  3. Sum all possible substrings
Key Insight: For each position without adjacent duplicates, it contributes to multiple substrings.Time Complexity: O(n²) - checking each possible substring Space Complexity: O(1)
import java.util.Scanner;

public class AdjacentCharacters {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        
        long count = 1; // Empty string
        
        for (int i = 0; i < n; i++) {
            int validLength = 1;
            count++; // Single character always valid
            
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(j) != s.charAt(j - 1)) {
                    count++;
                } else {
                    break; // Adjacent characters same, stop
                }
            }
        }
        
        System.out.println(count);
    }
}

​
Problem 2: 01 String Alternating Pattern (Pinduoduo)

Description:Given a binary string (0s and 1s), you can perform the following operation any number of times:
  • Split the string into two parts
  • Reverse each part individually
  • Concatenate them in the original order
Find the maximum length of alternating 01 substring achievable.Example:Input:
5
10010
Output:
5
Explanation: Split as “10” and “010”, reverse to get “01” and “010”, concatenate to “01010” (length 5)
Key Insight:The operation is equivalent to treating the string as a circular array (ring structure). Any split and reverse operation corresponds to selecting a substring from the doubled string.Strategy:
  1. Double the string: s = s + s (simulate circular structure)
  2. Find the longest alternating 01 pattern in the doubled string
  3. Result cannot exceed original string length n
Why this works: Any rotation and reversal can be found as a substring in the doubled string.
import java.util.Scanner;

public class AlternatingBinaryString {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        
        s += s; // Create circular string
        
        int maxLen = 1;
        int currentLen = 1;
        
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                currentLen++;
                maxLen = Math.max(maxLen, currentLen);
            } else {
                currentLen = 1;
            }
        }
        
        // Result cannot exceed original length
        System.out.println(Math.min(maxLen, n));
    }
}
Time Complexity: O(n) Space Complexity: O(n) for the doubled string

​
Mathematical & Logic Problems

​
Problem 3: GCD Prime Number (Meituan)

Description:Given an integer n > 1, find an integer m (2 ≤ m ≤ n) such that gcd(n, m) is a prime number.Input:
  • First line: t (number of test cases, 1 ≤ t ≤ 100)
  • For each test case: integer n (2 ≤ n ≤ 10⁵)
Output:
  • For each test case: output m
  • If multiple answers exist, output any valid one
Example:Input:
2
10
13
Output:
2
26
Explanation:
  • gcd(10, 2) = 2 (prime)
  • gcd(13, 26) = 13 (prime)
Strategy:
  1. Try all values of m from 2 to n
  2. Calculate gcd(n, m)
  3. Check if gcd is prime
  4. Return first valid m
Optimizations:
  • Use Euclidean algorithm for GCD
  • Optimize prime checking
import java.util.Scanner;

public class GCDPrime {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println(findM(n));
        }
    }
    
    static int findM(int n) {
        for (int m = 2; m <= n; m++) {
            if (isPrime(gcd(n, m))) {
                return m;
            }
        }
        return -1;
    }
    
    // Euclidean algorithm for GCD
    static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // Optimized prime checking
    static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}
Time Complexity: O(n × √n) - checking each m and testing primality Space Complexity: O(1)

​
Problem 4: Minimum Array Range (Meituan)

Description:Given an array of integers, you can perform the following operations:
  • Decrease the maximum element by 1
  • Increase the minimum element by 1
Find the minimum number of operations to make the array range (max - min) as small as possible.Input:
  • First line: n (array length)
  • Second line: n integers
Output:
  • Minimum number of operations
Example:Input:
5
1 2 3 4 5
Output:
3
Explanation: After 3 operations, array can become [2,2,3,4,4] or similar with minimum range.
Key Insight:After operations, the final array will have all elements in range [min_final, max_final]. The optimal strategy is to find which elements should be the boundary.Strategy:
  1. Sort the array
  2. For each possible split point i:
    • Elements before i will be increased to nums[i]
    • Elements after i+1 will be decreased to nums[i+1]
  3. Calculate operations needed for each split
  4. Return minimum
import java.util.Arrays;
import java.util.Scanner;

public class MinimumRange {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Arrays.sort(nums);
        int minOps = Integer.MAX_VALUE;
        
        // Try each split point
        for (int i = 0; i < n - 1; i++) {
            // Elements [0...i] -> increase to nums[i]
            // Elements [i+1...n-1] -> decrease to nums[i+1]
            int ops = 0;
            
            for (int j = 0; j <= i; j++) {
                ops += nums[i] - nums[j];
            }
            
            for (int j = i + 1; j < n; j++) {
                ops += nums[j] - nums[i + 1];
            }
            
            minOps = Math.min(minOps, ops);
        }
        
        System.out.println(minOps);
    }
}
Time Complexity: O(n²) Space Complexity: O(1) excluding input array

​
Data Structure Problems

​
Problem 5: Graph Restoration

Description:Given n points and their shortest distances from point 1, restore a valid undirected graph where:
  • No node has degree > limit
  • The shortest distances are preserved
Input:
  • Line 1: n (nodes), limit (max degree)
  • Line 2: n integers d_i (distance from node 1 to node i)
Output:
  • First line: m (number of edges)
  • Next m lines: u v (edge between u and v)
Example:Input:
3 3
0 1 1
Output:
3
1 2
1 3
2 3
Strategy:
  1. Group nodes by their distance from node 1
  2. Connect each node to a node in the previous distance level
  3. Ensure no node exceeds degree limit
import java.util.*;

public class GraphRestoration {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int limit = sc.nextInt();
        
        int[] dist = new int[n + 1];
        Map<Integer, List<Integer>> levelNodes = new HashMap<>();
        
        for (int i = 1; i <= n; i++) {
            dist[i] = sc.nextInt();
            levelNodes.computeIfAbsent(dist[i], k -> new ArrayList<>()).add(i);
        }
        
        List<int[]> edges = new ArrayList<>();
        int[] degree = new int[n + 1];
        
        // Connect nodes level by level
        for (int level = 1; level <= n; level++) {
            if (!levelNodes.containsKey(level)) continue;
            
            for (int node : levelNodes.get(level)) {
                // Find a parent in previous level
                boolean connected = false;
                for (int parent : levelNodes.get(level - 1)) {
                    if (degree[parent] < limit && degree[node] < limit) {
                        edges.add(new int[]{parent, node});
                        degree[parent]++;
                        degree[node]++;
                        connected = true;
                        break;
                    }
                }
            }
        }
        
        System.out.println(edges.size());
        for (int[] edge : edges) {
            System.out.println(edge[0] + " " + edge[1]);
        }
    }
}
Time Complexity: O(n × limit) Space Complexity: O(n)

​
Classic Algorithm Problems

​
Sorting Algorithms Reference

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

private int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    
    swap(arr, i + 1, right);
    return i + 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
Time Complexity: Average O(n log n), Worst O(n²) Space Complexity: O(log n) for recursion stack
public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    System.arraycopy(temp, 0, arr, left, temp.length);
}
Time Complexity: O(n log n) - stable Space Complexity: O(n)
// Find exact match
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Not found
}

// Find leftmost position
public int leftBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}
Time Complexity: O(log n) Space Complexity: O(1)

​
Common Data Structures

​
Array and List Operations

// Array initialization
int[] nums = new int[]{0, 1, 3};
int[] nums2 = {1, 2, 3, 4};

// Array traversal
for (int i = 0; i < nums.length; i++) {
    System.out.print(nums[i] + " ");
}

// Enhanced for loop
for (int num : nums) {
    System.out.print(num + " ");
}

// Convert ArrayList to array
ArrayList<Integer> list = new ArrayList<>();
int[] arr = list.stream().mapToInt(Integer::intValue).toArray();

​
Problem-Solving Tips

Clarify Requirements

  • Ask about input constraints
  • Clarify edge cases
  • Confirm expected output format
  • Understand performance requirements

Choose Right Approach

  • Brute force first, then optimize
  • Consider time/space trade-offs
  • Identify patterns (two pointers, sliding window, etc.)
  • Use appropriate data structures

Test Your Code

  • Test with example cases
  • Test edge cases (empty, single element, max size)
  • Test with negative numbers if applicable
  • Verify time complexity

Communicate Clearly

  • Explain your thought process
  • Discuss trade-offs
  • Mention alternative approaches
  • Ask for feedback

​
Practice Resources

Consistent practice is key. Aim to solve at least one problem daily, focusing on understanding patterns rather than memorizing solutions.
Recommended Platforms:
  • LeetCode: Most popular, excellent for FAANG preparation
  • 牛客网 (Nowcoder): Chinese companies’ actual interview problems
  • 力扣 (LeetCode CN): Chinese version with local company problems
  • HackerRank: Good for fundamentals and company assessments
Topic Progression:
  1. Arrays and Strings (2 weeks)
  2. Linked Lists (1 week)
  3. Stacks and Queues (1 week)
  4. Trees and Graphs (2 weeks)
  5. Dynamic Programming (2 weeks)
  6. Advanced Topics (2 weeks)

Back to Common Questions

Review interview Q&A before applying your coding skills

Build docs developers (and LLMs) love

Get started for freeTalk to us