Posts

We build a simple Tri where each node’s value is the sum of all words in the Tri that have same prefix as current node. Let me explain with a simple example. Suppose, we have an empty Tri. Insert "apple" with value=3. While inserting a key, we shall increase values of all intermediate nodes. Here’s how to Tri looks like after insertion: Now let’s insert "app" with value=2. Please note that we shall increase the value of intermediate nodes while inserting app. Therefore, the first 3 nodes will have value=5. ...

We are given a number n. On the number line, there are infinite numbers on the right of n and left of n that are palindromes. The question is asking us to find a number that is a palindrome and has the minimum distance from n on the number line. We break the problem into 2 parts: find the next element on the number line after n that is a palindrome. find the previous element on the number line before n that is a palindrome. Suppose i and j are numbers such that i < n < j and i and j are both palindromes. And i and j are the nearest numbers to n on the number line We just find which of i and j is the nearer one to n on the number line and return it The simplest way of doing this is: ...

I use hcreate(), hdestroy() and hsearch() from C standard library for hashmap implementation. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #define _GNU_SOURCE #include <search.h> #include <errno.h> #define MAX_SIZE 1e4 #define KEY_SIZE 20 ENTRY* create_entry_set_number( int data ); bool dfs( struct TreeNode*, int ); bool findTarget(struct TreeNode* root, int k) { hcreate( MAX_SIZE ); const bool res = dfs( root, k ); hdestroy(); return res; } bool dfs( struct TreeNode* node, int target ) { if ( !node ) return false; const ENTRY* required = create_entry_set_number( target - node -> val ); const ENTRY* cur_node = create_entry_set_number( node -> val ); if ( hsearch( *required, FIND ) ) return true; else hsearch( *cur_node, ENTER ); return dfs( node -> left, target ) || dfs( node -> right, target ); } ENTRY* create_entry_set_number( int data ) { ENTRY* item = ( ENTRY* ) malloc( sizeof(ENTRY) ); if ( !item ) exit(-ENOMEM); *item = ( ENTRY ) { .key = NULL, .data = NULL }; item -> key = (char*) reallocarray( item->key, KEY_SIZE, sizeof(char) ); sprintf( item -> key, "%d", data ); return item; }

consider the word “catsdogcats”. We have the dictionary: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] We iterate over the word: catsdogcats and at each iteration, we ask if the prefix is contained in dictionary. If the prefix is in the dictionary, we recursively call the function on the remaining word (excluding matched prefix) is c in dictionary ? is ca in dictionary ? is cat in dictionary ? -> YES call( sdogcats ) –[1] Prefix cat matched so recursively call with sdogcats ...

Level order traversal traverse down the levels until we are 1 level above the level to be replaced. for each node in the level obtained above, set left and right node value to val, and the original leftSubtree and rightSubtree become left and right links of newly inserted left and right node respectively 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 function addOneRow( root: TreeNode|null, val: number, depth: number): TreeNode|null { if ( depth <= 1 ) { return new TreeNode( val, root, null ); } let que = [ root ]; for ( let d=1; que.length && d < depth-1; d++ ) { const LVL = que.length; for ( let j=0; j < LVL; j++ ) { const node = que.shift(); if ( node.left ) que.push( node.left ); if ( node.right ) que.push( node.right ); } } while ( que.length ) { const node = que.shift(), leftSubtree = node.left, rightSubtree = node.right; node.left = new TreeNode( val, leftSubtree, null ); node.right = new TreeNode( val, null, rightSubtree ); } return root; }; Time: $$ O(n) $$ Space: $$ O(n) $$ Recursive delegation The idea here is that if we need to update the dth level at node, then we need to update the (d-1)th level from node.left and node.right. ...