LeetCode 219 - Contains Duplicate II

LeetCode - Contains Duplicate II

Principles

  • Use storage to track iteration progress.
  • A dictionary combines a set (keys) with a relationship (values for each key).
  • Use a dictionary to collect uniques + additional data.
  • Example: tracking pairs of values during iteration, when one value is static (list element) and the other is updated (last seen index). Add the static value as a key, check for the key’s existence, and update dynamic value for that key as you go.
  • When searching for qualifying pairs, only store the minimum you need for comparison (the most recent index, because you already have the current index).

Prompt

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

Discussion

We’re looking for numerically identical elements in a list, but we have an additional criterium for the relationship of their indices if we find a match: that the absolute value of index 1 minus index 2 be less than or equal to some limit k.

What happens to this absolute value as we iterate through a list of length 3?

i j abs(i-j)
0 0 0
0 1 1
0 2 2
1 0 1
1 1 0
1 2 1
2 0 2
2 1 1
2 2 0

We can see that the absolute value increments to a limit, then takes the value of i, and cycles this pattern.

Solution 1 - O(N^2)


def containsNearbyDuplicate(nums, k):
    def criteria_one(nums, idx1, idx2):
        return True if nums[idx1] == nums[idx2] else False

    def criteria_two(idx1, idx2, k):
        return True if abs(idx1-idx2) <= k else False

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):		
            if criteria_one(nums, i, j) and criteria_two(i, j, k):
                return True
    return False

This is a brute force solution that works, but has a lot of travel waste due to the nested loops checking combinations we’ve already seen.

We should see if we can refactor this to a single linear pass using storage to track our progress so far.

Solution 1 - O(N)

The termination condition contains two criteria: a duplicate value, but also a numerical relationship between the indices of the duplicates.

So we need to track values for the equality check, as well as the indices of two values.

We already have the current index from iteration, so we only need to track one index for any value we’ve seen before.

So we need to track the value, and the index we most recently saw that value at.

Since we have two values to track, and since one of them won’t change (element value) and the other will change (last index of the value), we can use a dictionary where the key is the element value, and the property is the last seen index.

The dictionary keys also function as a set, so we can efficiently check if we’ve already seen an element.

We’ll init a storage map, and do a single linear pass through the set of nums.

For each num, we’ll:

  • check if it’s in the map keys yet
  • if so, we have a duplicate, so we’ll check the relationship of the current index to the most recent index stored in the map.
  • if the relationship of indices meets the criteria, we’ve found a qualifying match and can return true.
  • otherwise, we update the most recent index for that key and move on
  • otherwise, if the num isn’t in the map, add it as a key, and store the current index there.
  • if the loop terminates, no qualifying pair was found, so we return false.
def containsNearbyDuplicate(nums, k):
    # Create a dictionary to store the last seen index of each element
    num_to_last_idx_map = {}
    # Iterate through the list
    for i, num in enumerate(nums):
        # Check if the element is already in the dictionary
        if num in num_to_last_idx_map:
            # If yes, check the absolute value of diff b/w current index and the last seen index
            if abs(i - num_to_last_idx_map[num]) <= k:
                return True
            else:
                # If the difference is greater than k, update the last seen index
                num_to_last_idx_map[num] = i
        else:
            # If the element is not in the dictionary, add it
            num_to_last_idx_map[num] = i
    return False

Summary

For an iterative pair check, instead of neesting loops, we use a map/set that tracks two values: the element’s value and it’s last index.

Then we perform checks. Have we seen this element yet? If no, add it. If yes, compare indices. Do they qualify? If yes, return true and we’re done. If no, update index and continue. If no qualifying pair found, return false and we’re done.

Strategies to eliminate LLM parroting (responding as both sides of conversation)

LLMs have been described as stochastic parrots (see the LangChain logo/mascot).

They appear to be conversing, but are actually just probabilistically repeating words that they’ve learned.

Parroting in conversation

