Golang Technical Interview Questions and Answers

Below are answers to common Golang technical interview questions. Each answer is written in simple and detailed language for easy understanding.

---

1. What is Go and why is it popular?

   • Answer: Go (or Golang) is an open-source programming language developed by Google. It is known for its simplicity, efficiency, and strong support for concurrency. Go is popular because it compiles quickly, produces fast executables, has a clean syntax, and makes it easy to write scalable and maintainable code.

2. Explain the difference between a slice and an array in Go.

   • Answer: An array in Go has a fixed size and cannot be resized after creation. A slice is a dynamically-sized, flexible view into the elements of an array. Slices are more commonly used because they can grow and shrink as needed.

3. How does Go handle concurrency?

   • Answer: Go handles concurrency using goroutines and channels. Goroutines are lightweight threads managed by the Go runtime, and channels are used to communicate between goroutines safely.

4. What are goroutines and how do they differ from threads?

   • Answer: Goroutines are functions or methods that run concurrently with other functions or methods. They are much lighter than threads and are managed by the Go runtime, allowing thousands of goroutines to run at the same time with minimal overhead.

5. What is a channel in Go and how is it used?

   • Answer: A channel is a built-in data structure that allows goroutines to communicate with each other and synchronize their execution. You can send and receive values through channels using the <- operator.

6. Explain the concept of interfaces in Go.

   • Answer: An interface in Go is a type that specifies a set of method signatures. Any type that implements those methods satisfies the interface. Interfaces allow for flexible and decoupled code.

7. How does Go handle memory management?

   • Answer: Go uses automatic garbage collection to manage memory. The runtime automatically frees memory that is no longer in use, reducing the risk of memory leaks.

8. What is the purpose of the defer statement in Go?

   • Answer: The defer statement is used to ensure that a function call is performed later in a program’s execution, usually for cleanup purposes. Deferred functions are executed after the surrounding function returns.

9. How do you handle errors in Go?

   • Answer: Errors in Go are handled by returning an error value as the last return value from a function. You check if the error is nil to determine if the operation was successful.

10. What is the Go init function and when is it called?

    • Answer: The init function is a special function that is executed automatically when a package is initialized. It is used to set up initial state or perform setup tasks.

11. Explain the use of the select statement in Go.

    • Answer: The select statement lets a goroutine wait on multiple communication operations. It blocks until one of its cases can proceed, making it useful for handling multiple channels.

12. What are the differences between buffered and unbuffered channels?

    • Answer: An unbuffered channel only allows sending and receiving when both the sender and receiver are ready. A buffered channel has a capacity and allows sending without a receiver until the buffer is full.

13. How do you create a custom type in Go?

    • Answer: You can create a custom type using the type keyword. For example: type MyInt int creates a new type called MyInt based on int.

14. What is the purpose of the go fmt tool?

    • Answer: go fmt automatically formats Go source code according to standard style guidelines, making code more readable and consistent.

15. How do you implement a simple HTTP server in Go?

    • Answer: You can use the net/http package. Example:

      package main
      import ("fmt"; "net/http")
      func handler(w http.ResponseWriter, r *http.Request) {
          fmt.Fprintf(w, "Hello, World!")
      }
      func main() {
          http.HandleFunc("/", handler)
          http.ListenAndServe(":8080", nil)
      }

16. What is the context package and how is it used in Go?

    • Answer: The context package is used to carry deadlines, cancellation signals, and other request-scoped values across API boundaries and between processes.

17. Explain the concept of embedding in Go.

    • Answer: Embedding allows one struct type to include another struct type, inheriting its fields and methods. This is Go’s way of achieving composition.

18. How do you perform unit testing in Go?

    • Answer: Go has a built-in testing framework. You write test functions in files ending with _test.go and run them using go test.

19. What is the purpose of the go mod command?

    • Answer: go mod is used for managing dependencies in Go projects. It helps you initialize, tidy, and manage modules.

20. How do you handle JSON in Go?

    • Answer: You use the encoding/json package to encode and decode JSON data using json.Marshal and json.Unmarshal functions.

21. What are the differences between var, const, and type in Go?

    • Answer: var declares variables, const declares constants (unchangeable values), and type defines new types.

22. How do you implement a linked list in Go?

    • Answer: You define a struct for the node and use pointers to link nodes together. Example:

      type Node struct {
          Value int
          Next  *Node
      }

23. What is the purpose of the sync package in Go?

    • Answer: The sync package provides basic synchronization primitives such as mutexes and wait groups for managing concurrent operations.

24. How do you implement a binary tree in Go?

    • Answer: You define a struct for the tree node with left and right pointers. Example:

      type TreeNode struct {
          Value int
          Left  *TreeNode
          Right *TreeNode
      }

