BigOh

Question 1

What is log(8) to base 2

Answer 1

its 3
log(8) base 2 = 3 as 2^3 = 8
log2(value) = exponent then 2^exponent = value

Question 2

Binary search runtime

Answer 2

O(log n)

Question 3

Quick sort runtime

Answer 3

O(n log n)

Question 4

Selection sort and few other sorts runtime

Answer 4

O(n^2)

Question 5

Runtime of Complex full search, recursive algorithms that solves a problem of size N

Answer 5

O(2^n)

Question 6

O(n!) runtime example

Answer 6

you are adding a loop for every element like travelling salesman, permutations

Question 7

4 BigOh rules

Answer 7

1. Always think about worst case
2. remove constants
3. remove non dominants
4. if there are multiple inputs user different terms like (n,m,p,q)

Question 8

What are 7 steps for problem solving

Answer 8

1. inputs n outputs
2. bruteforce approach
3. optimised approach
4. modular code
5. test examples
6. error checks n all
7. does input fit in memory- divide n conquer

Complete version

1. Write down the key points at the top
   
   1. data types, input constraints, sorted or unsorted
   2. multiple examples of inputs and outputs covering all scenarios (empty inputs, edge cases, normal cases)
   3. complex and simple examples
2. Start with the naive/brute force approach, discuss it with recruiter, dont code, discuss time and space complexity
3. Find better approach, did we use all information recruiter provided, write down the steps, walk thru the steps with recruiter
4. Write modular code, write important functions
5. Test all the examples, test all the cases (edge cases), walk thru the code with recruiter
6. Bullet proof the code, add error checks n all
7. In case the input doesnt fit in memory at once follow divide and conquer approach (for scalability)

Question 9

Coding skills

Answer 9

1. use descriptive names
2. separate logically independent code to functions / write modular code, skip some functions by informing interviewer
3. code comments
4. testing
5. discuss tradeoffs of solution