This is my recent study notes, some of common problems in the interview, and gives the solution ideas and methods, as well as Go code implementation.

Table of Contents

Introduction

Due to the limited level, the solution ideas and methods, as well as the code implementation, are only what I can get to at the moment. If you have better methods and ideas, please leave me a message in the comment section.

Problems

Find average of all the elements in a list

Arithmetic mean, There doesn’t seem to be a better algorithm for this problem, so let’s just sum and return the mean.

Solution:

// Average Find average of all the elements in a list
func Average(nums []int) int {
	n := len(nums)
	sum := 0
	for i := 0; i < n; i++ {
		sum += nums[i]
	}

	return sum / n
}

Complexity Analysis:

  • Time complexity: $O(n)$
  • Auxiliary Space: $O(1)$

Find the sum of all the elements of a two-dimensional list

Similar to the previous question, there seems to be no direct way but to variable all the elements and return their sum.

Solution:

// SumOfMatrixElement Find the sum of all the elements of a two-dimensional list
func SumOfMatrixElement(nums [][]int) int {
	length := len(nums)
	var sum int
	for i := 0; i < length; i++ {
		for j := 0; j < len(nums[i]); j++ {
			sum += nums[i][j]
		}
	}

	return sum
}

Complexity Analysis:

  • Time complexity: $O(n*m)$
  • Auxiliary Space: $O(1)$

Find the largest element in the list

The solution is to initialize max as first element, then traverse the given array from second element till end. For every traversed element, compare it with max, if it is greater than max, then update max.

Solution:

// MaxElement Find the largest element in the list
func MaxElement(nums []int) int {
	max := math.MinInt
	for i := 0; i < len(nums); i++ {
		if max < nums[i] {
			max = nums[i]
		}
	}

	return max
}

Complexity Analysis:

  • Time complexity: $O(n)$
  • Auxiliary Space: $O(1)$

Find the smallest element in the list

Similar to the previous question, but the final value returned is the minimum value.

Solution:

// SmallestElement Find the largest element in the list
func SmallestElement(nums []int) int {
	min := math.MaxInt
	for i := 0; i < len(nums); i++ {
		if min > nums[i] {
			min = nums[i]
		}
	}

	return min
}

Complexity Analysis:

  • Time complexity: $O(n)$
  • Auxiliary Space: $O(1)$

Find the second-largest element in the list

Find the second-largest element in a single traversal. Below is the complete algorithm for doing this:

  • Initialize the first as nums[0], second as nums[1] element, if nums[0] grater than nums[1], else exchanges
  • Start traversing the array from nums[2],
    • If the current element in array say nums[i] is greater than first. Then update first and second as second = first, first = nums[i]
    • If the current element is in between first and second, then update second to store the value of current variable as second = nums[i]
  • Return the value stored in second

Solution:

// SecondMax Find the second-largest number in the list
func SecondMax(nums []int) int {
	var first, second int

	if nums[0] > nums[1] {
		first, second = nums[0], nums[1]
	} else {
		first, second = nums[1], nums[0]
	}

	for i := 2; i < len(nums); i++ {
		if nums[i] > first {
			second = first
			first = nums[i]
		} else if nums[i] > second {
			second = nums[i]
		}
	}

	return second
}

Complexity Analysis:

  • Time complexity: $O(n)$, Only one traversal of the array is needed.
  • Auxiliary Space: $O(1)$, As no extra space is required.

Generate AllPermutation

Previously, a recursive approach was discussed to generate permutation. Here, I will use a different approach to solve this problem than before. For more discussion on this problem you can follow LeetCode-Permutations, Just deep search with DFS.

Solution:

// Permutations All permutations of an integer list
// The number of permutations of n numbers is n!
func Permutations(nums []int) [][]int {
	if len(nums) == 0 {
		return [][]int{}
	}
	var res [][]int
	var p []int
	used := make([]bool, len(nums))
	generatePermutation(nums, 0, p, &res, &used)
	return res
}