25. Explain the use of the sync.Mutex in Go.

    • Answer: sync.Mutex is used to provide mutual exclusion, allowing only one goroutine to access a critical section of code at a time.

26. What is the difference between a pointer and a value in Go?

    • Answer: A value is a direct piece of data, while a pointer holds the memory address of a value. Pointers allow you to share and modify data across functions.

27. How do you implement a stack in Go?

    • Answer: You can use a slice to implement a stack, using append to push and slicing to pop elements.

28. What is the purpose of the go vet tool?

    • Answer: go vet examines Go source code and reports suspicious constructs, such as mistakes that may not be caught by the compiler.

29. How do you implement a queue in Go?

    • Answer: You can use a slice to implement a queue, using append to enqueue and slicing to dequeue elements.

30. What is the purpose of the go build command?

    • Answer: go build compiles the source code of the Go program and produces an executable binary.

31. How do you implement a hash map in Go?

    • Answer: Go provides built-in maps. Example: m := make(map[string]int)

32. What is the purpose of the go test command?

    • Answer: go test runs tests written in Go source files to verify code correctness.

33. How do you implement a binary search in Go?

    • Answer: You repeatedly divide the sorted array in half to find the target value. Example:

      func binarySearch(arr []int, target int) int {
          left, right := 0, len(arr)-1
          for left <= right {
              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
      }

34. What is the purpose of the go run command?

    • Answer: go run compiles and runs Go programs in one step, useful for quick testing.

35. How do you implement a bubble sort in Go?

    • Answer: Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Example:

      func bubbleSort(arr []int) {
          n := len(arr)
          for i := 0; i < n-1; i++ {
              for j := 0; j < n-i-1; j++ {
                  if arr[j] > arr[j+1] {
                      arr[j], arr[j+1] = arr[j+1], arr[j]
                  }
              }
          }
      }

36. What is the purpose of the go install command?

    • Answer: go install compiles and installs the package, placing the resulting binary in the $GOPATH/bin directory.

37. How do you implement a quick sort in Go?

    • Answer: Quick sort is a divide-and-conquer algorithm that partitions the array and recursively sorts the subarrays. Example:

      func quickSort(arr []int) []int {
          if len(arr) < 2 {
              return arr
          }
          left, right := 0, len(arr)-1
          pivot := rand.Int() % len(arr)
          arr[pivot], arr[right] = arr[right], arr[pivot]
          for i := range arr {
              if arr[i] < arr[right] {
                  arr[i], arr[left] = arr[left], arr[i]
                  left++
              }
          }
          arr[left], arr[right] = arr[right], arr[left]
          quickSort(arr[:left])
          quickSort(arr[left+1:])
          return arr
      }

38. What is the purpose of the go doc command?

    • Answer: go doc displays documentation for a package or symbol in Go.

39. How do you implement a merge sort in Go?

    • Answer: Merge sort divides the array into halves, sorts each half, and merges them. Example:

      func mergeSort(arr []int) []int {
          if len(arr) <= 1 {
              return arr
          }
          mid := len(arr) / 2
          left := mergeSort(arr[:mid])
          right := mergeSort(arr[mid:])
          return merge(left, right)
      }
      func merge(left, right []int) []int {
          result := []int{}
          i, j := 0, 0
          for i < len(left) && j < len(right) {
              if left[i] < right[j] {
                  result = append(result, left[i])
                  i++
              } else {
                  result = append(result, right[j])
                  j++
              }
          }
          result = append(result, left[i:]...)
          result = append(result, right[j:]...)
          return result
      }

40. What is the purpose of the go generate command?

    • Answer: go generate is used to automate code generation tasks, such as creating code from templates or running tools before building.

41. How do you implement a depth-first search (DFS) in Go?

    • Answer: DFS can be implemented using recursion or a stack. Example:

      func dfs(node *TreeNode) {
          if node == nil {
              return
          }
          // process node
          dfs(node.Left)
          dfs(node.Right)
      }

42. What is the purpose of the go list command?

    • Answer: go list provides information about Go packages.

43. How do you implement a breadth-first search (BFS) in Go?

    • Answer: BFS can be implemented using a queue. Example:

      func bfs(root *TreeNode) {
          queue := []*TreeNode{root}
          for len(queue) > 0 {
              node := queue[0]
              queue = queue[1:]
              // process node
              if node.Left != nil {
                  queue = append(queue, node.Left)
              }
              if node.Right != nil {
                  queue = append(queue, node.Right)
              }
          }
      }

44. What is the purpose of the go get command?

    • Answer: go get is used to download and install packages and dependencies.

45. How do you implement a graph in Go?

    • Answer: A graph can be represented using an adjacency list (map of nodes to slices of neighbors). Example:

      type Graph map[int][]int

46. What is the purpose of the go mod tidy command?

    • Answer: go mod tidy removes unused dependencies and adds missing ones in your go.mod file.

47. How do you implement a trie in Go?

    • Answer: A trie is a tree-like data structure for storing strings. Example:

      type TrieNode struct {
          Children map[rune]*TrieNode
          IsEnd    bool
      }

48. What is the purpose of the go mod vendor command?

    • Answer: go mod vendor copies all dependencies into a vendor directory in your project.

49. How do you implement a priority queue in Go?

    • Answer: You can use the container/heap package to implement a priority queue.

50. What is the purpose of the go mod edit command?

    • Answer: go mod edit edits the go.mod file directly, allowing you to add, remove, or change module requirements.

51. How do you implement a bloom filter in Go?

    • Answer: A bloom filter is a probabilistic data structure for set membership. You use multiple hash functions and a bit array.

52. What is the purpose of the go mod verify command?

    • Answer: go mod verify checks that dependencies on disk match the cryptographic hashes in go.sum.

53. How do you implement a red-black tree in Go?

    • Answer: You define a struct for the node with color information and implement insertion and balancing logic. This is an advanced topic and usually uses third-party libraries.

54. What is the purpose of the go mod graph command?

    • Answer: go mod graph prints the dependency graph of your modules.

55. How do you implement a segment tree in Go?

    • Answer: A segment tree is a binary tree used for range queries. You define a struct for the tree and implement build, update, and query methods.

56. What is the purpose of the go mod why command?

    • Answer: go mod why explains why a dependency is needed in your project.

57. How do you implement a skip list in Go?

    • Answer: A skip list is a probabilistic data structure for fast search. You define nodes with multiple forward pointers at different levels.

58. What is the purpose of the go mod download command?

    • Answer: go mod download downloads modules to the local cache.

59. How do you implement a LRU cache in Go?

    • Answer: You can use a combination of a doubly linked list and a map to implement an LRU cache.

60. What is the purpose of the go mod vendor command?

    • Answer: go mod vendor copies dependencies to the vendor directory. (Duplicate of Q48)

61. How do you implement a hash table in Go?

    • Answer: Go’s built-in map type is a hash table. Example: m := make(map[string]int)

62. What is the purpose of the go mod init command?

    • Answer: go mod init initializes a new module, creating a go.mod file.

63. How do you implement a counting sort in Go?

    • Answer: Counting sort counts the occurrences of each value and uses this information to place elements in order.

64. What is the purpose of the go mod edit command?

    • Answer: go mod edit edits the go.mod file. (Duplicate of Q50)

65. How do you implement a radix sort in Go?

    • Answer: Radix sort processes each digit of the numbers, grouping them by digit value.

66. What is the purpose of the go mod tidy command?

    • Answer: go mod tidy cleans up dependencies. (Duplicate of Q46)

67. How do you implement a bucket sort in Go?

    • Answer: Bucket sort divides elements into buckets, sorts each bucket, and then concatenates them.

68. What is the purpose of the go mod vendor command?

    • Answer: go mod vendor copies dependencies to the vendor directory. (Duplicate of Q48/Q60)

69. How do you implement a shell sort in Go?

    • Answer: Shell sort is a generalization of insertion sort that allows the exchange of items far apart. You sort elements at specific intervals and reduce the interval over time.

---

DSA Questions and Answers in Go

1. Implement a function to reverse a string in Go.

   • Answer:

     func reverseString(s string) string {
         runes := []rune(s)
         for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
             runes[i], runes[j] = runes[j], runes[i]
         }
         return string(runes)
     }

