Jan 9 - Daily Programming Diary

12:30

Excited for the Crio event today. I have no idea what to expect and building a portfolio is probably the last thing that I want to do right now. Just signed up for Adsense and it was tricky to modify the SEO component to integrate the script. Phew!

It's almost 13:30 and the new Leetcode challenge is about to be posted. Today's challenge is...drum roll please...Word Ladder

14:50

Wow, a graph question that took so much time. But I'm glad I was able to solve it. Pretty sure there could be a better approach but it was the best I could do. It really helped putting everything on a paper to get the idea of how the whole thing works.

Approach : Start from the beginWord and generate the possible conversions from that by changing a letter. So mad can become *ad, m*d, and ma*. Whatever of these words exist in the original list but we haven't visited, we put them in a queue. And do the same thing till we reach the endWord, incrementing the counter each time queue empties.

Copyword-ladder.cpp: copy code to clipboard
1vector<string> getNeighbors(string str) {
2    vector<string> v;
3    for (int i = 0; i < str.length(); i++) {
4        char org = str[i];
5        for (int j = 0; j < 26; j++) {
6            str[i] = j + 'a';
7            v.push_back(str);
8        }
9        str[i] = org;
10    }
11    return v;
12}
13
14int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
15    queue<string> q;                                           // Keep track of neighbors
16    unordered_set<string> s(wordList.begin(), wordList.end()); // O(1)
17
18    if (s.find(endWord) == s.end()) return 0; // end word not in set
19
20    s.erase(beginWord); // same word twice? (Noop)
21    q.push(beginWord);  // Initial queue
22    int trans = 0;      // Level in BFS
23
24    while (!q.empty()) {
25        trans++;
26        int qSize = q.size(); // Initial queue size
27        for (int i = 0; i < qSize; i++) {
28            string currWord = q.front();
29            q.pop();          // Remove from queue (black)
30            if (currWord == endWord) return trans;
31            vector<string> v = getNeighbors(currWord);
32            for (int m = 0; m < v.size(); m++) {
33                if (s.find(v[m]) != s.end()) {  // If not exists
34                    s.erase(v[m]);  // Remove from set (white)
35                    q.push(v[m]);   // Add to queue (grey)
36                }
37            }
38        }
39    }
40    return 0; // If couldn't reach endWord
41}

The time complexity for O(26 * M^2 * N) where M is the length of each word, and N is the number of words. So asymptotically it is O(M^2 * N) and space complexity O(M * N) for the word set.

I am not sure I want to implement this code in Go. Yeah, maybe some other time.

17:30

Have been thinking about some open source contributions, but every time there's the same issue of not being able to find a project. So I thought I could use my <HideContent /> component and make it a standalone library with some cool features like preprocessing the input and encrypting the password with firebase or custom API.

19:30

Just attended the Crio Winter of Doing event. So what I understood from there is that there are some modules that need to be completed. The thing is that I already know a lot of that stuff but I have to go through all those modules if I want to process to stage 2 which is frustrating.

I started with the HTTP Module and they are teaching about reading request and response objects from Chrome Developer Tools. Then concepts about HTTP Methods (GET, POST, ...)

Will continue tomorrow.

22:30

Created some issues on GitHub in React repository and talked about setting up own server. Guess the downtime was a good thing! 😉
Still have to decide if we should use PostgreSQL or MongoDB, Node.js or nestjs. Always wanted to work on back-end. Yay!

Bye! Been a long time since I wrote like this.

EOD Checklist

• Go
• Leetcode January Challenge
• Raahee (Just attended the meeting)
• This blog