func generatePermutation(nums []int, index int, p []int, res *[][]int, used *[]bool) {
	if index == len(nums) {
		temp := make([]int, len(p))
		copy(temp, p)
		*res = append(*res, temp)
	}

	for i := 0; i < len(nums); i++ {
		if !(*used)[i] {
			(*used)[i] = true
			p = append(p, nums[i])
			generatePermutation(nums, index+1, p, res, used)
			p = p[:len(p)-1]
			(*used)[i] = false
		}
	}
}

Complexity Analysis:

  • Time complexity: $O(n^2)$
  • Auxiliary Space: $O(1)$

Write a method to compute Sum(N)=1+2+3+…+N

Gauss sum: $\dfrac{n\left(n+1\right)}{2}$, read more.

Solution:

func SumN(n int) int {
	return n * (n + 1) / 2
}

Complexity Analysis:

  • Time complexity: $O(1)$
  • Auxiliary Space: $O(1)$

A value is a maximum if the value before and after its index are smaller than it is or does not exist.

Start traversing list from the end and keep track of the max element. If we encounter an element whose value is grater then max, print the element and update max.

Solution:

// Maxima Print all the maxima’s in a list
// A value is a maximum if the value before and
// after its index are smaller than it is or does not exist
func Maxima(nums []int) []int {
	var ans []int

	length := len(nums)
	if nums[0] > nums[1] {
		ans = append(ans, nums[0])
	}

	for i := 2; i < length-1; i++ {
		if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
			ans = append(ans, nums[i])
			i++
		}
	}

	if nums[length-1] > nums[length-2] {
		ans = append(ans, nums[length-1])
	}

	return ans
}

Complexity Analysis:

  • Time complexity: $O(n)$
  • Auxiliary Space: $O(1)$

Given a list of intervals, merge all overlapping intervals

Example:

  • Input: {[1, 4], [3, 6], [8, 10]}

  • Output: {[1, 6], [8, 10]}

  • Sort all intervals in increasing order of start time.

  • Traverse sorted intervals starting from first interval, do following for every interval.

    • If current interval is not first interval, and it overlaps with previous interval, then merge it with previous interval. Keep doing it while the interval overlaps with the previous one.
    • Else add current interval to output list of intervals.

Solution:

func MergeIntervals(intervals [][]int) [][]int {
	if len(intervals) <= 1 {
		return intervals
	}

	if len(intervals) <= 1 {
		return intervals
	}
    // Sorting based on the increasing order of the start intervals
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	var ans [][]int
	ans = append(ans, intervals[0])
	for i := 1; i < len(intervals); i++ {
		lastInterval := ans[len(ans)-1]
		currLeft := intervals[i][0]
		currRight := intervals[i][1]

		if lastInterval[1] < currLeft {
			ans = append(ans, intervals[i])
		} else {
			lastInterval[1] = max(lastInterval[1], currRight)
		}
	}

	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

Complexity Analysis:

  • Time complexity: $O\left(n\log n\right)$
  • Auxiliary Space: $O(1)$

Reverse a list in-place

You cannot use any additional list in other wards Space Complexity should be $O(1)$.

Use two variable, start and end. Start set to 0 and end set to n-1. Increment start and decrement end. Swap the values stored at nums[start] and nums[end]. Stop when start is equal to end or start is greater than end.

Solution:

// Reverse a list in-place
// You cannot use any additional list in other wards Space Complexity should be O(1)
func Reverse(nums []int) []int {
	start, end := 0, len(nums)-1

	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}

	return nums
}

Complexity Analysis:

  • Time complexity: $O\left(\frac{n}{2}\right)$
  • Auxiliary Space: $O(1)$

Given a list of 0s and 1s. We need to sort it so that all the 0s are before all the 1s

Use two variable, start and end. Start set to 0 and end set to n-1. Increment start and decrement end. Swap the values stored at nums[start] and [end] only when nums[start] == 1 and nums[end] ==0. Stop when start is equal to end or start is greater than end.

Solution:

