5. Juniper Networks

Role	Senior Software Engineer
Profile	C, C++, DPDK, Networks

5.1. Round 1

Date	2024-01-23T14:00:53+0530

/**
 * linked lists common node
 *
 * Leetcode: 160. Intersection of Two Linked Lists
 *
 * Tags: #linked-lists, #two-pointers, #easy
 *
 * list a: 1 -> 2 -> 3 -> 4
 * list b: 6 -> 3 -> 4
 *
 * cmn_node: 2
 *
 *  a   b
 *  -----
 *  1   2
 *  2   4
 *  5
 *    3 // <- find
 *    4
 */

typedef struct Node {
	stuct Node next;
	int data;
} List;

/* Time complexity: O(n^2) square */
List *cmn_node(List *ah, List *bh)
{
	List *a = ah;
	List *b = bh;

	while (a) {
		while (b) {
			if (a->next == b->next) return a->next;
			b = b->next;
		}
		a = a->next;
	}
	return NULL;
}

/* Time compelxity: O(n) linear */
List *cmn_node(List *ah, List *bh)
{
	List *a = ah;
	List *b = bh;

	List *m[1024];

	int i = 0;
	while (a) {
		m[i++] = a;
		a = a->next;
	}

	i = 0;
	while (b) {
		if (m[i++] == b) return m[i];
		b = b->next;
	}
	return NULL;
}

5.2. Round 2

Date	2024-01-24T12:00:42+0530

/**
 * Linked list
 *
 * Input:
 *
 * 0    1    2    3
 * a -> b -> c -> d
 *
 * start = 1, end = 2
 *
 * Output:
 *
 * 0    1    2    3
 * a -> c -> b -> d
 */

typedef struct Node {
	struct Node *next;
	int data;
} List;

List *rev_list(List *head, int start, int end)
{
	List *curr = head, *prev = NULL, *next = NULL;
	int i = 0;

	while (i++ < start) {
		prev = curr;
		curr = curr->next;
	}

	List *h1 = NULL, t1 = curr;

	while (curr && i++ < end) {
		next = curr->next;
		curr->next = h1;
		h1 = curr;
		curr = next;
	}

	prev->next = h1;
	t1->next = curr;
	return curr;
}

/**
 * Inverse bits
 *
 * Input  : num = 101101, start = 1, end = 3
 * Output : num = 100011
 *
 * a = 110, b = ~a;
 */

int inv_bits(int a, int start, int end)
{
	int b = a;
	int mask = 0, i = start;
	while (i++ < end) mask = 1 << i;
	int t = a & mask;
	t = ~t;
	b |= t;
	return b;
}

5.3. Round 3

Date	2024-01-24T14:00:42+0530

/**
 * sorted array, remove repeated numbers
 *
 * Input:  [1 2 2 3 3 3 4 4 4 4 5 5 5 5 5]
 * Output: [1 2 3 4 5 0 0 0 0 0 0 0 0 0 0]
 *
 * Input:  [1 2 2 3 3] N=5, [6, 2+5+5, 3+5+5, 0, 0]
 * Output: [1 2 3 0 0] N=5, [6-5, 2+5+5-5, 3+5+5, 0, 0]
 */

void remove_repeated(int a[].int size)
{
	// x ^ 0 = x
	// x ^ x = 0

	for (int i = 0; i < size; i++) {
		int id = a[i] % size;
		a[id] += size;
	}

	for (int i = 0; i < size; i++) {
		while (a[i] / size >= 2) a[i] -= size;
	}
}

int clear_bit(int a, int pos) { return (a & ~(1 << pos)); }

int get_bit_count(int a)
{
	// 1101
	int count = 0;
	while (a) {
		if (a & 1) count++;
		a = a >> 1;
	}
	return count;
}

typedef struct Node {
	int d1, d2;
	char c1, ch2;
} List;

sizeof(List);

#define get_st_mem_offset (st, mem)(&(st *)->mem)

5.4. Round 4

Date	2024-01-24T15:00:42+0530

/**
 * 2D dynamic array
 */

char **alloc_2d(int rows, int cols)
{
	char **matrix = (void *)malloc(rows);
	memset(matrix, 0, rows);
	if (!matrix) return NULL;

	for (int i = 0; i < rows; i++) {
		matrix[i] = (void *)malloc(cols);
		if (!matrix[i]) goto freecols;
	}

freecols:
	for (int i = 0; i < rows; i++) free(matrix[i]);

	return matrix;
}

/**
 * Delete duplicate single linked list unsorted elements
 *
 * Input:  [1, 2, 2, 3]
 * output: [1, 2, 3]
 */

typedef struct Node {
	struct Node *next;
	int data;
} List;

typedef struct map {
	int k, v;
} hash_map;

void del_dups(List *head)
{
	hash_map m[];
	List *curr = head;

	int i = 0;
	List *prev = head;
	while (curr->next) {
		m[i].k = curr->data;
		m[i].v++;
		prev = curr;
		if (m[i].v > 1) {
			List *t = curr->next;
			free(curr);
			curr = t;
		}
		curr = curr->next;
	}
}