Insert Interval into Sorted List in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting interval into sorted list

What is the output of the Go code after inserting the interval [4, 8] into the sorted list of intervals?

DSA Go

package main
import "fmt"
func insertInterval(intervals [][]int, newInterval []int) [][]int {
    var result [][]int
    i := 0
    for i < len(intervals) && intervals[i][1] < newInterval[0] {
        result = append(result, intervals[i])
        i++
    }
    for i < len(intervals) && intervals[i][0] <= newInterval[1] {
        if intervals[i][0] < newInterval[0] {
            newInterval[0] = intervals[i][0]
        }
        if intervals[i][1] > newInterval[1] {
            newInterval[1] = intervals[i][1]
        }
        i++
    }
    result = append(result, newInterval)
    for i < len(intervals) {
        result = append(result, intervals[i])
        i++
    }
    return result
}
func main() {
    intervals := [][]int{{1, 3}, {6, 9}}
    newInterval := []int{4, 8}
    result := insertInterval(intervals, newInterval)
    fmt.Println(result)
}

A [[1,3],[4,9]]

B [[1,3],[4,8],[6,9]]

C [[1,3],[4,8]]

D [[1,3],[6,9],[4,8]]

💡 Hint

Think about how overlapping intervals are merged after insertion.

The new interval [4,8] overlaps with [6,9], so they merge into [4,9]. The final list is [[1,3],[4,9]].

🧠 Conceptual

intermediate

Number of intervals after insertion and merge

Given a sorted list of intervals [[1,2],[3,5],[6,7],[8,10],[12,16]] and a new interval [4,8], how many intervals will be in the list after inserting and merging?

A 3

B 4

C 5

D 2

💡 Hint

Check which intervals overlap with [4,8] and merge them.

Intervals [3,5],[6,7],[8,10] overlap with [4,8] and merge into [3,10]. The final list is [[1,2],[3,10],[12,16]] with 3 intervals.

🔧 Debug

advanced

Identify the error in interval insertion code

What error will this Go code produce when inserting [2,5] into [[1,3],[6,9]]? func insertInterval(intervals [][]int, newInterval []int) [][]int { var result [][]int i := 0 for i < len(intervals) && intervals[i][1] < newInterval[0] { result = append(result, intervals[i]) i++ } for i < len(intervals) && intervals[i][0] <= newInterval[1] { if intervals[i][0] > newInterval[0] { newInterval[0] = intervals[i][0] } if intervals[i][1] < newInterval[1] { newInterval[1] = intervals[i][1] } i++ } result = append(result, newInterval) for i < len(intervals) { result = append(result, intervals[i]) i++ } return result }

A The code will run correctly and produce [[1,5],[6,9]].

B The code will panic due to index out of range.

C The code will produce a syntax error due to missing braces.

D The merged interval will be incorrect because the min and max are assigned wrongly.

💡 Hint

Check how newInterval boundaries are updated inside the merge loop.

The code incorrectly updates newInterval boundaries by using > and < instead of < and >, causing wrong merged intervals.

📝 Syntax

advanced

Identify syntax error in Go interval insertion snippet

Which option contains a syntax error when trying to append intervals in Go?

DSA Go

var result [][]int
intervals := [][]int{{1,3},{6,9}}
newInterval := []int{2,5}
i := 0
for i < len(intervals) && intervals[i][1] < newInterval[0] {
    result = append(result, intervals[i])
    i++
}

A

result = append(result, intervals[i])
 i++

B result = append(result, intervals[i])

C result = append(result intervals[i])

D

result = append(result, intervals[i])
i++

💡 Hint

Check the syntax of the append function call.

Option C misses a comma between result and intervals[i], causing a syntax error.

🚀 Application

expert

Final intervals after multiple insertions

Starting with an empty list, insert intervals in order: [1,3], [6,9], [2,5], [10,11]. What is the final list of intervals after all insertions and merges?

A [[1,3],[2,5],[6,9],[10,11]]

B [[1,5],[6,9],[10,11]]

C [[1,9],[10,11]]

D [[1,5],[6,11]]

💡 Hint

Merge intervals after each insertion carefully.

After inserting [1,3] and [6,9], inserting [2,5] merges with [1,3] to form [1,5]. Then [10,11] is added separately.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. To merge overlapping intervals and keep the list sorted

B. To add the new interval at the end without merging

C. To remove all intervals that come before the new interval

D. To sort the list again after insertion

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. Inserting a new interval may cause overlaps.

2. Step 2: Determine the correct action

   We must merge any overlapping intervals with the new one to keep the list sorted and non-overlapping.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted -> Option A

4. Quick Check:

   Insert interval = merge and keep sorted [OK]

