Siddhant

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

[Siddhant @Siddhant_code]

#SDESheetChallenge @takeUforward_ @striver_79
1.majority number

simple brute force approach would be to solve this in O(n^2) a better would be to hash it but the optimal comes from voting algo where if a number appears more than n/2 times the contribution of that number to the count variable if increased when found and decreased when not would be positive
2. search in 2d matrix

brute force to search every element a better and intuitively my first approach was to determine which row the element might exist and consider it as a different array and apply binary search to that particular row

but the optimal solution considers the entire matrix as a flattened 2d array where we apply bs to get the target

3, pow(x,n)

brute force can be to multiply the number as many times as it wants

for optimal use the idea of making a sqaure recursively to get an even power and in case of odd multiply the number once again

[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