Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 398
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given a linked list and an integer `k`, remove the k-th node from the end of the list and return the head of the list.

`k` is guaranteed to be smaller than the length of the list.

Do this in one pass.

Pull request:
Day398
Resolves #799.

Patch:
diff --git a/README.md b/README.md
index 64392a6..86c0901 100644
--- a/README.md
+++ b/README.md
@@ -390,4 +390,5 @@ problems from
 * [Day 395](https://github.com/vaskoz/dailycodingproblem-go/issues/793)
 * [Day 396](https://github.com/vaskoz/dailycodingproblem-go/issues/795)
 * [Day 397](https://github.com/vaskoz/dailycodingproblem-go/issues/797)
+* [Day 398](https://github.com/vaskoz/dailycodingproblem-go/issues/799)
 
diff --git a/day398/problem.go b/day398/problem.go
new file mode 100644
index 0000000..a4a57b5
--- /dev/null
+++ b/day398/problem.go
@@ -0,0 +1,32 @@
+package day398
+
+// SinglyLL is a singly linked list of interface{} type.
+type SinglyLL struct {
+	Value interface{}
+	Next  *SinglyLL
+}
+
+// RemoveKthFromEnd removes the k-th node from the
+// end of the list and return the head of the list.
+// Runs in O(N) time and O(1) space.
+func RemoveKthFromEnd(head *SinglyLL, kth int) *SinglyLL {
+	headPtr := &SinglyLL{Value: nil, Next: head}
+	front := headPtr
+	follower := headPtr
+
+	for i := 0; i <= kth; i++ {
+		if front == nil {
+			panic("less than k elements in list")
+		}
+
+		front = front.Next
+	}
+
+	for ; front != nil; front = front.Next {
+		follower = follower.Next
+	}
+
+	follower.Next = follower.Next.Next
+
+	return headPtr.Next
+}


Test patch:
diff --git a/day398/problem_test.go b/day398/problem_test.go
new file mode 100644
index 0000000..229a723
--- /dev/null
+++ b/day398/problem_test.go
@@ -0,0 +1,62 @@
+package day398
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	head     *SinglyLL
+	kth      int
+	expected *SinglyLL
+}{
+	{
+		&SinglyLL{1, &SinglyLL{2, &SinglyLL{3, &SinglyLL{4, &SinglyLL{5, nil}}}}},
+		2,
+		&SinglyLL{1, &SinglyLL{2, &SinglyLL{3, &SinglyLL{5, nil}}}},
+	},
+	{
+		&SinglyLL{1, &SinglyLL{2, &SinglyLL{3, &SinglyLL{4, &SinglyLL{5, nil}}}}},
+		5,
+		&SinglyLL{2, &SinglyLL{3, &SinglyLL{4, &SinglyLL{5, nil}}}},
+	},
+}
+
+func TestRemoveKthFromEnd(t *testing.T) {
+	t.Parallel()
+
+	for tcid, tc := range testcases {
+		if res := RemoveKthFromEnd(tc.head, tc.kth); !equal(res, tc.expected) {
+			t.Errorf("TCID%d singly linked lists do not match", tcid)
+		}
+	}
+}
+
+func TestRemoveKthFromEndPanic(t *testing.T) {
+	t.Parallel()
+
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("Expected a panic when k is larger than length")
+		}
+	}()
+
+	head := &SinglyLL{1, &SinglyLL{2, &SinglyLL{3, &SinglyLL{4, &SinglyLL{5, nil}}}}}
+	RemoveKthFromEnd(head, 6)
+}
+
+func BenchmarkRemoveKthFromEnd(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			RemoveKthFromEnd(tc.head, tc.kth)
+		}
+	}
+}
+
+func equal(a, b *SinglyLL) bool {
+	for ; a != nil && b != nil; a, b = a.Next, b.Next {
+		if a.Value != b.Value {
+			return false
+		}
+	}
+
+	return a == nil && b == nil
+}