Following are problem solving interview questions. Practice each solution, most of them are self explainatory.
1. Find the Maximum of Two Numbers
func max(a, b int) int {
if a > b {
return a
}
return b
}
2. Factorial of a Number
func factorial(n int) int {
if n == 0 {
return 1
}
return n * factorial(n-1)
}
3. Fibonacci Sequence
func fibonacci(n int) int {
if n <= 1 {
return n
}
return fibonacci(n-1) + fibonacci(n-2)
}
4. Check for Prime Number
Optimizing Prime Checks with Go (Golang)
5. Slice Reverse
func reverseSlice(s []int) []int {
length := len(s)
for i := 0; i < length/2; i++ {
s[i], s[length-i-1] = s[length-i-1], s[i]
}
return s
}
6. Find Element in Slice
func findElement(s []int, el int) int {
for i, v := range s {
if v == el {
return i
}
}
return -1
}
7. Check Palindrome String
func isPalindrome(s string) bool {
for i := 0; i < len(s)/2; i++ {
if s[i] != s[len(s)-i-1] {
return false
}
}
return true
}
8. Find the Smallest Number in a Slice
func findMin(s []int) int {
min := s[0]
for _, v := range s {
if v < min {
min = v
}
}
return min
}
9. Count Occurrences of a Character in a String
func countChar(s string, char rune) int {
count := 0
for _, c := range s {
if c == char {
count++
}
}
return count
}
10. Check If Two Strings Are Anagrams
func areAnagrams(s1, s2 string) bool {
if len(s1) != len(s2) {
return false
}
charCount := make(map[rune]int)
for _, char := range s1 {
charCount[char]++
}
for _, char := range s2 {
charCount[char]--
if charCount[char] < 0 {
return false
}
}
return true
}
11. Merge Two Slices
func mergeSlices(s1, s2 []int) []int {
return append(s1, s2...)
}
12. Square Root Without Using Math Package
func sqrt(n float64) float64 {
x := n
z := (x + n/x) / 2
for z != x {
x = z
z = (x + n/x) / 2
}
return z
}
13. Bubble Sort
func bubbleSort(nums []int) []int {
n := len(nums)
for i := 0; i < n; i++ {
for j := 0; j < n-i-1; j++ {
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
}
return nums
}
14. Binary Search
func binarySearch(nums []int, target int) int {
low, high := 0, len(nums)-1
for low <= high {
mid := (low + high) / 2
if nums[mid] == target {
return mid
}
if nums[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
15. Check Power of Two
func isPowerOfTwo(n int) bool {
if n <= 0 {
return false
}
return n & (n-1) == 0
}
16. Find Missing Number in 1..n
func findMissingNumber(nums []int) int {
n := len(nums) + 1
total := n * (n + 1) / 2
sum := 0
for _, num := range nums {
sum += num
}
return total - sum
}
17. Find Intersection of Two Slices
func intersect(s1, s2 []int) []int {
m := make(map[int]bool)
var res []int
for _, num := range s1 {
m[num] = true
}
for _, num := range s2 {
if m[num] {
res = append(res, num)
}
}
return res
}
18. Rotate Slice by K Elements
func rotate(nums []int, k int) []int {
k %= len(nums)
reverse(nums)
reverse(nums[:k])
reverse(nums[k:])
return nums
}
func reverse(nums []int) {
for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
}
19. Unique Elements in a Slice
func unique(nums []int) []int {
m := make(map[int]bool)
var res []int
for _, num := range nums {
if !m[num] {
res = append(res, num)
m[num] = true
}
}
return res
}
20. Count Vowels and Consonants in a String
func countVowelsConsonants(s string) (int, int) {
vowels, consonants := 0, 0
for _, char := range s {
switch char {
case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
vowels++
default:
if (char >= 'a' && char <= 'z') || (char >= 'A' && char <= 'Z') {
consonants++
}
}
}
return vowels, consonants
}
21. Stack Using Slices
type Stack struct {
items []int
}
func (s *Stack) Push(item int) {
s.items = append(s.items, item)
}
func (s *Stack) Pop() int {
if len(s.items) == 0 {
return -1
}
item, _ := s.items[len(s.items)-1], s.items[:len(s.items)-1]
return item
}
22. Map Functions on Slice
func mapFunc(nums []int, f func(int) int) []int {
for i, v := range nums {
nums[i] = f(v)
}
return nums
}
23. Filter Elements in Slice
func filter(nums []int, f func(int) bool) []int {
var res []int
for _, v := range nums {
if f(v) {
res = append(res, v)
}
}
return res
}
24. Swap Two Numbers Without a Temporary Variable
func swap(a, b int) (int, int) {
a = a + b
b = a - b
a = a - b
return a, b
}
25. Determine If a String Starts With a Given Substring
func startsWith(s, prefix string) bool {
return strings.HasPrefix(s, prefix)
}
26. Determine If a String Ends With a Given Substring
func endsWith(s, suffix string) bool {
return strings.HasSuffix(s, suffix)
}
27. Remove Duplicates From a Slice
func removeDuplicates(nums []int) []int {
seen := make(map[int]bool)
result := []int{}
for _, value := range nums {
if _, exists := seen[value]; !exists {
seen[value] = true
result = append(result, value)
}
}
return result
}
28. Deep Copy a Slice
func deepCopy(nums []int) []int {
return append([]int(nil), nums...)
}
29. Count Set Bits of an Integer
func countSetBits(n int) int {
count := 0
for n != 0 {
count += n & 1
n >>= 1
}
return count
}
30. Convert Integer to Binary String
func toBinary(n int) string {
if n == 0 {
return "0"
}
result := ""
for n > 0 {
result = strconv.Itoa(n&1) + result
n >>= 1
}
return result
}
31. Find GCD of Two Numbers
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
32. Check If a Number Is Even or Odd
func isEven(n int) bool {
return n%2 == 0
}
33. Sum of All Elements in a Slice
func sum(nums []int) int {
total := 0
for _, v := range nums {
total += v
}
return total
}
34. Recursive Sum of Digits of a Number
func sumDigits(n int) int {
if n == 0 {
return 0
}
return n%10 + sumDigits(n/10)
}
35. Find the Second Largest Number in a Slice
func secondLargest(nums []int) int {
first, second := -1<<63, -1<<63
for _, num := range nums {
if num > first {
first, second = num, first
} else if num > second {
second = num
}
}
return second
}
36. Find the Missing Number in a Sequence
Find the missing number in a sequence from 1 to n.
func findMissing(nums []int, n int) int {
expectedSum := n * (n + 1) / 2
actualSum := 0
for _, v := range nums {
actualSum += v
}
return expectedSum - actualSum
}
37. Rotate a Slice
Rotate an integer slice to the right by k steps.
func rotate(nums []int, k int) {
n := len(nums)
k = k % n
reverse(nums, 0, n-1)
reverse(nums, 0, k-1)
reverse(nums, k, n-1)
}
func reverse(nums []int, start, end int) {
for start < end {
nums[start], nums[end] = nums[end], nums[start]
start++
end--
}
}
38. Count Occurrences of a Character in a String
func countOccurrences(s, char string) int {
return strings.Count(s, char)
}
39. Find the Majority Element
Find the element that appears more than n/2 times in a slice of size n.
(Boyer-Moore Voting Algorithm)
func majorityElement(nums []int) int {
count, candidate := 0, 0
for _, num := range nums {
if count == 0 {
candidate = num
}
if num == candidate {
count++
} else {
count--
}
}
return candidate
}
40. Flatten a Nested Slice of Integers
Given a nested slice of integers, flatten it.
func flatten(nested [][]int) []int {
var flat []int
for _, inner := range nested {
flat = append(flat, inner...)
}
return flat
}
41. Find Intersection of Two Slices
func intersection(nums1, nums2 []int) []int {
set := make(map[int]bool)
result := make(map[int]bool)
for _, num := range nums1 {
set[num] = true
}
for _, num := range nums2 {
if set[num] {
result[num] = true
}
}
var res []int
for num := range result {
res = append(res, num)
}
return res
}
42. Find the First Unique Character in a String
func firstUniqChar(s string) int {
count := make(map[rune]int)
for _, ch := range s {
count[ch]++
}
for i, ch := range s {
if count[ch] == 1 {
return i
}
}
return -1
}
43. Implement strStr()
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
func strStr(haystack, needle string) int {
l, r := len(haystack), len(needle)
for i := 0; i <= l-r; i++ {
if haystack[i:i+r] == needle {
return i
}
}
return -1
}
44. Check If All Characters in a String Are Unique
func isUnique(s string) bool {
chars := make(map[rune]bool)
for _, ch := range s {
if chars[ch] {
return false
}
chars[ch] = true
}
return true
}
45. Count Number of Words in a String
func countWords(s string) int {
words := strings.Fields(s)
return len(words)
}
46. Convert String to Integer (without using the built-in parsing functions)
func strToInt(s string) (int, error) {
if len(s) == 0 {
return 0, errors.New("empty string")
}
i, sign, res := 0, 1, 0
if s[0] == '-' {
sign = -1
i++
}
for ; i < len(s); i++ {
if s[i] < '0' || s[i] > '9' {
return 0, errors.New("invalid character in string")
}
res = res*10 + int(s[i]-'0')
}
return sign * res, nil
}
47. Find Smallest and Largest Number in a Slice
func minMax(nums []int) (int, int) {
if len(nums) == 0 {
return 0, 0
}
min, max := nums[0], nums[0]
for _, v := range nums {
if v < min {
min = v
}
if v > max {
max = v
}
}
return min, max
}
48. Merge Two Sorted Lists
Merge two sorted slices of integers into a new sorted slice.
Explanation: The function uses two pointers to compare elements in both slices. The smaller value between the two pointers is added to the result slice and the corresponding pointer is moved to the next position.
func mergeSortedLists(nums1 []int, nums2 []int) []int {
i, j := 0, 0
var result []int
for i < len(nums1) && j < len(nums2) {
if nums1[i] <= nums2[j] {
result = append(result, nums1[i])
i++
} else {
result = append(result, nums2[j])
j++
}
}
// Add remaining elements from nums1 (if any)
for i < len(nums1) {
result = append(result, nums1[i])
i++
}
// Add remaining elements from nums2 (if any)
for j < len(nums2) {
result = append(result, nums2[j])
j++
}
return result
}
49. Remove Duplicates from Slice
Remove duplicates from an integer slice without using any additional data structures.
Explanation: The solution below uses the idea of maintaining two pointers. One, i, is used to iterate over the array, and the other, j, keeps track of the position where the next unique element should be placed.
func removeDuplicates(nums []int) []int {
if len(nums) == 0 {
return nums
}
j := 0
for i := 1; i < len(nums); i++ {
if nums[i] != nums[j] {
j++
nums[j] = nums[i]
}
}
return nums[:j+1]
}
50. Find the Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Explanation: Use a sliding window approach. Maintain a start of the window and use a map to keep track of the characters and their latest positions. When a character repeats, update the start of the window.
func lengthOfLongestSubstring(s string) int {
charIndex := make(map[rune]int)
maxLength, start := 0, 0
for i, ch := range s {
// If the character is already in the map and its index is equal or larger than the current start
if idx, exists := charIndex[ch]; exists && idx >= start {
start = idx + 1
}
charIndex[ch] = i
if i-start+1 > maxLength {
maxLength = i - start + 1
}
}
return maxLength
}
51. Implement Binary Tree (Bonus Question)
package main
import "fmt"
type Node struct {
Data int
Left *Node
Right *Node
}
type BinaryTree struct {
Root *Node
}
func (t *BinaryTree) Insert(data int) {
if t.Root == nil {
t.Root = &Node{Data: data}
return
}
insert(t.Root, data)
}
func insert(node *Node, data int) {
if node == nil {
return
}
if data < node.Data {
if node.Left == nil {
node.Left = &Node{Data: data}
return
}
insert(node.Left, data)
} else {
if node.Right == nil {
node.Right = &Node{Data: data}
return
}
insert(node.Right, data)
}
}
func (t *BinaryTree) InOrderTraversal() {
inOrder(t.Root)
}
func inOrder(node *Node) {
if node == nil {
return
}
inOrder(node.Left)
fmt.Println(node.Data)
inOrder(node.Right)
}
func main() {
tree := &BinaryTree{}
values := []int{2, 3, 50, 20, 30, 4, 5, 8, 1}
for _, v := range values {
tree.Insert(v)
}
fmt.Println("In order Traversal")
tree.InOrderTraversal()
}
Explanation:
-
Struct Definitions:
-
Node
: Represents a node of the binary tree. It has a Data field (integer), a pointer to the Left child node, and a pointer to the Right child node. -
BinaryTree
: Represents the tree itself with a pointer to its root node.
-
-
Insertion Method:
-
(t *BinaryTree) Insert(data int)
: This is a method on the BinaryTree struct that takes an integer and inserts it into the tree. - If the tree's root is nil (empty), it sets the root to be a new node with the provided data.
- Otherwise, it calls the helper function insert to insert the data recursively.
-
insert(node *Node, data int)
: This is a recursive function that inserts a value into the tree. Depending on the value relative to the current node's data, it either goes left (smaller values) or right (larger values).
-
-
In-Order Traversal Method:
-
t *BinaryTree) InOrderTraversal()
: This method on the BinaryTree struct does an in-order traversal of the tree, printing out node data in the process. - It calls the helper function inOrder to perform the traversal.
-
inOrder(node *Node)
: This is a recursive function that performs an in-order traversal of the tree. This means it visits the left subtree, prints the current node's data, and then visits the right subtree.
-
-
main
Function:- A new instance of the binary tree is created.
- Values are inserted into the tree using the provided slice of integers.
- The tree is then traversed in-order, printing the values.
Top comments (0)