Tag: writing

  • Algorithms Flowchart for coding interviews

    Here’s a practical decision flowchart you can use during interviews and problem solving:

    START

      |

      v

    Can the problem be solved greedily by making

    the best local choice at each step?

      |

      +– YES –> GREEDY ALGORITHM

      |

      +– NO –>

                  |

                  v

    Does the problem ask for:

    – All possible solutions?

    – Any valid solution?

    – Enumerating combinations/permutations/subsets?

    – Constraint satisfaction?

                  |

                  +– YES –>

                  |          |

                  |          v

                  |     Can you prune invalid

                  |     partial solutions early?

                  |          |

                  |          +– YES –> BACKTRACKING

                  |          |

                  |          +– NO –> BRUTE FORCE

                  |

                  +– NO –>

                              |

                              v

    Does the problem have:

    1. Optimal substructure?

    2. Overlapping subproblems?

                              |

                              +– YES –>

                              |          |

                              |          v

                              |     Need optimal value,

                              |     counting, or minimum/

                              |     maximum answer?

                              |          |

                              |          +– YES –> DYNAMIC PROGRAMMING

                              |

                              +– NO –>

                                          |

                                          v

    Can it be modeled as a graph

    (states/nodes + transitions)?

                                          |

                                          +– YES –>

                                          |          |

                                          |          +– Shortest path –> BFS/Dijkstra

                                          |          |

                                          |          +– Reachability –> BFS/DFS

                                          |          |

                                          |          +– DAG ordering –> Topological Sort

                                          |

                                          +– NO –>

                                                      |

                                                      v

    Is it primarily about searching

    in a sorted/monotonic space?

                                                      |

                                                      +– YES –> BINARY SEARCH

                                                      |

                                                      +– NO –>

                                                                  |

                                                                  v

    Check specialized techniques:

    – Divide & Conquer

    – Two Pointers

    – Sliding Window

    – Heap/Priority Queue

    – Union-Find

    – Segment Tree

    – Trie

    – Mathematical/Bit Manipulation

    Quick Rule of Thumb

    If you see…Use
    Generate all combinations/permutationsBacktracking
    Optimize (min/max), count ways, repeated statesDynamic Programming
    Best local choice always worksGreedy
    State transitions on nodesGraph Algorithms
    Sorted/monotonic answer spaceBinary Search
    Subarray/substring with contiguous windowSliding Window
    Split into independent halvesDivide & Conquer

    Backtracking vs Dynamic Programming

    Need to explore choices?

           |

           +– No repeated states –> BACKTRACKING

           |

           +– Same state reached multiple times –>

                  DYNAMIC PROGRAMMING

    Examples:

    • N-Queens → Backtracking
    • Sudoku → Backtracking
    • Subset Sum (decision) → Backtracking or DP
    • Knapsack → DP
    • Coin Change → DP
    • Longest Common Subsequence → DP
    • Generate Parentheses → Backtracking
    • Traveling Salesman → DP + Bitmasking (or Backtracking for small inputs)
  • Pytorch implementation of paper: Convolutional Sequence to Sequence Learning

    The paper “Convolutional Sequence to Sequence Learning” (Gehring et al., 2017) by Facebook AI Research (FAIR) was a landmark shift in NMT. Unlike LSTMs or GRUs, which are inherently sequential, this model uses Convolutional Neural Networks (CNNs).

    Because CNNs can be computed in parallel, this architecture is significantly faster to train than RNNs. It also uses Gated Linear Units (GLU) and a sophisticated Position Embedding system to maintain word order.

    1. Position Embeddings

    Since CNNs have no natural concept of “time” or “order,” we must explicitly add positional information to the word embeddings.

    Python

    import torch
    import torch.nn as nn
    import torch.nn.functional as F
    
    class Encoder(nn.Module):
        def __init__(self, input_dim, emb_dim, hid_dim, n_layers, kernel_size, dropout, device, max_length=100):
            super().__init__()
            self.device = device
            self.scale = torch.sqrt(torch.FloatTensor([0.5])).to(device)
            
            self.tok_embedding = nn.Embedding(input_dim, emb_dim)
            self.pos_embedding = nn.Embedding(max_length, emb_dim)
            
            # Linear layer to map embedding dim to hidden dim
            self.emb2hid = nn.Linear(emb_dim, hid_dim)
            self.hid2emb = nn.Linear(hid_dim, emb_dim)
            
            # Convolutional blocks
            self.convs = nn.ModuleList([nn.Conv1d(in_channels=hid_dim, 
                                                  out_channels=2 * hid_dim, 
                                                  kernel_size=kernel_size, 
                                                  padding=(kernel_size - 1) // 2) 
                                        for _ in range(n_layers)])
            self.dropout = nn.Dropout(dropout)
    
        def forward(self, src):
            # src: [batch_size, src_len]
            batch_size = src.shape[0]
            src_len = src.shape[1]
            
            # Create position tensor
            pos = torch.arange(0, src_len).unsqueeze(0).repeat(batch_size, 1).to(self.device)
            
            # Combined embedding
            e = self.dropout(self.tok_embedding(src) + self.pos_embedding(pos))
            
            # Element-wise scaling as per paper
            conv_input = self.emb2hid(e).permute(0, 2, 1) 
            
            for conv in self.convs:
                # Residual connection
                convolved = conv(self.dropout(conv_input))
                
                # Gated Linear Unit (GLU) activation
                # Splits the 2*hid_dim channels into two, applies sigmoid to one
                convolved = F.glu(convolved, dim=1)
                
                # Add residual and scale
                conv_input = (conv_input + convolved) * self.scale
                
            # Extract combined and element-wise representations
            combined = self.hid2emb(conv_input.permute(0, 2, 1))
            return conv_input, combined
    
    

    2. The Gated Linear Unit (GLU)

    The paper uses GLUs instead of ReLU or Tanh. A GLU takes a vector $A$ and $B$ (split from the convolution output) and computes $A \otimes \sigma(B)$. This allows the network to control which information flows through the hierarchy.

    3. The Decoder with Multi-Step Attention

    The decoder uses a similar CNN structure but includes an attention mechanism in every layer. It looks at the encoder’s state to decide which source words are relevant.

    Python

    class Decoder(nn.Module):
        def __init__(self, output_dim, emb_dim, hid_dim, n_layers, kernel_size, dropout, trg_pad_idx, device, max_length=100):
            super().__init__()
            self.kernel_size = kernel_size
            self.trg_pad_idx = trg_pad_idx
            self.device = device
            self.scale = torch.sqrt(torch.FloatTensor([0.5])).to(device)
            
            self.tok_embedding = nn.Embedding(output_dim, emb_dim)
            self.pos_embedding = nn.Embedding(max_length, emb_dim)
            
            self.emb2hid = nn.Linear(emb_dim, hid_dim)
            self.hid2emb = nn.Linear(hid_dim, emb_dim)
            self.attn_hid2emb = nn.Linear(hid_dim, emb_dim)
            self.fc_out = nn.Linear(emb_dim, output_dim)
            
            self.convs = nn.ModuleList([nn.Conv1d(hid_dim, 2 * hid_dim, kernel_size, padding=kernel_size - 1) 
                                        for _ in range(n_layers)])
            self.dropout = nn.Dropout(dropout)
    
        def calculate_attention(self, embedded, convolved, encoder_convolved, encoder_combined):
            # convolved: [batch_size, hid_dim, trg_len]
            # encoder_convolved: [batch_size, hid_dim, src_len]
            
            # 1. Map convolved back to embedding space
            convolved_emb = self.attn_hid2emb(convolved.permute(0, 2, 1))
            
            # 2. Add current target embedding (Residual)
            query = (convolved_emb + embedded) * self.scale
            
            # 3. Dot product attention with encoder_convolved
            energy = torch.matmul(query, encoder_convolved.permute(0, 2, 1))
            attention = F.softmax(energy, dim=2)
            
            # 4. Weighted sum of encoder_combined
            weighted = torch.matmul(attention, encoder_combined)
            
            # 5. Map back to hid_dim
            return self.emb2hid(weighted).permute(0, 2, 1), attention
    
        def forward(self, trg, encoder_convolved, encoder_combined):
            # trg: [batch_size, trg_len]
            batch_size = trg.shape[0]
            trg_len = trg.shape[1]
            
            pos = torch.arange(0, trg_len).unsqueeze(0).repeat(batch_size, 1).to(self.device)
            embedded = self.dropout(self.tok_embedding(trg) + self.pos_embedding(pos))
            
            conv_input = self.emb2hid(embedded).permute(0, 2, 1)
            
            for conv in self.convs:
                # Casual Padding: ensure the conv doesn't "see" the future
                padding = torch.zeros(batch_size, conv_input.shape[1], self.kernel_size - 1).to(self.device)
                padded_input = torch.cat((padding, conv_input), dim=2)
                
                convolved = conv(self.dropout(padded_input))
                convolved = F.glu(convolved[:, :, :conv_input.shape[2] + self.kernel_size - 1], dim=1)
                
                # Multi-step Attention
                attn_weighted, _ = self.calculate_attention(embedded, convolved, encoder_convolved, encoder_combined)
                
                # Residual + Attention + Scale
                convolved = (convolved + attn_weighted) * self.scale
                conv_input = (conv_input + convolved) * self.scale
                
            output = self.fc_out(self.hid2emb(conv_input.permute(0, 2, 1)))
            return output
    
    

    Key Takeaways from the Paper

    1. Parallelism: Unlike LSTMs, the entire source sentence is processed at once through the convolutional layers.
    2. Causal Convolutions: In the decoder, we use specific padding to ensure that the prediction for word $t$ only depends on words $1 \dots t-1$.
    3. Multi-Step Attention: Applying attention at every layer allows the model to refine its “focus” as it goes deeper into the architecture.
    4. Deep Residuals: Because the network is deep, residual connections and the $\sqrt{0.5}$ scaling factor are critical for stable training.

    This architecture served as the bridge between RNN-based translation and the Transformer (Attention is All You Need), which would arrive just a few months later.

  • Pytorch implementation of paper: Bidirectional LSTMs (2005): Alex Graves and Schmidhuber published “Framewise Phoneme Classification with Bidirectional LSTM,” which allowed the model to look at both the past and the future context (very useful for speech and text).

    The 2005 paper by Alex Graves and Jürgen Schmidhuber was a major milestone for sequence labeling, particularly in speech recognition (phoneme classification). While bidirectional RNNs existed since 1997, Graves and Schmidhuber combined them with the LSTM‘s ability to handle long-term dependencies.

    The core idea is to process the input sequence using two separate hidden layers—one moving forward in time and one moving backward—and then concatenating their outputs at each time step.

    1. The Bidirectional Logic

    For any given time step $t$, the model has access to:

    1. Past context: Via the forward layer $\overrightarrow{h}_t$.
    2. Future context: Via the backward layer $\overleftarrow{h}_t$.

    The final representation for that time step is typically the concatenation: $h_t = [\overrightarrow{h}_t ; \overleftarrow{h}_t]$.


    2. PyTorch Implementation

    While PyTorch provides a bidirectional=True flag in its standard nn.LSTM, here is how you build it from the ground up using the LSTM cells we’ve discussed to understand the data flow.

    Python

    import torch
    import torch.nn as nn
    
    class BidirectionalLSTM(nn.Module):
        def __init__(self, input_size, hidden_size, output_size):
            super(BidirectionalLSTM, self).__init__()
            self.hidden_size = hidden_size
            
            # Two independent LSTM cells
            self.forward_cell = nn.LSTMCell(input_size, hidden_size)
            self.backward_cell = nn.LSTMCell(input_size, hidden_size)
            
            # The output layer takes the concatenated hidden states (2 * hidden_size)
            self.fc = nn.Linear(hidden_size * 2, output_size)
    
        def forward(self, x):
            # x shape: [batch_size, seq_len, input_size]
            batch_size, seq_len, _ = x.size()
            device = x.device
            
            # 1. Initialize states for both directions
            h_f = torch.zeros(batch_size, self.hidden_size).to(device)
            c_f = torch.zeros(batch_size, self.hidden_size).to(device)
            h_b = torch.zeros(batch_size, self.hidden_size).to(device)
            c_b = torch.zeros(batch_size, self.hidden_size).to(device)
            
            # Lists to store hidden states for each time step
            forward_states = [None] * seq_len
            backward_states = [None] * seq_len
            
            # 2. Forward Pass
            for t in range(seq_len):
                h_f, c_f = self.forward_cell(x[:, t, :], (h_f, c_f))
                forward_states[t] = h_f
                
            # 3. Backward Pass
            for t in reversed(range(seq_len)):
                h_b, c_b = self.backward_cell(x[:, t, :], (h_b, c_b))
                backward_states[t] = h_b
                
            # 4. Concatenation & Output
            # Combine [forward_t, backward_t] for every t
            combined_outputs = []
            for f, b in zip(forward_states, backward_states):
                combined_outputs.append(torch.cat((f, b), dim=1))
                
            # Stack to shape: [seq_len, batch_size, hidden_size * 2]
            out = torch.stack(combined_outputs)
            
            # 5. Framewise Classification (as per the paper)
            # Apply the linear layer to every time step
            logits = self.fc(out)
            
            return logits # [seq_len, batch_size, output_size]
    
    

    3. Why this was a breakthrough for Speech

    In speech recognition (phoneme classification), the sound you are hearing now is often disambiguated by the sound that comes immediately after it.

    • Standard LSTM: Only knows what has been said so far. It has to “guess” until the next phoneme arrives.
    • Bidirectional LSTM: Can “wait” to see the entire utterance before deciding what the phoneme at $t=5$ was, using context from $t=6, 7, 8…$

    4. Key Implementation Nuance: Padding

    When using bidirectional models on mini-batches of varying lengths, you must be careful with padding. If you don’t use pack_padded_sequence, the “backward” layer will start by processing a bunch of zero-padding tokens, which can corrupt the initial hidden state for the actual data.