2. Write a function to check if a string is a palindrome in Go.

   • Answer:

     func isPalindrome(s string) bool {
         runes := []rune(s)
         for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
             if runes[i] != runes[j] {
                 return false
             }
         }
         return true
     }

3. Implement a function to find the factorial of a number in Go.

   • Answer:

     func factorial(n int) int {
         if n == 0 {
             return 1
         }
         return n * factorial(n-1)
     }

4. Write a function to find the nth Fibonacci number in Go.

   • Answer:

     func fibonacci(n int) int {
         if n <= 1 {
             return n
         }
         return fibonacci(n-1) + fibonacci(n-2)
     }

5. Implement a function to sort an array using bubble sort in Go.

   • Answer:

     func bubbleSort(arr []int) {
         n := len(arr)
         for i := 0; i < n-1; i++ {
             for j := 0; j < n-i-1; j++ {
                 if arr[j] > arr[j+1] {
                     arr[j], arr[j+1] = arr[j+1], arr[j]
                 }
             }
         }
     }

6. Write a function to find the maximum element in an array in Go.

   • Answer:

     func maxElement(arr []int) int {
         max := arr[0]
         for _, v := range arr {
             if v > max {
                 max = v
             }
         }
         return max
     }

7. Implement a function to merge two sorted arrays in Go.

   • Answer:

     func mergeSortedArrays(a, b []int) []int {
         i, j := 0, 0
         result := []int{}
         for i < len(a) && j < len(b) {
             if a[i] < b[j] {
                 result = append(result, a[i])
                 i++
             } else {
                 result = append(result, b[j])
                 j++
             }
         }
         result = append(result, a[i:]...)
         result = append(result, b[j:]...)
         return result
     }