Hint: Merge overlaps to keep intervals sorted and non-overlapping [OK]

Common Mistakes:

• Just appending without merging
• Removing intervals incorrectly
• Sorting again after insertion

2. Which Go syntax correctly declares a slice of intervals where each interval is a slice of two integers?

easy

A. intervals := [][2]int{{1, 3}, {6, 9}}

B. intervals := [][]int{1, 3, 6, 9}

C. intervals := []int{1, 3, 6, 9}

D. intervals := [][]int{{1, 3}, {6, 9}}

Solution

1. Step 1: Identify slice of slices syntax

   In Go, [][]int means a slice of slices of int, suitable for intervals like [start, end].

2. Step 2: Check each option

   intervals := [][]int{{1, 3}, {6, 9}} correctly uses [][]int with nested slices for intervals. intervals := [][2]int{{1, 3}, {6, 9}} uses array [2]int which is valid but less common. intervals := []int{1, 3, 6, 9} is a flat slice, not intervals. intervals := [][]int{1, 3, 6, 9} is invalid syntax.

3. Final Answer:

   intervals := [][]int{{1, 3}, {6, 9}} -> Option D

4. Quick Check:

   Slice of slices = [][]int{{start,end}} [OK]

Hint: Use [][]int for slice of intervals in Go [OK]

Common Mistakes:

• Using flat []int instead of [][]int
• Incorrect array vs slice syntax
• Missing curly braces for nested slices

3. What is the output of the following Go code snippet after inserting interval [2,5] into intervals [[1,2],[6,9]]?

intervals := [][]int{{1, 2}, {6, 9}}
newInterval := []int{2, 5}
// After insertion and merging
result := [][]int{{1, 5}, {6, 9}}
fmt.Println(result)

medium

A. [[1 2] [6 9] [2 5]]

B. [[1 2] [2 5] [6 9]]

C. [[1 5] [6 9]]

D. [[2 5] [6 9]]

Solution

1. Step 1: Insert and check overlap

   New interval [2,5] overlaps with [1,2] because 2 <= 2. Merge them to [1,5].

2. Step 2: Keep other intervals

   [6,9] does not overlap with [1,5], so it stays as is.

3. Final Answer:

   [[1 5] [6 9]] -> Option C

4. Quick Check:

   Merged intervals = [[1 5] [6 9]] [OK]

Hint: Merge overlapping intervals to combine ranges [OK]

Common Mistakes:

• Not merging overlapping intervals
• Appending new interval without sorting
• Incorrect interval order

4. Given this Go function snippet to insert an interval, what is the bug?

func insert(intervals [][]int, newInterval []int) [][]int {
    var result [][]int
    for _, interval := range intervals {
        if interval[1] < newInterval[0] {
            result = append(result, interval)
        } else if interval[0] > newInterval[1] {
            result = append(result, newInterval)
            newInterval = interval
        } else {
            newInterval[0] = min(newInterval[0], interval[0])
            newInterval[1] = max(newInterval[1], interval[1])
        }
    }
    result = append(result, newInterval)
    return result
}

medium

A. Appending newInterval multiple times causes duplicates

B. Not updating newInterval correctly during merge

C. Missing return statement

D. Incorrect comparison operators in if conditions

Solution

1. Step 1: Analyze appending logic

   When interval[0] > newInterval[1], newInterval is appended and then replaced by interval. This can cause multiple appends of newInterval.

2. Step 2: Identify duplicate insertion

   Because newInterval is appended inside the loop multiple times, duplicates appear in result.

3. Final Answer:

   Appending newInterval multiple times causes duplicates -> Option A

4. Quick Check:

   Multiple appends = duplicates [OK]

Hint: Append newInterval once after loop to avoid duplicates [OK]

Common Mistakes:

• Appending inside loop multiple times
• Not updating newInterval boundaries
• Forgetting to return result

5. You have intervals [[1,3],[6,9]] and want to insert [2,7]. What is the final list after insertion and merging?

hard

A. [[1,3],[2,7],[6,9]]

B. [[1,9]]

C. [[1,7],[6,9]]

D. [[1,9],[6,9]]

Solution

1. Step 1: Merge [2,7] with overlapping intervals

   [2,7] overlaps with [1,3] and [6,9]. Merge all three intervals into one covering from min start 1 to max end 9.

2. Step 2: Final merged interval

   The merged interval is [1,9], replacing the original two intervals.

3. Final Answer:

   [[1,9]] -> Option B

4. Quick Check:

   Merge all overlapping = [[1,9]] [OK]

Hint: Merge all overlapping intervals into one big interval [OK]

Common Mistakes:

• Partial merges leaving overlaps
• Appending without merging
• Incorrect interval boundaries