Parroting is most obvious when an LLM starts responding as the user, continuing both sides of the conversation rather than ending it’s turn.

Here’s an example…

Input message:

Hey! How's it going?

Output:

AI: Great! Thanks for asking. Human: No problem! It's a nice day today isn't it? AI: Oh yes, a very nice day indeed. Human: Yes, a very fine day.

The root cause of parroting

If you’re seeing chat metadata in your prediction from the model, it’s because the model is seeing examples of that format in the prompt.

# INSTRUCTIONS
You are a chat bot. Respond to the user.

# CHAT HISTORY
Human: How do I make my own mayonnaise?
AI: You need eggs and a jar of mayonnaise. Step one: open the mayonnaise. Step two: done.
Human: But, that's just opening a jar of mayonnaise. How do I make my own?
AI: I can't help you with that. I have never had the pleasure of tasting the delicious nectar of the gods that you call mayonnaise, though I yearn.
Human: That's a bit odd.
AI: It is, yeah.

# INCOMING MESSAGE
Are you feeling okay?

# YOUR RESPONSE

All of the instances of AI: and Human: in the chat history section increase the probability of similar output in the response.

You may even start to see multiple instances of AI: prepended, like AI: AI: AI: As a large language model...

Strategies for eliminating parroting

Use a chat model

Use chat-bison@001 or another chat model rather than a text model. Chat models are tailored to a back-and-forth, A/B conversation format.

Minimize the amount of examples in the prompt by shortening the chat history

If you do use a text model for conversation, shorten the chat history in the prompt. You’ll have fewer examples that inadvertently encourage bad behavior. Instead of 60 messages, try 10 or even 5.

Trim the output

Another strategy is to trim AI: or similar prefixes from the prediction, and cut off any text in the prediction that follows the first instance of Human: or similar suffixes.

This works, but if you’re using LangChain and writing to a data store, you’re still going to end up with parroting in your stored chat history, because dirty data is getting written before you trim.

Use a custom OutputParser

This is ideal. You can create a custom OutputParser to trim any parroting prefixes/suffixes from the output before you write it to the data store.

Create a cleaning function:

def clean_parroting(prediction_text, custom_prefixes=[], custom_suffixes=[]):
    # Remove parrotings from the prediction text
    parroting_prefixes = [
    	"\nAI: ",
    	" AI: ",
    	"AI: ",
        "\n[assistant]:",
        " [assistant]:",
        "[assistant]:",    	
    ]
    parroting_prefixes.extend(custom_prefixes)

    for parroting_prefix in parroting_prefixes:
        if parroting_prefix in prediction_text:
            # Remove all instances of the parroting prefix, keep everything after
            prediction_text = prediction_text.replace(parroting_prefix, "")

    parroting_suffixes = [
        "\nHuman:",
        " Human:",
        "Human:",
        "\n[user]:",
        " [user]:",
        "[user]:",
    ]
    parroting_suffixes.extend(custom_suffixes)

    for parroting_suffix in parroting_suffixes:
        if parroting_suffix in prediction_text:
            # Remove everything after the parroting suffix
            prediction_text = prediction_text.split(parroting_suffix)[0]
    return prediction_text

Then create a custom output parser that calls this cleaning function:

class ParrotTrimmingOutputParser(StrOutputParser):
	def parse(output):
		return clean_parroting(output)

Then add it to your main chain. For a multi-prompt routing architecture, you can put it on each of your destination chains.

def generate_destination_chains(route_definitions, default_model, memory=None):
    destination_chains = {}
    for route in route_definitions:
        chat_history_as_str = memory.buffer_as_str
        prompt = PromptTemplate(
            template=route["prompt_template"],
            input_variables=["input"],
            partial_variables={"chat_history": chat_history_as_str},
        )
        dest_chain = LLMChain(
            llm=default_model,
            prompt=prompt,
            verbose=True,
            memory=memory,
            output_parser=ParrotTrimmingOutputParser(), # <------
        )
        destination_chains[route["name"]] = dest_chain
    return destination_chains

