打卡战拖：E6/L6 级别大牛再次刷题出战全记录

几天没来签到。但是刷题没停！盗墓也没停。不过要加大力度！

LIS 题 如何在实现O(n logn)的同时不能重建LIS

Intuition

Approach

The O(n log n) solution for finding the length of the longest increasing subsequence (LIS) in an array involves a combination of dynamic programming and binary search. The key idea here is to maintain an array that stores the smallest possible tail element for subsequences of different lengths. Here's how it works:

Initialization: Create an array tails to store the last element of the increasing subsequences. Initially, it is empty.
Iterate Through the Array: For each element num in the input array nums, do the following:
If num is larger than all elements in tails, append it to tails. This extends the longest subsequence found so far.
Otherwise, find the position of the smallest element in tails that is greater than or equal to num (using binary search) and replace it with num. This step ensures that the subsequence remains increasing and updates it to have the smallest possible elements, which allows for longer subsequences in the future.
Length of LIS: The length of the longest increasing subsequence is the size of the tails array after processing all elements.

The problem/question: How to rebuild the LIS List?

Below code is an extension of the O(n log n) algorithm for finding the length of the Longest Increasing Subsequence (LIS), with the additional feature of tracking the predecessor of each element that contributes to the final LIS. This tracking allows us to reconstruct the actual LIS, not just calculate its length

updating tails and result_dct:

If idx equals the length of tails, it means num is larger than all elements in tails. So, append num to tails. In result_dct, map num to the last element in tails (or float('inf') if tails is empty), indicating that num extends the longest subsequence found so far.
If idx is less than the length of tails, it means num should replace the current element at tails[idx]. In result_dct, map num to tails[idx-1], indicating that the predecessor of num in the subsequence is tails[idx-1].

Reconstructing the LIS:

After processing all elements, we reconstruct the LIS in reverse order, starting from the last element in tails and tracing back through the predecessors recorded in result_dct.
The reconstructed LIS is stored in result, which is then printed in reverse to show the LIS in the correct order.

Complexity

Time complexity:
O(nlog(n))O(n log (n))O(nlog(n))
Code

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        result_dct = {}
        tails = []
        for num in nums:
            idx = bisect_left(tails, num)
            if idx == len(tails):
                result_dct[num] = tails[-1] if tails else float('inf')
                tails.append(num)
            else:
                tails[idx] = num
                result_dct[num] = tails[idx-1] if (idx-1) >= 0 else float('inf')
        result = []
        tail = tails[-1]
        while tail != float('inf'):
            result.append(tail)
            tail = result_dct[tail]
        print(result[::-1])
        return len(tails)

昨天有个小公司的面试。
通过这次练习，结合与chatGPT的交谈，
我总结出以下几条：
Tech Leader Persona: The importance of speaking like a tech leader. This means showcasing confidence, depth of knowledge, and vision. Speak about technology not just as a user but as a strategist who understands its impact and future potential.
Project Ownership: Emphasize my involvement in projects by discussing the challenges faced, how I addressed them, and the outcomes. This shows leadership and problem-solving skills.
Deep Dives into Projects: Don't hesitate to go into detail about specific projects. This demonstrates my technical competence and my ability to engage deeply with my work.
Coding Questions: My approach to coding questions is key. For BFS, for instance, demonstrating an in-depth understanding and offering enhanced solutions (like considering time and space complexity) is vital. With tougher questions, maintain composure, think out loud, and methodically break down the problem. This shows not just technical skill but also how I handle pressure.
Curiosity and Relevance: My question about how the company uses large-language models was excellent. It shows thinking about the practical applications of technology in a business context, which is a valuable perspective.
Communication Skills: Throughout, remember that effective communication is critical. It’s not just what I know, but how I convey it. Make my explanations clear, structured, and accessible.
These pointers should help me reflect on my performance and prepare even better for future interviews. Remember, each interview is a learning experience.

奇点将至。大部分人都可能会被永久落下，但在真正被落下之前，还有几件事情可以做：
1.拥抱变化，包括随时随地深度使用chatGPT
2.迎接变化，继续研习和实践大语言模型、多模态等最新最前沿技术
3.顺应变化，等人工智能的奇点真正到来的那一天，工作都给机器去做了，人类还做什么了？无非就是运动、娱乐、社交和享受生活了。长远来看，最难发展的就是有效的社交和运动了，何不从现在做起？a) 和家人朋友保持良好的关系，b)积极运动。

今天签到。继续刷题。
今天的心得（或者说flag）一个月刷一家公司的面试。直到找到那匹配的马。

签到。
刷题的与斯坦福系统地学习人工智能课程的对比。
刷题可能是没有课程的压力，一个星期花的时候不会多于20小时？
系统学习有作业和考试做项目的压力，每周不得不花多于20小时。系统学习还有证书，放到简历里，成为敲门砖。
刷题完了之后，还要刷面试，也要花时间针对有兴趣的公司准备

今天继续刷题。

继续刷题！

继续战拖。要去更新一下八股文。