Initial commitHEADmaster

16 files changed, 795 insertions, 0 deletions

diff --git a/.editorconfig b/.editorconfig
new file mode 100644
index 0000000..e2f0bbd
--- /dev/null
+++ b/.editorconfig
@@ -0,0 +1,15 @@
+root = true
+
+[*.{c,h}]
+end_of_line = lf
+insert_final_newline = true
+charset = utf-8
+trim_trailing_whitespace = true
+indent_style = tab
+indent_size = 8
+max_line_length = 80
+
+[*.md]
+indent_style = space
+indent_size = 4
+trim_trailing_whitespace = false
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..f17e314
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+a.out
+*.gch
diff --git a/complexity.md b/complexity.md
new file mode 100644
index 0000000..9327bb4
--- /dev/null
+++ b/complexity.md
@@ -0,0 +1,14 @@
+# Time Complexity
+
+## Big O
+
+Big O is a way to categorize an algorithm's time or memory requirements based on
+input. It is not meant to be an exact measurement. It will not tell you how many
+CPU cycles it takes, instead it is meant to generalize the growth of the
+algorithm as the input grows.
+
+- Look for loops
+- Constants are dropped (Big O describes the upper bound or growth of the
+  algorithm where the constant eventually becomes irrelevant)
+- We often only consider worst case (e.g., searching through a list where the
+  element you want is the last one)
diff --git a/doublylinkedlist.c b/doublylinkedlist.c
new file mode 100644
index 0000000..e98217a
--- /dev/null
+++ b/doublylinkedlist.c
@@ -0,0 +1,161 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+struct node {
+	int val;
+	struct node *prev;
+	struct node *next;
+};
+
+struct node *head;
+struct node *tail;
+int len = 0;
+
+void
+prepend(int val)
+{
+	struct node *tmp = malloc(sizeof(struct node));
+	tmp->val = val;
+	if (head == NULL) {
+		head = tail = tmp;
+		return;
+	}
+	tmp->val = val;
+	tmp->next = head;
+	head->prev = tmp;
+	head = tmp;
+	++len;
+}
+
+void
+append(int val)
+{
+	struct node *tmp = malloc(sizeof(struct node));
+	tmp->val = val;
+	if (!tail) {
+		head = tail = tmp;
+		return;
+	}
+	tmp->prev = tail;
+	tail->next = tmp;
+	tail = tmp;
+	++len;
+}
+
+struct node
+*get_at(int i)
+{
+	struct node *cur = head;
+	for (int j = 0; cur && j < i; ++j) {
+		cur = cur->next;
+	}
+	return cur;
+}
+
+void
+insert_at(int val, int i)
+{
+	if (i > len) {
+		printf("index is greater than the list length\n");
+	} else if (i == len) {
+		append(val);
+		return;
+	} else if (i == 0) {
+		prepend(val);
+		return;
+	}
+	struct node *cur = get_at(i);
+	struct node *tmp = malloc(sizeof(struct node));
+	tmp->next = cur;
+	tmp->prev = cur->prev;
+	cur->prev = tmp;
+
+	if (tmp->prev) {
+		tmp->prev->next = tmp;
+	}
+	++len;
+}
+
+int
+remove_node(struct node *tmp)
+{
+	--len;
+	if (len == 0) {
+		head = tail = NULL;
+		return -1;
+	}
+
+	if (tmp->prev) {
+		tmp->prev->next = tmp->next;
+	}
+	if (tmp->next) {
+		tmp->next->prev = tmp->prev;
+	}
+
+	if (tmp == head) {
+		head = tmp->next;
+	}
+	if (tmp == tail) {
+		tail = tmp->prev;
+	}
+
+	int val = tmp->val;
+	free(tmp);
+	return val;
+}
+
+int
+remove_val(int val)
+{
+	struct node *cur = head;
+	for (int i = 0; cur && cur->val != val && i < len; ++i) {
+		cur = cur->next;
+	}
+	if (!cur) {
+		return -1;
+	}
+	return remove_node(cur);
+}
+
+int
+remove_at(int i)
+{
+	struct node *tmp = get_at(i);
+	if (!tmp) {
+		return -1;
+	}
+	return remove_node(tmp);
+}
+
+int
+get(int i)
+{
+	get_at(i)->val;
+}
+
+void
+print()
+{
+	struct node *cur = head;
+	while (cur != NULL) {
+		printf("%d ", cur->val);
+		cur = cur->next;
+	}
+	printf("\n");
+}
+
+int
+main()
+{
+	int val, n = 0;
+	printf("How many integers?\n");
+	scanf("%d", &n);
+	for (int i = 0; i < n; ++i) {
+		printf("Enter an integer \n");
+		scanf("%d", &val);
+		prepend(val);
+		print();
+	}
+
+	return 0;
+}
diff --git a/maze/data_structures.h b/maze/data_structures.h
new file mode 100644
index 0000000..e856aaa
--- /dev/null
+++ b/maze/data_structures.h
@@ -0,0 +1,16 @@
+#ifndef DATA_STRUCTURES_H
+#define DATA_STRUCTURES_H
+
+struct point {
+	char c;
+	int x;
+	int y;
+	struct point *next;
+};
+
+extern struct point *head;
+
+void push(int x, int y, char c);
+char pop();
+
+#endif
diff --git a/maze/point.c b/maze/point.c
new file mode 100644
index 0000000..c83c80d
--- /dev/null
+++ b/maze/point.c
@@ -0,0 +1,29 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "data_structures.h"
+
+struct point *head;
+
+void
+push(int x, int y, char c)
+{
+	struct point *tmp = malloc(sizeof(struct point));
+	tmp->c = c;
+	tmp->x = x;
+	tmp->y = y;
+	tmp->next = head;
+	head = tmp;
+}
+
+char
+pop()
+{
+	if (head == NULL) {
+		return -1;
+	}
+	struct point *tmp = head;
+	char c = tmp->c;
+	head = head->next;
+	free(tmp);
+	return c;
+}
diff --git a/maze/solver.c b/maze/solver.c
new file mode 100644
index 0000000..3617f73
--- /dev/null
+++ b/maze/solver.c
@@ -0,0 +1,88 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "data_structures.h"
+
+int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
+
+int
+walk(struct point maze[7][7], char wall, struct point cur, int vis[7][7],
+		struct point end)
+{
+	printf("%d %d ", cur.x, cur.y);
+	if (maze[cur.y][cur.x].c == wall) {
+		printf("wall\n");
+		return 0;
+	}
+	if (vis[cur.y][cur.x]) {
+		printf("vis\n");
+		return 0;
+	}
+	if (cur.x == end.x && cur.y == end.y) {
+		push(end.c, end.x, end.y);
+		return 1;
+	}
+
+	printf("\n");
+	vis[cur.y][cur.x] = 1;
+	push(cur.x, cur.y, cur.c);
+
+	for (int i = 0; i < 4; ++i) {
+		int y = cur.y + dir[i][0];
+		int x = cur.x + dir[i][1];
+		if (x >= 0 && x < 7 && y >= 0 && y < 7) {
+			if (walk(maze, wall, maze[y][x], vis, end)) {
+				return 1;
+			}
+		}
+	}
+
+	pop(cur.c);
+
+	return 0;
+}
+
+void
+solve(struct point maze[7][7], char wall, struct point start, struct point end)
+{
+	int vis[7][7];
+	for (int y = 0; y < 7; ++y) {
+		for (int x = 0; x < 7; ++x) {
+			vis[y][x] = 0;
+		}
+	}
+	walk(maze, wall, start, vis, end);
+}
+
+int
+main()
+{
+	struct point maze[7][7];
+	for (int y = 0; y < 7; ++y) {
+		for (int x = 0; x < 7; ++x) {
+			if (x == 0 & y == 0) {
+				maze[y][x].c = 'S';
+			} else if (x == 6 && y == 6) {
+				maze[y][x].c = 'E';
+			} else if (y == 1 && x < 6
+					|| y == 3 && x > 0
+					|| y == 5 && x < 6) {
+				maze[y][x].c = '#';
+			} else {
+				maze[y][x].c = ' ';
+			}
+			maze[y][x].x = x;
+			maze[y][x].y = y;
+			printf("%c", maze[y][x].c);
+		}
+		printf("\n");
+	}
+	solve(maze, '#', maze[0][0], maze[6][6]);
+
+	printf("\n\nreverse solution\n\n");
+	struct point *cur = head;
+	while (cur->next != NULL) {
+		printf("%d %d\n", cur->x, cur->y);
+		cur = cur->next;
+	}
+	return 0;
+}
diff --git a/min_heap.c b/min_heap.c
new file mode 100644
index 0000000..feeaf68
--- /dev/null
+++ b/min_heap.c
@@ -0,0 +1,113 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int *arr;
+size_t len = 0;
+
+int
+get_parent(int i)
+{
+	return (i - 1) / 2;
+}
+
+int
+get_left_child(int i)
+{
+	return i * 2 + 1;
+}
+
+int
+get_right_child(int i)
+{
+	return i * 2 + 2;
+}
+
+void
+heapify_down(int i)
+{
+	int l = get_left_child(i);
+	int r = get_right_child(i);
+
+	if (i >= len || l >= len) {
+		return;
+	}
+
+	int left_val = arr[l];
+	int right_val = arr[r];
+	int val = arr[i];
+
+	if (right_val > left_val && val > left_val) {
+		arr[i] = left_val;
+		arr[l] = val;
+		heapify_down(l);
+	} else if (left_val > right_val && val > right_val) {
+		arr[i] = right_val;
+		arr[r] = val;
+		heapify_down(r);
+	}
+}
+
+void
+heapify_up(int i)
+{
+	if (i == 0) {
+		return;
+	}
+
+	int p = get_parent(i);
+	int parent_val = arr[p];
+	int child_val = arr[i];
+
+	if (parent_val > child_val) {
+		arr[i] = parent_val;
+		arr[p] = child_val;
+		heapify_up(p);
+	}
+}
+
+void
+insert(int val)
+{
+	arr = realloc(arr, ++len * sizeof(int));
+	arr[len - 1] = val;
+	heapify_up(len - 1);
+}
+
+int
+delete()
+{
+	if (len == 0) {
+		return -1;
+	}
+	int val = arr[0];
+	if (len == 1) {
+		free(arr);
+		return val;
+	}
+
+	arr[0] = arr[--len];
+	heapify_down(0);
+	arr = realloc(arr, len * sizeof(int));
+	return val;
+
+}
+
+int
+main()
+{
+	arr = calloc(len, sizeof(int));
+	insert(5);
+	insert(3);
+	insert(9);
+	insert(7);
+	for (int i = 0; i < len; ++i) {
+		printf("%d ", arr[i]);
+	}
+	printf("\n");
+	delete();
+	for (int i = 0; i < len; ++i) {
+		printf("%d ", arr[i]);
+	}
+	printf("\n");
+	return 0;
+}
diff --git a/queue.c b/queue.c
new file mode 100644
index 0000000..e0923ec
--- /dev/null
+++ b/queue.c
@@ -0,0 +1,68 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+struct node {
+	int val;
+	struct node *next;
+};
+
+struct node *head;
+struct node *tail;
+
+void
+enqueue(int val)
+{
+	struct node *tmp = malloc(sizeof(struct node));
+	tmp->val = val;
+	if (head == NULL) {
+		tail = head = tmp;
+		return;
+	}
+	tail->next = tmp;
+	tail = tmp;
+}
+
+int
+deque()
+{
+	if (head == NULL) {
+		return -1;
+	}
+	struct node *tmp = head;
+	int val = tmp->val;
+	head = head->next;
+	free(tmp);
+	return val;
+}
+
+int
+peek()
+{
+	return head == NULL ? -1 : head->val;
+}
+
+void
+print()
+{
+	struct node *cur = head;
+	while (cur != NULL) {
+		printf("%d ", cur->val);
+		cur = cur->next;
+	}
+	printf("\n");
+}
+
+int
+main()
+{
+	int val, n = 0;
+	printf("How many integers?\n");
+	scanf("%d", &n);
+	for (int i = 0; i < n; ++i) {
+		printf("Enter an integer \n");
+		scanf("%d", &val);
+		enqueue(val);
+		print();
+	}
+	return 0;
+}
diff --git a/recursion.md b/recursion.md
new file mode 100644
index 0000000..a79729c
--- /dev/null
+++ b/recursion.md
@@ -0,0 +1,8 @@
+# Recursion
+
+1. Base case
+2. Function call with consecution
+
+- Pre
+- Recurse
+- Post
diff --git a/search.c b/search.c
new file mode 100644
index 0000000..33218b0
--- /dev/null
+++ b/search.c
@@ -0,0 +1,61 @@
+#include <stdio.h>
+#include <math.h>
+
+int
+linear(int *haystack, int len, int needle)
+{
+	for (int i = 0; i < len; ++i) {
+		if (haystack[i] == needle) {
+			return 1;
+		}
+	}
+	return 0;
+}
+
+int
+binary(int *haystack, int low, int high, int needle)
+{
+	if (low > high) {
+		return 0;
+	}
+
+	int mid = low + (high - low) / 2;
+	if (haystack[mid] == needle) {
+		return 1;
+	} else if (haystack[mid] > needle) {
+		binary(haystack, low, mid - 1, needle);
+	} else {
+		binary(haystack, mid + 1, high, needle);
+	}
+}
+
+int
+square(int *breaks, int len, int needle)
+{
+	int jmp = floor(sqrt(len));
+	int i = jmp;
+	for (; i < len; i += jmp){
+		if (breaks[i]) {
+			break;
+		}
+	}
+	i -= jmp;
+	for (int j = 0; j <= jmp && i < len; ++i, ++j) {
+		if (breaks[i]) {
+			return i;
+		}
+	}
+	return 0;
+}
+
+int
+main()
+{
+	int haystack[5] = {0, 1, 2, 3, 4};
+	int breaks[5] = {0, 0, 1, 0, 0};
+	int len = sizeof(haystack) / sizeof(int);
+	printf("%d\n", linear(haystack, len, 3));
+	printf("%d\n", binary(haystack, 0, len, 3));
+	printf("%d\n", square(breaks, len, 3));
+	return 0;
+}
diff --git a/sort.c b/sort.c
new file mode 100644
index 0000000..2044d57
--- /dev/null
+++ b/sort.c
@@ -0,0 +1,60 @@
+#include <stdio.h>
+
+int
+partition(int *nums, int low, int high)
+{
+	int pivot = nums[high];
+	int i = low - 1;
+	for (int j = low; j < high; ++j) {
+		if (nums[j] <= pivot) {
+			int tmp = nums[j];
+			nums[j] = nums[++i];
+			nums[i] = tmp;
+		}
+	}
+
+	nums[high] = nums[++i];
+	nums[i] = pivot;
+	return i;
+}
+
+int
+*quick(int *nums, int low, int high)
+{
+	if (low >= high) {
+		return nums;
+	}
+
+	int i = partition(nums, low, high);
+	nums = quick(nums, low, i - 1);
+	nums = quick(nums, i + 1, high);
+	return nums;
+}
+
+int
+*bubble(int *nums, int len)
+{
+	for (int i = 0; i < len; ++i) {
+		for (int j = i; j < len - 1 - i; ++j) {
+			if (nums[j] > nums[j + 1]) {
+				int tmp = nums[j];
+				nums[j] = nums[j + 1];
+				nums[j + 1] = tmp;
+			}
+		}
+	}
+	return nums;
+}
+
+int
+main()
+{
+	int nums[5] = {0, 4, 2, 1, 3};
+	int len = sizeof(nums) / sizeof(int);
+	/* int *res = bubble(nums, len); */
+	int *res = quick(nums, 0, 4);
+	for (int i = 0; i < len; ++i) {
+		printf("%d\n", res[i]);
+	}
+	return 0;
+}
diff --git a/stack.c b/stack.c
new file mode 100644
index 0000000..a460629
--- /dev/null
+++ b/stack.c
@@ -0,0 +1,63 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+struct node {
+	int val;
+	struct node *prev;
+};
+
+struct node *head;
+
+void
+push(int val)
+{
+	struct node *tmp = malloc(sizeof(struct node));
+	tmp->val = val;
+	tmp->prev = head;
+	head = tmp;
+}
+
+int
+pop()
+{
+	if (head == NULL) {
+		return -1;
+	}
+	struct node *tmp = head;
+	int val = tmp->val;
+	head = head->prev;
+	free(tmp);
+	return val;
+}
+
+int
+peek()
+{
+	return head == NULL ? -1 : head->val;
+}
+
+void
+print()
+{
+	struct node *cur = head;
+	while (cur != NULL) {
+		printf("%d ", cur->val);
+		cur = cur->prev;
+	}
+	printf("\n");
+}
+
+int
+main()
+{
+	int val, n = 0;
+	printf("How many integers?\n");
+	scanf("%d", &n);
+	for (int i = 0; i < n; ++i) {
+		printf("Enter an integer \n");
+		scanf("%d", &val);
+		push(val);
+		print();
+	}
+	return 0;
+}
diff --git a/tree/data_structures.h b/tree/data_structures.h
new file mode 100644
index 0000000..dbc7bdc
--- /dev/null
+++ b/tree/data_structures.h
@@ -0,0 +1,14 @@
+#ifndef DATA_STRUCTURES_H
+#define DATA_STRUCTURES_H
+
+struct node {
+	int val;
+	struct node *left;
+	struct node *right;
+};
+
+extern struct node *root;
+
+struct node *insert(struct node* cur, int val);
+
+#endif
diff --git a/tree/node.c b/tree/node.c
new file mode 100644
index 0000000..c0d7738
--- /dev/null
+++ b/tree/node.c
@@ -0,0 +1,29 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "data_structures.h"
+
+struct node *root = NULL;
+
+struct node
+*create(int val)
+{
+	struct node *tmp = malloc(sizeof(struct node));
+	tmp->val = val;
+	tmp->left = NULL;
+	tmp->right = NULL;
+	return tmp;
+}
+
+struct node
+*insert(struct node *cur, int val)
+{
+	if (cur == NULL) {
+		return create(val);
+	}
+	if (val < cur->val) {
+		cur->left = insert(cur->left, val);
+	} else if (val > cur->val) {
+		cur->right = insert(cur->right, val);
+	}
+	return cur;
+}
diff --git a/tree/tree.c b/tree/tree.c
new file mode 100644
index 0000000..82b4544
--- /dev/null
+++ b/tree/tree.c
@@ -0,0 +1,54 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "data_structures.h"
+
+void
+pre_order(struct node *cur)
+{
+	if (cur == NULL) {
+		return;
+	}
+	printf("%d ", cur->val);
+	pre_order(cur->left);
+	pre_order(cur->right);
+}
+
+void
+in_order(struct node *cur)
+{
+	if (cur == NULL) {
+		return;
+	}
+	in_order(cur->left);
+	printf("%d ", cur->val);
+	in_order(cur->right);
+}
+
+void
+post_order(struct node *cur)
+{
+	if (cur == NULL) {
+		return;
+	}
+	post_order(cur->left);
+	post_order(cur->right);
+	printf("%d ", cur->val);
+}
+
+int
+main()
+{
+	struct node *root = NULL;
+	root = insert(root, 10);
+	int val, n = 0;
+	printf("How many integers do you want to add to root with val 10?\n");
+	scanf("%d", &n);
+	for (int i = 0; i < n; ++i) {
+		printf("Enter a number \n");
+		scanf("%d", &val);
+		insert(root, val);
+		in_order(root);
+		printf("\n");
+	}
+	return 0;
+}