8. Write a function to find the intersection of two arrays in Go.

   • Answer:

     func intersection(a, b []int) []int {
         m := make(map[int]bool)
         for _, v := range a {
             m[v] = true
         }
         res := []int{}
         for _, v := range b {
             if m[v] {
                 res = append(res, v)
                 m[v] = false
             }
         }
         return res
     }

9. Implement a function to check if two strings are anagrams in Go.

   • Answer:

     func areAnagrams(s1, s2 string) bool {
         if len(s1) != len(s2) {
             return false
         }
         count := make(map[rune]int)
         for _, c := range s1 {
             count[c]++
         }
         for _, c := range s2 {
             count[c]--
             if count[c] < 0 {
                 return false
             }
         }
         return true
     }

10. Write a function to find the first non-repeating character in a string in Go.

    • Answer:

      func firstNonRepeatingChar(s string) rune {
          count := make(map[rune]int)
          for _, c := range s {
              count[c]++
          }
          for _, c := range s {
              if count[c] == 1 {
                  return c
              }
          }
          return 0 // or any invalid value
      }

11. Implement a function to find the longest substring without repeating characters in Go.

• Answer:

  func lengthOfLongestSubstring(s string) int {
      m := make(map[rune]int)
      maxLen, start := 0, 0
      runes := []rune(s)
      for i, c := range runes {
          if idx, ok := m[c]; ok && idx >= start {
              start = idx + 1
          }
          m[c] = i
          if i-start+1 > maxLen {
              maxLen = i - start + 1
          }
      }
      return maxLen
  }

12. Write a function to find the sum of all even numbers in an array in Go.

• Answer:

  func sumEven(arr []int) int {
      sum := 0
      for _, v := range arr {
          if v%2 == 0 {
              sum += v
          }
      }
      return sum
  }

13. Implement a function to find the second largest element in an array in Go.

• Answer:

  func secondLargest(arr []int) int {
      first, second := -1<<31, -1<<31
      for _, v := range arr {
          if v > first {
              second = first
              first = v
          } else if v > second && v != first {
              second = v
          }
      }
      return second
  }

14. Write a function to rotate an array to the right by k positions in Go.

• Answer:

  func rotateRight(arr []int, k int) []int {
      n := len(arr)
      k = k % n
      return append(arr[n-k:], arr[:n-k]...)
  }

15. Implement a function to find the missing number in an array of integers from 1 to n in Go.

• Answer:

  func missingNumber(arr []int) int {
      n := len(arr) + 1
      total := n * (n + 1) / 2
      sum := 0
      for _, v := range arr {
          sum += v
      }
      return total - sum
  }

16. Write a function to check if a linked list is a palindrome in Go.

• Answer:

  type ListNode struct {
      Val  int
      Next *ListNode
  }
  func isPalindromeList(head *ListNode) bool {
      vals := []int{}
      for node := head; node != nil; node = node.Next {
          vals = append(vals, node.Val)
      }
      for i, j := 0, len(vals)-1; i < j; i, j = i+1, j-1 {
          if vals[i] != vals[j] {
              return false
          }
      }
      return true
  }

17. Implement a function to find the intersection of two linked lists in Go.

• Answer:

  func getIntersectionNode(a, b *ListNode) *ListNode {
      m := make(map[*ListNode]bool)
      for node := a; node != nil; node = node.Next {
          m[node] = true
      }
      for node := b; node != nil; node = node.Next {
          if m[node] {
              return node
          }
      }
      return nil
  }

18. Write a function to detect a cycle in a linked list in Go.

• Answer:

  func hasCycle(head *ListNode) bool {
      slow, fast := head, head
      for fast != nil && fast.Next != nil {
          slow = slow.Next
          fast = fast.Next.Next
          if slow == fast {
              return true
          }
      }
      return false
  }

19. Implement a function to reverse a linked list in Go.

• Answer:

  func reverseList(head *ListNode) *ListNode {
      var prev *ListNode
      curr := head
      for curr != nil {
          next := curr.Next
          curr.Next = prev
          prev = curr
          curr = next
      }
      return prev
  }

20. Write a function to find the middle element of a linked list in Go.

