Books:

Int Max value - 10^9

Long max value - 10^18 -> 19 digits

Interviewbit
leetcode
GeeksforGeeks

Refactoringguru for Java design patterns

Dare2Dream

DataStructure Algorithms & Problem solving

DataStructures to solve problem very effeciently.

Coding -X time & Debug/Testing takes 10-20X time

So, coding accuracy will improve productivity

Effeciency is money-This differentiates between good and great developers.

CS fundamentals

OS, DBMS, Networking

Design

LLD/OOPS design

HLD/System Design

Facebook messager

50 Billion messages/day, each message of size 500 Bytes

50B * 500 Bytes = 25000 Billion Bytes = 25000 * 10^9 Bytes = 25K * 1GB = 25 TB

Thought process/how to think to solve the issue

Meet & Greet

1 VP, 2 directors of engineering & 2 co-founders of companies
To do big in carrer - command on technology is key
DSA and computer fundamentals - 15 weeks
LLD - 5 weeks

Coding is 10-15% in software engineering
Other time goes in reading & understanding others code
Writing maintainable, extensible, testable & reproducible code

Use Design patterns

HLD - 5 weeks

to design systems for very large number of users
Scalability problems are addressed

Sort strings in a list
Size of list is 50Peta bytes
1000GB is 1TB and 1000TB is 1PB

Netflix accounts for 15% of internet traffic

Projects - 6 weeks(Learn frameworks and work on real projects)

Productivity- speed at which one can convert knowledge into real life project.

Optional Electives

Advanced DSA
Concurrent programming

Multi Threading

Product management

Active learning - apply by coding Assignments & homework

HighLevel Design

What and why HLD

Study of large scale systems from 50 feet view architecture
When we develop any code, we are used to working one system
When we get Million/Billion users it will not work
eg: Netflix which accounts for 15% of internet traffic runs on thousands and thousands of servers
Even sorting numbers is complex when program runs on 100*1000 servers

Sort names from a list of size 50PB of data

Case Study

del.icio.us formed in 2005/6 which is a book marking website
Bookmarks are local to machine

Laptop, server, internet
ip address
DNS server to maintain global mapping between ip & domain name
DNS maintained by ICANN a non-profitable organization
isps/mncs maintain copy of dns to avoid latency
8.8.8.8 & 8.8.4.4 are google DNS servers
vertical scaling - trechnolgy and cost limitation
buy lot of cheap machines
User -> single machine(Load balancer)-> talks to 29 machines

Load balancer only forwards the request and NO computation/storage
to which m/c does it forward?

random/round robin(non-deterministic)/ user%#servers lot of shuffling when server goes down and comesup
User data? Shared DB?
what happens when system dies

Load balancer will have failover to handle failures

Consistent Hashing

Put users and servers on same number line
move in one direction
go crazy- use multiple hash functions
This will not suffer from shaffling anomaly

Store user-server mapping in load balancer
it will take (userid, serverid)*#users = 8 bytes * 1Billion users = 8GB
Time to read 1byte from RAM-100nano secs/0.1 micro secs, read/seek from disk/hdd- 10milli secs, SSD is 10/100 times faster than HDD

diff is 100000

cashes is much faster than RAM
so formula based approach is better

Put users and servers on same numberline
Hash function

cannot be reversable
output is bounded

Map users and servers to same number line/range by using same hash functions with same output range

Books suggested

https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321

Low Level Design

What LLD

Closer look at application - 5 feet view
Programming Paradigms
SOLID principles
Design principles
ER-Diagrams
Database Schemas
MVC
Clean Architecture

Why LLD

Allows make our code better
10-15% of dev time spent in coding
Maintenance

testing, code, refactoring

Read, review and research

Look at other people code

Writing code is easier is than reading and understanding other code

Maintainable

Testable, debuggable, refactorable

Readable

Transparent/obvious code/boring
self-explanatory

Extensible

Requirements change all time
eg: RBI Mandate - No automatic payments with Credit card with out approval
Anticipate future requirement changes and structure itself in a manner that incorporating such changes is simpler.

How do we achieve the 3 goals

Programming Paradigms - Object Oriented Programming
Guidelines/Principles that others have figured out-SOLID Principles
Standards- widely accepted & battle tested solutions. to common problems.

Design patterns

How to breakdown a vague problem and make it executable
Programing Paradigms

Object Oriented - widely used
Procedural

Top-to-Bottom

Functional
Declarative
Imerative
Data Driven
Reactive/event driven
Aspect Oriented
Most modern programming languages are multi-paradigm in nature

Object Oriented

Smart phone is a concept

is it real thing

os, apps, features, call, camera, security, feel, touch screen
Smart phone

Attributes

size, design, color, screen size, resolution, battery life, camera quality, OS

Behaviors

calls, browse, install apps, take photos/videos, listen to music

Battery

Attributes

size, capacity, weight, chargable, time for charge, manufacturer, warranty, #ports

Behavior

get charged, charge other things, heat up, blow up, degrade over time

Relationships

Smartphone has a battery, touchscreen
has-a relationship

smartphone has battery
bird has legs

is-a relationship

Bird is a living thing
Smartphone is a electronic device
inheritance

Every concept has

Attributes/physical properties
behavior/functionality
relationship with other concepts

Objects

Physical & takes space

Object oriented Programming

We think of programs/solutions in terms of concepts and objects
Concept/idea - use Class to represent it

