Sorting
What are the 3 N^2 sorting algorithms
Bubble, Selection and Insertion
Stacks use what rule?
First in Last out
Using Masters theorem, what is the time complexity of: T(n)=T(n-1)+lgn
O(nlgn)
How do we know we've reached the end of a list (without tail)
Current node's next is NULL
Binary Search works when the array is
Ascending or descending
Which sorting algo has the most efficient best case?
Insertion sort
Queues use what rule?
First in First Out
Using Masters theorem, what is the time complexity of:T(n)=5T(n-2)+n
O(5(^𝑛/2) 𝑛)
What is the code doing?
Node<T>* p;
while (front!= NULL)
{
p = front;
front = front->next;
delete p;
}
Deleting Nodes from front
Find the output
int key = 1;
switch(key){
case 1:
cout << "key is 1 ";
case 2:
cout << "key is 2 "; break;
case 3:
cout << "key is 3 ";
case 4:
cout << "key is 4 ";
default:
cout << "key is default "; break;
}
key is 1 key is 2
Show the 3rd pass of Bubble Sort : 3,6,9,2,1
2,1,3,6,9
What Functions do Queues primarily use ?
Enqueue,Dequeue, isFull and is Empty
Given this block of Code, What is the Recurrence Relation that represent it:void func1(int x){
if(x>0){
cout<< x<<endl;
cout<< x +5 <<endl;
func1(x-1)
}
}
T(n) = T(n-1) + 3
What is the code doing?
node<T>* p1, *p2;
p1= front1; p2= front2;
while(p1->next != NULL)
{ p1 = p1->next; }
p1->next = p2;
Combining two linked lists
Which function(s) are inline ?
class Restaurant { // Info about a restaurant
public:
void SetName(string restaurantName) { // Sets the restuarant's name
name = restaurantName;
}
void SetRating(int userRating) { // Sets the rating (1-5, with 5 best)
rating = userRating;
}
void Print(); // Prints name and rating on one line
private:
string name;
int rating;
};
void Restaurant::Print() {
cout << name << " -- " << rating << endl;
}
SetName and SetRating
Show the 3rd pass of Insertion Sort of the following array: 9,8,5,4,1
5,8,9,4,1
What functions do Stacks primarily use?
Push,Pop, Isfull and is Empty
Given this block of Code, What is the Recurrence Relation that represent it:void func2(int y){
if(x>0){
for(int i=0;i<y;i++) {
cout<< x +5 <<endl;
}
func1(x-1)
func1(x-1)
}
}
T(n) = 2T(n-1) + 2n +2
What will be the value of “sum” after the following code snippet terminates?
void solve(ListNode* root) {
/* The LinkedList is defined as:
root-> val = value of the node root-> next = address of next element
from the node The List is 1 -> 2 -> 3 -> 4 -> 5 */
int sum = 0;
while (root != NULL) {
sum += root -> val;
root = root -> next;
}
cout << sum << endl;
}
15
Output of the following pseudo code
#include<iostream>
using std::cout using std::endl
int main() {
int count=5
for( count =1; count <= 10; count++ )// loop {
if( count ==5) break
cout << count <<" " }
cout << "\n Out of loop at count = " << count << endl return 0
} // end main
1 2 3 4
Out of loop at count = 5
Show the 3rd pass of selection sort of the following array: 18,5,2,1,13
1,2,5,18,13
Insert a “Helicopter” into a stack and pop the elements, what result do you get ?
Helicopter in reverse
T(n) =T(n−1) +n find T(n) after 4th step
T(n -4)+(n−3) + (n−2) + (n−1) +n
What will be the output of the following code snippet for the list 1->2->3->4->5->6?
void solve(struct node* start) {
if(start == NULL) return;
print("%d ", start->data);
if(start->next != NULL )
solve(start->next->next);
print("%d ", start->data);
}
What
1 3 5 5 3 1
Find the output of cout<< fun(2);
int fun(int n)
{
if (n == 4)
return n
else return 2*fun(n+1)
}
16