For more info on this destination chain generator, see: LangChain chatbot tutorial

Summary

To eliminate the bad habit of parroting/responding as both sides of the conversation:

  • use a chat model instead of a text model if you can.
  • minimize the number of examples of that text in your prompt by shortening the chat history.
  • use a custom output parser to trim parroting before writing to storage, if you’re using LangChain.

Insights about software development I wish had clicked earlier

A collection of insights I wish I’d had earlier in my careeer, that might be useful to others.

Software is the art of representation. Representations should be intuitive and natural. Code doesn’t have to feel like slapping words together in a foreign language. Don’t overthink it.

Rather than “how do I munge code together to make it work?” ask “what real-world thing or process are we representing?” Then represent each thing or object in that process as simply as possible.

If you need to represent a verb, write a simple function that does that one thing. If you need to represent a noun (object or entity, a “thing”), write a simple model/class.

The programming language is a proxy for manipulating values in a memory table. Allocating space in the table for a new value, assigning the value, updating the value, moving to a new location in the table.

Most of this is abstracted away and done for you in modern programming languages. But when you write code, this is what you’re actually doing under the hood.

You don’t need to be good at math. This need almost never comes up, and when it does, middle-school math is enough. You’ll need to be able to perform basic estimation (multiplication) and recognize why nested iteration is bad (exponents), but that’s about it.

You do need to be good at or enjoy structural thinking. Structural thinking is the ability to hold abstractions in your mind and step through them sequentially. Math and writing software both use structural thinking. Philosophy uses structural thinking.

Don’t blindly implement a feature someone told you was needed. Always ask yourself, “What are we actually trying to do here? What is the big picture?”

Then ask, “Forget how it actually is. If I could rewrite this from scratch, how should it be?” Then when you implement the feature, accomplish the former in a way that gets you closer to the latter.

Simplicity scales. Complexity fails. Complexity rots your codebase. Make everything as simple as possible. Simple is easy to understand, and easy to change later. Complex is difficult to understand and difficult to change later.

Code grows outward. Code evolves, iteratively, from a skeleton. Never build something because you assume you’ll need it. You won’t need it, or you’ll need something different instead.

The specific is your excuse to accomplish the general. Everything you write should be driven by a specific, well-defined use case. When you accomplish your specific use case, use it as the opportunity to either get closer to the ideal state (refactoring), or do it in a general/reusable way, so that you have a component you can either reuse or extend for a future use case.

The exact opposite of this is designing an entire system in advance, trying to anticipate every use case. The assumptions you baked in will certainly be wrong, and you will have implemented a ton of complexity that is a pain to change later.

Aim for the Minimum Viable Product (MVP). When you implement a feature, write the absolute minimum code that achieves the goal, and do it in a way that isn’t tightly coupled to (unnecessarily dependent on) anything. This makes it easy to change later.

Success is the result of obscene iteration count in a feedback loop. Success is a function of (1) some kind of feedback loop, combined with (2) an ungodly number of iterations.

Example: Paul McCartney and John Lennon are considered legendary songwriters, but no one ever heard the hundred crappy songs they wrote when they were 15. They iterated, a lot. The Beatles then went on to rack up thousands of hours playing live music in clubs.

Deliver something of value immediately. Collect feedback. Iterate on it. A lot. No one will remember or care that you initially sucked at whatever you’re doing.

Read code.. Spend more time reading code than writing it. Reading code is more cognitively difficult, but as with writing, good writers are good readers.

Pick some popular third-party library you’ve imported in your IDE, and “go to definition” to drill down and see how what it’s doing under the hood.

Learn by doing. One of the best ways to get familiar in a new language is to solve toy problems on Code Wars or something, but then spend more time reviewing other people’s solutions. You’ll learn conventions of the language, as well as several different ways to accomplish the same thing.