• Answer:

  func middleNode(head *ListNode) *ListNode {
      slow, fast := head, head
      for fast != nil && fast.Next != nil {
          slow = slow.Next
          fast = fast.Next.Next
      }
      return slow
  }

21. Implement a function to find the height of a binary tree in Go.

• Answer:

  type TreeNode struct {
      Val   int
      Left  *TreeNode
      Right *TreeNode
  }
  func treeHeight(root *TreeNode) int {
      if root == nil {
          return 0
      }
      l := treeHeight(root.Left)
      r := treeHeight(root.Right)
      if l > r {
          return l + 1
      }
      return r + 1
  }

22. Write a function to perform an in-order traversal of a binary tree in Go.

• Answer:

  func inorderTraversal(root *TreeNode) []int {
      res := []int{}
      var inorder func(*TreeNode)
      inorder = func(node *TreeNode) {
          if node == nil {
              return
          }
          inorder(node.Left)
          res = append(res, node.Val)
          inorder(node.Right)
      }
      inorder(root)
      return res
  }

23. Implement a function to check if a binary tree is balanced in Go.

• Answer:

  func isBalanced(root *TreeNode) bool {
      var check func(*TreeNode) int
      check = func(node *TreeNode) int {
          if node == nil {
              return 0
          }
          l := check(node.Left)
          r := check(node.Right)
          if l == -1 || r == -1 || abs(l-r) > 1 {
              return -1
          }
          if l > r {
              return l + 1
          }
          return r + 1
      }
      return check(root) != -1
  }
  func abs(x int) int {
      if x < 0 {
          return -x
      }
      return x
  }

24. Write a function to find the lowest common ancestor of two nodes in a binary tree in Go.

• Answer:

  func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
      if root == nil || root == p || root == q {
          return root
      }
      left := lowestCommonAncestor(root.Left, p, q)
      right := lowestCommonAncestor(root.Right, p, q)
      if left != nil && right != nil {
          return root
      }
      if left != nil {
          return left
      }
      return right
  }

25. Implement a function to convert a binary tree to a doubly linked list in Go.

• Answer:

  type DllNode struct {
      Val  int
      Prev *DllNode
      Next *DllNode
  }
  func treeToDoublyList(root *TreeNode) *DllNode {
      var head, prev *DllNode
      var inorder func(*TreeNode)
      inorder = func(node *TreeNode) {
          if node == nil {
              return
          }
          inorder(node.Left)
          curr := &DllNode{Val: node.Val}
          if prev == nil {
              head = curr
          } else {
              prev.Next = curr
              curr.Prev = prev
          }
          prev = curr
          inorder(node.Right)
      }
      inorder(root)
      return head
  }

26. Write a function to find the diameter of a binary tree in Go.

• Answer:

  func diameterOfBinaryTree(root *TreeNode) int {
      diameter := 0
      var depth func(*TreeNode) int
      depth = func(node *TreeNode) int {
          if node == nil {
              return 0
          }
          l := depth(node.Left)
          r := depth(node.Right)
          if l+r > diameter {
              diameter = l + r
          }
          if l > r {
              return l + 1
          }
          return r + 1
      }
      depth(root)
      return diameter
  }

27. Implement a function to find the kth smallest element in a binary search tree in Go.

• Answer:

  func kthSmallest(root *TreeNode, k int) int {
      stack := []*TreeNode{}
      for {
          for root != nil {
              stack = append(stack, root)
              root = root.Left
          }
          root = stack[len(stack)-1]
          stack = stack[:len(stack)-1]
          k--
          if k == 0 {
              return root.Val
          }
          root = root.Right
      }
  }

28. Write a function to serialize and deserialize a binary tree in Go.

• Answer:

  func serialize(root *TreeNode) string {
      if root == nil {
          return "#"
      }
      return fmt.Sprintf("%d,%s,%s", root.Val, serialize(root.Left), serialize(root.Right))
  }
  func deserialize(data string) *TreeNode {
      vals := strings.Split(data, ",")
      var build func() *TreeNode
      build = func() *TreeNode {
          if len(vals) == 0 {
              return nil
          }
          val := vals[0]
          vals = vals[1:]
          if val == "#" {
              return nil
          }
          v, _ := strconv.Atoi(val)
          node := &TreeNode{Val: v}
          node.Left = build()
          node.Right = build()
          return node
      }
      return build()
  }

29. Implement a function to find the maximum depth of a binary search tree in Go.

• Answer:

  func maxDepth(root *TreeNode) int {
      if root == nil {
          return 0
      }
      l := maxDepth(root.Left)
      r := maxDepth(root.Right)
      if l > r {
          return l + 1
      }
      return r + 1
  }

30. Write a function to check if a binary search tree is valid in Go.

