Siddhant

building stuff | CSE'2028| dsa and ML | Gen ai

[Siddhant @Siddhant_code]

@Kcodess gupta ko 30 ki jagah 60 do toh woh maharaja mac bhi bana deta hai...#guptapaglu

[Siddhant @Siddhant_code]

@striver_79 "the interviewer will not be happy" is equally legendary

[Siddhant @Siddhant_code]

@niketrajdwivedi @cneuralnetwork thalairaj's salan is best ever ...but meghna altogether hits diff

[Siddhant @Siddhant_code]

@xaemio @takeUforward_ @striver_79 yeah... not in my wildest dream i would have thought of that approach

[Siddhant @Siddhant_code]

@ajay_2512x stalin sort

[Siddhant @Siddhant_code]

#SDESheetChallenge @takeUforward_ @striver_79

1.find the duplicate number(u cannot come up with the optimal approach if u see this ques for the first time)

one naive approach to solve this in O(nlogn) would be to sort and check every adjacent index for repeating values but the interviewer will not be happy

so the optimal approach (had to see the editorial ngl)

use the gods of linkedlist problem solving.. fast and slow pointers.... since every number lie in the range 1 to n two number would point on the same index.. and then visualise it as finding the start of loop in a linkedlist

2. finding a and b the repeating number and the missing one

first intuition is to hash this occurances can be noted down and boom interviewer will not be happy

optimal - make equations the actual sum - expected sum = X(repeating) - Y(missing) same when squared…now the x+y + x - y /2 gives a ; simultaneously a - val1 gives b ;

3. coutning inversions (most mindfuck question of this challenge until now)(star marked to revise again)

in case of a brute approach we just use a n^2 nested loop and count the inversions
optimal approach uses a merge sort method …basically a type of divide and conquer having two pointers and iteratively keep comparong them on the required conditions and merging halves

[Siddhant @Siddhant_code]

@pvitraw no 3 equal was easier tbh and div 4 has lot of cheaters ... 1102 submission in cyclic xor is insane... i guess it had 500 submissions in div 3

[Siddhant @Siddhant_code]

@rrrautela @takeUforward_ @striver_79 bfs hum sharminda hain 😭

[Siddhant @Siddhant_code]

@AdityaP92697804 @striver_79 @takeUforward_ bas jaa hi raha

[Siddhant @Siddhant_code]

#SDESheetChallenge @striver_79 @takeUforward_
day 3
1. merging sorted lists
a very brute approach would have been to use two pointer make a third array start iterating copying smaller or larger elements then copying it to the nums1 while we can also do the other way of specifying larger elements to end of nums1 using two pointers..

2.merge intervals

sort them and check if the extremes overlap if they do take the max

3.rotate array by 90

transpose and reverse every row

[Siddhant @Siddhant_code]

@AdityaP92697804 @takeUforward_ finally nashta done

[Siddhant @Siddhant_code]

#SDESheetChallenge @striver_79 @takeUforward_
DAY-2
brute force - O(n^2) check all subarrays and get rejected
optimal - whenever the sum gets less than 0 make sum 0 and also before that check max condition

Buy and sell stock

brute - O(n^2) bekaar

try to sell on minimum and sell when profit is max

Sort 0s 1s and 2s

use any sorting algo would fetch us at best O(nlog n)

so we use a three pointer method which we call dutch national flag algo

[Siddhant @Siddhant_code]

@AdityaP92697804 @takeUforward_ letsss gooo

[Siddhant @Siddhant_code]

#SDESheetChallenge @striver_79 @takeUforward_
SET MATRIX ZERO
when u first look at the problem you know every zero in the original array makes every column every row zero … here comes the brute force approach store the row and the column corresponding to evry zero in seperate arrays… and zero the rows and columns complexity - O(mxn +z) z is small so O(m X n ) and space complexity is (m + n) two arrays for rows and columns .

now to optimise this we can approach it using the first row and first column …it does a similar work which the two arrays did in the brute approach ..now instead of making two different arrays we can just use the first row and first column to mark rows and columns that need to be zeros

also … check if the first rows or columns contains zeros …

Pascal Triangle…

simple you know you know kind of question where we just find ncr(r-1,c-1)

Next permutation
if brute ….generate all permutations and the interviewer will not be happy

optimal idea is to find the smaller number followed by a larger number when iterated ulta

now find the first number greater than number at the index when we come ulta swap and reverse the subarray

[Siddhant @Siddhant_code]

@Kcodess cool thanks

[Siddhant @Siddhant_code]

Anyone who can help me get into open source and understand how it works
#opensource #buildinpublic