Getting TestCase Based I/O Without Any Loop In Golang

Sometimes interview questions come with some twist like

Solve this problem without using any loops

So today I will explain how to solve general input/output (i/o) with test cases problem where special rule defines as saying “Do not use any Loop statement”. We’re going to solve this in Golang. When this type of problem was asked by the interviewer, the first thing that came to our mind(especially those who didn’t solve lots of problem-solving in his/her school/university life). The problem statement is given below that we will try to solve the problem without using any loop.

Note: This problem can be solved differently or different recursive implementation can be applied too.

Problem Statement

– We want you to calculate the sum of squares of given integers, excluding any negatives.
– The first line of the input will be an integer N (1 <= N <= 100), indicating the number of test cases to follow.
– Each of the test cases will consist of a line with an integer X (0 < X <= 100), followed by another line consisting of X number of space-separated integers Yn(-100 <= Yn<= 100).
– For each test case, calculate the sum of squares of the integers, excluding any negatives, and print the calculated sum in the output.

Note 1: Do not put blank lines between test case solutions.
Note 2: Take input from standard input and output to standard output.

Rules

– Do not use any Loop statement
– You may only use standard library packages
– There should be no output until all the input has been received.

Solution

Defining Main & standard library packages

package main

import "fmt"

Defining a global variable for storing results

var result []int

Defining main function

func main() {
    var testCaseNum int
    fmt.Scanln(&testCaseNum)

    nTestCase(0, testCaseNum)
}

Recursively taking inputs using ReadN

Note: The function will finish when the test case and index value become equal and we’re printing the result array recursively using PrintN as Golang doesn’t have any built-in functions which print array without any loop (to my knowledge at least).

func nTestCase(idx int, testCase int) {
    if idx == testCase {
        PrintN(result, 0)
        return
    }
    var n int
    fmt.Scanln(&n)
    
    all := make([]int, n)
    ReadN(all, 0, n)  // reading array elements

    result = append(result, sumOfSquare(all, 0, n))

    nTestCase(idx + 1, testCase)
}

Calculating sum of squares of given integers, excluding any negatives.

func sumOfSquare(values []int, idx int, arrayLen int) int {
    if idx == arrayLen {
        return 0
    }

    if values[idx] > 0 {  // ignoring negative numbers in the array
        return values[idx] * values[idx] + sumOfSquare(values, idx + 1, arrayLen)
    }
    return sumOfSquare(values, idx + 1, arrayLen)
}

Reading integer array inputs recursively

func ReadN(all []int, idx, n int) {
    if n == 0 {
        return
    }
    if m, err := fmt.Scan(&all[idx]); m != 1 {
        panic(err)
    }
    ReadN(all, idx+1, n-1)
}

Outputting result integer array recursively

func PrintN(values []int, idx int) {
    if len(values) == idx {
        return
    }
    fmt.Println(values[idx])

    PrintN(values, idx + 1)
}

In conclusion, When we saw this type of problem for the first time, we thought it’s easy problem until we read the line Do not use any Loop statement in your solution and the problem becomes hard for newbie or not too much experience on problem-solving.

You can read our other blog posts Here

So now we all know how to tackle this type of problem. Stay tuned for our next blog post. Thank you.

Implementation of Floyd’s Cycle-Finding Algorithm in Golang

What is a loop in a linked list

A very common operation in a linked list is to traverse throughout the LinkedList. But when no null value is reached as traversing throughout the linked list, we call this as loops in a linked list. So to detect whether a LinkedList has a loop or not, we can use Floyd’s Cycle-Finding Algorithm also known as a slow-fast pointer or hear tortoise algorithm.

We are implementing Floyd’s Cycle-Finding Algorithm to find loops in a linked list

Linked List

Node & Linked list struct

type Node struct {
    data interface{}
    next *Node
}

type LinkedList struct {
    head *Node
}

Push to a Linked List

func (ll *LinkedList) Push(data interface{}) {
    list := &Node{
        data: data,
    }
    list.next = ll.head
    if ll.head != nil {
        ll.head = list
    }
    ll.head = list

    l := ll.head
    for l.next != nil {
        l = l.next
    }
}

Display the Linked list