• Answer:

  func isValidBST(root *TreeNode) bool {
      var validate func(*TreeNode, *int, *int) bool
      validate = func(node *TreeNode, min, max *int) bool {
          if node == nil {
              return true
          }
          if min != nil && node.Val <= *min {
              return false
          }
          if max != nil && node.Val >= *max {
              return false
          }
          return validate(node.Left, min, &node.Val) && validate(node.Right, &node.Val, max)
      }
      return validate(root, nil, nil)
  }

31. Implement a function to find the longest path in a binary tree in Go.

• Answer:

  func longestPath(root *TreeNode) int {
      maxLen := 0
      var dfs func(*TreeNode) int
      dfs = func(node *TreeNode) int {
          if node == nil {
              return 0
          }
          l := dfs(node.Left)
          r := dfs(node.Right)
          if l+r > maxLen {
              maxLen = l + r
          }
          if l > r {
              return l + 1
          }
          return r + 1
      }
      dfs(root)
      return maxLen
  }

32. Write a function to find the sum of all nodes at a given level in a binary tree in Go.

• Answer:

  func sumAtLevel(root *TreeNode, level int) int {
      if root == nil {
          return 0
      }
      if level == 0 {
          return root.Val
      }
      return sumAtLevel(root.Left, level-1) + sumAtLevel(root.Right, level-1)
  }

33. Implement a function to find the path from root to a given node in a binary tree in Go.

• Answer:

  func pathToNode(root *TreeNode, target int) []int {
      path := []int{}
      var dfs func(*TreeNode) bool
      dfs = func(node *TreeNode) bool {
          if node == nil {
              return false
          }
          path = append(path, node.Val)
          if node.Val == target || dfs(node.Left) || dfs(node.Right) {
              return true
          }
          path = path[:len(path)-1]
          return false
      }
      dfs(root)
      return path
  }

34. Write a function to find the sum of all leaf nodes in a binary tree in Go.

• Answer:

  func sumOfLeaves(root *TreeNode) int {
      if root == nil {
          return 0
      }
      if root.Left == nil && root.Right == nil {
          return root.Val
      }
      return sumOfLeaves(root.Left) + sumOfLeaves(root.Right)
  }

35. Implement a function to find the maximum path sum in a binary tree in Go.

• Answer:

  func maxPathSum(root *TreeNode) int {
      maxSum := -1 << 31
      var dfs func(*TreeNode) int
      dfs = func(node *TreeNode) int {
          if node == nil {
              return 0
          }
          l := max(0, dfs(node.Left))
          r := max(0, dfs(node.Right))
          sum := node.Val + l + r
          if sum > maxSum {
              maxSum = sum
          }
          if l > r {
              return node.Val + l
          }
          return node.Val + r
      }
      dfs(root)
      return maxSum
  }
  func max(a, b int) int {
      if a > b {
          return a
      }
      return b
  }

36. Write a function to find the vertical order traversal of a binary tree in Go.

• Answer:

  func verticalOrder(root *TreeNode) [][]int {
      if root == nil {
          return [][]int{}
      }
      m := make(map[int][]int)
      minCol, maxCol := 0, 0
      type Pair struct {
          Node *TreeNode
          Col  int
      }
      queue := []Pair{{root, 0}}
      for len(queue) > 0 {
          p := queue[0]
          queue = queue[1:]
          m[p.Col] = append(m[p.Col], p.Node.Val)
          if p.Node.Left != nil {
              queue = append(queue, Pair{p.Node.Left, p.Col - 1})
              if p.Col-1 < minCol {
                  minCol = p.Col - 1
              }
          }
          if p.Node.Right != nil {
              queue = append(queue, Pair{p.Node.Right, p.Col + 1})
              if p.Col+1 > maxCol {
                  maxCol = p.Col + 1
              }
          }
      }
      res := [][]int{}
      for i := minCol; i <= maxCol; i++ {
          res = append(res, m[i])
      }
      return res
  }

37. Implement a function to find the zigzag level order traversal of a binary tree in Go.

• Answer:

  func zigzagLevelOrder(root *TreeNode) [][]int {
      res := [][]int{}
      if root == nil {
          return res
      }
      queue := []*TreeNode{root}
      leftToRight := true
      for len(queue) > 0 {
          n := len(queue)
          level := make([]int, n)
          for i := 0; i < n; i++ {
              node := queue[0]
              queue = queue[1:]
              if leftToRight {
                  level[i] = node.Val
              } else {
                  level[n-1-i] = node.Val
              }
              if node.Left != nil {
                  queue = append(queue, node.Left)
              }
              if node.Right != nil {
                  queue = append(queue, node.Right)
              }
          }
          res = append(res, level)
          leftToRight = !leftToRight
      }
      return res
  }

