Baidu Interview Questions

What Baidu interviews focus on

Common Baidu interview questions

• Given an array of integers, find the longest increasing subsequence.
  What a strong answer covers

  • Define LIS as a subsequence that is strictly increasing and not necessarily contiguous.
  • Dynamic programming O(n^2) approach: dp[i] = length of LIS ending at i.
  • Optimization with patience sorting and binary search O(n log n) using a tail array.
  • Common pitfall: LIS is not unique; algorithm finds length and can reconstruct with parent pointers.
  • Time O(n log n), space O(n).

  View a sample answer

  The longest increasing subsequence (LIS) problem asks for the length of the longest subsequence of a given array where elements are in strictly increasing order. The subsequence does not need to be contiguous. A straightforward dynamic programming solution computes dp[i] as the length of the LIS ending at index i, updating for each j < i with nums[j] < nums[i]. This takes O(n^2) time. To improve, we can use patience sorting: maintain an array 'tails' where tails[i] is the smallest possible tail value for an increasing subsequence of length i+1. For each number, we binary search to find the first tails element >= num and replace it, or append if larger than all. This yields O(n log n) time and O(n) space. A pitfall is misunderstanding that the algorithm only gives length; reconstructing the actual subsequence requires storing predecessor indices. The O(n log n) method is preferred for large n.

  def length_of_lis(nums):
      """
      Returns the length of the longest increasing subsequence.
      Uses patience sorting with binary search for O(n log n).
      """
      import bisect
      tails = []
      for num in nums:
          idx = bisect.bisect_left(tails, num)
          if idx == len(tails):
              tails.append(num)
          else:
              tails[idx] = num
      return len(tails)
  
  # Example usage
  nums = [10, 9, 2, 5, 3, 7, 101, 18]
  print(length_of_lis(nums))  # Output: 4

• Implement a function to detect cycles in a directed graph.
  What a strong answer covers

  • Graph can be represented using adjacency list or matrix.
  • DFS with a recursion stack (or visited set with in-stack marker) to detect back edges.
  • Alternative: Kahn's algorithm (topological sort) uses in-degree and queue; cycle exists if not all nodes processed.
  • Time complexity O(V+E), space O(V) for recursion stack and visited arrays.
  • Pitfall: must handle disconnected graphs; start DFS from every unvisited node.

  View a sample answer

  To detect a cycle in a directed graph, we can use DFS with an additional recursion stack. We maintain a visited array to track nodes processed in current DFS path. If we encounter a node already in the recursion stack, a back edge exists, indicating a cycle. Alternatively, Kahn's algorithm computes in-degrees, repeatedly removes nodes with zero in-degree, and if all nodes are removed, no cycle exists. The DFS approach is simpler for educational purposes but may cause stack overflow for deep graphs; Kahn's algorithm is iterative and often preferred in production. Time complexity is O(V+E), space O(V). A common pitfall is forgetting to reset the recursion stack for each DFS tree; use a single array with three states: unvisited, visiting, visited.

  def has_cycle(graph):
      """
      Detect cycle in directed graph using DFS.
      graph: adjacency list (dict of node -> list of neighbors).
      Returns True if cycle exists.
      """
      WHITE, GRAY, BLACK = 0, 1, 2
      color = {node: WHITE for node in graph}
      
      def dfs(node):
          if color[node] == GRAY:
              return True
          if color[node] == BLACK:
              return False
          color[node] = GRAY  # mark as visiting
          for neighbor in graph.get(node, []):
              if dfs(neighbor):
                  return True
          color[node] = BLACK  # mark as visited
          return False
      
      # Handle disconnected graph
      for node in graph:
          if color[node] == WHITE:
              if dfs(node):
                  return True
      return False
  
  # Example
  if __name__ == '__main__':
      graph = {
          0: [1],
          1: [2],
          2: [0],  # cycle: 0->1->2->0
          3: []
      }
      print(has_cycle(graph))  # Output: True

• Design a real-time search autocomplete system like Baidu's.
  What a strong answer covers

  • Low latency requirement (<100ms) for top suggestions as user types.
  • Use a trie (prefix tree) for fast prefix matching; store frequencies for ranking.
  • Cache top-k suggestions at each node to avoid recomputation.
  • Handle updates (new queries, frequency changes) via batch processing or delta updates.
  • Scale horizontally by sharding the trie based on prefix ranges or using consistent hashing.

  View a sample answer

  A real-time search autocomplete system needs to return top suggestions quickly as the user types. The core data structure is a trie where each node stores a prefix and top-k frequent queries that start with that prefix. To optimize latency, we precompute and cache the top-k list at each node. When a user types a query, we traverse the trie and return the cached list. Input queries are logged and processed asynchronously to update frequencies. For distribution, we can shard the trie by prefix (e.g., first two characters) across multiple servers, using consistent hashing to balance load. A load balancer directs requests to the appropriate shard. For fault tolerance, we replicate each shard. Additionally, we can use a CDN to cache static top queries for common prefixes. The system must handle memory constraints; we can limit trie depth or use compression. Updates are batched and applied periodically to avoid locking.

• Design a distributed cache for a high-traffic website.
  What a strong answer covers

  • High throughput and low latency are key requirements.
  • Use consistent hashing to distribute cache keys across nodes for scalability.
  • Replication or hot-standby for fault tolerance; consider read replicas.
  • Cache eviction policies: LRU, LFU, or TTL-based; choose based on access patterns.
  • Avoid cache stampede with locks or hedge requests; use write-through/behind for consistency.

  View a sample answer

  A distributed cache for a high-traffic website must be fast, scalable, and fault-tolerant. We'll use a cluster of cache nodes (e.g., Redis or Memcached) with consistent hashing to map keys to nodes, minimizing remapping when nodes change. Each node stores data in memory with an eviction policy like LRU to handle limited capacity. To ensure availability, we replicate each shard (e.g., primary-replica) or use a redundancy scheme like CRDTs. For consistency, we can use write-through cache (update cache and database synchronously) or write-behind (batch updates). To prevent cache stampede (many requests on cache miss), we can use a mutex (only one thread populates cache) or stale reads with async refresh. Monitoring is crucial; we track hit rate, latency, and memory usage. Scaling is achieved by adding nodes and adjusting the hash ring. Pitfalls include hot keys (use local caching or replication at client side) and network bottlenecks (use efficient serialization).