class xys{
//member variables - attributes
   .....
//behavior
   ..methods
//relationships are also member variables
   ..Battery battery;
    TouchScreen screen;

Method vs Function

Method is tied to an Object

VS Code

Microsoft backed
Github behind it
opensource defacto
Github co-pilot

Inheritance vs Composition

Should we model as is-a relation or has-a relation
Composition is usually preferred as it have some advantages and simpler to maintain

Model concepts of Child, Father, Son, Daughter, GrandParent, Mother Parent using OOP

has-a relation is bi-directional

Composition(ownership-directional)
Aggregation(no ownership)
class GrandParent extends Parent{
}
class Parent extends Child{
list<Child>
}
class Child{
Parent mom, dad;
}

Introduction to Problem Solving

Given a number, check if the number if Prime OR not.

Count factors from 1 to N and the sum should be 2.
Assumption

Processor can make 10^8 iterations in one sec
Input is given value is 10^9 value. So number of iterations is 10^9 and hence time is 10 Secs
Input is of order 10^18. Time - 10^10 secs ~ 317 years

Optimizations

if a if factor of N, then N/a will also be a factor
unique factos will come as long as i is <= N/i(take factors for proof)
so i^2=N => i=sqrt(N)
for(int i=2;i<sqrt(N);i++) if N%i==0 {
if (i=N/i) cnt++ else cnt=cnt+2; }
number of iterations: sqrt(10^18)=10^9 = 10 secs
No Fancy Algorithm

Sum of first N natural numbers

N*(N+1)/2
Observations: 1,2,3....99.100
write everything in revers 100, 99 .....3,2,1
Add both : 101..101... these willbe 100 times 101.
Sum= 100* 101/2

Azn Q: Given N, howmany times we need to divide by 2 till it becomes 1

Highest powerof 2, less than or equal to N. Highest power of 2 is defined as LogN

Number of times a number has to be divided to become 1 is logN

Azn Q: Given a perfect square, find the sq root of it.

for(int i=1;i<N;i++) if i*i==N return i;
For 2^32 - how many iterations will be done

2^16/10^8 = (10^3 * 2^6)/10^8 = 2^6/10^5 which is a very small number

For 2^64 = 2^64/10^8 = (10^9* 2^2)/10^5 = 10^4/2^2 = 45 sec
Optimizations

Square always lies in [1..N]
start with middle value & discard half of the search space comparing the value i*i value with N

Time Complexity

Maths concept for revision

How many times we need to divide N by 2 to reduce to 1 is LogN
[a,b] means inclusive (a,b) means exclusive
Arithmetic progression: Any series where any consecutive terms has same difference

a, a+d, a+2d...
Sum of first n numbers for a progression

n*a + (n*n-1)/2*d = n/2*(2a+(n-1)d)

Geometric progression: Any series where any consecutive terms have a common/ratio

a, ar, ar^2, ar^3..
sum of first N terms =a*(r^n - 1)/(r-1)

base a X means- Number of times we need to divide X by a till it becomes 1
loga a^X= x

Find Time Complexity

for(int i=1;i<=N;i=i+2) -> (N+1)/2 which is odd numbers in [1,N]
for(int i=1;i*i<N;i=i++) -> sqrt(N)
int i=N; while (i>1) i=i/2; -> log(N)
after k steps when N becomes 1 1=N/2^k ie 2^k=N ie k=log(N)
for (i=0;i<N;i=i*2) is infinite
for (i=1;i<N;i=i*2) is logN
Nested loops

for (i=1;i<=10;i++)
for (j=1;j<=N;j++) is 10*N
for (i=1;i<=N;i++)
for (j=1;j<=N;j++) is N*N ie N^2
for (i=1;i<=N;i++)
for (j=1;j<=N;j=j*2) is NlogN
for (i=1;i<=2^N;i++) is [1,2^n]
for (i=1;i<=N;i++) is
for (j=1;j<=2^i;j++) a*(r^n - 1)/(r-1) => 2* 2^n -1
for (i=1;i<=N;i=i+2)
for (j=1;j<=i;j=j++)

How to calculate BigO from number of iterations

Neglect all lower order terms(lower power)
Neglect all constant coefficents

eg: 4n^2+3n+2^100 => 3n+2 is lower order term & 4 is constant coefficents

so TC is O(N^2)

n*sqrt(n) + 4logn + 31 n* logn

try with 2^32 for n
O(n*sqrt(n))

for (i=1;i<=10;i++) - 10 iterations 10* N^0 and TC: O(1)(Constant time complexity)

Best time complixity order

O(1)
O(logn) -> almost same as O(1)- constant time complixity
O(sqrtn) ->
O(n)
nlogn
n sqrtn
n^2
2^n
n!
n^n-> worst time complexity

Time Complexity-2

Why execution time is not correct measure for comparing algorithms

Hardware dependency(Mac vs Samsung mobile)
Interpreter vs Compiler(Python vs C/C++)
Semiconductor performance based on weather(perf is low when temperature is high)
Input size

Number of Iterations is good measure of comparison

(eg: 100logN vs N/10)
Graph is right way to compare
eg: walking distance, bike, car, cab, ... Bucketize the distances
Why do we ignore lower order terms

distance from home -> moon 3.8lac KM

In functions/algorithms, bucketize based on growth rate.
Growth rate for LogN is slow compared to N/10. Growth rate is determined by highest ordered term

10N vs N^2

Asymptotic measure

Comparing algoritems with very large input size is called Asymptotic analysis.

BigO means growth rate

A function f(n) is O(g(n)), if f(n)<= c* g(n) then g(n) is O(f(n))
Limitations

BigO only talks about growth rate and NOT about time taken
O(N^2) may take more time than O(N^3)

eg: 10N^2+100N+1000 vs O(N^3)

Space Complexity

Space being created in program
Integer - 4 bytes, Long- 8 bytes, Double - 8 bytes
Input Space + Extra space or Auxiliary space

Introduction to Arrays

Given an array find the count of elements that have atlest one element greater than itself.

Find the max value in array- Cmax
Iterate over array to get count of elements equal to Cmax-countmax
return size()-countmax
#number of iterations is 2N & TC: O(N)

HM: Try to do the above problem with single iteration/loop.
Given an array A and a integer B. A pair(i,j) in the array is a good pair if i!=j and (A[i]+A[j]==B). Check if any good pair exist or not.

Brute Force

Visit all pairs including i=j & j<i
Iterations: N^2 & TC: O(N^2)

Optimized approach

For every i run a loop of j(from i+1) and check if A[i]+A[j]==B or not. Also, check if i!=j.
Iterations: N*(N-1)/2 TC: O(N^2)

MS, Amz: Given an array of size N, reverse the array with constant extra space

While (i++<j--) swap (a[i],a[j])
Iterations: N/2 & TC:O(N)

Given an array of size N and two indices. Reverse array from index S to E.

While (s++<e--) swap (a[s],a[e])
Iterations: (e-s+1)/2 & TC:O(N)

Amz: Rotate the Array: You are given an integer array A and an integer B. You have to print the same array after rotating it B times towards right(clock wise direction). (B<size of array)

Reverse all the elements of array
Reverse first B elements followed by the rest of N-B elements.
Iterations: n/2+B/2+(n-B)/2 =n TC:O(N)

Given an array of integers A and multiple values in B, which represents the number of times array A needs to be left rotated. Find the rotated array for each value and return the result in the from of a matrix where i^th row represents the rotated array for the i^th value in B.

Create new array to return the result
insert elements from B to end of array
insert elements from 0 to B-1

Arrays Prefix Sum for range sum queies

Amz- Given an integer array A of size N & Q queries of the format S & E. Return some of elements from index S to E.
- Brute force
- Optimization

DirectI: Given an integer array, return true if there exists Equilibrium index in the array

Equilibrium index is an index for which sum of all the elements on left is equal to sum of all the elements on right side

prefix sum the array
if prefixsum(0,i-1) equals prefixsum(i+1,N-1) return true
TC: O(N), SC:O(N)

without prefix sum/extra space

TC: O(N^2), SC:O(1)

Given an array & Q queries, Each query has start index, end index & indicator even/odd(o/e). Return sum of odd/even numbers based on indicator for each query.

Build Prefixsum_even & prefixsum_odd
Retrun value from either ps_e or ps_o based on Query input

Google, DirectI, Code Nation: Given an integer array, count the number of special index in array. Special index is the index after removing which sum(odd index elements)=sum(even index elements)

4, 3, 2, 7, 6 , -2 -> 0,2 is special index
eg: after removal of index i, sum(odd)=oddpresum(0,i-1)+evenpresum(i+1,N-1)
Create prefix sum for even & odd. use the prefix sum in above formula

Given an integer array A of size N. You can pick B elements from either left or right end of the array A to get maximum sum. Find and return this maximum possible sum.

Create prefix sum & suffix sum arrays
run the for loop to get the max sum

Arrays Carry Forward

Left Max: max of elements that are left to current element
Right Max: max of elements that are right to current element
Given an array build an array leftmax & rightmax
Carry forward

Given a string of alphabets in lowercase, return count of pairs(i,j) where i<j & s[i]='a', s[j]='g'

Bruteforce

For every a, count the #g on right side of it
TC: O(N^2)

Optimization

Every g will make a valid pair with a on left of it
ans=0, count_a=0;
for (i..n) if S[i]=='a' count_a++;
else if S[i]='g' ans+= count_a;
return ans;
TC: O(N)

Amz: Given an array, return length of smallest subarray that contains both minimum and maximum of the array.

Ans subarray will always have max/min in the corners.
There will only be one min and one max in the ans subarray
Logic: Bruteforce O(N^2)

Find Min & Max in the array
For every min, find closest max on right
For every max, find closest min on the right

Optimization

Find Min & Max in the array
for (1:N)
lastmin, lastmax
calculate length when once the lastmin/lastmax are changed. Override with new value with new length is less than existing length value
TC: O(N)

N light bulbs connected with faulty wire. Every bulb has its own switch and initial status of lighting state. eg 1 0 0 1 0. When a switch of any bulb is toggled, all the switches right of it will get toggled. What is min switch press required to turn ON all the bulbs?

Start from index 0
Search for bulb which is OFF and toggle it.
pseudocode

switchpressed=0;
for(i=0;i<n;i++){
   //curr state of switch
     if (switchpressed%2==0) currstate=a[i] else currstate = (a[i] == 0?1:0);
    if currstate==0 then switchpressed++;

Arrays: Subarrays

You are given an integer array A of length N.
You are also given a 2D integer array B with dimensions M x 2, where each row denotes a [L, R] query.
For each query, you have to find the sum of all elements from L to R indices in A (1 - indexed).
More formally, find A[L] + A[L + 1] + A[L + 2] +... + A[R - 1] + A[R] for each query.
Given an array of integers A, find and return the product array of same size where i'th eement of the product array will be equal to the product of all the elements divided by the i'th element of the array.

Contest1: https://www.scaler.com/academy/mentee-dashboard/class/16971/session

Aakash has N ingredients, and ith ingreidient have A[i] sweetness. He wants to make perfect dish using the given ingredients. The dish will be perfect if it has following properties

There is atleast one ingredient whose sweetness is prime number
Total sweetness should be atleast B & atmost C. Find number of ways to make perfect dish

An Array is fanatic if all of its elements are divisible by 4. Given an array A of N integers, return the minimum number of operations to make the array fanatic. In one operation, you can remove any two array elements, sum them up and append this sum to end of the array.

eg: [1, 3, 4, 4, 2, 2]
Find Mod for all numbers and ignore numbers with mod 0
Find number of numbers with mod 1, 2, 3
matches=min(m1,m3); opertions += matches;
m1-=matches; m3-=matches;
Create M2 from either 2 M1 or 2 M3
if m1>0 operations + = m1/2; & m2+=m1/2; m1=m1%2;
if m3>0 operations + = m3/2; & m2+=m3/2; m1=m3%2;
if (m1!=0 || m3!=0) return -1;
if (m2%2==0) operations += m2/2; return operations;
return -1;

Bus travels to N different stops. and at each stop some people get in and get out. You are given an array A, where A[i] gives the amount of people who have got into/got off the bus based on a[i] is +ve or -ve. B is the capacity of the bus. Initially bus can have some amount of people in it. Find total number of possible ways of how many people are initially in bus before first stop such that at any time there are 0 to B number of people in the bus.

if ((B+min<0) || (max>B)) return 0;
        if (min<0 && max>0) return B-max+min+1;
        if (min<0 && max<0) return B+min+1;

        if (min>=0) return (B-max)+1;
        else return (B-max)+1+min;

Anurag left his job as a travelling salesman. He went to a car rental company to rent a car. Car company showed him A cars parked in a row. He has a superstition, that he always buys things in contiguous sub array. Considering all ways to rent a car, for each car, find the #ways to rent it. Return array where integer at index i represents the number of ways to choose ith car.

Hint: Number of subarrays
Number of elements equals and after it * Number of elements equals and before it

Sorting

Why sorting - Arranging data in asc/desc based on parameter(value or factors..)

Given an Array of size N, at every step remove an element. Cost to remove element is sum of array elements present before removing array element. Find min cost to remove all the elements
Given N elements, calculate no of noble integers present. Element a[i] is said to be Noble int if number of elements < a[i] equals a[i]
Given N elements, sort them in increasing order of #factors. If same number of factors, the element with less value comes first.
Given N elements, sort in increasing order of #digits. if 2 elements have same #digits element with more value should come first.

Comparator

sort(arr, comparator) // to override built-in sort
comp(a,b) returns true if a to come first

Min cost to remove all elements
Nobel integer

Given an integer array A, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p.

Notes: Ensure cases where the elements are same & nobel element is the last element in array

Sort by Color

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Hint: Count the number and add to a new array instead of Sort.

Comparator

Modular Arithmetic

int range is 10^8 & long range is 10^18
Reminder = dividend - greatest multiple of divisor <=dividend
(a+b)%m = (a%m + b%m)%m
Divisibility by rules

sum of digits is divisible by 3

Given a number in form of Array A & number P. What is A%P value when P is int
Given three 2-digit integers, A, B and C, find out the minimum number that can be obtained by concatenating them in any order.

Return the minimum result that can be obtained.
Given eight integers A, B, C, D, E, F, G and H which represent two rectangles in a 2D plane.
For the first rectangle it's bottom left corner is (A, B) and top right corner is (C, D) and for the second rectangle it's bottom left corner is (E, F) and top right corner is (G, H).

Find and return whether the two rectangles overlap or not.

Arrays & Maths

There are N doors & a person is standing in front of every door which are all in closed status. The person standing in front of 1st door opens all the doors. The 2nd person toggles the status of every 2nd door. 3rd person toggles the status of every 3rd door. Return which all doors will be finally open. Hint: #factors of every number. odd vs event, perfect sqares are the answer
Nth Magical number: Magical number is a number that can be expressed as sum of unique powers of 5. Given a number N, return Nth Magical number. eg: 5^1, 5^2, 5^1 + 5^2,

Hint: binary representation of N & multiply with the power of 5 & sum

Majority Element

Given an array of size N return if there exists a number with frequency > N/2. Solve the problem with out any extra space

Hint: delete 2 distinct elements

Moovs voting algorithm
Maintain ME & respective count variables.

Given an array of size N return if there exists a number with frequency > N/3. Solve the problem with out any extra space

Hint: delete 3 distinct elements by maintaining 2 counters
once you get Majority element1 & 2, traverse thru array to get the actual count and verify if count >N/3

If there are N people in a circle including leader of the team, what should be the position leader should stand in order to save his life.

If the number of people is in power of 2 then the person who starts killing wins
if the number of people is NOT in power of 2 at the start, keep track of the count as it reduces. The person who has the sword when the count reduces to power of 2 will win.
After killing X number of people, the position of sword is in 2X+1 position
Movie: Imitation game

Arrays: Interview Problems

Given a binary array, one is allowed to replace atmost one 0 with 1. Return length of consecutive 1's
Given a binary array, one is allowed to swap atmost one 0 with 1. Return length of consecutive 1's
Find number of tripples i,j,k(indices) such that i<j<k & a[i]<a[j]<a[k]
Given an array of size N, print the start and end index of all the subarrays of length K
Find max subarray sum with length K.(Complexity -N^2)

Using Sliding window approach(will reduce Time complexity to N)

Given an integer array A of size N, pick up K elements from either left or right end of array A to get max Sum.
Given an array of integers A, of size N. Return the maximum size subarray of A having only non-negative elements. If there are more than one such subarrays, return the one having the earliest starting index in A. NOTE: It is guaranteed that an answer always exists. Maintain 2 set of counters for global size, global start, end & local size, start and end.
Write a program to input an integer N from user and print hollow diamond star pattern series of N lines. Note: print using 2 for loops.
for (int r=0;r<2*N;r++){

for(int i=0;i<N;i++){
if (i>=(N-cnt)) System.out.print(" "); else System.out.print("*");
}
for(int i=0;i<N;i++){
if (i>=cnt) System.out.print("*"); else System.out.print(" ");
}
if (r<N-1) cnt++; else if (r>N-1) cnt--;
System.out.println("");
}
Write a program to input an integer N from user and print hollow inverted right triangle star pattern of N lines using '*'.

for (int r=0;r<N;r++){

for(int i=0;i<N-r;i++){
if (r==0) System.out.print("*");
else if ((i==0) || (i==(N-r-1))) System.out.print("*");
else System.out.print(" ");
}

System.out.println("");
}

Why sun never went to college

what will one ocean tell to other when they meet

Sharpner said something to pencil. What do you think it was.- stop going in circles and get to point.

Tall when young and short when old - candle, pencil

Name a duck that walks on 2 legs

how do you measure a snake. inches as they don't have feet

lady standing under a bridge - miss understanding

what do you call a fat lady waiting - motivating

Crabs - are bad at sharing - because they are sel+fish

DSA- Recursion 1

Given a directory structure, search a file in it. 2 methods that return AllDirectories in a given Directory & All files in a given Directory are provided.

Check if file is present in directory.
Get all directories in to a list-> invoke the recurssion in a loop for each directory

DSA- Recursion2

int pow(a,n)
if (n%2==0) the a^n/2 * a^n/2 else a * a^n/2 * a^n/2
2^32 ~ 10^9
Time complexity of recursion function

Using recurrence relation
Time complexity of funtion like f(n)=f(n-1)+f(n-2) is O(2^N)
Height of tree is N & number of leaf nodes is 2^N
What is time complexity for T(N)=T(N/2)+1

T(N/2^k)+K
Base case is T(1)=1
after K steps

N/2^k=1 => 2^k=N => k=logN

after logN steps

T(N/2^logN)+logN => T(N/N)+logN
LogN

What is time complexity for T(N)=T(N/2)+1

O(N)

2^logN is N
T(N)=2T(N/2)+N

NlogN

Space Complexity

Max size of stack at any moment
Depth of tree

Space complixity of a^n=a^n/2 * a^n/2 is logn
On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row A and index B, return the B^th indexed symbol in row A. (The values of B are 1-indexed.) (1 indexed).

DSA-LinkedLists

Applications that are implemented with LL

Inverted indexes in Elastic Search, Solr, Lucene
Hashmap data when collisions happen

DSA - Trees

How to store hierarchy in data

eg: filesystem, HTML DOM

TREE

You are given the root node of a binary tree A, You have to find the height of the given tree.

A binary tree's height is the number of nodes along the longest path from the root node down to the farthest leaf node.

max(left tree, right tree)+1

DSA HomeWork2- https://www.scaler.com/academy/mentee-dashboard/class/17337/session?navref=cl_dd

Largest Number: Given array of N positive numbers, arrange them so that they form largest number

eg: 10, 2, 31 -> 31210
31, 3 ->331
37, 3 ->373
To compare the numbers A and B, we can view both of them as strings, and make them of the same length by calculating (A + B) and (B + A). Then we can just compare these 2 strings lexicographically, and sort them according to it.

Change Character: Given String A of size N. You can change atmost B chars in the given string to any other letter. Find min of distinct chars in the resulting string.

eg: abcabbccd & B=3
Get frequency of each char using Frequency array(Hash map also works but not preferred approach)
Arrange chars in order of frequency
And replace the ones from left with low freqency

Valid Sudoku

9*9 grid
NO duplicate in row
No duplicate in column
No duplicate in white 3*3 square
For every row check for duplicates
HashSet per row

for (int i=0;i<9;i++){
   set={};
   for(int j=0;j<9;j++){
    if set contains matrix[i][j]; return "invalid"; else
       add matrix[i][j] to set
similar to above perform column check
for block check
index starts at 0 to 2, 3 to 5 and 6 to 8
perform similar check as row

Kth Symbol

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row A and index B, return the B^th indexed symbol in row A. (The values of B are 1-indexed.) (1 indexed).

Constraints: 1 <= A <= 20 & 1 <= B <= 2^{A - 1}
Soln: Find all rows up to N
Constraints: 1 <= A <= 10^4 & 1 <= B <= min(2^{A - 1}, 10^9)
Soln: Find only rows which are necessary

    public int kth(int N, int K) {
        if (N==1) return 0;
        if(K % 2 == 0){
      return kth(N - 1, K / 2) == 0 ? 1 : 0;
      }else{
         return kth(N - 1, (K + 1) / 2);
      }
}

Gray code

The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer A representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
Constraint: 1 <= A <= 16
public class Solution {
public ArrayList<Integer> grayCode(int a) {
ArrayList<Integer> res = new ArrayList<>();
int i = computeGrayCode(res,a,0);
return res;
}
public int computeGrayCode(ArrayList<Integer> res, int a,int num){
if(a == 0) {
res.add(num);
return num;
}
num=computeGrayCode(res, a-1,num);
num = num ^ (1<<(a-1));
num=computeGrayCode(res, a-1,num);
return num;
}
}

DSA - Trees2

Given a binary tree & a number K, check if number is present in tree or not

use preorder traversal

Given 2 binary trees, return true if they are identical

Value at root nodes are same
Left subtree of one tree should be identical to other tree
right subtree of one tree should be identical to other tree
Use recursion with preorder traversal

Given 2 binary trees, check if they are symmetric(mirror images) to each other

Root values must be same
roots left becomes right and vice versa
use recurssion with preorder comparing left nodes with right on other tree

Given a binary tree, revert it(convert to its mirror image)

inorder traversal - swap left & right trees

Binary Search Tree
Height Balanced Binary search tree

ht(right sub tree)-ht(left sub tree)<=1

self-balanced binary search trees

AVL tree, Red black tree
Optimal for searching

Given a Binary search tree, find a key
Given a Binary search tree and range ( start, end), count no of nodes with value within range
Binary search tree applications

hashmap, hashset, treemap, treeset

Binary trees

Heaps & priority queues
Segment trees, tries

DSA- Subsequences and subsets

Subsequenc

Parts of array, elements of array in same order but need not to contiguous
Any sequence that can be generated by deleting 0 or more elements from an array

Subset

Same as subsequence but order doesn't matter
Has only unique values

Given an array of size N(distinct elements), check if there exists a subset with sum K

for (int i=0; i<2^n;i++){
   //check which all bits are set for i
   int sum=0;
   for (int j=0; j<n; j++){
       if (checkbit(i,j)){
           sum+= A[j];
}
if (sum==K) return true; else return false;
Time Complexity is O(2^n * n) & space complexity is O(1)

Number of subsets in which ith element will be present is 2^(n-1). sum of all subsets in which ith element is present is a[i]*2^(n-1). Sum of all subsets is sum+=a[i]*2^(n-1) => a[i]<<n-1
Given an array of N distinct elements, calculate sum of all subsets & divide by 2^N

sum of all subsets = 2^n-1 * a0+ 2^n-2* a1+ 2^n-3 * a2+ ... = 2^n-1 *(a1+a2+a3....)/2^n
= (a1+a2...an)/2

Given an array, find the sum of max of every subsequence

Approach - contribution technique- count contribution of every element in the total sum- find number of subsequence in which element is maximum
sol

sort the array
contribution of ith element is a[i]*2^i
sum=sum+a[i]*2^i;

DSA-Stacks and Queues

Stack is abstract data type which means logical definition is fixed and implementation can be in different ways.
Operations

Push, Pop, Top/Peek, isEmpty, size()

Stack Applications

Recursion, Undo-Redo, Browser Back button,
Implementation using LL

Insert from front & remove from front

Implement stack which supports getMin() function

Maintain another stack to maintain min at every level

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Given a string A consisting only of '(' and ')'. You need to find whether parantheses in A is balanced or not ,if it is balanced then return 1 else return 0.
Given an expression string A, examine whether the pairs and the orders of “{“,”}”, ”(“,”)”, ”[“,”]” are correct in A.
Return 0, if the paranthesis sequence is not balanced.Return 1, if the paranthesis sequence is balanced.

DSA-Hashing2

2-Sum Problem

Given an Array A and number K, return True if there exists pair (i,j) in the array such that A[i]+A[j] = K

For every value of I, check if Hashset/map has element K-A[i], if yes return true else insert A[i]

Given N array elements, calculate number of distinct elements in every window of size K

Process first window of size K & build freqency of the elements(Initial window)
Iterate over remaining windows(Sliding window)

remove first element of the prev window
Add new element

Given an array, find the length of largest sequence which can be rearranged to form a sequence of consecutive numbers

eg: 100, 4, 200, 1,3,2 -> 1234
Add all elements to set
Iterate over set elements to avoid duplicates and perform the following

if SET has element a[i] -1 then just skip
count sequence length for every element as start by checking if SET has next element and increment the length if so.

DSA-Hashing

SET

It is a data structure which internally that bucketize all the items inserted in it. Its only job is to tell/SEARCH whether a given item/object is present in it or not in O(1) time. All operations on SET are performed in O(1) time
Internally it uses concepts like Hashcode, Binary Tree(Self Balancing Binary search tree),
In Java/C#, set is known as HashSet, C++ -> Unordered Set, Python/JavaScript/Ruby -> SET, C ->
Set only stores Unique elements

Given an array, count the # of distinct elements
Map

It is a key value storage
In Java is known as HashMap, C++ -> Unordered Map, Python -> Dictionary, /JavaScript/Ruby -> Map
Given an array of strings, Q queries having a string in each query. Return sum of ascii values of chars in string
Given an array of size N, find the first non-repeating element in the array

Build hashmap with frequencies & iterate over array and return first element with frequency 1

Given an array of size N, return true if there exists a subarray with sum=0

Number of subarrays is N(N+1)/2
Use prefix sum & verify if any 2 elements have same value or any element has value 0

Given an array A of N distinct and positive elements, the task is to find number of unordered pairs whose sum already exists in given array.

put array elements in hashset and then use nested loops to find if that sum exists or not

Given two integer array A and B of size N and M respectively. Your task is to find all the common elements in both the array.
Given a string A consisting of lowercase characters. Check if characters of the given string can be rearranged to form a palindrome. Return 1 if it is possible to rearrange the characters of the string A such that it becomes a palindrome else return 0.
Given an array of integers A and an integer B. Find the total number of subarrays having sum equals to B.

DSA-Strings

Class

Ascii value of 'A' is 65, 'a' is 97, '0' is 48
Strings are immutable in Java. Use String Builder for changes
Given a string toggle case of each char

If char is upper, add 32 else substract 32
Alternatively, use xor 32 - 'A'^32 = 'a'

Given a String with lowercase chars, sort it in dictionary order

cnt[26]; for each char -> cnt[s[i]-'a']++; -> iterate over cnt array and print
This approach is called Count Sort Approach

Given a Char array storing a sentence, reverse it word by word. Note: no extra space before or after sentence. All words are separated by single space.

Reverse complete sentence & reverse words individually.

Given a string, return length of longest palendromic substring

every char as center & partition as center
for(i=0;i<str.length();i++) {
max(ans,getPalLen(str,i,i); max(ans,getPalLen(str,i,i+1);
};
Time complixity -> O(N)
To achieve O(N) complixity, use Manach's algorithm

Given a string, determine if it is a palindrome. While checking for a palindrome, you have to ignore spaces, case and all special characters; i.e. consider only alphanumeric characters.
Given a string A consisting of lowercase characters. Check if characters of the given string can be rearranged to form a palindrome. Return 1 if it is possible to rearrange the characters of the string A such that it becomes a palindrome else return 0.

Bit Manupulations

Bitwise Operators

&, |, ^, ~, >>, <<
X | 1 is X when it is ODD & X+1 when X is Even
X & 1 is 1 when it is ODD & 0 when X is Even
X ^ 1 is X-1 when it is ODD & X+1 when X is Even
X | X is X, Y&Y is Y, A^A is 0, A^0 is A
A^B is same as B^A. All bit wise operators are Commutative.
If A^B=K then A^K =B
A<<n is A*2^n(Assuming NO overflow). 1<<n is 2^n
A>>n is A/2^n(Assuming NO overflow). 1>>n is 1/2^n

Given an array where all the numbers appear even number of times except one number which appears odd number of times. Find odd time appearing number.

use property X^X is 0 & X^0 is X

Given 2 positive numbers N & i, check if ith bit is 1 or 0

N & 1<<i-1 == 1<<i-1 then set else unset OR
(N>>i) & 1 == 1 then SET else Unset

Given 2 positive numbers N & i, set ith bit in N

N = N | 1<<i-1

Given 2 positive numbers N & i, toggle ith bit in N

XOR with 1

*Given a +ve number N, toggle all the bits starting from right most set bit.

Just return N-1

*Given a number, count the number of Set bits in it.

for( i in 1 to 32) checkbit
T(C) is logN

N & (N-1) Unset the last set bit
Reverse the bits of an 32 bit unsigned integer A.
Alex and Sam are very good friends. Alex is doing programming a lot these days. He has set a target A for himself. Initially, Alex score is zero. Alex can only double his score by doing a question or Alex can seek help from Sam for doing questions which will contribute 1 to Alex score. Alex wants his score to be exactly A. Also, he does not want to take much help from Sam.

Find and return the minimum number of times Alex needs to take help from Sam to achieve a score of exactly A.

Arrays - 2D Matrices

Given N*M matrix, print all diagonals going from R->L

Diagnonals can be started from 0th row or Nth column
Transpose a matrix
rotate matrix by 90 degrees

Transpose & reverse each row

Given a square matrix- print all boundaries
Spiral printing of matrix

You are given a 2D integer matrix A, make all the elements in a row or column zero if the A[i][j] = 0. Specifically, make entire ith row and jth column zero.

public class Solution {
    public ArrayList<ArrayList<Integer>> solve(ArrayList<ArrayList<Integer>> A, ArrayList<ArrayList<Integer>> B) {
        ArrayList<ArrayList<Integer>> c = new ArrayList<ArrayList<Integer>>();
        
        for (int i=0;i<A.size();i++){
            ArrayList<Integer> col = new ArrayList<Integer>();
            for (int j=0;j<A.get(i).size();j++){
                col.add(A.get(i).get(j) + B.get(i).get(j));
            }
           // c.add(col);
            c. add(new ArrayList<Integer>(col));

        }
        return c;
    }
}
 
Set Values 

public class Solution {
    public ArrayList<ArrayList<Integer>> solve(ArrayList<ArrayList<Integer>> A, int B) {
        for (int i=0;i<A.size();i++){
            for (int j=0;j<A.get(i).size();j++){
                A.get(i).set(j,A.get(i).get(j) * B);
            }
        }
        return A;
    }
}

Contribution Technique

Arrays: subarrays

Find the sum of all the subarrays
You are given a string S, and you have to find all the amazing substrings of S. Amazing Substring is one that starts with a vowel (a, e, i, o, u, A, E, I, O, U)

Hint: The main idea to solve this problem is to traverse the string and when you encounter a vowel, add ( length(string) - position_of_curr_char ) to the answer

You are given an integer array A. Decide whether it is possible to divide the array into one or more subarrays of even length such that first and last element of all subarrays will be even. Return "YES" if it is possible otherwise return "NO" (without quotes).
If the first and the last element is even and the size of the array is even then only the answer will be “YES”.
Otherwise answer will be “NO”, as we can’t divide the array into subarrays that meets the given conditions in the question.

So, if(A[0]%2 == 0 and A[n-1]%2 == 0 and n%2 == 0)
return “YES”;

public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int maxSubArray(final List<Integer> A) {
int maxSum=Integer.MIN_VALUE;
for (int i=0;i<A.size();i++){
for (int j=i;j<A.size();j++){
int subsum = subArraySum(A,i,j);
if (subsum>maxSum) maxSum=subsum;
}
}
return maxSum;
}
public int subArraySum(List<Integer> A1, int si, int se) {
int sum=0;
while(si<=se) sum+=A1.get(si++);
return sum;
}
}

for (int i=0;i<A.size();i++){
sum+=A.get(i)
psum.add(sum)
}

SubArrays

Given an array A of N non-negative numbers and you are also given non-negative number B.

You need to find the number of subarrays in A having sum less than B. We may assume that there is no overflow. Hint: prefix sum
Given an array of integers A.
A subarray of an array is said to be good if it fulfils any one of the criteria:
1. Length of the subarray must be even and the sum of all the elements of the subarray must be less than B.
2. Length of the subarray must be odd and the sum of all the elements of the subarray must be greater than B.
Your task is to find the count of good subarrays in A.
You are given an integer array A of length N comprising of 0's & 1's, and an integer B.
You have to tell all the indices of array A that can act as a centre of 2 * B + 1 length 0-1 alternating subarray. A 0-1 alternating array is an array containing only 0's & 1's, and having no adjacent 0's or 1's. Hint: Use Brute force.

Utility Functions:

Read Array of size N

private static Scanner scan = new Scanner(System.in);
int[] myIntegers = getIntegers(5);
public static int[] getIntegers(int n){
        int[] values = new int[n];
        for (int i=0;i<n;i++) values[i]=scan.nextInt();
        return values;
    }
Read String

Scanner sc= new Scanner(System.in);
String str= sc.nextLine();

Prefix sum

public ArrayList<Long> prefixSum(ArrayList<Integer> A){
Long psum=0L;
ArrayList<Long> prefix=new ArrayList<Long>();
for(int i=0;i<A.size();i++){
psum+=Long.valueOf(A.get(i));
prefix.add(psum);
}
return prefix;
}
public int rangesum(ArrayList<Integer> prefixsum, int S, int E)
{
if (E<0) return 0;
if (S>prefixsum.size()-1) return 0;
return (prefixsum.get(E)-prefixsum.get(S));
}

Reverse Array
Reverse part of Array
Swap elements
HashSet

Set<Long> hset = new HashSet<>();
for(int i=0;i<A.size();i++){
if (hset.add(prefix.get(i)) == false) return 1;
}

for (Integer i : hset)
System.out.println(i);

if hset.contains(i+1) ...

HashMap
HashMap<Integer, Integer> countMap
= new HashMap<Integer, Integer>();

for (int i : A) {
if (countMap.containsKey(i)) {

countMap.put(i, countMap.get(i) + 1);
}
else {
countMap.put(i, 1);
}
}
for (int i : A)
if (countMap.get(i)>1) return i;
HashMap traversing

for (Map.Entry mapElement : countMap.entrySet()) {
if ((int)mapElement.getValue()%2!=0) cntodd++;
}

public class Solution {
    // DO NOT MODIFY THE LIST
    public String largestNumber(final List < Integer > A) {
        StringBuffer strBuf = new StringBuffer();
        Node num[];
        int i = 0;
        num = new Node[A.size()];
        for (int n: A) {
            num[i] = new Node(n);
            i++;
        }
        Arrays.sort(num);
        for (Node n: num) {
            if (n.number == 0 && strBuf.length() != 0)
                continue;
            strBuf.append(n.number);
        }
        return strBuf.toString();
    }
    class Node implements Comparable < Node > {
        int number;
        public Node(int number) {
            this.number = number;
        }
        @Override
        public int compareTo(Node o) {
            String first = String.valueOf(this.number) + String.valueOf(o.number);
            String second = String.valueOf(o.number) + String.valueOf(this.number);
            return second.compareTo(first);
        }
    }
}

 public int isSame(TreeNode A, TreeNode B){
     if ((A==null) && (B==null)) return 1;
     if ((A!=null) && (B==null)) return 0;
     if ((A==null) && (B!=null)) return 0;
     if (A.val !=B.val) return 0;
     if ((isSame(A.left,B.left)!=1)||(isSame(A.right,B.right)!=1)) return 0;
     return 1;
    }

Replace each letter with it's ASCII code in a string in PL/SQL

Search This Blog

Scaler

Techniques

Replace each letter with it's ASCII code in a string in PL/SQL

Comments

Post a Comment

Popular posts from this blog

Low Level Designs

System Design

CS Fundamentals