Given a string, $S$, of length $n$ and containing only characters in the set $\left\{\text{(}, \text{\{}, \text{[}, \text{)}, \text{\}}, \text{]}\right\}$, determine whether $S$ is balanced. A string of parentheses is said to be balanced iff.:
The approach is to use a stack in order to keep track of the state of our balance (and bracket types!) as we traverse $S$ linearly. Push each opening bracket onto the stack and pop each closing bracket off (only if it matches with the current top of the stack). If a closing bracket doesn't match with the current top of the stack (e.g., $\text{)}$ and $\text{\{}$), then the string is unbalanced. Once linear scan has terminated, if the stack is non-empty then the string is also unbalanced. If the stack is empty then the string is balanced.
#define STACKLEN 10000
bool isValid(char* s) {
if (s == NULL) return false;
size_t n = strlen(s);
size_t d = 0;
char stack[STACKLEN];
for (size_t i=0;i<n;i++) {
switch(s[i]) {
case '(':
case '{':
case '[':
stack[d] = s[i];
d++;
break;
case ')':
if (d > 0 && stack[d-1] == '(') {
d--;
} else {
return false;
}
break;
case '}':
if (d > 0 && stack[d-1] == '{') {
d--;
} else {
return false;
}
break;
case ']':
if (d > 0 && stack[d-1] == '[') {
d--;
} else {
return false;
}
break;
}
}
return d == 0;
}
Note: This is a Leetcode solution and, as such, makes use of an explicit bound on $n$ (i.e., 10000).
Given an array, $A$, of length $n$, that is sorted in non-decreasing order, produce the array, $A'$, of length $k$, that contains only the unique elements of $A$ in their original order.
int removeDuplicates(int* nums, int numsSize) {
if (nums == NULL || numsSize == 0) return 0;
if (numsSize == 1) return 1;
size_t pos = 0;
size_t arrlen = numsSize;
while (pos < arrlen - 1) {
if (nums[pos] == nums[pos+1]) {
for (size_t j=pos;j<arrlen-1;j++) {
nums[j] = nums[j+1];
}
arrlen--;
} else {
pos++;
}
}
return arrlen;
}
Note: This is a Leetcode solution and, as such, modifies the provided array (nums) by overwriting the duplicate elements as soon as they're encountered. The size of the resulting array is communicated via the returned value of the removeDuplicates function.
Given an array, $A$, of length $n$, and a value $x$, produce the array, $A'$, of length $k$, that contains all of the elements in $A$ such that $\forall i\leq k, A'\left[i\right]\neq x$.
Things to keep in mind:
int removeElement(int* nums, int numsSize, int val) {
if (nums == NULL || numsSize == 0) return 0;
size_t pos = 0;
size_t arrlen = numsSize;
while (pos < arrlen) {
if (nums[pos] == val) {
for (size_t j=pos;j<arrlen-1;j++) {
nums[j] = nums[j+1];
}
arrlen--;
} else {
pos++;
}
}
return arrlen;
}
Note: This is a Leetcode solution and, as such, modifies the input array (nums) in-place and communicates the length of the resultant array ($k$) via the return value.
Given two strings, $\text{haystack}$ of length $n$ and $\text{needle}$ of length $m\leq n$, compute the index into $\text{haystack}$ at which the first occurrence of $\text{needle}$ arises. If $\text{needle}$ does not occur within $\text{haystack}$ at all, return some sentinel value (usually $-1$).
Note that this is essentially strstr(3).
int strStr(char* haystack, char* needle) {
if (needle == NULL || haystack == NULL) return -1;
if (strlen(haystack) < strlen(needle)) return -1;
size_t n = strlen(haystack);
size_t m = strlen(needle);
for (size_t i=0;i<n;i++) {
for (size_t j=0;j<m;j++) {
if (haystack[i+j] != needle[j]) {
break;
} else if (j + 1 == m) {
return i;
}
}
}
return -1;
}
Given a string, $S$, determine the length of the last word in $S$. A word is a maximally-long substring of $S$, $s'$, that is delimited by whitespace (or the start or end of $S$). Usually this problem is presented in such a way that the number of words in $S$, $w\left(S\right)>0$. This obviously bounds the length of $S$, $n>0$ also.
int lengthOfLastWord(char* s) {
if (s == NULL) return -1;
if (strlen(s) == 1) return 1;
unsigned int w = 0;
bool in_word = false;
for (size_t i=strlen(s)-1;i>0;i--) {
if (in_word) {
if (s[i] == ' ') {
in_word = false;
return w;
} else {
w++;
}
} else {
if (s[i] != ' ') {
in_word = true;
w++;
}
}
}
if (s[0] != ' ') return w + 1;
else return w;
}
Note: This is a Leetcode solution and, as such, exploits the provided guarantee that there is at least one word within s.
Given an integer, $N\in\mathbb{N}$, represented as a sequence of its decimal digits $\overline{N}=\left\langle d_1, d_2, \dots, d_k\right\rangle$, compute $N+1$ as its decimal sequence, $\overline{N+1}$.
The complexity in this problem arise from the potential for arithmetic overflow. This will impact our algorithm in two ways:
#define MAX_DIGIT 9
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* plusOne(int* digits, int digitsSize, int* returnSize) {
if (digits == NULL || returnSize == NULL) return NULL;
if (digitsSize == 0) return NULL;
int* res = calloc(digitsSize + 1, sizeof(int));
if (res == NULL) return NULL;
*returnSize = digitsSize + 1;
bool overflow = false;
size_t i = digitsSize - 1;
do {
if (i == digitsSize - 1) {
if (digits[i] == MAX_DIGIT) {
res[i+1] = 0;
overflow = true;
} else {
res[i+1] = digits[i] + 1;
}
} else {
if (overflow) {
if (digits[i] == MAX_DIGIT) {
res[i+1] = 0;
} else {
res[i+1] = digits[i] + 1;
overflow = false;
}
} else {
res[i+1] = digits[i];
}
}
i--;
} while (i != SIZE_MAX);
if (overflow) {
/* the entire addition overflowed so add the new MSD */
res[0] = 1;
return res;
}
else {
/* we preallocated above so clip the array (this is a leak lol) */
*returnSize -= 1;
return res + 1;
}
}
Given two binary numbers, $a$ and $b$, encoded as strings, return $a + b$ also encoded as a string.
char* addBinary(char* a, char* b) {
if (a == NULL || b == NULL) return NULL;
size_t len_a = strlen(a), len_b = strlen(b);
/* 1-bit case */
if (len_a == 1 && len_b == 1) {
if (a[0] == '1' && b[0] == '1') return "10";
else if (a[0] == '0' && b[0] == '0') return "0";
else return "1";
}
/* allocate result buffer */
size_t reslen = len_a > len_b ? len_a + 1 : len_b + 1;
char* res = calloc(reslen + 1, sizeof(char));
if (res == NULL) return NULL;
bool carry = false;
/* pad smaller number and normalise to LHS, RHS */
size_t smaller_len = len_a > len_b ? len_b : len_a;
size_t padding_digits = reslen - 1 - smaller_len;
char* rhs = calloc(padding_digits + smaller_len + 1, sizeof(char));
if (rhs == NULL) return NULL;
for (size_t i=0;i<padding_digits;i++) rhs[i] = '0';
char* to_pad = len_a > len_b ? b : a;
strncpy(rhs + padding_digits, to_pad, strlen(to_pad));
char* lhs = to_pad == b ? a : b;
assert(strlen(lhs) == strlen(rhs));
size_t i = reslen - 1;
while (true) {
if (i == 0) break;
if (lhs[i-1] == '1' && rhs[i-1] == '1') {
if (carry) {
res[i] = '1';
carry = true;
} else {
res[i] = '0';
carry = true;
}
} else if (lhs[i-1] == '0' && rhs[i-1] == '0') {
if (carry) {
res[i] = '1';
carry = false;
} else {
res[i] = '0';
carry = false;
}
} else {
if (carry) {
res[i] = '0';
carry = true;
} else {
res[i] = '1';
carry = false;
}
}
i--;
}
if (carry) res[0] = '1';
else res += 1;
free(rhs);
return res;
}
Given $x\in\mathbb{N}$ (where $0\in\mathbb{N}$!) compute $\left\lfloor\sqrt{x}\right\rfloor$. Do not make use of any builtin or standard library implementations of $\sqrt{x}$!
The naive approach is to check that $\forall k\in\mathbb{N}|k<x, k^2=x$:
int mySqrt(int x) {
if (x < 2) return x;
unsigned int glb = 1;
for (unsigned int i=1;i<(unsigned int)x;i++) {
if (i * i < (unsigned int)x) glb = i;
else if (i * i > (unsigned int)x) return glb;
else return i;
}
return 0; /* unreachable */
}
There is of course a fairly obvious improvement to this algorithm that exploits the trivially sorted nature of $\mathbb{N}$ to achieve a runtime that is asymptotically logarithmic in $x$.
int mySqrt(int x) {
if (x < 2) return x;
uint64_t lo = 1, hi = (uint64_t)x / 2, mid = 0, next = 0;
while (lo <= hi) {
mid = lo + (hi - lo) / 2;
if (mid <= x / mid) {
next = mid + 1;
if (next > x / next) return (int)mid;
lo = mid + 1;
} else hi = mid - 1;
}
return 0; /* unreachable */
}
The runtime here is $\mathcal{O}\left(\log{n}\right)$ due to the use of binary search.
A staircase has $n\in\mathbb{N}$ steps. How many distinct ways are there to climb the entire staircase by only taking either 1 or 2 steps at a time?
This problem is equivalent to computing the $n$th Fibonacci number.
The naive solution is to recurse on $n$ which is definitionally the Fibonacci sequence.
$$\boxed{\forall k\in\mathbb{N}|k>2, F\left(k\right)=F\left(k-2\right)+F\left(k-1\right)}$$
int climbStairs(int n) {
if (n <= 3) return n;
return climbStairs(n - 2) + climbStairs(n - 1);
}
This solution will fail near $n=26$ due to stack overflow. The iterative solution is:
int climbStairs(int n) {
int* seq = calloc(n + 1, sizeof(int));
if (seq == NULL) return 0;
seq[0] = 1, seq[1] = 1;
for(size_t i=2;i<=n;i++) seq[i] = seq[i-2] + seq[i-1];
int ans = seq[n];
free(seq);
return ans;
}
Given a sorted (in ascending order) linked list of integers, return a linked list containing no duplicates whilst preserving the sorted order.
Traverse the list linearly. At each node, loop until the given run of duplicates is of length one, then continue.
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL) return NULL;
if (head->next == NULL) return head;
struct ListNode* ptr = head;
while (ptr != NULL && ptr->next != NULL) {
while (ptr->next != NULL) {
if (ptr->val == ptr->next->val) ptr->next = ptr->next->next;
else break;
}
ptr = ptr->next;
}
return head;
}