38. Write a function to find the sum of all nodes in a binary tree in Go.

• Answer:

  func sumOfNodes(root *TreeNode) int {
      if root == nil {
          return 0
      }
      return root.Val + sumOfNodes(root.Left) + sumOfNodes(root.Right)
  }

39. Implement a function to find the kth largest element in an array in Go.

• Answer:

  import "sort"
  func kthLargest(arr []int, k int) int {
      sort.Ints(arr)
      return arr[len(arr)-k]
  }

40. Write a function to find the longest increasing subsequence in an array in Go.

• Answer:

  func lengthOfLIS(nums []int) int {
      if len(nums) == 0 {
          return 0
      }
      dp := make([]int, len(nums))
      for i := range dp {
          dp[i] = 1
      }
      maxLen := 1
      for i := 1; i < len(nums); i++ {
          for j := 0; j < i; j++ {
              if nums[i] > nums[j] && dp[j]+1 > dp[i] {
                  dp[i] = dp[j] + 1
              }
          }
          if dp[i] > maxLen {
              maxLen = dp[i]
          }
      }
      return maxLen
  }

41. Implement a function to find the longest common subsequence of two strings in Go.

• Answer:

  func longestCommonSubsequence(text1, text2 string) int {
      m, n := len(text1), len(text2)
      dp := make([][]int, m+1)
      for i := range dp {
          dp[i] = make([]int, n+1)
      }
      for i := 1; i <= m; i++ {
          for j := 1; j <= n; j++ {
              if text1[i-1] == text2[j-1] {
                  dp[i][j] = dp[i-1][j-1] + 1
              } else {
                  if dp[i-1][j] > dp[i][j-1] {
                      dp[i][j] = dp[i-1][j]
                  } else {
                      dp[i][j] = dp[i][j-1]
                  }
              }
          }
      }
      return dp[m][n]
  }

42. Write a function to find the maximum subarray sum using Kadane's algorithm in Go.

• Answer:

  func maxSubArray(nums []int) int {
      maxSoFar, maxEndingHere := nums[0], nums[0]
      for i := 1; i < len(nums); i++ {
          if maxEndingHere+nums[i] > nums[i] {
              maxEndingHere = maxEndingHere + nums[i]
          } else {
              maxEndingHere = nums[i]
          }
          if maxEndingHere > maxSoFar {
              maxSoFar = maxEndingHere
          }
      }
      return maxSoFar
  }

43. Implement a function to find the minimum subarray sum in an array in Go.

• Answer:

  func minSubArray(nums []int) int {
      minSoFar, minEndingHere := nums[0], nums[0]
      for i := 1; i < len(nums); i++ {
          if minEndingHere+nums[i] < nums[i] {
              minEndingHere = minEndingHere + nums[i]
          } else {
              minEndingHere = nums[i]
          }
          if minEndingHere < minSoFar {
              minSoFar = minEndingHere
          }
      }
      return minSoFar
  }

44. Write a function to find the maximum product subarray in an array in Go.

• Answer:

  func maxProduct(nums []int) int {
      maxProd, minProd, result := nums[0], nums[0], nums[0]
      for i := 1; i < len(nums); i++ {
          candidates := []int{nums[i], maxProd * nums[i], minProd * nums[i]}
          maxProd, minProd = candidates[0], candidates[0]
          for _, v := range candidates {
              if v > maxProd {
                  maxProd = v
              }
              if v < minProd {
                  minProd = v
              }
          }
          if maxProd > result {
              result = maxProd
          }
      }
      return result
  }

45. Implement a function to find the longest palindromic substring in a string in Go.

• Answer:

  func longestPalindrome(s string) string {
      n := len(s)
      if n == 0 {
          return ""
      }
      start, maxLen := 0, 1
      for i := 0; i < n; i++ {
          l, r := i, i
          for l >= 0 && r < n && s[l] == s[r] {
              if r-l+1 > maxLen {
                  start = l
                  maxLen = r - l + 1
              }
              l--
              r++
          }
          l, r = i, i+1
          for l >= 0 && r < n && s[l] == s[r] {
              if r-l+1 > maxLen {
                  start = l
                  maxLen = r - l + 1
              }
              l--
              r++
          }
      }
      return s[start : start+maxLen]
  }

46. Write a function to find the shortest path in a grid using BFS in Go.