• Explain the difference between L1 and L2 regularization and when to use each.
  What a strong answer covers

  • L1 regularization (Lasso) adds sum of absolute weights to loss; L2 (Ridge) adds sum of squares.
  • L1 promotes sparsity (few nonzero weights) useful for feature selection.
  • L2 encourages small weights but not zero; more stable when features are correlated.
  • L1 is not differentiable at zero; use subgradient or proximal methods.
  • Choose L1 for high-dimensional data with irrelevant features; L2 for general regularization.

  View a sample answer

  L1 and L2 regularization are techniques to prevent overfitting by penalizing large weights. L1 adds the sum of absolute values of weights (λΣ|w_i|) to the loss function, leading to sparse models where some weights become exactly zero. This is useful for feature selection when you suspect many features are irrelevant. L2 adds the sum of squares (λΣw_i^2), shrinking weights but not making them zero, and works well when features are correlated or all are relevant. L2 is more stable and differentiable everywhere, making it easier to optimize. In practice, L1 can be sensitive to outliers and may select one feature from a group of correlated ones. L2 is often the default. Hybrid models like Elastic Net combine both. The choice depends on the problem: if you need interpretability or have many redundant features, L1; otherwise, L2. Regularization strength λ is tuned via cross-validation.

• How would you handle class imbalance in a classification problem?
  What a strong answer covers

  • Class imbalance occurs when one class has significantly fewer samples; can bias model towards majority.
  • Resampling: oversample minority (e.g., SMOTE) or undersample majority (random or Tomek links).
  • Cost-sensitive learning: assign higher misclassification cost to minority class.
  • Ensemble methods: use boosting or bagging with balanced training sets.
  • Evaluation: use precision-recall curve, AUC, or F1-score instead of accuracy.

  View a sample answer

  Class imbalance is a common problem where one class (minority) is far fewer than others, causing models to favor the majority class. Several strategies exist. Resampling: oversampling the minority (e.g., SMOTE generates synthetic examples) or undersampling the majority (loses data but can be effective). Cost-sensitive learning modifies the loss function to penalize misclassifications of minority class more heavily. Ensemble methods like balanced random forests or XGBoost with scale_pos_weight can help. Another approach is to use anomaly detection for extreme imbalance. It's crucial to evaluate with appropriate metrics: accuracy is misleading; use precision, recall, F1-score, or AUC-ROC. Pitfalls include overfitting with oversampling (especially duplicates) and losing informative samples with undersampling. A combination of techniques often works best, along with tuning on a validation set. In production, consider using stratified sampling for train/test splits.

• Tell me about a time you had to work under tight deadlines to deliver a project.
  What a strong answer covers

  • Use STAR method: Situation, Task, Action, Result.
  • Choose a project with a clear tight deadline and high stakes.
  • Describe specific actions taken to prioritize, communicate, and deliver.
  • Highlight collaboration with team and trade-offs made.
  • Result should be concrete: on-time delivery, positive feedback, or business impact.

  View a sample answer

  In my previous role, our team was tasked with launching a new feature for a major client's website within two weeks, but the initial timeline was four weeks. The situation was critical because the client had already delayed the launch multiple times. As the lead engineer, I first assessed the scope and identified essential versus nice-to-have features. I proposed a minimal viable product (MVP) approach, focusing on core functionality. We held daily stand-ups to track progress and used a Kanban board to visualize bottlenecks. I personally refactored a critical module to reduce integration time. We also communicated transparently with the client about the trade-offs. As a result, we delivered the MVP on the exact deadline, the client was satisfied, and we added remaining features in subsequent sprints. The key was ruthless prioritization and clear communication.

• Describe a situation where you disagreed with a team member and how you resolved it.
  What a strong answer covers

  • STAR method again: describe a specific disagreement.
  • Focus on technical or process-related conflict, not personal.
  • Explain how you listened, found common ground, or used data to decide.
  • Emphasize respect and collaboration.
  • Result: improved solution, stronger team relationship, or learning.

  View a sample answer

  During a project, my colleague and I disagreed on the choice of database for a new service. I advocated for a NoSQL document store due to its flexibility, while my teammate preferred a relational database for its transaction guarantees. Instead of escalating, we scheduled a meeting to list pros and cons for our specific use case, including scalability, consistency needs, and development time. We realized that most queries were key-value lookups, but a few required joins. We compromised by using a hybrid approach: a document store for the main data and a relational database for transactional analytics. We presented this to the team, who agreed. The result was a robust architecture that met all requirements, and we both learned to approach disagreements with data. The project was delivered on time, and our working relationship improved from mutual respect.

Tips to prepare

• Master data structures and algorithms with a focus on dynamic programming, trees, and graphs, as they are common in Baidu interviews.
• Practice system design for distributed systems, especially in the context of search, recommendation, and large-scale data processing.
• Review core ML concepts: supervised vs unsupervised learning, overfitting, feature selection, and model evaluation metrics.
• Be prepared to explain your thought process clearly and write bug-free code on a whiteboard or in a shared editor.
• Research Baidu's products (e.g., Baidu Search, Apollo, DuerOS) to understand the technical challenges they face.

Frequently asked