// Segregate0and1 given a list of 0s and 1s. We need to sort it so that all the 0s are before all the 1s
func Segregate0and1(nums []int) []int {
	start, end := 0, len(nums)-1
	for start < end {
		if nums[start] == 1 {
			nums[start], nums[end] = nums[end], nums[start]
			end--
		} else {
			start++
		}
	}

	return nums
}

Complexity Analysis:

  • Time complexity: $O\left(\frac{n}{2}\right)$
  • Auxiliary Space: $O(1)$

Given an array of 0s, 1s and 2s. We need to sort it so that all the 0s are before all the 1s and all the 1s are before 2s

Same as above first think 0s and 1s as one group and move all the 2s on the right side. Then do a second pass over the array to sort 0s and 1s.

Solution:

// Segregate0and1and2 Given an array of 0s, 1s and 2s
// We need to sort it so that all the 0s are before all the 1s and all the 1s are before 2s
func Segregate0and1and2(nums []int) []int {
	low, mid, high := 0, 0, len(nums)-1

	for mid <= high {
		if nums[mid] == 0 {
			nums[low], nums[mid] = nums[mid], nums[low]
			low++
			mid++
		} else if nums[mid] == 1 {
			mid++
		} else {
			nums[mid], nums[high] = nums[high], nums[mid]
			high--
		}
	}

	return nums
}

Complexity Analysis:

  • Time complexity: $O\left(\frac{n}{2}\right)$
  • Auxiliary Space: $O(1)$

Find the duplicate elements in a list of size n where each element is in the range 0 to n-1

We will exploit the constraint “every element is in the range 0 to n-1”. We can take a list nums[] of size n and set all the elements to 0. Whenever we get a value say val1. We will increment the value at nums[var1] index by 1. In the end, we can traverse the list arr and print the repeated values. Additional Space Complexity will be $O(n)$ which will be less than Hash-Table approach.

Solution:

// FindDuplicates find the duplicate elements in a list of size n where each element is in the range 0 to n-1
func FindDuplicates(nums []int) []int {
	var result []int
	length := len(nums)

	for i := 0; i < length; i++ {
		x := nums[i] % length
		nums[x] = nums[x] + length
	}

	for i := 0; i < length; i++ {
		if nums[i] >= length*2 {
			result = append(result, i)
		}
	}

	return result
}

Complexity Analysis:

  • Time complexity: $O(n)$
  • Auxiliary Space: $O(1)$

Find the maximum element in a sorted and rotated list

Binary search algorithm is ok.

Solution:

// FindMax Find the maximum element in a sorted and rotated list
func FindMax(nums []int) int {
	low, mid, high := 0, 0, len(nums)-1

	if nums[low] == nums[high] {
		return nums[low]
	}

	for low+1 < high {
		mid = low + (high-low)>>1
		if nums[low] < nums[mid] {
			low = mid
		} else if nums[low] > nums[mid] {
			high = mid
		} else {
			low = mid
		}
	}

	if nums[high] >= nums[low] {
		return nums[high]
	} else {
		return nums[low]
	}
}

Complexity Analysis:

  • Time complexity: $O\left(n\log n\right)$
  • Auxiliary Space: $O(1)$

Given a slice with ’n’ elements & a value ‘x’, find two elements in the list that sums to ‘x’

Similar to LeetCode’s Two Sum.

Solution:

// CheckPairs Given a slice with 'n' elements & a value 'x'
//  find two elements in the list that sums to 'x'
func CheckPairs(nums []int, x int) []int {
	m := make(map[int]int)

	for k, v := range nums {
		if i, ok := m[x-v]; ok {
			return []int{i, k}
		} else {
			m[v] = k
		}
	}

	return nil
}

Write a method to find the sum of every number in an int number

Example: input= 1984, output should be 22 (1+9+8+4)

Solution:

// SumOfDigits return the sum of every number in an int number
func SumOfDigits(num int) int {
	var ans int
	for num > 0 {
		ans = ans + num%10
		num = num / 10
	}

	return ans
}

Conclusion

Hard to top, can’t top it.

Reference