• Answer:

  type Point struct{ X, Y int }
  func shortestPathBFS(grid [][]int, start, end Point) int {
      n, m := len(grid), len(grid[0])
      dirs := []Point{{0,1},{1,0},{0,-1},{-1,0}}
      visited := make([][]bool, n)
      for i := range visited {
          visited[i] = make([]bool, m)
      }
      queue := []Point{start}
      visited[start.X][start.Y] = true
      steps := 0
      for len(queue) > 0 {
          size := len(queue)
          for i := 0; i < size; i++ {
              p := queue[0]
              queue = queue[1:]
              if p == end {
                  return steps
              }
              for _, d := range dirs {
                  nx, ny := p.X+d.X, p.Y+d.Y
                  if nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && grid[nx][ny] == 0 {
                      queue = append(queue, Point{nx, ny})
                      visited[nx][ny] = true
                  }
              }
          }
          steps++
      }
      return -1
  }

47. Implement a function to find the number of islands in a grid using DFS in Go.

• Answer:

  func numIslands(grid [][]byte) int {
      n, m := len(grid), len(grid[0])
      var dfs func(int, int)
      dfs = func(x, y int) {
          if x < 0 || y < 0 || x >= n || y >= m || grid[x][y] != '1' {
              return
          }
          grid[x][y] = '0'
          dfs(x+1, y)
          dfs(x-1, y)
          dfs(x, y+1)
          dfs(x, y-1)
      }
      count := 0
      for i := 0; i < n; i++ {
          for j := 0; j < m; j++ {
              if grid[i][j] == '1' {
                  count++
                  dfs(i, j)
              }
          }
      }
      return count
  }

48. Write a function to find the maximum area of an island in a grid using DFS in Go.

• Answer:

  func maxAreaOfIsland(grid [][]int) int {
      n, m := len(grid), len(grid[0])
      var dfs func(int, int) int
      dfs = func(x, y int) int {
          if x < 0 || y < 0 || x >= n || y >= m || grid[x][y] == 0 {
              return 0
          }
          grid[x][y] = 0
          area := 1
          area += dfs(x+1, y)
          area += dfs(x-1, y)
          area += dfs(x, y+1)
          area += dfs(x, y-1)
          return area
      }
      maxArea := 0
      for i := 0; i < n; i++ {
          for j := 0; j < m; j++ {
              if grid[i][j] == 1 {
                  area := dfs(i, j)
                  if area > maxArea {
                      maxArea = area
                  }
              }
          }
      }
      return maxArea
  }

49. Implement a function to find the shortest path in a weighted graph using Dijkstra's algorithm in Go.

• Answer:

  import (
      "container/heap"
      "math"
  )
  type Edge struct{ To, Weight int }
  type Item struct {
      Node, Dist int
  }
  type MinHeap []Item
  func (h MinHeap) Len() int           { return len(h) }
  func (h MinHeap) Less(i, j int) bool { return h[i].Dist < h[j].Dist }
  func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
  func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
  func (h *MinHeap) Pop() interface{} {
      old := *h
      n := len(old)
      x := old[n-1]
      *h = old[:n-1]
      return x
  }
  func dijkstra(n int, graph map[int][]Edge, start int) []int {
      dist := make([]int, n)
      for i := range dist {
          dist[i] = math.MaxInt32
      }
      dist[start] = 0
      h := &MinHeap{{start, 0}}
      heap.Init(h)
      for h.Len() > 0 {
          item := heap.Pop(h).(Item)
          u := item.Node
          if item.Dist > dist[u] {
              continue
          }
          for _, e := range graph[u] {
              if dist[u]+e.Weight < dist[e.To] {
                  dist[e.To] = dist[u] + e.Weight
                  heap.Push(h, Item{e.To, dist[e.To]})
              }
          }
      }
      return dist
  }

50. Write a function to find the minimum spanning tree of a graph using Prim's algorithm in Go.

• Answer:

  import (
      "container/heap"
  )
  type EdgeP struct{ To, Weight int }
  type ItemP struct {
      Node, Weight int
  }
  type MinHeapP []ItemP
  func (h MinHeapP) Len() int           { return len(h) }
  func (h MinHeapP) Less(i, j int) bool { return h[i].Weight < h[j].Weight }
  func (h MinHeapP) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
  func (h *MinHeapP) Push(x interface{}) { *h = append(*h, x.(ItemP)) }
  func (h *MinHeapP) Pop() interface{} {
      old := *h
      n := len(old)
      x := old[n-1]
      *h = old[:n-1]
      return x
  }
  func prim(n int, graph map[int][]EdgeP) int {
      visited := make([]bool, n)
      h := &MinHeapP{{0, 0}}
      heap.Init(h)
      total := 0
      for h.Len() > 0 {
          item := heap.Pop(h).(ItemP)
          u := item.Node
          if visited[u] {
              continue
          }
          visited[u] = true
          total += item.Weight
          for _, e := range graph[u] {
              if !visited[e.To] {
                  heap.Push(h, ItemP{e.To, e.Weight})
              }
          }
      }
      return total
  }