No vex, been busy with life, as election dey go, seems like we will resume this thread

truthCoder:


Anytime you apply for any role this year, ask yourself this simple question?

Who is going to review my application?

You never know. You just never know.

I own you Andrew.

bros..can I talk to you in private please? Good morning

Tenrack:
bros..can I talk to you in private please? Good morning

truthcoder@protonmail.com

truthCoder:


truthcoder@protonmail.com

thanks boss

truthCoder:


truthcoder@protonmail.com

already sent you a mail sir.

Please can anyone come up with an optimized solution for solving this PS?

Design an algorithm to find all the common elements in two sorted lists of
numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output
should be 2, 5, 5.

Time complexity should be 0(n) or better
NB : am terrible with algos so any contribution would be highly appreciated

namikaze
truthcoder
qtguru
tensazangetsu20

richebony:
Please can anyone come up with an optimized solution for solving this PS?

Design an algorithm to find all the common elements in two sorted lists of
numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output
should be 2, 5, 5.

Time complexity should be 0(n) or better
NB : am terrible with algos so any contribution would be highly appreciated

namikaze
truthcoder
qtguru
tensazangetsu20

Have you tried using an Hashmap/Set?

For example:

from collections import Counter

def common_elements(A, B):
    res, map = [], Counter(A)
    for num in B:
        if map[num]:
            res.append(num)
            map[num] -= 1
    return res
    

def test():
    listA = [2, 5, 5, 5]
    listB = [2, 2, 3, 5, 5, 7]
    got = common_elements(listA, listB)
    want = [2, 5, 5]
    assert got == want, f'got {got} want {want}'
    
test()

namikaze:

Have you tried using an Hashmap/Set?

For example:

from collections import Counter

def common_elements(A, B):
    res, map = [], Counter(A)
    for num in B:
        if map[num]:
            res.append(num)
            map[num] -= 1
    return res
    

def test():
    listA = [2, 5, 5, 5]
    listB = [2, 2, 3, 5, 5, 7]
    got = common_elements(listA, listB)
    want = [2, 5, 5]
    assert got == want, f'got {got} want {want}'
    
test()

Thanks a lot man !!


function commonElements(first, second) {
const res = [];
const map = {};

for (let element of first) {
map[element] = (map[element] || 0) + 1;
}

for (element of second) {
if (map[element]) {
res.push(element);
map[element]--;
}
}
return res
}


Hope u don't mind my asking, but how many languages do you actually know because I have seen your code in golang, I once confused you with another handle ( decide )

richebony:



Thanks a lot man !!


function commonElements(first, second) {
const res = [];
const map = {};

for (let element of first) {
map[element] = (map[element] || 0) + 1;
}

for (element of second) {
if (map[element]) {
res.push(element);
map[element]--;
}
}
return res
}


Hope u don't mind my asking, but how many languages do you actually know because I have seen your code in golang, I once confused you with another handle ( decide )

I mostly use golang for my side projects, js(nodejs) because I gotta get a job , python for DSA . I also know Java, C and C++ but I don't use them anymore.

@qtguru

Hi!
Please, how do I join your class?

Ayrastarr:
@qtguru

Hi!
Please, how do I join your class?

Do you write PHP ?

Tobedated:
Well if someone is studying JavaScript and want to learn dsa he should check out codevolution on YouTube the guy is amazing teaches you all the basics you'll need


If you want to prepare for interview

Then I'll recommend Blind75 it's the holy grail of leetcode you'll find it and solutions at neetcode YouTube channel or neetcode.io

That's my own 5cent I have to offer good luck to all of us

please guide me on javascript

qtguru:


Do you write PHP ?

Still learning

Ayrastarr:


Still learning

that's enough I'll share the resources here and meeting for the next class

qtguru:


that's enough I'll share the resources here and meeting for the next class

Alright.

Thank you

Edipet:
please guide me on javascript

sorry boss me sef still dey learn am i'll recommend you check out a youtube video or a book on it

richebony:
Please can anyone come up with an optimized solution for solving this PS?

Design an algorithm to find all the common elements in two sorted lists of
numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output
should be 2, 5, 5.

Time complexity should be 0(n) or better
NB : am terrible with algos so any contribution would be highly appreciated

namikaze
truthcoder
qtguru
tensazangetsu20

The most efficient way to solve this is two pointers in O(n) time and O(k) space where k is the number of common elements. Using a set or hashmap might be O(n) time, but O(n) space so is less efficient.

Longest Palindromic Substring


Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Difficulty:

Medium

Textbook dynamic programming problem. The key is recognizing that for any palindrome s, adding the same letter to its start and end also gives a palindrome.

For instance, "aba" is a palindrome. Add "c" to it's beginning and end gives "cabac", which is also a palindrome.

Now, for the base case, every string of length 1 is a palindrome. Also, every string of length two with the same letters (i.e "bb" is also a palindrome.

Then, the recurrence is given two indices i and j in string s such that s[i] and s[j] contain the same letters, find the longest palindrome in the substring s[i + 1 : j - 1], then add 2 to the length of this longest palindrome to find the length of the longest palindrome in the substring s[0: n] where n is the size of string s.

In the case where s[i] != s[j], the longest palindrome must be from either increasing i or decreasing j. This is because picking i and j together does not form a palindrome, therefore we must make a choice to drop one.

Thus, the full recurrence relation becomes:

s[i:j] = 2 + s[i+1:j-1] if s[i] == s[j]
s[i:j] = max(s[i+1 : j], s[i : j-1] if s[i] != s[j]

Knowing the base case(s) and recurrence relation for a dp problem makes the code implementation trivial, so I will not bother to write it down here.

drDoom3:


The most efficient way to solve this is two pointers in O(n) time and O(k) space where k is the number of common elements. Using a set or hashmap might be O(n) time, but O(n) space so is less efficient.

In python:

def common_elements(arr1, arr2):
i, j = 0, 0 # pointers for arr1 and arr2 respectively
res = [] # result array

while i < len(arr1) and j < len(arr2):
# first skip all recurring values in both arrays
while i + 1 < len(arr1) and arr1[i] == arr1[i + 1]:
i += 1
while j + 1 < len(arr2) and arr2[j] == arr2[j + 1]:
j += 1

if arr1[i] == arr2[j]: # both are the same, so add to res
res.append(arr1[i])
i, j += 1
elif arr[i] < arr2[j]: # move i pointer
i += 1
else: # move j pointer
j += 1

return res

This should solve it with O(n) time and O(k) extra space where k is the size of res. We don't need a hashmap/set to store every single value in this case.