Data Structure in Dart – Interview Patterns & Problem Solving

1. How Interview Problems Actually Work

Interviewers are testing:

• Problem decomposition
• Data structure selection
• Time & space tradeoffs
• Edge case thinking

Most problems are variations of known patterns.

---

2. The 12 Core Interview Patterns

---

Pattern 1: Array Traversal & Sliding Window

When to Use

• Subarrays
• Continuous segments
• Max / min sum

Example Problem

Find the maximum sum of a subarray of size k.

Dart Example

int maxSubArraySum(List<int> nums, int k) {
  int windowSum = 0, maxSum = 0;

  for (int i = 0; i < nums.length; i++) {
    windowSum += nums[i];
    if (i >= k - 1) {
      maxSum = maxSum > windowSum ? maxSum : windowSum;
      windowSum -= nums[i - (k - 1)];
    }
  }
  return maxSum;
}

Time: O(n)

---

Pattern 2: Two Pointers

When to Use

• Sorted arrays
• Palindromes
• Pairs

Example

Check if a string is a palindrome.

bool isPalindrome(String s) {
  int left = 0, right = s.length - 1;

  while (left < right) {
    if (s[left] != s[right]) return false;
    left++;
    right--;
  }
  return true;
}

---

Pattern 3: Hash Map Lookup

When to Use

• Frequency count
• Fast lookup
• Avoid nested loops

Example

Two Sum problem

List<int> twoSum(List<int> nums, int target) {
  final map = <int, int>{};

  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (map.containsKey(complement)) {
      return [map[complement]!, i];
    }
    map[nums[i]] = i;
  }
  return [];
}

Time: O(n)

---

Pattern 4: Fast & Slow Pointers

When to Use

• Cycles
• Linked lists
• Middle element

Example

Detect cycle in a linked list.

bool hasCycle(ListNode head) {
  var slow = head, fast = head;

  while (fast?.next != null) {
    slow = slow!.next;
    fast = fast.next!.next;
    if (slow == fast) return true;
  }
  return false;
}

---

Pattern 5: Stack (Monotonic Stack)

When to Use

• Next greater element
• Valid parentheses
• Undo operations

Example

Valid parentheses.

bool isValid(String s) {
  final stack = <String>[];
  final map = {')': '(', '}': '{', ']': '['};

  for (var c in s.split('')) {
    if (map.containsValue(c)) {
      stack.add(c);
    } else {
      if (stack.isEmpty || stack.removeLast() != map[c]) {
        return false;
      }
    }
  }
  return stack.isEmpty;
}

---

Pattern 6: Binary Search

When to Use

• Sorted data
• Search space reduction

Example

int binarySearch(List<int> nums, int target) {
  int left = 0, right = nums.length - 1;

  while (left <= right) {
    int mid = (left + right) ~/ 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

---

Pattern 7: BFS (Queue)

When to Use

• Shortest path
• Level traversal

Example

void bfs(Map<int, List<int>> graph, int start) {
  final queue = <int>[start];
  final visited = <int>{start};

  while (queue.isNotEmpty) {
    int node = queue.removeAt(0);
    for (var neighbor in graph[node]!) {
      if (!visited.contains(neighbor)) {
        visited.add(neighbor);
        queue.add(neighbor);
      }
    }
  }
}

---

Pattern 8: DFS (Recursion / Stack)

When to Use

• Paths
• Backtracking
• Components

void dfs(int node, Map<int, List<int>> graph, Set<int> visited) {
  visited.add(node);
  for (var next in graph[node]!) {
    if (!visited.contains(next)) {
      dfs(next, graph, visited);
    }
  }
}

---

Pattern 9: Tree Traversal

Traversal	Use Case
Inorder	BST sorted output
Preorder	Serialization
Postorder	Deletion

---

Pattern 10: Divide & Conquer

Example

Merge Sort

List<int> mergeSort(List<int> nums) {
  if (nums.length <= 1) return nums;

  int mid = nums.length ~/ 2;
  return merge(
    mergeSort(nums.sublist(0, mid)),
    mergeSort(nums.sublist(mid)),
  );
}

---

Pattern 11: Greedy

When to Use

• Local optimal → global optimal

Example

Activity selection

---

Pattern 12: Dynamic Programming

When to Use

• Overlapping subproblems
• Optimal substructure

Example

int fib(int n) {
  final dp = List.filled(n + 1, 0);
  dp[1] = 1;

  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

---

3. How to Identify the Right Pattern (Mental Checklist)

Ask:

1. Sorted? → Binary Search / Two Pointers
2. Subarray? → Sliding Window
3. Frequency? → HashMap
4. Shortest path? → BFS
5. All paths? → DFS / Backtracking
6. Optimization? → DP / Greedy

---

4. Common Interview Mistakes

Jump to code
Ignore edge cases
Wrong DS choice
Forget complexity

---

5. Interview Answer Structure (Gold Standard)

1. Clarify problem
2. Explain approach
3. Analyze complexity
4. Code
5. Test edge cases

---

6. Flutter Developer Advantage

• UI trees → Tree traversal
• Navigation → Stack
• Caching → LRU
• Infinite lists → Queue + List

Use these examples to stand out.

---

7. Final Takeaway

You don’t solve problems by memorizing answers.
You solve them by recognizing patterns.

Master patterns → Pass interviews → Build better systems.