https://www.java67.com/2018/06/data-structure-and-algorithm-interview-questions-programmers.html
Books to refer
https://te.1lib.limited/book/5269268/3fd6d5?dsource=recommend
https://www.raywenderlich.com/books/data-structures-algorithms-in-kotlin/v2.0/chapters/3-linked-list
The complexity of an algorithm can broadly fall into the following three categories:
“Best case analysis: Best case defines the minimum time required by an algorithm to produce the output. It’s also represented as Omega notation (Ω).
Average case analysis: Average case defines the average time required by an algorithm to produce the output for different sized input. It’s also represented as Theta notation (θ).
Worst case analysis: Worst case defines the maximum time required by an algorithm to produce the output. It’s also represented as a Big O notation (O).”
“O(n) > θ(n)>Ω(1)”
val x = 10
val y = x * 2
for (i in 0..y) {
if (i % 2 == 0) {
println(“$i is Even”)
} else {
println(“$i is Odd”)
}
}“Let’s break down the code to understand it better, as follows:
The first line, val x = 10, requires one instruction, that is, assigning the value 10 to x.”
“The second line, val y = x * 2, requires three instructions. The first instruction is to look for x, the second instruction is to multiply it by 2, and the third instruction is to assign the result to y.”
“The third line, for (int i = 0; i < y; i++), will run two more instructions in the first iteration of the loop. One is the assignment instruction, i = 0, and the other one is the comparison instruction, i < y. After the first iteration, there are two more further iterations, that is, i++ and i < y. So the total for instructions here is 4n.”
“From the fourth line onward (the body of the for loop), for every iteration, the body will run a few more instructions, such as i % 2 and result is 0 and then, based on output, print instruction. Moreover, the print instruction is dependent on the result of a condition that itself depends on the condition of the for loop. So the total for instructions here is 2n (mod and comp) + 2n (concat and print) = 4n. Note that the counting of instructions might not be accurate; we’re doing it to understand the process. For example, string concat might not be a single instruction. Similarly, printing to console also might have multiple instructions. But we’re considering those as one instruction to understand them better.”
“For example, instead of saying the complexity of the preceding algorithm is f(n) = 1 + 3 + 4n + 4n = 4 + 8n, we can simplify it further.”
“f(n) = 4 + 8n, it’s clear that 4 and 8 never change, so by ignoring those, we can conclude f(n) = n. ”
Asymptotic behavior
“those factors that change based on the input. This is what we call asymptotic behavior.”
“Let’s see some examples:
f(n) = 3n + 5 can be considered f(n) = n”
“f(n) = 5 can be considered f(n) = 1
f(n) = n2 + 3n + 5 can be considered f(n) = n2
In simple terms, we can summarize the asymptotic behavior of an algorithm as follows:
Any program that doesn’t have any loop has f(n) = 1.
Any program with one for loop has f(n) = n.
Any program with one nested for loop (for loop inside another for loop) has f(n) = n2.”
https://hackernoon.com/a-code-review-checklist-to-focus-on-the-important-parts-au4f3ykj
https://algs4.cs.princeton.edu/home/
https://github.com/NavalKishor/Books
find the total no of same item pair in an array of n element
fun same_number_of_pair(n: Int, ar: Array<Int>): Int {
//1 1 3 1 2 1 3 3 3 3
var tpc=0
val dupMap=mutableMapOf<Int,Int>()
for (i in ar){
var pci = dupMap[i]?:0
pci++
dupMap[i]= pci
}
for (v in dupMap.values){
var pci=v
val pcimod = pci%2
if(pcimod==0){
tpc+=pci/2
}else{
tpc+=(pci-pcimod)/2
}
}
return tpc
}
Input (stdin)
10
1 1 3 1 2 1 3 3 3 3
Expected Output
4
swift Array Element
public static void swiftArrayElement(swift: Int, input: Array<Int>): Int {
int inputsize=input.length;
System.out.println(Arrays.toString(input));
System.out.println("swift the array by"+swift+"element from end.");
for (int i=0;i<swift;i++){
int k=inputsize-1;
for (int j=k-1;j>=0;j--,k--){
int temp =input[k];
input[k] = input[j];
input[j]=temp;
}
}
for(int i=0;i<inputsize;i++){
System.out.print(input[i]+" ");
}
System.out.println(Arrays.toString(input));
}
Input (stdin)
2
1 2 3 4 5
Expected Output
4 5 1 2 3
Draw pattern like pyramid of number, asterisk and alphabet
simple logic to keep in mind is its a square matrix of NxN order
fun main() {
println("----print * Pyramid----")
val rows=5
for(row in 0..rows){
for(col in row..rows){
print(" ")
}
for(col in 0..row){
print("*")
}
for(col in row downTo 1){
print("*")
}
println()
}
println("----print Asterisk down Pyramid----")
for(row in rows downTo 0){
for(col in row..rows){
print(" ")
}
for(col in 0..row){
print("*")
}
for(col in row downTo 1){
print("*")
}
println()
}
println("----print No Pyramid----")
for(row in 0..rows){
for(col in row..rows){
print(" ")
}
for(col in 0..row){
print("${col+1}")
}
for(col in row downTo 1){
print("${col}")
}
println()
}
println("----print No by 1 space Pyramid----")
for(row in 0..rows){
for(col in row..rows){
print(" ")
}
for(col in 0..row){
print("1 ")
}
println()
}
println("----print Alphabet Pyramid----")
for(row in 0..rows){
for(col in row..rows){
print(" ")
}
for(col in 0..row){
print("${(64+col+1).toChar()}")
}
for(col in row downTo 1){
print("${(64+col).toChar()}")
}
println()
}
println("----print Number incremental order ----")
for(row in 0..rows){
for(col in 0..row){
print("${col+1}")
}
println()
}
println("----print Number decremental order ----")
for(row in rows downTo 0){
for(col in 0..row){
print("${col+1}")
}
println()
}
println("----print Number incremental and decremental order ----")
for(row in rows downTo 0){
for(col in 0..row){
print("${col+1}")
}
for(col in row..rows){
print(" ")
}
for(col in row..rows){
print(" ")
}
for(col in row downTo 0){
print("${col+1}")
}
println()
}
}
output
----print Asterisk Pyramid----
*
***
*****
*******
*********
***********
----print Asterisk down Pyramid----
***********
*********
*******
*****
***
*
----print Number Pyramid----
1
121
12321
1234321
123454321
12345654321
----print No by 1 space Pyramid----
1
1 1
1 1 1
1 1 1 1
1 1 1 1 1
1 1 1 1 1 1
----print Alphabet Pyramid----
A
ABA
ABCBA
ABCDCBA
ABCDEDCBA
ABCDEFEDCBA
----print Number incremental order ----
1
12
123
1234
12345
123456
----print Number decremental order ----
123456
12345
1234
123
12
1
----print Number incremental and decremental order ----
123456 654321
12345 54321
1234 4321
123 321
12 21
1 1
Way You See Way The Thing You Get 