bephrem1 / interviewpen Goto Github PK

View Code? Open in Web Editor NEW

1.8K 1.8K 793.0 527 KB

Code samples for Back to Back SWE lessons (archive).

Home Page: https://interviewpen.com

Java 94.88% Python 5.12%

interviewpen's People

Contributors

Stargazers

Watchers

Forkers

path-to-learn victoto gouraharidas computerkraft flyfire leiwang8224 anandmcts1 learnwithjunie varunbehl26 lpshikhar pkmsoftpro ankit08015 yusefjmustafa sanyakathuria10 vineetpalan nancyzhong jintongxing zzyuting cosyboy zjwbupt dongzcc sarangan saiporuri92 nd6023 avinash2fly soudiptad99 mibrah42 yyyybzzzz archit1510130 dariogonzalezleegstra njtrojan amanrayat mithlesh-4257 harishav sagar0207 pherricoxide aasimkamal kouxudong kotak86 silavsale nayak11 jackywang1992 yogiprogram satinder147 navneet-nmk kelvinson adityarandive rajatk95 ankita19 venkateshreddypala xmonader caqtiml shuhaobai sahiljohari wpmapat abhipandey1 jsgalleguillos anandsoft wzli1214 vinaykpal ymn1k samnoon1971 francisknight ivanshastin arshiyapathan anupamsurbhi jeremy-yan-liu patil1695 mohki890 jlskent claytonsibanda acha241 nfs1310 mrsan22 prateekparihar abhinvsinh zhoujun0920 96malhar mansinit umangmathur92 huyducnguyensource dineshkumaark mohaksnghl mukeshkdangi dkp1903 shashwathkamath hlltarakci nathanzhu144 sssunwoo codegenesis bhardwaj-aman shrutiaggarwal99 zinalacina vathsal heciritoglu ravishnitp mvenuthy birth2507 rajiv3269 kirtibansal

interviewpen's Issues

Update declaration of "UndirectedGraphNode"

The updated declaration of class "UndirectedGraphNode" is as follows:

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

Bug in OnlineMedian.java

At line 58, the new number should be pushed into lowerHalf when higherHalf is empty.

Giving wrong answer for "875"

it seems correct but idk why it's giving wrong answer for input 875

Line 67 is == instead of !=

// Skip non-empty entries. They already have a value in them.
  if (board[row][col] == EMPTY_ENTRY) {
    return solveSudokuCell(row, col + 1, board);
  }

Sir, according to me you have made a typo error in writing the formula for g(n) in the inner loop, as the formula should be g(i)+=g(j-1)*g(n-j) but you have write g(i)+=g(j-i)*g(i-j), sir if I am wrong then please make me clear, else kindly edit the code
Thanks

Go from O(n) to O(1) in is_palindrome

Love your videos!

Right now your isPalindrome function is taking O(n) work to determine if a string is a palindrome. However, we don't need to do that because the function can be built recursively and pre-computed. In other words once you know that "bcedfcb" is not a palindrome, you don't need to take O(n) time for the sequence "abcedfcba" (since it's the same sequence with two letters outside.

I believe this change takes your big O complexity from O(n*2^n) to just O(2^n) since there are 2^n ways to partition a string of length n and its now doing constant time work in each partition (previously it was doing O(n) work). Essentially you have O(n^2) to precompute all palindromes and O(2^n) to calculate all partitions. O(n^2 + 2^n) -> O(2^N)

Basically I'm suggesting to use the isPalindrome function from this question: https://leetcode.com/problems/longest-palindromic-substring/solution/

Here is my code:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)

        # This precomputers all palindromes in O(n^2) time given total complexity O(n^2 + 2^n) = O(2^n)
        # Your solutions does n work  (instead of O(1) on each backtrace) making it O(n*2^n) in the worst case
        is_palindrome = [[None] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if i == j:
                    is_palindrome[i][j] = True
                elif i + 1 == j:
                    is_palindrome[i][j] = s[i] == s[j]
                else:
                    if s[i] != s[j]:
                        is_palindrome[i][j] = False
                    else:
                        is_palindrome[i][j] = is_palindrome[i + 1][j - 1]
        
        solutions = []
        def _split(path, start):
            if start == n:
                solutions.append(path[:])
                return
            
            for end in range(start, n):
                if is_palindrome[start][end]:
                    path.append(s[start:end+1])
                    _split(path, end + 1)
                    path.pop()
        
        _split([], 0)
        return solutions

Extra ']' in code is causing compile time error

https://github.com/bephrem1/backtobackswe/blob/713399f94bf48842cfdb9a9d23b1a154b3642f0c/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/changeMakingProblem2.java#L49

It should have been [j - currentCoinValue]

Videos Missing Code

Change the constructor

For https://github.com/bephrem1/backtobackswe/blob/master/Graphs/CloneAGraph/CloneAGraph.java#L57
Change the constructor to take the ArrayList of the newNode as the argument to the constructor along with val.

Not Needed for

https://github.com/bephrem1/backtobackswe/blob/2c66c302f266215876178ca5c72202925960d952/Sorting%2C%20Searching%2C%20%26%20Heaps/ImplementABinaryHeap/ImplementABinaryHeap.java#L191

return  index != 0;

Isn't it enough?

Bug in SearchALinkedListWithJumps

While boxed type Integer is stored in a heap, it is still immutable. You can see in the Integer class sources that the primitive value it wraps is declared as final here.

Another thing is that objects are indeed passed to methods as references, but that references are copied to a local variable (parameter) of a method.
So currentOrder += 1 is the same as currentOrder = currentOrder + 1, and JVM, in that case, unboxes currentOrder to a primitive value, performs addition and then boxes result into a new instance of Integer. Then the reference to this new object is assigned to currentOrder, overriding the initial value of it. But it held just a copy of a reference passed, so the original variable used as an argument remains the same, pointing to an old boxing object instance.

This can be observed from a simple example here or by using the following list to run the program:

ListNode a = new ListNode();
ListNode b = new ListNode();
ListNode c = new ListNode();
a.next = b;
b.next = c;
a.jump = c;

Result should be a:0 b:2 c:1, but it is a:0 b:1 c:1.

Graphs/cloneAGraph.java

Request to add UndirectedGraphNode definition.