20 Jan, 2023 Pramp discussion

Problem to ask

H-Tree Construction

An H-tree is a geometric shape that consists of a repeating pattern resembles the letter “H”.

It can be constructed by starting with a line segment of arbitrary length, drawing two segments of the same length at right angles to the first through its endpoints, and continuing in the same vein, reducing (dividing) the length of the line segments drawn at each stage by √2.

Here are some examples of H-trees at different levels of depth:

depth = 1

depth = 2

depth = 3

Problem

RAN SUCCESSFULLY IN FIRST GO.

/**
- both arrays are sorted
- bigger array length iteration
- hashmap of smaller array- search O(1)
- tc: creation of hashmap from array + iterating through bigger array O(M+N)
- sc: N for hashmap created + (M-N)
**/
function findDuplicates(arr1, arr2) {
  const arr1_len = arr1.length;
  const arr2_len = arr2.length;
  // which array is bigger? It doesn't matter for now
  const arr_val_map = new Map();
  for (let i = 0; i < arr1_len; i++) {
    arr_val_map.set(arr1[i], 0); // frequency addition required?
  }
  
  const duplicate_elements = [];
  for (let j = 0; j < arr2_len; j++) {
    const cur_ele = arr2[j];
    if (arr_val_map.has(cur_ele)) {
      duplicate_elements.push(cur_ele);
    }
  }
  
  return duplicate_elements;
}
 
//const arr1 = [1, 2, 3, 5, 6, 7];
//const arr2 = [3, 6, 7, 8, 20];
//console.log(findDuplicates(arr1, arr2));

working_codetwo_pointer_approach

function duplicateWithTwoPointer(arr1, arr2) {
	const arr1_len = arr1.length;
	const arr2_len = arr2.length;
	const bigger_arr = arr1_len > arr2_len ? arr1 : arr2;
	const smaller_arr = arr1_len > arr2_len ? arr2 : arr1;
	let first_pointer = 0;
	let second_pointer = 0;
	const result = [];
	for (let i = 0; i < bigger_arr.length; i++) {
		const firstEl = arr1[first_pointer];
		const secondEl = arr2[second_pointer];
		if (firstEl < secondEl) {
			first_pointer++;
		} else if (secondEl < firstEl) {
			second_pointer++;
		} else if (firstEl === secondEl) {
			result.push(firstEl);
			first_pointer++;
			second_pointer++;
		}
	}
	return result;
}
 
const arr1 = [1, 2, 3, 5, 6, 7];
const arr2 = [3, 6, 7, 8, 20];
console.log(duplicateWithTwoPointer(arr1, arr2));