func (ll *LinkedList) Display() {
    list := ll.head
    for list != nil {
        fmt.Printf("%+v -> ", list.data)
        list = list.next
    }
    fmt.Println()
}

Detect loops in LinkedList using Floyd’s Cycle-Finding Algorithm

func (ll *LinkedList) DetectLoop() bool {
    slowPtr := ll.head
    fastPtr := ll.head

    for slowPtr != nil && fastPtr != nil && fastPtr.next != nil {
        slowPtr = slowPtr.next
        fastPtr = fastPtr.next.next
        if slowPtr == fastPtr {
            return true
        }
    }
    return false
}

If you like, you can read the same article on my Personal Blog

Main function

func main() {
    link := LinkedList{}
    link.Push(1)
    link.Push(2)
    link.Push(3)
    link.Push(4)
    link.Push(5)

    // creating a loop in the above linked list
    link.head.next.next.next.next.next = link.head  // comment this then for no loop

    if link.DetectLoop() {
        fmt.Println("found loop")
    } else {
        fmt.Println("no loop")
    }
}

// output
found loop

Reverse a linked list using Golang

As we start coding and slowly learning about Data Structures(DS), we come across a very famous linear data structure which is known as a linked list. Linked lists and their related questions are quite popular in interviewers who love problem-solving.

What is a Linked List?

A linked list is a common linear data structure. its elements are also known as **Node** are not stored at a contiguous location. The nodes are linked using pointers. Linked lists are popular as their size is not fixed like an array. Linked list’s each node contains a value and a pointer to the next node. The head pointer points to the first node, and the last node of the list points to null. When the linked list is empty, the head pointer points to null.

Types of Linked Lists:
1. Singly Linked List (Uni-directional)
2. Doubly Linked List (Bi-directional)
3. Circular Linked List

I’ll write about linked list types in a different post as this post about reversing a linked list.

Pros:

  1. Dynamically increase in size
  2. Easy to insertion/deletion

Cons:

  1. Accessing a random node is not allowed.
  2. Additional memory space needs for each node in a linked list.
  3. Not cache friendly.

Linked List

Node for a linked list

type Node struct {
    prev *Node
    next *Node
    key interface{}
}

type LinkedList struct {
    head *Node
    tail *Node
}

Push method for a Linked List

func (ll *LinkedList) Push(key interface{}) {
    list := &Node{
        next: ll.head,
        key: key,
    }
    if ll.head != nil {
        ll.head.prev = list
    }
    ll.head = list
    
    l := ll.head
    for ll.next != nil {
        l = l.next
    }
    ll.tail = l
}
 

Display a Linked list

func (ll *LinkedList) Display() {
    list := ll.head
    for list != nil {
        fmt.Printf("%+v ->", list.key)
        list = list.next
    }
    fmt.Println()
}

// normal display function
func Display(list *Node) {
    for list != nil {
        fmt.Printf("%v ->", list.key)
        list = list.next
    }
    fmt.Println()
}

Reverse a Linked list

func (ll *LinkedList) Reverse() {
    currentNode := ll.head
    var next *Node
    var previousNode *Node
    ll.tail = ll.head

    for currentNode != nil {
        next, currentNode.next = currentNode.next, previousNode
        previousNode, currentNode = currentNode, next
    }
    ll.head = previousNode
    Display(ll.head)
}

If you like, you can read the same article on my Personal Blog

Main function

func main() {
    link := LinkedList{}
    link.Push(9)
    link.Push(12)
    link.Push(15)
    link.Push(8)
    link.Push(1)
    link.Push(3)

    fmt.Println("==============================")
    fmt.Printf("Head: %v\n", link.head.key)
    fmt.Printf("Tail: %v\n", link.tail.key)
    link.Display()
    fmt.Println("==============================")
    link.Reverse()
    fmt.Printf("head: %v\n", link.head.key)
    fmt.Printf("tail: %v\n", link.tail.key)
    fmt.Println("==============================")
}

// output
==============================
Head: 3
Tail: 9
3 -> 1 -> 8 -> 15 -> 12 -> 9 -> 
==============================
9 -> 12 -> 15 -> 8 -> 1 -> 3 -> 
head: 9
tail: 3
==============================