How to analyse a program

Big O notation

Theta notation

Omega notation

 2

 Stacks 

a) Array and linked list implementation of a stack 

create stack()
 isempty()
 push()
 pop()

b) infix to post fix conversion

c) evaluate postfix expression

 1. Check for balanced parentheses in an expression

2, Manage 2 stacks in an array

3. Check palindrome or not

4. Reverse a string

5. Sort stack

6 Get MIN in O(1) time 

7. Find next greater element 

...etc

 2

Recursion analysis using stack frames

Recursion tree

 Analysis of 
factorial problem

Analysis of
fib series

 a) Array and linked list implementation of a queue

create queue()
 isempty()
 insert()
 remove()

b) circular queue

c) double ended queue

 1. Queue using 2 stacks

 2. Sort queue 

 3. Reverse Queue 

...etc

a) linked list

insertFront()
insertAfter()
insertEnd()
DelFirst()
DelEnd()
DeleAfter()

b) Circular linked list

insert()
remove()
stack as CLL
queue as CLL

c) Doubly linked list
setLeft()
setRight()
remove()
removeLeft()
RemoveRight()

35 + problems on  LL

1. Find common node  which is common to both the lists. You are allowed to traverse both the lists only once.
2. delete a node p given in a linked list efficiently .....
3. Find kth element from last
4. Swap Kth node from beginning with Kth node from end in a Linked List
5. Alternating split of a given Singly Linked List
6.  check whether linked list polyndrome or not 
7. pair wise swap
8. delete N nodes after M nodes
9. reverse alternate k nodes
10. Delete alternate nodes of a Linked Listet ...etc

6

7

8

Binary Tree 

Binary Search Tree

Balanced Search Trees

a) Tree terminology 

 b) General tree

 a) expression tree

 b) Binary Tree

 e) Tree traversal

    PreTraversal()

    postTraversal()

    inorderTrav()

a) createtree()

b) setleft()

c) setRight()

d) createTree()

e) disposeTree()

f) FindKey)_

g) findMin()

h) findMax()

35 + problems on trees

1. Find number of full nodes  in a tree. 
2. Function to return 1 if there exists a path from the root to a leaf whose values sum is S      otherwise ...etc

3

3

1

 10

11

 Sorting

Array interview questions1

 Bubble sort
Insertion sort
Quick sort
Merge sort
Heap sort
Priority queue

Related to sorting

1.  given a binary digits like 001101 arrange the numbers such that zeroes should follow 1s ike 0001111.

 2

1

 12

 Searching

Linear Search
Binary search

1. Sorted array with duplicates write a function that returns the lowest index of an element x in that array
2.  ... etc

13

Hashing

Open Hashing

Closed hashing

linear probing

14

TRIES

15

Suffix trees

16

Ternary Search Tree

17

Tournament Tree

18

B Tree

19

Divide and Conquer

Merge Sort

Quick Sort

20

Graphs