coding interview implementations

Question 1

Write a ‘Two Sum’ solution in C.

Answer 1

int* twoSum(int* nums, int numsSize, int target) {\n for (int i = 0; i < numsSize; i++) {\n for (int j = i + 1; j < numsSize; j++) {\n if (nums[i] + nums[j] == target) {\n int* result = malloc(2 * sizeof(int));\n result[0] = i;\n result[1] = j;\n return result;\n }\n }\n }\n return NULL;\n}

This C implementation uses a nested loop to check each pair of elements.

Question 2

Write a ‘Two Sum’ solution in Python.

Answer 2

def two_sum(nums, target):\n lookup = {}\n for i, num in enumerate(nums):\n if target - num in lookup:\n return [lookup[target - num], i]\n lookup[num] = i\n return []

This Python implementation uses a dictionary for faster lookups.

Question 3

Write a ‘Two Sum’ solution in Ruby.

Answer 3

def two_sum(nums, target)\n lookup = {}\n nums.each_with_index do |num, i|\n complement = target - num\n return [lookup[complement], i] if lookup[complement]\n lookup[num] = i\n end\n nil\nend

This Ruby implementation uses a hash for storing and checking complements.

Question 4

How to reverse an integer in C?

Answer 4

int reverse(int x) {\n int rev = 0;\n while (x != 0) {\n int pop = x % 10;\n x /= 10;\n if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;\n if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;\n rev = rev * 10 + pop;\n }\n return rev;\n}

This C code handles overflow by checking the condition before each multiplication and addition.

Question 5

How to reverse an integer in Python?

Answer 5

def reverse(x):\n sign = [1,-1][x < 0]\n rst = sign * int(str(abs(x))[::-1])\n return rst if -(231)-1 < rst < 231 else 0

Python’s slicing is used for reversing the number, and overflow is handled.

Question 6

How to reverse an integer in Ruby?

Answer 6

def reverse(x)\n sign = x.negative? ? -1 : 1\n rev = x.abs.to_s.reverse.to_i * sign\n rev.bit_length > 31 ? 0 : rev\nend

Ruby’s string manipulation methods are used, and overflow is checked using bit_length.

Question 7

Implement a stack using arrays in C.

Answer 7

typedef struct {\n int top;\n int capacity;\n int* array;\n} Stack;\n\nStack* createStack(int capacity) {\n Stack* stack = (Stack) malloc(sizeof(Stack));\n stack->capacity = capacity;\n stack->top = -1;\n stack->array = (int) malloc(stack->capacity * sizeof(int));\n return stack;\n}\n\nvoid push(Stack* stack, int item) {\n if (stack->top == stack->capacity - 1) return;\n stack->array[++stack->top] = item;\n}\n\nint pop(Stack* stack) {\n if (stack->top == -1) return INT_MIN;\n return stack->array[stack->top–];\n}

This C implementation uses a struct to define the stack and its operations.

Question 8

Implement a stack using lists in Python.

Answer 8

class Stack:\n def __init__(self):\n self.items = []\n\n def push(self, item):\n self.items.append(item)\n\n def pop(self):\n return self.items.pop()\n\n def is_empty(self):\n return not self.items

Python’s built-in list structure and methods are used to implement stack operations.

Question 9

Implement a stack using arrays in Ruby.

Answer 9

class Stack\n def initialize\n @stack = []\n end\n\n def push(item)\n @stack.push(item)\n end\n\n def pop\n @stack.pop\n end\n\n def is_empty\n @stack.empty?\n end\nend

Ruby’s array is utilized to implement the stack with push and pop methods.

Question 10

Implement a Queue using arrays in C.

Answer 10

typedef struct {\n int front, rear, size;\n unsigned capacity;\n int* array;\n} Queue;\n\nQueue* createQueue(unsigned capacity) {\n Queue* queue = (Queue) malloc(sizeof(Queue));\n queue->capacity = capacity;\n queue->front = queue->size = 0;\n queue->rear = capacity - 1;\n queue->array = (int) malloc(queue->capacity * sizeof(int));\n return queue;\n}\n\nvoid enqueue(Queue* queue, int item) {\n if (queue->size == queue->capacity) return;\n queue->rear = (queue->rear + 1)%queue->capacity;\n queue->array[queue->rear] = item;\n queue->size = queue->size + 1;\n}\n\nint dequeue(Queue* queue) {\n if (queue->size == 0) return INT_MIN;\n int item = queue->array[queue->front];\n queue->front = (queue->front + 1)%queue->capacity;\n queue->size = queue->size - 1;\n return item;\n}

This C code demonstrates a circular queue implementation using arrays.

Question 11

Implement a Queue using lists in Python.

Answer 11

class Queue:\n def __init__(self):\n self.items = []\n\n def enqueue(self, item):\n self.items.insert(0, item)\n\n def dequeue(self):\n if self.is_empty():\n return None\n return self.items.pop()\n\n def is_empty(self):\n return len(self.items) == 0

Python’s list methods insert and pop are used for enqueue and dequeue operations, respectively.

Question 12

Implement a Queue using arrays in Ruby.

Answer 12

class Queue\n def initialize\n @queue = []\n end\n\n def enqueue(item)\n @queue.unshift(item)\n end\n\n def dequeue\n @queue.pop\n end\n\n def is_empty\n @queue.empty?\n end\nend

Ruby’s array methods unshift and pop are employed to add and remove elements from the queue.

Question 13

Write a function to perform a linear search in C.

Answer 13

int linearSearch(int arr[], int n, int x) {\n for (int i = 0; i < n; i++) {\n if (arr[i] == x)\n return i;\n }\n return -1;\n}

This C function iterates over the array to find the element, returning its index or -1 if not found.

Question 14

Write a function to perform a linear search in Python.

Answer 14

def linear_search(arr, x):\n for i in range(len(arr)):\n if arr[i] == x:\n return i\n return -1

The Python function uses a for loop to iterate over the list and find the target element.

Question 15

Write a function to perform a linear search in Ruby.

Answer 15

def linear_search(arr, x)\n arr.each_with_index do |item, index|\n return index if item == x\n end\n -1\nend

Ruby’s each_with_index is used for iterating over the array and checking each element.

Question 16

Implement a binary search algorithm in C.

Answer 16

int binarySearch(int arr[], int l, int r, int x) {\n while (l <= r) {\n int m = l + (r - l) / 2;\n if (arr[m] == x)\n return m;\n if (arr[m] < x)\n l = m + 1;\n else\n r = m - 1;\n }\n return -1;\n}

This C implementation uses a while loop for the binary search, adjusting the search range based on comparisons.

Question 17

Implement a binary search algorithm in Python.

Answer 17

def binary_search(arr, x):\n l, r = 0, len(arr) - 1\n while l <= r:\n mid = (l + r) // 2\n if arr[mid] == x:\n return mid\n elif arr[mid] < x:\n l = mid + 1\n else:\n r = mid - 1\n return -1

Python’s implementation uses integer division to find the middle element for comparisons.

Question 18

Implement a binary search algorithm in Ruby.

Answer 18

def binary_search(arr, x)\n l, r = 0, arr.length - 1\n while l <= r\n mid = (l + r) / 2\n return mid if arr[mid] == x\n arr[mid] < x ? l = mid + 1 : r = mid - 1\n end\n nil\nend

Ruby’s implementation uses simple arithmetic to halve the search range and conditional statements for comparison.