Posts

Suppose, while traversing the array you encounter a 132 pattern that violates the non-decreasing property. Now you have 2 options to fix this anomaly. a=1, b=3, c=2 Either we decrease b and make it equal to c i.e.b=c=2. Or we increase c to make it equal to b i.e. c=b=3. I would argue that we should always try to decrease b. Since, it enables us to have lower last value i.e. c. It decreases the chance of next number in the sequence violating the non-decreasing property. ...

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 ...