Programming
Uploaded by
ABCUSER1Programming
Uploaded by
ABCUSER1In programming, data types and operators are fundamental concepts that form the foundation of
creating efficient programs.
1. Data Types:
Data types define the type of data a variable can store, and they determine the operations that can be
performed on those variables. There are two main categories of data types:
Primitive Data Types:
These are the most basic types that serve as the building blocks for more complex data types:
• Integer (int): Represents whole numbers, e.g., 1, -5, 42.
• Float (float): Represents decimal numbers or real numbers, e.g., 3.14, -7.5.
• Character (char): Represents a single character, e.g., 'a', 'B', '9'.
• Boolean (bool): Represents truth values, typically true or false.
• String (string): Represents a sequence of characters (often used for text), e.g., "hello", "1234".
Derived Data Types:
These are based on primitive types and are more complex:
• Array: A collection of variables of the same type, e.g., int arr[5] to store 5 integers.
• Pointer: A variable that stores the memory address of another variable.
• Structure (struct): A user-defined data type that groups different data types together, e.g., to
represent a student with name, age, and marks.
• Union: Similar to structure, but it allows multiple data types to share the same memory
location.
Abstract Data Types (ADTs):
These are higher-level data types defined by the programmer that are not built into the language but
are implemented via classes and operations:
• List
• Queue
• Stack
• Tree
• Graph
2. Operators:
Operators perform operations on variables and values. They can be categorized into several types:
Arithmetic Operators:
Used to perform mathematical operations:
• + (addition)
• - (subtraction)
• * (multiplication)
• / (division)
• % (modulus, remainder)
Relational Operators:
Used to compare values:
• == (equal to)
• != (not equal to)
• > (greater than)
• < (less than)
• >= (greater than or equal to)
• <= (less than or equal to)
Logical Operators:
Used to perform logical operations:
• && (AND)
• || (OR)
• ! (NOT)
Assignment Operators:
Used to assign values to variables:
• = (simple assignment)
• +=, -=, *=, /=, %= (compound assignment)
Bitwise Operators:
Used to perform operations at the bit level:
• & (AND)
• | (OR)
• ^ (XOR)
• ~ (NOT)
• << (left shift)
• >> (right shift)
Increment/Decrement Operators:
Used to increment or decrement the value of a variable by 1:
• ++ (increment)
• -- (decrement)
Conditional (Ternary) Operator:
Used for concise conditional expressions:
• ? : (If condition is true, do X, else do Y)
Comma Operator:
Used to separate expressions, often for executing multiple statements in a single line:
• ,
Sizeof Operator:
Returns the size (in bytes) of a data type or variable:
• sizeof(type)
Pointer Operators:
• & (address-of operator, gets the memory address of a variable)
• * (dereference operator, accesses the value at a memory address)
These are the core concepts related to data types and operators in programming. Let me know if you'd
like to dive deeper into any specific area!
Certainly! Let's dive deeper into Data Types and Operators.
1. Data Types
In programming, data types are important because they define the nature of the data that a variable can
hold. Data types allow you to understand how much memory the variable will occupy and the operations
that can be performed on it.
A. Primitive Data Types:
These are the basic data types provided by most programming languages.
1. Integer (int):
o Description: Represents whole numbers without fractional parts.
o Size: Typically 4 bytes (32 bits), but can vary based on the system (16-bit or 64-bit).
o Examples: 0, -5, 42, 1000
o Operations: Addition, subtraction, multiplication, division, comparison, etc.
CopyEdit
int a = 10; // integer declaration
2. Floating Point (float, double):
o Description: Used for representing real numbers (i.e., numbers with a fractional part).
▪ float: Single precision (typically 32 bits, 4 bytes).
▪ double: Double precision (typically 64 bits, 8 bytes).
o Examples: 3.14, -0.001, 42.0
o Operations: Arithmetic operations (addition, multiplication, etc.), comparison, etc.
CopyEdit
float a = 3.14f; // Single precision floating point
double b = 3.141592653589793; // Double precision floating point
3. Character (char):
o Description: Represents a single character or symbol, typically stored as an integer
value.
o Size: Usually 1 byte (8 bits).
o Examples: 'a', 'A', '9', '$', '!'
o Operations: You can perform arithmetic with characters (since they are often
represented by ASCII values).
CopyEdit
char ch = 'A'; // character declaration
4. Boolean (bool):
o Description: Represents truth values, typically only true or false.
o Size: 1 byte (8 bits) in most systems.
o Examples: true, false
o Operations: Logical operations like AND, OR, NOT.
CopyEdit
bool isValid = true; // boolean declaration
5. String (string):
o Description: Represents a sequence of characters, often used for text data. In languages
like C, strings are arrays of char. In languages like Python or Java, strings are objects.
o Examples: "Hello", "123", "John Doe"
o Operations: Concatenation, substring extraction, length calculation, etc.
CopyEdit
char name[] = "Alice"; // string in C (array of chars)
B. Derived Data Types:
Derived types are built using primitive data types. They allow for more complex data structures.
1. Array:
o Description: A collection of elements, all of the same data type. The elements are stored
in contiguous memory locations.
o Examples: int arr[5] = {1, 2, 3, 4, 5};
o Operations: Access elements by index, iterate through arrays.
CopyEdit
int arr[5] = {1, 2, 3, 4, 5}; // array of integers
2. Pointer:
o Description: A variable that stores the memory address of another variable. Pointers are
used for dynamic memory allocation, arrays, and function arguments.
o Operations: Dereferencing (using *), address-of (using &), pointer arithmetic.
c
CopyEdit
int x = 10;
int* ptr = &x; // pointer to an integer
3. Structure (struct):
o Description: A user-defined data type that groups different types of data (variables)
together.
o Examples: A struct could represent a student with name, age, and marks.
CopyEdit
struct Student {
char name[50];
int age;
float marks;
};
4. Union:
o Description: A data structure similar to struct, but all members share the same memory
location. This means only one member can hold a value at any given time, saving
memory.
CopyEdit
union Data {
int i;
float f;
char str[20];
};
C. Abstract Data Types (ADTs):
ADTs are higher-level types that are typically implemented using structures, classes, or functions. They
describe operations on the data, and users don’t need to worry about the underlying implementation.
1. List: A collection of items where each item is ordered. You can access elements by index.
2. Stack: A collection where the last element added is the first one removed (LIFO: Last In First
Out).
3. Queue: A collection where the first element added is the first one removed (FIFO: First In First
Out).
4. Tree: A hierarchical structure consisting of nodes. Common in representing data with hierarchical
relationships.
5. Graph: A collection of nodes (vertices) connected by edges, used to represent complex
relationships.
2. Operators
Operators are symbols that perform operations on variables and values. They help manipulate data and
variables.
A. Arithmetic Operators:
Used for mathematical calculations.
• + : Addition (e.g., a + b)
• - : Subtraction (e.g., a - b)
• * : Multiplication (e.g., a * b)
• / : Division (e.g., a / b)
• % : Modulus (returns remainder of division, e.g., a % b)
CopyEdit
int a = 10, b = 3;
int sum = a + b; // sum = 13
int mod = a % b; // mod = 1
B. Relational Operators:
Used for comparing values.
• == : Equal to
• != : Not equal to
• > : Greater than
• < : Less than
• >= : Greater than or equal to
• <= : Less than or equal to
CopyEdit
if (a > b) { // check if a is greater than b
// do something
C. Logical Operators:
Used to perform logical operations, especially in conditionals.
• && : Logical AND (both conditions must be true)
• || : Logical OR (either condition must be true)
• ! : Logical NOT (inverts the condition)
CopyEdit
if (a > 5 && b < 10) { // both conditions must be true
// do something
D. Assignment Operators:
Used to assign values to variables. They include compound operators.
• = : Simple assignment
• += : Add and assign (e.g., a += b is equivalent to a = a + b)
• -= : Subtract and assign
• *= : Multiply and assign
• /= : Divide and assign
• %= : Modulo and assign
CopyEdit
a += 5; // a = a + 5
b *= 2; // b = b * 2
E. Increment and Decrement Operators:
Used to increase or decrease a variable’s value by 1.
• ++ : Increment (e.g., a++ or ++a)
• -- : Decrement (e.g., a-- or --a)
CopyEdit
a++; // increment a by 1
b--; // decrement b by 1
F. Bitwise Operators:
Perform operations on binary numbers at the bit level.
• & : AND
• | : OR
• ^ : XOR (exclusive OR)
• ~ : NOT (inverts all bits)
• << : Left shift
• >> : Right shift
CopyEdit
int a = 5; // binary 0101
int b = a << 1; // b = 1010 (shift left)
G. Conditional (Ternary) Operator:
A shorthand for if-else conditions.
• Syntax: condition ? expression_if_true : expression_if_false;
CopyEdit
int max = (a > b) ? a : b; // returns a if a > b, otherwise b
H. Sizeof Operator:
Returns the size (in bytes) of a data type or variable.
c
CopyEdit
printf("Size of int: %zu\n", sizeof(int)); // prints the size of int
I. Pointer Operators:
• & : Address-of operator (returns the memory address of a variable).
• * : Dereference operator (accesses the value at the memory address).
CopyEdit
int a = 5;
int* ptr = &a; // ptr stores the address of a
printf("%d", *ptr); // dereference to get the value of a
These detailed explanations cover all essential data types and operators in programming. Let me know if
you need more information or examples!
Control Flow Statements are constructs that dictate the order in which instructions in a program are
executed. They enable decision-making, looping, and branching, allowing programs to handle different
situations dynamically.
Types of Control Flow Statements
1. Decision-Making Statements
2. Looping (Iteration) Statements
3. Jump Statements
1. Decision-Making Statements
These statements allow the program to execute certain parts of the code based on conditions.
A. if Statement
• Executes a block of code if a given condition evaluates to true.
Syntax:
c
CopyEdit
if (condition) {
// code to execute if condition is true
Example:
CopyEdit
int x = 10;
if (x > 5) {
printf("x is greater than 5\n");
B. if-else Statement
• Executes one block of code if the condition is true and another block if the condition is false.
Syntax:
CopyEdit
if (condition) {
// code if condition is true
} else {
// code if condition is false
Example:
CopyEdit
int x = 10;
if (x % 2 == 0) {
printf("x is even\n");
} else {
printf("x is odd\n");
C. if-else-if Ladder
• Tests multiple conditions sequentially. The first true condition's block is executed.
Syntax:
CopyEdit
if (condition1) {
// code if condition1 is true
} else if (condition2) {
// code if condition2 is true
} else {
// code if all conditions are false
Example:
CopyEdit
int marks = 85;
if (marks >= 90) {
printf("Grade: A\n");
} else if (marks >= 75) {
printf("Grade: B\n");
} else {
printf("Grade: C\n");
D. Nested if
• An if statement inside another if statement.
Example:
c
CopyEdit
int a = 10, b = 20;
if (a > 5) {
if (b > 15) {
printf("a is greater than 5 and b is greater than 15\n");
E. switch Statement
• Allows multiple conditional branches based on the value of a variable. Ideal for checking discrete
values.
Syntax:
CopyEdit
switch (expression) {
case value1:
// code for value1
break;
case value2:
// code for value2
break;
default:
// code if none of the cases match
Example:
CopyEdit
int day = 3;
switch (day) {
case 1:
printf("Monday\n");
break;
case 2:
printf("Tuesday\n");
break;
case 3:
printf("Wednesday\n");
break;
default:
printf("Invalid day\n");
2. Looping (Iteration) Statements
Loops allow the execution of a block of code multiple times.
A. for Loop
• Repeats a block of code for a known number of iterations.
Syntax:
CopyEdit
for (initialization; condition; increment/decrement) {
// code to execute
Example:
CopyEdit
for (int i = 0; i < 5; i++) {
printf("i = %d\n", i);
B. while Loop
• Repeats a block of code while a condition is true. The condition is checked before the loop
executes.
Syntax:
CopyEdit
while (condition) {
// code to execute
Example:
CopyEdit
int i = 0;
while (i < 5) {
printf("i = %d\n", i);
i++;
C. do-while Loop
• Similar to while, but the loop executes at least once because the condition is checked after
execution.
Syntax:
CopyEdit
do {
// code to execute
} while (condition);
Example:
CopyEdit
int i = 0;
do {
printf("i = %d\n", i);
i++;
} while (i < 5);
D. Nested Loops
• A loop inside another loop.
Example:
CopyEdit
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 2; j++) {
printf("i = %d, j = %d\n", i, j);
3. Jump Statements
These statements alter the normal flow of execution by transferring control to another part of the code.
A. break Statement
• Exits the nearest enclosing loop or switch statement.
Example:
CopyEdit
for (int i = 0; i < 5; i++) {
if (i == 3) {
break;
printf("i = %d\n", i);
B. continue Statement
• Skips the current iteration of the loop and proceeds to the next iteration.
Example:
CopyEdit
for (int i = 0; i < 5; i++) {
if (i == 3) {
continue;
printf("i = %d\n", i);
C. return Statement
• Exits a function and optionally returns a value.
Example:
CopyEdit
int add(int a, int b) {
return a + b;
D. goto Statement
• Transfers control to a labeled statement. Use is generally discouraged due to readability and
maintainability concerns.
Syntax:
CopyEdit
goto label;
label:
// code to execute
Example:
c
CopyEdit
int i = 0;
loop:
if (i < 5) {
printf("i = %d\n", i);
i++;
goto loop;
Comparison of Loops
Feature for Loop while Loop do-while Loop
Condition Check Before loop execution Before loop execution After loop execution
Use Case Known iterations Unknown iterations Execute at least once
Example Iterating over arrays Waiting for user input Menu-driven programs
Control flow statements are essential for designing dynamic and interactive programs. Let me know if
you'd like deeper examples or specific applications of any of these!
Here is a more detailed explanation of functions and storage classes, tailored for GATE-level
preparation. This version expands on concepts, examples, and GATE-related insights.
Functions
A function is a reusable block of code designed to perform a specific task. It is a fundamental
programming concept used to modularize code, enhance readability, and reduce redundancy.
1. Components of a Function
1. Return Type
o Specifies the type of value the function will return (e.g., int, float, void for no return
value).
o Functions can return single values, pointers, or structures.
Example:
CopyEdit
int sum(int a, int b); // Return type: int
2. Function Name
o Identifies the function uniquely in the program.
3. Parameters (Arguments)
o Input values passed to the function.
o Can be of any data type, including arrays and pointers.
4. Function Body
o Contains the code that defines the function's task.
5. Return Statement
o Sends a value back to the calling function.
o If the return type is void, the return statement can be omitted or written as return;.
2. Types of Functions
1. Library Functions (Predefined)
o Provided by standard libraries (e.g., <stdio.h>, <math.h>).
o Examples: printf(), scanf(), sqrt(), etc.
2. User-Defined Functions
o Created by programmers to perform custom tasks.
Example:
CopyEdit
float multiply(float x, float y) {
return x * y;
}
3. Function Declaration (Prototype)
• Introduces the function to the compiler before its usage.
• Ensures the compiler knows about the function's name, return type, and parameters.
• Helps in cases where the function definition appears after the main() function.
Syntax:
CopyEdit
return_type function_name(parameters);
Example:
CopyEdit
int add(int, int); // Function prototype
4. Function Definition
• Specifies the function’s actual implementation.
Syntax:
CopyEdit
return_type function_name(parameters) {
// Function body
Example:
CopyEdit
int add(int a, int b) {
return a + b;
}
5. Function Call
• Invokes the function to execute its code.
Syntax:
CopyEdit
function_name(arguments);
Example:
CopyEdit
int result = add(3, 5); // Function call
6. Parameter Passing Techniques
1. Call by Value
o A copy of the argument is passed to the function.
o Changes made inside the function do not affect the original variable.
Example:
CopyEdit
void change(int x) {
x = 10;
int main() {
int a = 5;
change(a);
printf("%d", a); // Output: 5
2. Call by Reference
o The address of the argument is passed to the function.
o Changes made inside the function affect the original variable.
Example:
CopyEdit
void change(int *x) {
*x = 10;
int main() {
int a = 5;
change(&a);
printf("%d", a); // Output: 10
7. Recursion
Recursion is a technique where a function calls itself.
• Base Case: Stops the recursion.
• Recursive Case: The condition under which the function calls itself.
Advantages:
• Simplifies problems like factorial, Fibonacci, and tree traversals.
Disadvantages:
• Can lead to stack overflow if the base case is missing.
Example:
CopyEdit
int factorial(int n) {
if (n == 0)
return 1; // Base case
return n * factorial(n - 1); // Recursive case
}
GATE Focus:
• Understand recursion’s time complexity and space usage (stack memory).
8. Inline Functions
• Inline functions suggest to the compiler to replace the function call with the function body,
improving performance for small functions.
• Mostly applicable in C++ (inline keyword).
Storage Classes
Storage classes define scope, visibility, lifetime, and default initialization of variables.
1. Types of Storage Classes
A. Automatic (auto)
• Default for variables declared inside a function.
• Scope: Local to the block.
• Lifetime: Exists until the block ends.
• Initialization: Garbage value (if not explicitly initialized).
Example:
CopyEdit
void test() {
auto int x = 10; // auto is implicit
printf("%d\n", x);
B. External (extern)
• Declares a global variable accessible across multiple files.
• Scope: Global.
• Lifetime: Program lifetime.
• Initialization: Default to 0.
Example:
CopyEdit
extern int x; // Declaration
int x = 10; // Definition
C. Static
• Retains its value across function calls.
• Scope: Local to the block where declared.
• Lifetime: Program lifetime.
• Initialization: Default to 0.
Example:
CopyEdit
void counter() {
static int count = 0; // Retains value
count++;
printf("%d\n", count);
D. Register
• Hints the compiler to store the variable in a CPU register for faster access.
• Scope: Local to the block.
• Lifetime: Exists until the block ends.
• Initialization: Garbage value.
Example:
CopyEdit
void test() {
register int i = 5; // Stored in register if possible
printf("%d\n", i);
2. Key Differences Between Storage Classes
Storage Class Scope Lifetime Default Value Keyword
auto Local Block Garbage value auto
extern Global Program lifetime 0 extern
static Local (or global) Program lifetime 0 static
register Local Block Garbage value register
GATE-Specific Focus
1. Function-Related Topics:
o Recursive functions: Analyze time complexity and trace outputs.
o Parameter passing: Focus on call by value vs call by reference.
o Static variables: Understand value retention across function calls.
2. Storage Classes:
o How variables behave inside and outside functions.
o Questions on default initialization, scope, and lifetime.
o Usage of extern across files.
3. Expected Question Types:
o Predicting program outputs.
o Identifying syntax errors or undefined behavior.
o Understanding the effects of scope and lifetime on variables.
Functions: Practice Questions
Q1: Predict the Output
c
CopyEdit
#include <stdio.h>
int compute(int x, int y) {
if (y == 0)
return 0;
else
return x + compute(x, y - 1);
int main() {
int result = compute(5, 3);
printf("%d\n", result);
return 0;
Solution:
• This is a recursive function that calculates x * y by repeated addition.
• The function reduces y by 1 in each recursive call until it reaches 0.
• Calculation:
o compute(5, 3) → 5 + compute(5, 2)
o compute(5, 2) → 5 + compute(5, 1)
o compute(5, 1) → 5 + compute(5, 0)
o compute(5, 0) → 0
Output: 15
Q2: What will be the output of the following program?
CopyEdit
#include <stdio.h>
void recursiveFunction(int n) {
if (n > 0) {
printf("%d ", n);
recursiveFunction(n - 1);
printf("%d ", n);
int main() {
recursiveFunction(3);
return 0;
Solution:
• The function first prints n and calls itself with n - 1.
• After returning from the recursive call, it prints n again.
• Execution:
o Call: recursiveFunction(3) → Prints 3, calls recursiveFunction(2)
o Call: recursiveFunction(2) → Prints 2, calls recursiveFunction(1)
o Call: recursiveFunction(1) → Prints 1, calls recursiveFunction(0)
o recursiveFunction(0) does nothing and returns.
o Prints 1 2 3 as the recursion unwinds.
Output: 3 2 1 1 2 3
Q3: Error Identification
CopyEdit
#include <stdio.h>
int add(int a, int b) {
return a + b;
void main() {
int result = add(5, 6);
printf("%d\n", result);
Solution:
• The main() function is declared as void, which is invalid in standard C.
• It should be declared as int main() with a return 0; at the end.
Correct Code:
CopyEdit
int main() {
int result = add(5, 6);
printf("%d\n", result);
return 0;
Q4: Tricky Recursion
CopyEdit
#include <stdio.h>
int fun(int n) {
if (n == 0)
return 1;
return n * fun(n / 2);
}
int main() {
printf("%d\n", fun(10));
return 0;
Solution:
• The recursion calculates the product of n and the result of fun(n/2) until n becomes 0.
• The sequence of calls is:
o fun(10) → 10 * fun(5)
o fun(5) → 5 * fun(2)
o fun(2) → 2 * fun(1)
o fun(1) → 1 * fun(0)
o fun(0) → 1 (base case)
Output: 10 * 5 * 2 * 1 = 100
Storage Classes: Practice Questions
Q5: Predict the Output
CopyEdit
#include <stdio.h>
void counter() {
static int count = 0;
count++;
printf("%d ", count);
}
int main() {
counter();
counter();
counter();
return 0;
Solution:
• The static variable count retains its value across function calls.
• Execution:
o First call: count = 0 → count++ → count = 1
o Second call: count = 1 → count++ → count = 2
o Third call: count = 2 → count++ → count = 3
Output: 1 2 3
Q6: Scope of Variables
CopyEdit
#include <stdio.h>
int x = 10; // Global variable
void display() {
int x = 20; // Local variable
printf("%d ", x);
int main() {
display();
printf("%d\n", x);
return 0;
Solution:
• The global variable x is 10.
• Inside display(), the local variable x shadows the global variable.
• Execution:
o display() prints the local x = 20.
o main() prints the global x = 10.
Output: 20 10
Q7: Use of extern
CopyEdit
#include <stdio.h>
int x = 5; // Global variable
void modify() {
extern int x;
x = 10; // Modifies the global variable
int main() {
printf("%d ", x);
modify();
printf("%d\n", x);
return 0;
Solution:
• The extern keyword in modify() refers to the global variable x.
• Execution:
o Before modify(): x = 5
o After modify(): x = 10
Output: 5 10
Q8: Register Variables
CopyEdit
#include <stdio.h>
void test() {
register int i = 10; // Stored in a CPU register (if possible)
printf("%d\n", i);
int main() {
test();
return 0;
Solution:
• The variable i is declared as register. While the compiler attempts to store it in a register, this
doesn’t affect program behavior.
Output: 10
Pointers
1. Pointer Basics
A pointer is a variable that stores the memory address of another variable. It enables efficient
manipulation of arrays, dynamic memory, and function arguments.
Declaration Syntax:
CopyEdit
data_type *pointer_name;
Example:
CopyEdit
int x = 10;
int *p = &x; // 'p' stores the address of variable 'x'
2. Pointer Operators
• Address-of operator (&): Returns the address of a variable.
CopyEdit
int x = 10;
int *p = &x; // p stores the address of x
• Dereference operator (*): Accesses the value stored at the memory address held by the pointer.
CopyEdit
printf("%d\n", *p); // Outputs the value of x (10)
3. Types of Pointers
1. Null Pointer: A pointer that points to nothing (NULL).
CopyEdit
int *p = NULL;
2. Dangling Pointer: A pointer that references memory which has been deallocated.
3. Void Pointer: A generic pointer that can store the address of any type.
c
CopyEdit
void *ptr;
int x = 10;
ptr = &x;
4. Function Pointer: A pointer that stores the address of a function.
CopyEdit
void (*func_ptr)() = &some_function;
4. Pointer Arithmetic
Pointer arithmetic involves operations on pointers, which are relative to the size of the data type.
Example:
CopyEdit
int arr[] = {10, 20, 30};
int *p = arr; // Points to arr[0]
printf("%d\n", *(p + 1)); // Outputs 20 (arr[1])
Operations:
• Increment (p++): Moves to the next memory location.
• Decrement (p--): Moves to the previous memory location.
• Addition/Subtraction (p + n, p - n): Adjusts the pointer by n memory locations.
5. Pointers and Arrays
Pointers are closely related to arrays; the array name itself acts as a pointer to its first element.
Example:
CopyEdit
int arr[] = {1, 2, 3};
int *p = arr; // Points to arr[0]
printf("%d\n", *(p + 2)); // Outputs 3 (arr[2])
6. Dynamic Memory Allocation
Memory can be allocated and managed at runtime using malloc, calloc, realloc, and free:
1. malloc(): Allocates memory without initializing.
CopyEdit
int *p = (int *)malloc(5 * sizeof(int)); // Allocates space for 5 integers
2. calloc(): Allocates and initializes memory to zero.
CopyEdit
int *p = (int *)calloc(5, sizeof(int)); // Initializes 5 integers to 0
3. free(): Deallocates memory to prevent memory leaks.
CopyEdit
free(p);
4. realloc(): Resizes an allocated memory block.
CopyEdit
p = (int *)realloc(p, 10 * sizeof(int)); // Resizes memory for 10 integers
7. Pointers to Pointers
A pointer can store the address of another pointer.
Example:
CopyEdit
int x = 10;
int *p = &x;
int **q = &p; // 'q' points to the address of 'p'
printf("%d\n", **q); // Outputs 10
8. Passing Pointers to Functions
Passing pointers allows functions to modify variables outside their scope.
Example:
CopyEdit
void modify(int *p) {
*p = 20;
int main() {
int x = 10;
modify(&x);
printf("%d\n", x); // Outputs 20
return 0;
Strings
Strings in C are character arrays terminated by a null character (\0).
1. String Declaration
1. Character Array:
CopyEdit
char str[6] = "Hello"; // Includes null terminator '\0'
2. Pointer to String:
CopyEdit
char *str = "Hello"; // Pointer to string literal
2. String Input and Output
1. Using scanf and printf:
CopyEdit
char str[50];
scanf("%s", str); // Reads input until a space
printf("%s\n", str);
2. Using gets and puts:
CopyEdit
char str[50];
gets(str); // Reads input including spaces (deprecated)
puts(str); // Outputs string with a newline
3. String Functions (<string.h>)
Function Description Example
Returns the length of the string
strlen(str) strlen("Hello") → 5
(excluding \0).
strcpy(dest,
Copies src into dest. strcpy(dest, "World")
src)
strcat(dest,
Appends src to dest. strcat(dest, "World")
src)
strcmp(s1, s2) Compares s1 and s2. strcmp("abc", "xyz") → Negative value
strchr(str, ch) Finds the first occurrence of ch in str. strchr("Hello", 'e') → Pointer to 'e'
strstr("Hello World", "World") → Pointer to
strstr(s1, s2) Finds the first occurrence of s2 in s1.
"World"
4. Strings and Pointers
Strings can be manipulated using pointers for flexibility and performance.
Example:
CopyEdit
char str[] = "Hello";
char *p = str;
while (*p != '\0') {
printf("%c", *p);
p++;
5. Common Operations
1. Reversing a String:
CopyEdit
void reverse(char *str) {
int len = strlen(str);
for (int i = 0; i < len / 2; i++) {
char temp = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = temp;
2. Checking Palindrome:
CopyEdit
int isPalindrome(char *str) {
int len = strlen(str);
for (int i = 0; i < len / 2; i++) {
if (str[i] != str[len - i - 1])
return 0;
return 1;
3. Counting Vowels:
CopyEdit
int countVowels(char *str) {
int count = 0;
while (*str != '\0') {
if (*str == 'a' || *str == 'e' || *str == 'i' || *str == 'o' || *str == 'u')
count++;
str++;
return count;
6. Common GATE Topics
1. String manipulation using pointers.
2. Differences between char array and char pointer.
3. Implementation of string functions (strlen, strcpy, etc.).
4. String reversal and palindrome check.
5. Dynamic memory allocation for strings.
Advanced Topics in Pointers
1. Pointer-to-Pointer Operations
Pointers to pointers are commonly used when dealing with multi-dimensional arrays, linked lists, or
dynamic memory allocation.
Example:
CopyEdit
#include <stdio.h>
int main() {
int x = 100;
int *p = &x; // p points to x
int **q = &p; // q points to p
printf("Value of x: %d\n", **q); // Outputs: 100
return 0;
2. Multi-Dimensional Arrays and Pointers
A 2D array is treated as an array of arrays, and pointers can access its elements.
Example:
CopyEdit
#include <stdio.h>
int main() {
int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
int (*p)[3] = arr; // p points to an array of 3 integers
printf("%d\n", *(*(p + 1) + 2)); // Access arr[1][2] → Outputs: 6
return 0;
3. Function Pointers
Function pointers store the address of a function and allow dynamic invocation.
Example:
c
CopyEdit
#include <stdio.h>
void greet() {
printf("Hello, GATE Aspirant!\n");
int main() {
void (*func_ptr)() = greet; // Pointer to the greet function
func_ptr(); // Invoke the function using the pointer
return 0;
Application: Useful for callback mechanisms or dynamic dispatch.
Advanced Topics in Strings
1. Dynamic String Manipulation
Using pointers with dynamically allocated strings allows efficient memory use.
Example:
CopyEdit
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char *str = (char *)malloc(20 * sizeof(char));
strcpy(str, "Dynamic String");
printf("%s\n", str); // Outputs: Dynamic String
free(str); // Release memory
return 0;
2. Implementing Custom String Functions
Reimplementing standard string functions helps solidify concepts.
Custom strlen Implementation:
CopyEdit
int custom_strlen(const char *str) {
int length = 0;
while (*str != '\0') {
length++;
str++;
return length;
Custom strcpy Implementation:
CopyEdit
void custom_strcpy(char *dest, const char *src) {
while ((*dest++ = *src++) != '\0');
Custom strcmp Implementation:
CopyEdit
int custom_strcmp(const char *s1, const char *s2) {
while (*s1 && (*s1 == *s2)) {
s1++;
s2++;
}
return *(unsigned char *)s1 - *(unsigned char *)s2;
Sample Problems for Practice
Problem 1: Pointer Arithmetic
What will the following code output?
CopyEdit
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40};
int *p = arr;
printf("%d %d\n", *p, *(p + 3));
return 0;
Solution:
• *p gives the first element of the array (10).
• *(p + 3) gives the fourth element (40).
Output: 10 40
Problem 2: Dangling Pointer
What is wrong with the following code?
CopyEdit
#include <stdio.h>
int *getAddress() {
int x = 10;
return &x;
}
int main() {
int *p = getAddress();
printf("%d\n", *p); // Undefined behavior
return 0;
Solution:
The function returns the address of a local variable (x), which gets destroyed when the function exits.
This results in a dangling pointer.
Problem 3: Strings and Pointers
Predict the output:
CopyEdit
#include <stdio.h>
#include <string.h>
int main() {
char str1[20] = "GATE";
char str2[] = "2025";
strcat(str1, str2);
printf("%s\n", str1);
return 0;
Solution:
• strcat(str1, str2) appends str2 ("2025") to str1 ("GATE").
Output: GATE2025
Problem 4: Reversing a String
Write a program to reverse a string using pointers.
Solution:
CopyEdit
#include <stdio.h>
#include <string.h>
void reverseString(char *str) {
char *start = str;
char *end = str + strlen(str) - 1;
char temp;
while (start < end) {
temp = *start;
*start = *end;
*end = temp;
start++;
end--;
int main() {
char str[] = "GATE2025";
reverseString(str);
printf("%s\n", str); // Outputs: 5202ETAG
return 0;
Problem 5: Palindrome Check
Check whether a string is a palindrome.
Solution:
CopyEdit
#include <stdio.h>
#include <string.h>
int isPalindrome(const char *str) {
const char *start = str;
const char *end = str + strlen(str) - 1;
while (start < end) {
if (*start != *end) {
return 0; // Not a palindrome
start++;
end--;
return 1; // Palindrome
int main() {
char str[] = "madam";
if (isPalindrome(str)) {
printf("Palindrome\n");
} else {
printf("Not a Palindrome\n");
return 0;
}
Problem 6: Function Pointers
Write a program to use function pointers for arithmetic operations.
Solution:
CopyEdit
#include <stdio.h>
int add(int a, int b) { return a + b; }
int multiply(int a, int b) { return a * b; }
int main() {
int (*operation)(int, int); // Declare a function pointer
operation = add;
printf("Sum: %d\n", operation(5, 10)); // Outputs: 15
operation = multiply;
printf("Product: %d\n", operation(5, 10)); // Outputs: 50
return 0;
Problem 7: Double Pointer with Dynamic Memory
Write a program to dynamically allocate a 2D array using double pointers.
Solution:
CopyEdit
#include <stdio.h>
#include <stdlib.h>
int main() {
int rows = 3, cols = 3;
int **arr = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
arr[i] = (int *)malloc(cols * sizeof(int));
// Initialize and print the 2D array
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
arr[i][j] = i + j;
printf("%d ", arr[i][j]);
printf("\n");
// Free memory
for (int i = 0; i < rows; i++) {
free(arr[i]);
free(arr);
return 0;
1. Dynamic Memory Allocation Problems
Dynamic memory allocation allows for the creation of memory blocks at runtime. Here are some
common examples and problems using malloc, calloc, realloc, and free.
Problem 1: Allocating a 1D Array Dynamically
Write a program that takes input from the user for n elements, dynamically allocates memory, stores the
elements, and prints them.
Solution:
CopyEdit
#include <stdio.h>
#include <stdlib.h>
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
// Dynamically allocate memory for n integers
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1;
// Input elements
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
// Print elements
printf("Entered elements are:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
// Free the dynamically allocated memory
free(arr);
return 0;
Problem 2: Allocating a 2D Array Dynamically
Write a program that dynamically allocates memory for a 2D array (matrix) and fills it with user input.
Then, print the matrix.
Solution:
CopyEdit
#include <stdio.h>
#include <stdlib.h>
int main() {
int rows, cols;
printf("Enter number of rows and columns: ");
scanf("%d %d", &rows, &cols);
// Dynamically allocate memory for 2D array (matrix)
int **matrix = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
matrix[i] = (int *)malloc(cols * sizeof(int));
}
// Input elements
printf("Enter elements of the matrix:\n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
scanf("%d", &matrix[i][j]);
// Print the matrix
printf("Matrix is:\n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
printf("%d ", matrix[i][j]);
printf("\n");
// Free the dynamically allocated memory
for (int i = 0; i < rows; i++) {
free(matrix[i]);
free(matrix);
return 0;
Problem 3: Resizing a Dynamically Allocated Array
Write a program that resizes a dynamically allocated array using realloc and then prints the elements.
Solution:
CopyEdit
#include <stdio.h>
#include <stdlib.h>
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
// Dynamically allocate memory
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1;
// Input elements
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
// Resize the array
printf("Enter the new size of the array: ");
scanf("%d", &n);
arr = (int *)realloc(arr, n * sizeof(int));
if (arr == NULL) {
printf("Memory reallocation failed!\n");
return 1;
// Input new elements
printf("Enter %d more elements:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
// Print the elements
printf("The elements are:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
// Free the dynamically allocated memory
free(arr);
return 0;
2. Multi-Dimensional Array Pointers
Problem 1: Accessing Elements of a 2D Array Using Pointers
Write a program to access the elements of a 2D array using a pointer to pointer.
Solution:
CopyEdit
#include <stdio.h>
int main() {
int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
int (*p)[3] = arr; // Pointer to an array of 3 integers
// Accessing array elements using the pointer
printf("Element at [0][0]: %d\n", *(*(p + 0) + 0)); // 1
printf("Element at [1][2]: %d\n", *(*(p + 1) + 2)); // 6
return 0;
Problem 2: Pointer to a Pointer with 2D Array
Write a program to print elements of a 2D array using pointer-to-pointer notation.
Solution:
CopyEdit
#include <stdio.h>
int main() {
int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
int *ptr = &arr[0][0]; // Pointer to the first element
// Print the elements using pointer-to-pointer
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
printf("%d ", *(ptr + i * 3 + j));
printf("\n");
}
return 0;
3. Custom String Operations
Problem 1: Implementing strcat Function
Write a function my_strcat that concatenates two strings and appends the result to the first string.
Solution:
CopyEdit
#include <stdio.h>
void my_strcat(char *dest, const char *src) {
while (*dest != '\0') {
dest++; // Move to the end of the destination string
while (*src != '\0') {
*dest = *src; // Append each character from src to dest
dest++;
src++;
*dest = '\0'; // Null-terminate the resulting string
int main() {
char str1[100] = "Hello, ";
char str2[] = "World!";
my_strcat(str1, str2);
printf("Concatenated String: %s\n", str1); // Outputs: Hello, World!
return 0;
Problem 2: Implementing strchr Function
Write a function my_strchr that finds the first occurrence of a character in a string.
Solution:
CopyEdit
#include <stdio.h>
char *my_strchr(const char *str, char ch) {
while (*str != '\0') {
if (*str == ch) {
return (char *)str; // Return the pointer to the character
str++;
return NULL; // Return NULL if the character is not found
int main() {
char str[] = "Programming";
char *result = my_strchr(str, 'a');
if (result != NULL) {
printf("Found 'a' at position: %ld\n", result - str);
} else {
printf("'a' not found.\n");
}
return 0;
Problem 3: Checking if Two Strings Are Anagrams
Write a program that checks if two strings are anagrams of each other.
Solution:
CopyEdit
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int areAnagrams(char *str1, char *str2) {
int count[256] = {0};
// If lengths are different, they cannot be anagrams
if (strlen(str1) != strlen(str2)) {
return 0;
// Count characters in both strings
for (int i = 0; str1[i] != '\0'; i++) {
count[str1[i]]++;
count[str2[i]]--;
// If counts of all characters are zero, the strings are anagrams
for (int i = 0; i < 256; i++) {
if (count[i] != 0) {
return 0;
return 1;
int main() {
char str1[] = "listen";
char str2[] = "silent";
if (areAnagrams(str1, str2)) {
printf("The strings are anagrams.\n");
} else {
printf("The strings are not anagrams.\n");
return 0;
These problems and examples should help you master dynamic memory, multi-dimensional arrays, and
custom string operations in C, all of which are crucial for the GATE exam.
1. Arrays
An array is a collection of elements stored in contiguous memory locations. Arrays allow random access
using indices.
1.1 Key Properties
• Fixed size: The size is defined at compile time.
• Homogeneous: All elements are of the same data type.
• Random access: Access time for an element is O(1)O(1)O(1).
1.2 Common Operations on Arrays
1. Traversal: Access each element sequentially.
2. Insertion: Add an element at a specific position.
3. Deletion: Remove an element from a specific position.
4. Search: Find the position of a given element.
5. Sorting: Arrange elements in ascending or descending order.
1.3 Example Programs
1. Traversal
CopyEdit
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array elements are:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
2. Insertion
Insert an element x at position pos in the array.
c
CopyEdit
#include <stdio.h>
int main() {
int arr[10] = {1, 2, 3, 4, 5};
int n = 5; // Current number of elements
int x = 99, pos = 3;
// Shift elements to the right
for (int i = n; i >= pos; i--) {
arr[i] = arr[i - 1];
arr[pos - 1] = x; // Insert x at position pos
n++;
printf("Array after insertion:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
3. Deletion
Delete the element at position pos from the array.
CopyEdit
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = 5, pos = 3;
// Shift elements to the left
for (int i = pos - 1; i < n - 1; i++) {
arr[i] = arr[i + 1];
n--;
printf("Array after deletion:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
4. Searching
Find the index of an element x in the array.
CopyEdit
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = 5, x = 30;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
printf("Element %d found at index %d\n", x, i);
return 0;
printf("Element not found\n");
return 0;
1.4 Important GATE Questions
1. Implement a circular array.
2. Find the maximum sum subarray (Kadane's algorithm).
3. Rotate an array by kkk positions.
2. Linked Lists
A linked list is a dynamic data structure where elements (nodes) are linked using pointers.
2.1 Types of Linked Lists
1. Singly Linked List: Each node has data and a pointer to the next node.
2. Doubly Linked List: Each node has data, a pointer to the next node, and a pointer to the previous
node.
3. Circular Linked List: The last node points back to the head.
2.2 Operations on Linked Lists
1. Traversal: Visit all nodes in sequence.
2. Insertion:
o At the beginning.
o At the end.
o After a specific node.
3. Deletion:
o From the beginning.
o From the end.
o A specific node.
4. Search: Find a node with a specific value.
5. Reverse: Reverse the order of nodes.
2.3 Example Programs
1. Singly Linked List Implementation
Insertion at the Beginning
CopyEdit
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the beginning
void insertAtBeginning(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = *head;
*head = newNode;
// Function to print the linked list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
printf("NULL\n");
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);
printf("Linked List: ");
printList(head);
return 0;
Deletion from the Beginning
CopyEdit
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
2. Doubly Linked List Implementation
Insertion at the End
CopyEdit
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to insert at the end
void insertAtEnd(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
// Function to print the doubly linked list
void printList(struct Node* head) {
struct Node* last;
while (head != NULL) {
printf("%d -> ", head->data);
last = head;
head = head->next;
printf("NULL\n");
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf("Doubly Linked List: ");
printList(head);
return 0;
}
3. Circular Linked List
Traversal
CopyEdit
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to print circular linked list
void printList(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
// Function to create a circular linked list
void createCircularList(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (*head == NULL) {
*head = newNode;
newNode->next = *head;
} else {
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
temp->next = newNode;
newNode->next = *head;
int main() {
struct Node* head = NULL;
createCircularList(&head, 10);
createCircularList(&head, 20);
createCircularList(&head, 30);
printf("Circular Linked List: ");
printList(head);
return 0;
Arrays
1. Key Characteristics
• Size: Fixed; determined at the time of declaration.
• Indexing: 0-based in most programming languages.
• Memory Allocation: Contiguous blocks.
• Data Type: Homogeneous (all elements must be of the same type).
2. Operations on Arrays
Operation Description Time Complexity
Access
Access element at an index. O(1)O(1)O(1)
(Read)
Traversal Visit each element sequentially. O(n)O(n)O(n)
O(n)O(n)O(n) or O(logn)O(\log
Search Find an element's index (Linear or Binary Search).
n)O(logn)
Add an element at a specific position (shifting
Insertion O(n)O(n)O(n)
needed).
Deletion Remove an element (shifting needed). O(n)O(n)O(n)
Sorting Arrange elements (e.g., Quick Sort, Merge Sort). O(nlogn)O(n \log n)O(nlogn)
3. Types of Arrays
1. One-Dimensional Array: Linear collection of elements.
o Syntax: int arr[5];
o Access: arr[i]
2. Multi-Dimensional Arrays:
o Example: 2D Array for matrices.
▪ Declaration: int arr[3][4];
▪ Access: arr[i][j]
o Useful for grid-based problems.
3. Dynamic Arrays (e.g., ArrayList in Java, std::vector in C++):
o Resizable arrays where size can grow or shrink dynamically.
4. Examples
a. Binary Search
Efficiently find an element in a sorted array.
c
CopyEdit
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
return -1;
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 30;
int index = binarySearch(arr, size, target);
if (index != -1) printf("Element found at index %d\n", index);
else printf("Element not found\n");
return 0;
b. Matrix Multiplication (2D Array Example)
CopyEdit
#include <stdio.h>
#define ROW 2
#define COL 2
void multiplyMatrices(int A[ROW][COL], int B[ROW][COL], int C[ROW][COL]) {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
C[i][j] = 0;
for (int k = 0; k < COL; k++) {
C[i][j] += A[i][k] * B[k][j];
int main() {
int A[ROW][COL] = {{1, 2}, {3, 4}};
int B[ROW][COL] = {{5, 6}, {7, 8}};
int C[ROW][COL];
multiplyMatrices(A, B, C);
printf("Resultant Matrix:\n");
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
printf("%d ", C[i][j]);
printf("\n");
}
return 0;
Linked Lists
1. Key Characteristics
• Dynamic Size: Unlike arrays, the size of a linked list is flexible.
• Nodes: Composed of data and a pointer to the next node (or previous node in doubly linked
lists).
• Memory Allocation: Non-contiguous; each node is allocated dynamically.
• No Random Access: Traversal is required to access elements.
2. Types of Linked Lists
a. Singly Linked List
• Each node contains:
o data: Value stored in the node.
o next: Pointer to the next node.
• The last node’s next pointer is NULL.
b. Doubly Linked List
• Each node contains:
o data: Value stored in the node.
o next: Pointer to the next node.
o prev: Pointer to the previous node.
• Allows traversal in both directions.
c. Circular Linked List
• In a singly or doubly circular linked list, the last node points back to the head.
3. Operations on Linked Lists
Operation Singly LL Complexity Doubly LL Complexity
Traversal O(n)O(n)O(n) O(n)O(n)O(n)
Search O(n)O(n)O(n) O(n)O(n)O(n)
Insertion O(1)O(1)O(1) (Head) / O(n)O(n)O(n) (Tail) Same
Deletion O(1)O(1)O(1) (Head) / O(n)O(n)O(n) (Specific) Same
4. Examples
a. Singly Linked List Implementation
Insert a Node at the End
CopyEdit
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtEnd(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
temp->next = newNode;
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
printf("NULL\n");
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf("Linked List: ");
printList(head);
return 0;
b. Doubly Linked List Example
Delete a Node from the End
CopyEdit
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
if (temp->prev) temp->prev->next = NULL;
else *head = NULL; // Only one node
free(temp);
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
printf("NULL\n");
Advanced Topics
1. Circular Linked List
A circular linked list is a variation of a linked list where:
• Last Node Points to the First Node:
o For singly linked list: last->next = head.
o For doubly linked list: last->next = head and head->prev = last.
1.1 Key Operations
a. Traversal
Traversal in a circular linked list requires stopping when we return to the head node.
CopyEdit
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to traverse the circular linked list
void printList(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
if (*head == NULL) {
*head = newNode;
newNode->next = newNode; // Point to itself
return;
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
temp->next = newNode;
newNode->next = *head;
}
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf("Circular Linked List:\n");
printList(head);
return 0;
b. Deletion
Deleting a node requires updating the last node’s pointer if deleting the head.
CopyEdit
void deleteHead(struct Node** head) {
if (*head == NULL) return;
struct Node* temp = *head;
if ((*head)->next == *head) {
// Single node in the list
*head = NULL;
free(temp);
return;
}
struct Node* last = *head;
while (last->next != *head) {
last = last->next;
last->next = (*head)->next;
*head = (*head)->next;
free(temp);
2. Merging Two Sorted Linked Lists
This is a commonly asked GATE question where two sorted linked lists are merged into a single sorted
list.
Approach
• Compare the data values of the nodes in both lists.
• Use recursion or iteration to build the merged list.
Implementation
CopyEdit
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to merge two sorted linked lists
struct Node* mergeSortedLists(struct Node* l1, struct Node* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
struct Node* result = NULL;
if (l1->data <= l2->data) {
result = l1;
result->next = mergeSortedLists(l1->next, l2);
} else {
result = l2;
result->next = mergeSortedLists(l1, l2->next);
return result;
// Utility function to insert a node at the end
void insertAtEnd(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
// Function to print the list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
printf("NULL\n");
int main() {
struct Node* list1 = NULL;
struct Node* list2 = NULL;
insertAtEnd(&list1, 10);
insertAtEnd(&list1, 20);
insertAtEnd(&list1, 30);
insertAtEnd(&list2, 15);
insertAtEnd(&list2, 25);
insertAtEnd(&list2, 35);
printf("List 1: ");
printList(list1);
printf("List 2: ");
printList(list2);
struct Node* mergedList = mergeSortedLists(list1, list2);
printf("Merged Sorted List: ");
printList(mergedList);
return 0;
3. Solving GATE-Specific Problems
3.1 Detect and Remove Loop in a Linked List
A loop in a linked list occurs when a node points back to a previous node, forming a cycle.
Approach
• Use Floyd's Cycle Detection Algorithm (Tortoise and Hare Method):
1. Use two pointers (slow and fast).
2. Move slow by one step and fast by two steps.
3. If slow == fast, a loop exists.
• To remove the loop, fix the next pointer of the node causing the loop.
Implementation
CopyEdit
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to detect and remove a loop
void detectAndRemoveLoop(struct Node* head) {
struct Node *slow = head, *fast = head;
// Detect the loop
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break; // Loop detected
// If a loop is found
if (slow == fast) {
slow = head;
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
fast->next = NULL; // Remove the loop
// Utility function to create a loop for testing
void createLoop(struct Node* head, int k) {
struct Node* temp = head;
struct Node* loopNode = NULL;
int count = 1;
while (temp->next != NULL) {
if (count == k) loopNode = temp;
temp = temp->next;
count++;
temp->next = loopNode; // Create loop
// Function to print the list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
printf("NULL\n");
// Main Function
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAtEnd(&head, 4);
insertAtEnd(&head, 5);
createLoop(head, 3); // Create a loop for testing
detectAndRemoveLoop(head);
printf("List after removing loop: ");
printList(head);
return 0;
3.2 Reverse a Linked List
Implementation
CopyEdit
struct Node* reverseList(struct Node* head) {
struct Node* prev = NULL;
struct Node* curr = head;
struct Node* next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
return prev; // New head
}
1. Stacks
How It Works:
A stack is a linear data structure that allows operations only at one end called the top. This makes it
simple but restricted in how elements can be accessed.
Implementation Approaches:
1. Using Arrays/Lists:
o Directly use a list in languages like Python.
o push and pop can be implemented using .append() and .pop() respectively.
python
CopyEdit
stack = []
stack.append(10) # Push 10
stack.append(20) # Push 20
print(stack.pop()) # Pop -> 20
print(stack[-1]) # Peek -> 10
2. Using Linked List:
o Each node points to the next, forming a chain.
o The top of the stack is the head of the list.
python
CopyEdit
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
def pop(self):
if not self.top:
return "Stack is empty"
data = self.top.data
self.top = self.top.next
return data
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.pop()) # Pop -> 20
Applications in Detail:
• Function Call Stacks:
o Used to store function calls and local variables during recursion.
o Example: When a recursive function is called, its state is saved in the call stack.
• Expression Parsing and Evaluation:
o Convert infix expressions to postfix (or prefix).
o Evaluate postfix expressions.
• Backtracking:
o Problems like maze solving or navigating a file directory rely on stack-based backtracking.
2. Queues
How It Works:
A queue uses FIFO logic, where elements are added to the rear and removed from the front. This
ensures that the order of arrival is maintained.
Implementation Approaches:
1. Using Arrays/Lists:
o A list can be used to simulate a queue.
o Enqueue using .append() and dequeue using .pop(0).
o Inefficient for large-scale use because removing from the front involves shifting
elements.
python
CopyEdit
queue = []
queue.append(10) # Enqueue 10
queue.append(20) # Enqueue 20
print(queue.pop(0)) # Dequeue -> 10
2. Using Deque (Double-Ended Queue):
o Efficient and optimized for both ends.
o Use Python’s collections.deque.
python
CopyEdit
from collections import deque
queue = deque()
queue.append(10) # Enqueue 10
queue.append(20) # Enqueue 20
print(queue.popleft()) # Dequeue -> 10
3. Using Linked List:
o Implement with pointers to the head (front) and tail (rear).
o Efficient for dynamic data.
python
CopyEdit
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = self.rear = None
def enqueue(self, data):
new_node = Node(data)
if not self.rear:
self.front = self.rear = new_node
return
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if not self.front:
return "Queue is empty"
data = self.front.data
self.front = self.front.next
if not self.front:
self.rear = None
return data
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue()) # Dequeue -> 10
Applications in Detail:
• Task Scheduling:
o Used in Operating System (OS) to manage processes.
o Ready Queue holds processes waiting for CPU execution.
• Breadth-First Search (BFS):
o BFS in graph traversal uses a queue to explore nodes layer by layer.
• Producer-Consumer Model:
o Used in real-time systems where producers add tasks to a queue and consumers process
them.
Advanced Variants
1. Circular Queue:
• Reuses empty spaces left after dequeue by wrapping around.
• Useful for memory-efficient queuing.
• Enqueue and dequeue operations are handled modulo the size of the queue.
2. Double-Ended Queue (Deque):
• Allows insertions and deletions at both ends.
• Can be implemented using collections.deque in Python.
3. Priority Queue:
• Each element is assigned a priority.
• Elements with higher priority are dequeued before others.
• Implemented using heaps (min-heap or max-heap).
Comparisons
Feature Stack Queue
Principle LIFO FIFO
Insert Operation Push Enqueue
Feature Stack Queue
Delete Operation Pop Dequeue
Access Restricted to Top Restricted to Front
Use Cases Backtracking, Parsing Scheduling, BFS
1. Convert the infix expression (A + B) * (C - D) to postfix.
Infix Expression: (A + B) * (C - D)
Solution:
To convert from infix to postfix:
• Use the stack to hold operators and parentheses.
• Follow the order of precedence (e.g., * > +).
Steps:
1. Push ( onto the stack.
2. Push A (operand), directly to the output.
3. Push + (operator) onto the stack.
4. Push B (operand), directly to the output.
5. Pop + and add to the output when ) is encountered.
6. Push * (operator) onto the stack.
7. Push C (operand), directly to the output.
8. Push - (operator) onto the stack.
9. Push D (operand), directly to the output.
10. Pop - and add to the output when ) is encountered.
11. Pop * and add to the output at the end.
Postfix Expression: AB+CD-*
2. Implement a stack using two queues.
Problem: Implement a stack data structure using two queues, with operations push(x) and pop().
Solution:
Use two queues, queue1 and queue2, to simulate the stack's LIFO behavior.
• Push Operation:
o Enqueue the new element into queue2.
o Move all elements from queue1 to queue2.
o Swap the names of queue1 and queue2.
• Pop Operation:
o Dequeue the front element from queue1.
python
CopyEdit
from collections import deque
class StackUsingTwoQueues:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, x):
self.queue2.append(x)
while self.queue1:
self.queue2.append(self.queue1.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
def pop(self):
if not self.queue1:
return "Stack is empty"
return self.queue1.popleft()
stack = StackUsingTwoQueues()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop()) # 30
3. Find the next greater element for an array using stacks.
Problem: Given an array of integers, find the next greater element for every element in the array. The
next greater element for an element is the first element on the right side that is greater than it.
Example:
• Input: [4, 5, 2, 10, 8]
• Output: [5, 10, 10, -1, -1]
Solution:
Use a stack to keep track of elements and find the next greater element.
Steps:
1. Traverse the array from right to left.
2. For each element, pop elements from the stack that are smaller.
3. If the stack is not empty, the element at the top of the stack is the next greater element.
4. If the stack is empty, there is no next greater element, so it’s -1.
python
CopyEdit
def nextGreaterElement(nums):
stack = []
result = [-1] * len(nums)
for i in range(len(nums) - 1, -1, -1):
while stack and stack[-1] <= nums[i]:
stack.pop()
if stack:
result[i] = stack[-1]
stack.append(nums[i])
return result
print(nextGreaterElement([4, 5, 2, 10, 8])) # Output: [5, 10, 10, -1, -1]
4. Simulate a queue using two stacks.
Problem: Implement a queue using two stacks, with operations enqueue(x) and dequeue().
Solution:
Use two stacks, stack1 and stack2, to simulate the FIFO behavior of a queue.
• Enqueue Operation:
o Simply push elements into stack1.
• Dequeue Operation:
o If stack2 is empty, move all elements from stack1 to stack2 (by popping from stack1 and
pushing to stack2).
o Pop from stack2 to simulate the dequeue operation.
python
CopyEdit
class QueueUsingTwoStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, x):
self.stack1.append(x)
def dequeue(self):
if not self.stack2:
if not self.stack1:
return "Queue is empty"
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
queue = QueueUsingTwoStacks()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.dequeue()) # 10
print(queue.dequeue()) # 20
5. BFS and DFS on a Graph (Related to Queues and Stacks)
Problem: Given a graph, perform Breadth-First Search (BFS) and Depth-First Search (DFS) starting from
a given node.
Solution:
• BFS: Uses a queue to explore the graph level by level.
• DFS: Uses a stack (or recursion, which internally uses the call stack) to explore the graph as
deeply as possible before backtracking.
python
CopyEdit
from collections import deque
# Graph Representation using adjacency list
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
# BFS
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# DFS
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
print("BFS:", end=" ")
bfs(graph, 0)
print("\nDFS:", end=" ")
dfs(graph, 0)
Output:
makefile
CopyEdit
BFS: 0 1 2 3 4 5
DFS: 0 2 5 1 4 3
These practice questions cover a wide range of stack and queue applications commonly tested in GATE.
Keep practicing problems like these to strengthen your understanding and improve your coding skills.
1. Infix to Postfix Conversion (Detailed Explanation)
Problem:
Convert the infix expression (A + B) * (C - D) to postfix.
Solution Approach:
To convert an infix expression to postfix:
1. Initialize an empty stack for operators and an empty list for the output.
2. Traverse the expression from left to right:
o Operands (A, B, C, D) go directly to the output.
o Left Parenthesis ( is pushed onto the stack.
o Right Parenthesis ) causes the stack to be popped to the output until a left parenthesis is
encountered.
o Operators are pushed onto the stack based on precedence. If the current operator has
lower or equal precedence than the operator on top of the stack, pop from the stack to
the output.
Operator Precedence and Associativity:
• * > + (Multiplication has higher precedence than addition).
• Left-to-right associativity for both + and *.
Steps:
1. Read ( → Push onto the stack.
2. Read A → Add to the output.
3. Read + → Push onto the stack.
4. Read B → Add to the output.
5. Read ) → Pop + from the stack and add it to the output.
6. Read * → Push onto the stack.
7. Read ( → Push onto the stack.
8. Read C → Add to the output.
9. Read - → Push onto the stack.
10. Read D → Add to the output.
11. Read ) → Pop - from the stack and add it to the output, then pop * from the stack and add it to
the output.
Postfix Expression:
AB+CD-*
This is a standard problem in GATE, testing both understanding and implementation skills.
2. Simulate a Queue Using Two Stacks (Detailed Explanation)
Problem:
Simulate a queue using two stacks with operations enqueue(x) and dequeue().
Solution Approach:
You can use two stacks (stack1 and stack2) to simulate a queue. The idea is to reverse the order of
elements by using the stacks:
• Enqueue Operation:
o Simply push elements onto stack1.
• Dequeue Operation:
o If stack2 is empty, move all elements from stack1 to stack2 (this reverses the order).
o Then pop from stack2.
Steps for Enqueue:
1. Push the element into stack1.
Steps for Dequeue:
1. If stack2 is empty:
o Pop all elements from stack1 and push them onto stack2.
2. Pop the top element from stack2 and return it.
Code Example:
python
CopyEdit
class QueueUsingTwoStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, x):
# Push element to stack1
self.stack1.append(x)
def dequeue(self):
if not self.stack2:
if not self.stack1:
return "Queue is empty"
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
# Example usage
queue = QueueUsingTwoStacks()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.dequeue()) # 10
print(queue.dequeue()) # 20
This problem tests your ability to manage two stacks and understand the reversal mechanism that makes
a queue possible.
3. Find Next Greater Element Using Stack (Detailed Explanation)
Problem:
Given an array, find the next greater element for every element. If no greater element exists, return -1.
Approach:
We can use a monotonic stack to efficiently solve this problem:
• Traverse the array from right to left.
• For each element, pop all elements from the stack that are less than or equal to the current
element (because they can’t be the next greater element).
• If the stack is not empty after this, the element on top of the stack is the next greater element.
• Otherwise, return -1.
Steps:
1. Start with an empty stack.
2. Iterate through the array from right to left:
o While the stack is not empty and the top of the stack is less than or equal to the current
element, pop the stack.
o If the stack is empty, the next greater element is -1.
o Otherwise, the top of the stack is the next greater element.
3. Push the current element onto the stack.
Code Example:
python
CopyEdit
def nextGreaterElement(nums):
stack = []
result = [-1] * len(nums) # Initialize result array with -1s
for i in range(len(nums) - 1, -1, -1):
# Pop elements from the stack while they are less than or equal to the current element
while stack and stack[-1] <= nums[i]:
stack.pop()
# If stack is not empty, top element is the next greater element
if stack:
result[i] = stack[-1]
# Push current element to stack
stack.append(nums[i])
return result
# Test the function
print(nextGreaterElement([4, 5, 2, 10, 8])) # Output: [5, 10, 10, -1, -1]
This approach has a time complexity of O(n) because each element is pushed and popped from the stack
at most once.
4. Graph Traversal - BFS and DFS (Detailed Explanation)
BFS (Breadth-First Search):
• Queue-based algorithm for traversing a graph level by level.
• Start from the source node, mark it as visited, and enqueue it.
• Dequeue nodes, explore their neighbors, and enqueue unvisited neighbors.
DFS (Depth-First Search):
• Stack-based algorithm (or recursion) for exploring a graph by diving deep into each branch
before backtracking.
• Start from the source node, mark it as visited, and recursively explore its neighbors.
Code Example (BFS and DFS):
python
CopyEdit
from collections import deque
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
# BFS
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# DFS
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
print("BFS:", end=" ")
bfs(graph, 0)
print("\nDFS:", end=" ")
dfs(graph, 0)
Output:
makefile
CopyEdit
BFS: 0 1 2 3 4 5
DFS: 0 2 5 1 4 3
BFS and DFS are both fundamental graph traversal techniques that often appear in GATE exam questions.
Conclusion:
By thoroughly understanding these problems and implementing them, you'll be well-prepared for the
GATE exam. Practice coding these problems and tweak your approach to handle various edge cases.
These topics are central to algorithms and data structures, and mastering them will boost your problem-
solving efficiency.
1. Infix to Postfix Conversion (Detailed Explanation)
Problem:
Convert the infix expression (A + B) * (C - D) to postfix.
Solution Approach:
To convert an infix expression to postfix:
1. Initialize an empty stack for operators and an empty list for the output.
2. Traverse the expression from left to right:
o Operands (A, B, C, D) go directly to the output.
o Left Parenthesis ( is pushed onto the stack.
o Right Parenthesis ) causes the stack to be popped to the output until a left parenthesis is
encountered.
o Operators are pushed onto the stack based on precedence. If the current operator has
lower or equal precedence than the operator on top of the stack, pop from the stack to
the output.
Operator Precedence and Associativity:
• * > + (Multiplication has higher precedence than addition).
• Left-to-right associativity for both + and *.
Steps:
1. Read ( → Push onto the stack.
2. Read A → Add to the output.
3. Read + → Push onto the stack.
4. Read B → Add to the output.
5. Read ) → Pop + from the stack and add it to the output.
6. Read * → Push onto the stack.
7. Read ( → Push onto the stack.
8. Read C → Add to the output.
9. Read - → Push onto the stack.
10. Read D → Add to the output.
11. Read ) → Pop - from the stack and add it to the output, then pop * from the stack and add it to
the output.
Postfix Expression:
AB+CD-*
This is a standard problem in GATE, testing both understanding and implementation skills.
2. Simulate a Queue Using Two Stacks (Detailed Explanation)
Problem:
Simulate a queue using two stacks with operations enqueue(x) and dequeue().
Solution Approach:
You can use two stacks (stack1 and stack2) to simulate a queue. The idea is to reverse the order of
elements by using the stacks:
• Enqueue Operation:
o Simply push elements onto stack1.
• Dequeue Operation:
o If stack2 is empty, move all elements from stack1 to stack2 (this reverses the order).
o Then pop from stack2.
Steps for Enqueue:
1. Push the element into stack1.
Steps for Dequeue:
1. If stack2 is empty:
o Pop all elements from stack1 and push them onto stack2.
2. Pop the top element from stack2 and return it.
Code Example:
python
CopyEdit
class QueueUsingTwoStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, x):
# Push element to stack1
self.stack1.append(x)
def dequeue(self):
if not self.stack2:
if not self.stack1:
return "Queue is empty"
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
# Example usage
queue = QueueUsingTwoStacks()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.dequeue()) # 10
print(queue.dequeue()) # 20
This problem tests your ability to manage two stacks and understand the reversal mechanism that makes
a queue possible.
3. Find Next Greater Element Using Stack (Detailed Explanation)
Problem:
Given an array, find the next greater element for every element. If no greater element exists, return -1.
Approach:
We can use a monotonic stack to efficiently solve this problem:
• Traverse the array from right to left.
• For each element, pop all elements from the stack that are less than or equal to the current
element (because they can’t be the next greater element).
• If the stack is not empty after this, the element on top of the stack is the next greater element.
• Otherwise, return -1.
Steps:
1. Start with an empty stack.
2. Iterate through the array from right to left:
o While the stack is not empty and the top of the stack is less than or equal to the current
element, pop the stack.
o If the stack is empty, the next greater element is -1.
o Otherwise, the top of the stack is the next greater element.
3. Push the current element onto the stack.
Code Example:
python
CopyEdit
def nextGreaterElement(nums):
stack = []
result = [-1] * len(nums) # Initialize result array with -1s
for i in range(len(nums) - 1, -1, -1):
# Pop elements from the stack while they are less than or equal to the current element
while stack and stack[-1] <= nums[i]:
stack.pop()
# If stack is not empty, top element is the next greater element
if stack:
result[i] = stack[-1]
# Push current element to stack
stack.append(nums[i])
return result
# Test the function
print(nextGreaterElement([4, 5, 2, 10, 8])) # Output: [5, 10, 10, -1, -1]
This approach has a time complexity of O(n) because each element is pushed and popped from the stack
at most once.
4. Graph Traversal - BFS and DFS (Detailed Explanation)
BFS (Breadth-First Search):
• Queue-based algorithm for traversing a graph level by level.
• Start from the source node, mark it as visited, and enqueue it.
• Dequeue nodes, explore their neighbors, and enqueue unvisited neighbors.
DFS (Depth-First Search):
• Stack-based algorithm (or recursion) for exploring a graph by diving deep into each branch
before backtracking.
• Start from the source node, mark it as visited, and recursively explore its neighbors.
Code Example (BFS and DFS):
python
CopyEdit
from collections import deque
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
# BFS
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# DFS
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
print("BFS:", end=" ")
bfs(graph, 0)
print("\nDFS:", end=" ")
dfs(graph, 0)
Output:
makefile
CopyEdit
BFS: 0 1 2 3 4 5
DFS: 0 2 5 1 4 3
BFS and DFS are both fundamental graph traversal techniques that often appear in GATE exam questions.
Conclusion:
By thoroughly understanding these problems and implementing them, you'll be well-prepared for the
GATE exam. Practice coding these problems and tweak your approach to handle various edge cases.
These topics are central to algorithms and data structures, and mastering them will boost your problem-
solving efficiency.
1. Stack to Reverse a String
Problem:
Write a function that uses a stack to reverse a given string.
Solution Approach:
1. Traverse the string and push each character onto the stack.
2. Pop characters from the stack and add them to the result string.
Code Example:
python
CopyEdit
def reverseString(s):
stack = []
# Push each character to the stack
for char in s:
stack.append(char)
# Pop characters from the stack to form the reversed string
reversed_str = ''
while stack:
reversed_str += stack.pop()
return reversed_str
print(reverseString("GATE")) # Output: "ETAG"
This problem helps you understand stack operations like push and pop.
2. Implement a Circular Queue
Problem:
Design a circular queue of fixed size using an array. Implement the following operations:
• enqueue(x) - Add element to the queue.
• dequeue() - Remove the front element from the queue.
• front() - Return the front element.
• is_empty() - Check if the queue is empty.
• is_full() - Check if the queue is full.
Solution Approach:
• Use two pointers (front and rear) to represent the front and rear of the queue.
• In a circular queue, when the rear pointer reaches the end of the array, it should wrap around to
the beginning.
Code Example:
python
CopyEdit
class CircularQueue:
def __init__(self, size):
self.size = size
self.queue = [None] * size
self.front = self.rear = -1
def enqueue(self, x):
if (self.rear + 1) % self.size == self.front:
print("Queue is full")
return
elif self.front == -1:
self.front = self.rear = 0
else:
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = x
def dequeue(self):
if self.front == -1:
print("Queue is empty")
return None
elif self.front == self.rear:
element = self.queue[self.front]
self.front = self.rear = -1
return element
else:
element = self.queue[self.front]
self.front = (self.front + 1) % self.size
return element
def front_element(self):
if self.front == -1:
return "Queue is empty"
return self.queue[self.front]
def is_empty(self):
return self.front == -1
def is_full(self):
return (self.rear + 1) % self.size == self.front
# Example usage
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
print(cq.dequeue()) # Output: 10
print(cq.front_element()) # Output: 20
3. Implement a Stack Using Linked List
Problem:
Implement a stack using a linked list. The stack should support the following operations:
• push(x) - Add an element to the stack.
• pop() - Remove the top element from the stack.
• peek() - Return the top element of the stack.
• is_empty() - Check if the stack is empty.
Solution Approach:
• Use a linked list where the top of the stack is the head node.
• Each push operation involves inserting a new node at the head.
• Each pop operation involves removing the head node.
Code Example:
python
CopyEdit
class StackNode:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def push(self, x):
new_node = StackNode(x)
new_node.next = self.top
self.top = new_node
def pop(self):
if self.top is None:
print("Stack is empty")
return None
else:
popped_node = self.top
self.top = self.top.next
return popped_node.data
def peek(self):
if self.top is None:
print("Stack is empty")
return None
return self.top.data
def is_empty(self):
return self.top is None
# Example usage
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.pop()) # Output: 20
print(stack.peek()) # Output: 10
This problem will test your understanding of linked list and stack operations.
4. Implement a Priority Queue (Max-Heap)
Problem:
Implement a priority queue using a max-heap. Support the following operations:
• insert(x) - Insert an element into the priority queue.
• delete_max() - Remove and return the maximum element.
• peek_max() - Return the maximum element without removing it.
Solution Approach:
• A max-heap is a complete binary tree where each parent node is greater than its children.
• Use a list to represent the heap, with the parent at index i and the children at indices 2i + 1 and
2i + 2.
Code Example:
python
CopyEdit
class MaxHeap:
def __init__(self):
self.heap = []
def insert(self, x):
self.heap.append(x)
self._heapify_up(len(self.heap) - 1)
def delete_max(self):
if len(self.heap) == 0:
return "Heap is empty"
max_element = self.heap[0]
self.heap[0] = self.heap[-1]
self.heap.pop()
self._heapify_down(0)
return max_element
def peek_max(self):
if len(self.heap) == 0:
return "Heap is empty"
return self.heap[0]
def _heapify_up(self, index):
parent = (index - 1) // 2
if index > 0 and self.heap[index] > self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
self._heapify_up(parent)
def _heapify_down(self, index):
left_child = 2 * index + 1
right_child = 2 * index + 2
largest = index
if left_child < len(self.heap) and self.heap[left_child] > self.heap[largest]:
largest = left_child
if right_child < len(self.heap) and self.heap[right_child] > self.heap[largest]:
largest = right_child
if largest != index:
self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
self._heapify_down(largest)
# Example usage
max_heap = MaxHeap()
max_heap.insert(10)
max_heap.insert(20)
max_heap.insert(5)
print(max_heap.delete_max()) # Output: 20
print(max_heap.peek_max()) # Output: 10
5. Stack to Sort Elements (Using Only One Extra Stack)
Problem:
Sort a stack using only one extra stack (without using any sorting algorithms like quicksort or mergesort).
Solution Approach:
1. Use an additional stack to help in sorting.
2. While the original stack is not empty, pop the top element.
3. Compare it with the top of the auxiliary stack:
o If the auxiliary stack is empty or the top of the auxiliary stack is greater than the popped
element, push the popped element onto the auxiliary stack.
o Otherwise, pop elements from the auxiliary stack and push them back to the original
stack until the condition is met.
4. Repeat until the original stack is empty, and the auxiliary stack will contain the sorted elements.
Code Example:
python
CopyEdit
def sort_stack(stack):
aux_stack = []
while stack:
temp = stack.pop()
while aux_stack and aux_stack[-1] > temp:
stack.append(aux_stack.pop())
aux_stack.append(temp)
return aux_stack
# Example usage
stack = [34, 3, 31, 98, 92, 23]
sorted_stack = sort_stack(stack)
print(sorted_stack) # Output: [3, 23, 31, 34, 92, 98]
Next Steps for GATE Preparation:
• Time Complexity Analysis: Be sure to analyze the time complexity of the operations for these
data structures, as this will be useful for answering related questions in GATE.
• Practice Edge Cases: For all problems, consider edge cases such as empty structures, single-
element structures, and full structures (like a full queue or a stack with one element).
• Mock Tests: Regularly attempt GATE mock tests and try solving these problems under time
constraints.
Trees in Detail for GATE Preparation
Trees are one of the most important topics in Data Structures and Algorithms for the GATE exam. Let’s
break down the topic and provide theory, examples, algorithms, and problems to help you master trees
for GATE.
1. Types of Trees
1. Binary Tree:
o Each node has at most two children: left and right.
o Full Binary Tree: Every node has 0 or 2 children.
o Complete Binary Tree: All levels are completely filled except possibly the last, which is
filled from left to right.
o Perfect Binary Tree: All internal nodes have two children, and all leaves are at the same
level.
2. Binary Search Tree (BST):
o A binary tree where the left child’s value is less than the parent, and the right child’s
value is greater than the parent.
3. AVL Tree:
o A self-balancing binary search tree where the height difference (balance factor)
between the left and right subtrees of any node is at most 1.
4. B-Tree:
o A self-balancing search tree that maintains sorted data and allows searches, sequential
access, insertions, and deletions in logarithmic time. Used in databases.
5. Heap:
o A complete binary tree used to implement priority queues.
o Max-Heap: Parent node is greater than or equal to its children.
o Min-Heap: Parent node is less than or equal to its children.
6. Trie (Prefix Tree):
o A tree for storing strings where nodes represent prefixes.
2. Tree Traversals
Traversal refers to visiting each node of the tree in a systematic way. There are two types:
a. Depth-First Traversal (DFT):
1. Inorder Traversal:
o Left → Root → Right
o Used to retrieve elements of a BST in sorted order.
o Example: For the tree below, the output is D B E A F C.
css
CopyEdit
/ \
B C
/\ /
2. D E F
3. CopyEdit
4. Preorder Traversal:
o Root → Left → Right
o Example: A B D E C F.
5. Postorder Traversal:
o Left → Right → Root
o Example: D E B F C A.
b. Breadth-First Traversal (BFT):
1. Level-Order Traversal:
o Visit nodes level by level from left to right.
o Example: A B C D E F.
Traversal Code:
python
CopyEdit
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
# Inorder Traversal
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=" ")
inorder(root.right)
# Preorder Traversal
def preorder(root):
if root:
print(root.val, end=" ")
preorder(root.left)
preorder(root.right)
# Postorder Traversal
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=" ")
# Level-Order Traversal
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Example Usage
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')
root.right.left = Node('F')
print("Inorder: ", end="")
inorder(root) # Output: D B E A F C
print("\nPreorder: ", end="")
preorder(root) # Output: A B D E C F
print("\nPostorder: ", end="")
postorder(root) # Output: D E B F C A
print("\nLevel Order: ", end="")
level_order(root) # Output: A B C D E F
3. Binary Search Tree Operations
1. Insertion in BST:
o Compare the value with the root.
o Insert into the left subtree if smaller; otherwise, insert into the right subtree.
Code for BST Insertion:
python
CopyEdit
class BSTNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return BSTNode(key)
if key < root.val:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=" ")
inorder(root.right)
# Example Usage
root = None
keys = [50, 30, 70, 20, 40, 60, 80]
for key in keys:
root = insert(root, key)
print("Inorder of BST: ", end="")
inorder(root) # Output: 20 30 40 50 60 70 80
2. Deletion in BST:
o If the node is a leaf, remove it.
o If the node has one child, replace it with its child.
o If the node has two children, replace it with the inorder successor (minimum value in
the right subtree).
4. Tree Height and Diameter
1. Height of a Tree:
o The height of a tree is the number of edges on the longest path from the root to a leaf.
Code for Height:
python
CopyEdit
def height(root):
if root is None:
return 0
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1
print("Height of Tree:", height(root)) # Output: 3
2. Diameter of a Tree:
o The diameter is the longest path between two nodes in the tree (may or may not pass
through the root).
Code for Diameter:
python
CopyEdit
def diameter(root):
if not root:
return 0
def helper(node):
if not node:
return 0, 0 # height, diameter
lh, ld = helper(node.left)
rh, rd = helper(node.right)
height = max(lh, rh) + 1
dia = max(ld, rd, lh + rh)
return height, dia
_, dia = helper(root)
return dia
print("Diameter of Tree:", diameter(root)) # Output depends on the tree structure
5. Problem Solving: GATE-Level Questions
1. Question: Construct a BST from the preorder sequence [10, 5, 1, 7, 40, 50].
Solution:
• The first element is the root.
• Split the array into left subtree (values smaller than root) and right subtree (values larger than
root).
• Recursively repeat for both subtrees.
2. Question: Given a binary tree, print the left view of the tree.
Hint:
• Use level-order traversal and print the first node of each level.
3. Question: Write a program to check if a binary tree is balanced.
Hint:
• A tree is balanced if the height difference between left and right subtrees of any node is at most
1.
Next Steps for GATE Prep
• Practice Problems: Solve tree-related problems from previous GATE papers.
• Important Topics:
o Traversals (Inorder, Preorder, Postorder).
o BST Operations (Insertion, Deletion).
o AVL Trees and Rotations.
o Heaps (Max-Heap, Min-Heap).
• Mock Tests: Attempt mock tests to manage time and accuracy.
GATE-Specific Additions to Focus On
1. Theory Questions
Understanding the theoretical aspects of trees is crucial, as these are commonly tested in GATE. Focus
on:
• Properties of Trees:
o Height of a complete binary tree with nnn nodes: ⌊log2n⌋+1\lfloor \log_2 n \rfloor +
1⌊log2n⌋+1.
o Maximum number of nodes at height hhh: 2h−12^h - 12h−1.
o Minimum number of nodes in a binary tree of height hhh: hhh (skewed tree).
• Advantages of Special Trees:
o AVL Trees: Ensure O(logn)O(\log n)O(logn) complexity for search, insertion, and
deletion.
o B-Trees: Efficient for database indexing due to minimized disk I/O.
o Heaps: Fast access to the smallest or largest element (priority queues).
• Heap Properties:
o In a max-heap, the root is the largest element.
o In a min-heap, the root is the smallest element.
2. Traversal-Based Questions
Traversal is a fundamental concept in trees and often appears in GATE:
• Inorder, Preorder, Postorder Traversals:
o Questions on converting one traversal order to another.
o Example: Construct a binary tree using given inorder and preorder sequences.
• Level Order Traversal:
o Often tested in problems involving BFS on trees.
• Common Question Types:
o Find the preorder traversal of a BST after a sequence of insertions.
o Identify which traversal gives sorted output (Answer: Inorder for BST).
3. Complexity Analysis
Understand and remember the time and space complexity of operations on trees:
Binary Search
Operation Binary Tree AVL Tree Heap
Tree
Search O(n) O(h) (h: height) O(log n) O(n)
Insertion O(n) O(h) O(log n) O(log n)
Deletion O(n) O(h) O(log n) O(log n)
Traversals (All) O(n) O(n) O(n) O(n)O(n)O(n)
Construct Tree O(nlogn)O(n \log
O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n)
(Sequences) n)O(nlogn)
• Note:
o nnn: Number of nodes in the tree.
o hhh: Height of the tree (O(logn)O(\log n)O(logn) for balanced trees, O(n)O(n)O(n) for
skewed trees).
4. Heap Operations
Heap is a popular topic in GATE, especially in questions related to priority queues and heapify
operations.
• Heapify:
o Converts an array into a heap (min or max).
o Time complexity: O(n)O(n)O(n) for building the heap.
• Insert/Delete in Heap:
o Time complexity: O(logn)O(\log n)O(logn).
• Applications:
o Heap Sort: Sorts an array in O(nlogn)O(n \log n)O(nlogn).
o Priority Queues: Implemented using heaps for efficient access to max/min element.
Example Problem:
Build a min-heap from the array [4, 10, 3, 5, 1].
5. Tree Construction Problems
Tree construction from traversal sequences is a classic question type in GATE:
• Given Inorder and Preorder/Postorder:
o Inorder: Left → Root → Right.
o Preorder: Root → Left → Right.
o Postorder: Left → Right → Root.
Example:
Given Inorder = [D, B, E, A, F, C] and Preorder = [A, B, D, E, C, F], construct the binary tree.
6. Special Tree-Based Algorithms
Focus on unique properties or operations in specialized trees:
• AVL Tree Rotations:
o Left-Left (LL), Right-Right (RR), Left-Right (LR), Right-Left (RL).
o Questions test rebalancing the tree after insertion or deletion.
• B-Trees:
o Questions often test splitting nodes and maintaining balance during insertions.
• Tries:
o Questions may involve prefix-matching or finding the longest common prefix.
7. Previous Year GATE Questions
Solve previous years' questions to understand patterns. Example topics:
• Traversal questions: Find preorder from given inorder and postorder sequences.
• Construct BST from a sequence of keys.
• Questions on height, depth, and diameter of trees.
• Heap operations: Insertion and deletion in a min-heap/max-heap.
Suggested Next Steps
• Mock Tests: Attempt tree-specific questions under timed conditions.
• Topic-Wise Quizzes: Solve quizzes focused on AVL Trees, Heaps, and Traversals.
• Reference Books: Use "Data Structures and Algorithm Analysis in C" by Mark Allen Weiss and
"Introduction to Algorithms" by Cormen (CLRS) for in-depth study.
1. AVL Trees
An AVL Tree is a self-balancing Binary Search Tree (BST) where the height difference between the left and
right subtrees of any node (called the balance factor) is at most 1.
1.1 Key Properties
1. Balance Factor =Height(left subtree)−Height(right subtree)= \text{Height(left subtree)} -
\text{Height(right subtree)}=Height(left subtree)−Height(right subtree).
o Balance Factor∈{−1,0,1}\text{Balance Factor} \in \{-1, 0, 1\}Balance Factor∈{−1,0,1}.
2. Rotations are used to restore balance after insertion or deletion:
o Single Rotations:
▪ Left Rotation (LL imbalance).
▪ Right Rotation (RR imbalance).
o Double Rotations:
▪ Left-Right Rotation (LR imbalance).
▪ Right-Left Rotation (RL imbalance).
1.2 AVL Rotations
1. Left Rotation (LL Imbalance):
markdown
CopyEdit
/\
T1 y
/\
T2 x
After Left Rotation:
markdown
CopyEdit
y
/\
z x
/\
T1 T2
2. Right Rotation (RR Imbalance):
markdown
CopyEdit
/\
y T3
/\
x T2
After Right Rotation:
markdown
CopyEdit
/\
x z
/\
T2 T3
3. Left-Right Rotation (LR Imbalance):
o Perform a left rotation on the left child, then a right rotation on the root.
4. Right-Left Rotation (RL Imbalance):
o Perform a right rotation on the right child, then a left rotation on the root.
1.3 Insertion in an AVL Tree
1. Insert the node as in a BST.
2. Update heights of all affected nodes.
3. Check for balance factor violations.
4. Perform the necessary rotations to restore balance.
Code for AVL Tree Insertion:
python
CopyEdit
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def get_height(self, root):
if not root:
return 0
return root.height
def get_balance(self, root):
if not root:
return 0
return self.get_height(root.left) - self.get_height(root.right)
def right_rotate(self, z):
y = z.left
T3 = y.right
# Perform rotation
y.right = z
z.left = T3
# Update heights
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def left_rotate(self, z):
y = z.right
T2 = y.left
# Perform rotation
y.left = z
z.right = T2
# Update heights
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def insert(self, root, key):
# Perform normal BST insertion
if not root:
return AVLNode(key)
if key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
# Update height of the ancestor node
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
# Get balance factor
balance = self.get_balance(root)
# Balance the tree
if balance > 1 and key < root.left.key: # LL Case
return self.right_rotate(root)
if balance < -1 and key > root.right.key: # RR Case
return self.left_rotate(root)
if balance > 1 and key > root.left.key: # LR Case
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
if balance < -1 and key < root.right.key: # RL Case
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.key, end=" ")
self.inorder(root.right)
# Example Usage
avl = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
root = avl.insert(root, key)
print("Inorder Traversal of AVL Tree: ", end="")
avl.inorder(root)
# Output: 10 20 25 30 40 50
2. Heap Operations
A Heap is a complete binary tree used for efficient retrieval of the maximum (in a max-heap) or
minimum (in a min-heap).
2.1 Operations on a Max-Heap
1. Insert:
o Add the new element at the end of the heap.
o Perform an up-heapify operation to maintain the max-heap property.
2. Delete Max:
o Replace the root with the last element in the heap.
o Perform a down-heapify operation to restore the max-heap property.
Code for Max-Heap Operations:
python
CopyEdit
class MaxHeap:
def __init__(self):
self.heap = []
def insert(self, key):
self.heap.append(key)
self._heapify_up(len(self.heap) - 1)
def delete_max(self):
if len(self.heap) == 0:
return "Heap is empty"
max_value = self.heap[0]
self.heap[0] = self.heap[-1]
self.heap.pop()
self._heapify_down(0)
return max_value
def _heapify_up(self, index):
parent = (index - 1) // 2
if index > 0 and self.heap[index] > self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
self._heapify_up(parent)
def _heapify_down(self, index):
largest = index
left_child = 2 * index + 1
right_child = 2 * index + 2
if left_child < len(self.heap) and self.heap[left_child] > self.heap[largest]:
largest = left_child
if right_child < len(self.heap) and self.heap[right_child] > self.heap[largest]:
largest = right_child
if largest != index:
self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
self._heapify_down(largest)
def get_max(self):
if len(self.heap) == 0:
return "Heap is empty"
return self.heap[0]
# Example Usage
max_heap = MaxHeap()
keys = [10, 20, 15, 30, 40]
for key in keys:
max_heap.insert(key)
print("Max Value:", max_heap.get_max()) # Output: 40
print("Deleted Max:", max_heap.delete_max()) # Output: 40
print("Max Value After Deletion:", max_heap.get_max()) # Output: 30
2.2 Common Questions on AVL and Heaps
1. AVL Tree Rotations:
o Identify the type of imbalance and correct it using single or double rotations.
2. Heapify Questions:
o Create a heap from an unsorted array in O(n)O(n)O(n) time.
3. Priority Queue:
o Implement priority queue operations using heaps.
Hashing: Comprehensive Concepts
Hashing is a technique used to map data to a fixed-size value (hash code) for efficient data retrieval. It
plays a key role in data structures like hash tables, cryptographic applications, and database indexing.
1. Hash Function
A hash function takes input data (key) and maps it to an integer value (hash code) within a fixed range.
Key Properties of a Good Hash Function:
1. Deterministic: Same key should always produce the same hash code.
2. Efficient: Should compute hash codes quickly.
3. Uniform Distribution: Should distribute keys uniformly across the hash table to avoid clustering.
4. Minimize Collisions: Should map different keys to distinct hash codes as much as possible.
2. Hash Table
A hash table is a data structure that stores key-value pairs using a hash function. It supports:
• Insertion: O(1)O(1)O(1) average time.
• Search: O(1)O(1)O(1) average time.
• Deletion: O(1)O(1)O(1) average time.
3. Collisions and Resolution Techniques
Collisions occur when two keys produce the same hash code. They are resolved using:
3.1 Open Addressing
• All elements are stored in the hash table itself.
• If a collision occurs, find the next empty slot.
Techniques:
1. Linear Probing:
o Search for the next available slot linearly.
o Hash function: h(k,i)=(h′(k)+i)mod Nh(k, i) = (h'(k) + i) \mod Nh(k,i)=(h′(k)+i)modN.
o Problem: Clustering of elements.
2. Quadratic Probing:
o Search using quadratic increments.
o Hash function: h(k,i)=(h′(k)+c1i+c2i2)mod Nh(k, i) = (h'(k) + c_1 i + c_2 i^2) \mod
Nh(k,i)=(h′(k)+c1i+c2i2)modN.
o Reduces clustering but may require larger tables.
3. Double Hashing:
o Use a secondary hash function to resolve collisions.
o Hash function: h(k,i)=(h1(k)+i⋅h2(k))mod Nh(k, i) = (h_1(k) + i \cdot h_2(k)) \mod
Nh(k,i)=(h1(k)+i⋅h2(k))modN.
o Effective in reducing clustering.
3.2 Chaining
• Use a linked list or other structures to store all keys with the same hash value.
• A separate chain (linked list) handles collisions.
• Advantage: Handles dynamic resizing well.
4. Load Factor
The load factor (α\alphaα) of a hash table is the ratio of the number of elements to the table size.
α=Number of ElementsSize of Table\alpha = \frac{\text{Number of Elements}}{\text{Size of
Table}}α=Size of TableNumber of Elements
• If α\alphaα increases, collisions become more frequent.
• Rehashing is performed to resize the table when α\alphaα exceeds a threshold (e.g., 0.75).
5. Rehashing
Rehashing involves:
1. Doubling the table size.
2. Recomputing the hash codes for all existing keys.
3. Reinserting the keys into the new table.
6. Hashing Applications
1. Hash Tables:
o Used for fast key-value storage.
o Examples: Dictionaries in Python, Maps in C++.
2. Cryptographic Hashing:
o Secure hashing for digital signatures, data integrity.
o Examples: MD5, SHA-256.
o Properties: One-way, collision-resistant.
3. Bloom Filters:
o Probabilistic data structures using multiple hash functions.
o Used for membership queries.
4. Database Indexing:
o Hashing used for efficient record retrieval.
7. Examples of Hash Functions
7.1 Division Method
h(k)=kmod Nh(k) = k \mod Nh(k)=kmodN
• NNN is typically a prime number.
• Simple and effective.
7.2 Multiplication Method
h(k)=⌊N⋅(k⋅Amod 1)⌋h(k) = \lfloor N \cdot (k \cdot A \mod 1) \rfloorh(k)=⌊N⋅(k⋅Amod1)⌋
• AAA is a constant between 0 and 1.
7.3 Universal Hashing
• Uses a family of hash functions to minimize collision probabilities.
8. Code Examples
8.1 Hash Table Implementation with Chaining
python
CopyEdit
class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(size)]
def hash_function(self, key):
return key % self.size
def insert(self, key, value):
index = self.hash_function(key)
for item in self.table[index]:
if item[0] == key:
item[1] = value
return
self.table[index].append([key, value])
def search(self, key):
index = self.hash_function(key)
for item in self.table[index]:
if item[0] == key:
return item[1]
return None
def delete(self, key):
index = self.hash_function(key)
for item in self.table[index]:
if item[0] == key:
self.table[index].remove(item)
return
# Example Usage
hash_table = HashTable(10)
hash_table.insert(1, "Value1")
hash_table.insert(11, "Value2")
print(hash_table.search(1)) # Output: Value1
hash_table.delete(1)
print(hash_table.search(1)) # Output: None
8.2 Open Addressing Example
python
CopyEdit
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return key % self.size
def insert(self, key, value):
index = self.hash_function(key)
for i in range(self.size):
probe_index = (index + i) % self.size
if self.table[probe_index] is None or self.table[probe_index][0] == key:
self.table[probe_index] = (key, value)
return
raise Exception("Hash table is full")
def search(self, key):
index = self.hash_function(key)
for i in range(self.size):
probe_index = (index + i) % self.size
if self.table[probe_index] is None:
return None
if self.table[probe_index][0] == key:
return self.table[probe_index][1]
return None
def delete(self, key):
index = self.hash_function(key)
for i in range(self.size):
probe_index = (index + i) % self.size
if self.table[probe_index] is None:
return
if self.table[probe_index][0] == key:
self.table[probe_index] = None
return
# Example Usage
hash_table = HashTableOpenAddressing(10)
hash_table.insert(1, "Value1")
hash_table.insert(11, "Value2")
print(hash_table.search(1)) # Output: Value1
hash_table.delete(1)
print(hash_table.search(1)) # Output: None
Let’s delve into cryptographic hashing and GATE-related hashing problems in detail.
1. Cryptographic Hashing
Cryptographic hashing ensures secure and unique hash codes for input data. It's widely used in
cryptography, data integrity checks, and digital signatures.
1.1 Properties of Cryptographic Hash Functions
1. Deterministic:
o For the same input, the output should always be the same.
2. Pre-image Resistance:
o It should be computationally infeasible to reverse-engineer the input from the hash
output.
o Example: Given H(x)H(x)H(x), it’s hard to find xxx.
3. Collision Resistance:
o Two different inputs should not produce the same hash value.
o Example: H(x1)≠H(x2)H(x_1) \neq H(x_2)H(x1) =H(x2) for x1≠x2x_1 \neq x_2x1 =x2.
4. Avalanche Effect:
o A slight change in the input should produce a completely different output.
5. Efficiency:
o Should compute the hash quickly.
1.2 Common Cryptographic Hash Algorithms
1. MD5 (Message Digest 5):
o Produces a 128-bit hash value.
o Vulnerable to collisions; not recommended for security purposes.
2. SHA (Secure Hash Algorithms):
o Family includes SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), and SHA-3.
o Example: SHA-256 produces a 256-bit hash value.
3. HMAC (Hash-based Message Authentication Code):
o Combines a cryptographic hash function with a secret key for message authentication.
1.3 Applications
• Data Integrity:
o Verify if data has been tampered with during transmission.
• Digital Signatures:
o Provide authentication and non-repudiation.
• Password Storage:
o Store passwords securely in hashed form.
• Blockchain:
o Hashing is fundamental for proof-of-work and transaction verification.
1.4 Python Code for Hashing
Using the hashlib library in Python:
python
CopyEdit
import hashlib
# MD5 Hash
data = "hello world".encode()
md5_hash = hashlib.md5(data).hexdigest()
print("MD5 Hash:", md5_hash)
# SHA-256 Hash
sha256_hash = hashlib.sha256(data).hexdigest()
print("SHA-256 Hash:", sha256_hash)
# SHA-512 Hash
sha512_hash = hashlib.sha512(data).hexdigest()
print("SHA-512 Hash:", sha512_hash)
Output:
mathematica
CopyEdit
MD5 Hash: 5eb63bbbe01eeed093cb22bb8f5acdc3
SHA-256 Hash: b94d27b9934d3e08a52e52d7da7dabfa...
SHA-512 Hash: 309ecc489c12d6eb4cc40f50c902f2b4...
2. GATE-Related Hashing Concepts and Problems
2.1 Common Topics in GATE
1. Hash Functions:
o Division method.
o Multiplication method.
o Universal hashing.
2. Hash Collisions:
o Open addressing.
o Chaining.
3. Load Factor and Rehashing:
o Calculation of load factor and impact on performance.
4. Applications:
o Hash-based indexing in databases.
o Hashing in dynamic programming (e.g., memoization).
2.2 Important Formulas
1. Hash Function Using Division:
h(k)=kmod Nh(k) = k \mod Nh(k)=kmodN
Where NNN is typically a prime number.
2. Load Factor:
α=Number of ElementsTable Size\alpha = \frac{\text{Number of Elements}}{\text{Table
Size}}α=Table SizeNumber of Elements
3. Time Complexity:
o Best Case: O(1)O(1)O(1) (No collisions).
o Worst Case: O(n)O(n)O(n) (All keys hash to the same index in chaining).
2.3 Practice Problems
1. Find the hash value using the Division Method.
• Table Size (NNN) = 7.
• Keys: [10, 20, 15, 7].
Solution: Using h(k)=kmod Nh(k) = k \mod Nh(k)=kmodN,
• h(10)=10mod 7=3h(10) = 10 \mod 7 = 3h(10)=10mod7=3
• h(20)=20mod 7=6h(20) = 20 \mod 7 = 6h(20)=20mod7=6
• h(15)=15mod 7=1h(15) = 15 \mod 7 = 1h(15)=15mod7=1
• h(7)=7mod 7=0h(7) = 7 \mod 7 = 0h(7)=7mod7=0
2. Load Factor Calculation and Rehashing
• Initial table size: 5.
• Elements inserted: [12, 7, 25, 8].
• After 3 insertions, the table is resized when α>0.75\alpha > 0.75α>0.75.
Solution:
α=Number of ElementsTable Size=35=0.6\alpha = \frac{\text{Number of Elements}}{\text{Table Size}} =
\frac{3}{5} = 0.6α=Table SizeNumber of Elements=53=0.6
No rehashing is required. After inserting the 4th element:
α=45=0.8\alpha = \frac{4}{5} = 0.8α=54=0.8
Rehashing is triggered, and the table size doubles to 10.
3. GATE 2021 Question Q: A hash table of size 10 uses open addressing with linear probing. What is the
position of the key 434343 if the hash function is h(k)=kmod 10h(k) = k \mod 10h(k)=kmod10 and the
following keys are already present: [23, 43, 13, 33]?
Solution:
• h(43)=43mod 10=3h(43) = 43 \mod 10 = 3h(43)=43mod10=3
• h(23)=23mod 10=3h(23) = 23 \mod 10 = 3h(23)=23mod10=3 (collision).
• Linear probing: Next slot is 444.
Answer: Position 444.
3. Advanced Hashing Topics
1. Perfect Hashing:
o Hashing with no collisions, achieved by creating an auxiliary hash function for colliding
keys.
2. Bloom Filters:
o A probabilistic data structure using multiple hash functions to test membership.
o False positives possible; false negatives are not.
3. Consistent Hashing:
o Used in distributed systems to distribute keys across nodes dynamically.
You might also like
- Csc121 - Topic 3 Algorithm Design For Sequence Control Structure - PPTMNo ratings yetCsc121 - Topic 3 Algorithm Design For Sequence Control Structure - PPTM29 pages
- Week 1 Introduction To Programming Basics Javaspart II NotesNo ratings yetWeek 1 Introduction To Programming Basics Javaspart II Notes14 pages
- Topics: No. of Questions: Type: Assessment Duration: Difficulty LevelNo ratings yetTopics: No. of Questions: Type: Assessment Duration: Difficulty Level11 pages
- C++ Identifiers, Data Types and OperatorsNo ratings yetC++ Identifiers, Data Types and Operators5 pages
- 1) Introduction To Computer Programming: Dr. E. LangNo ratings yet1) Introduction To Computer Programming: Dr. E. Lang52 pages
- Data Structure: Edusat Learning Resource MaterialNo ratings yetData Structure: Edusat Learning Resource Material91 pages
- Unit 1: Introduction To Fundamental Data Types and StructuresNo ratings yetUnit 1: Introduction To Fundamental Data Types and Structures15 pages
- Csc121 - Topic 3 Algorithm Design For Sequence Control StructureNo ratings yetCsc121 - Topic 3 Algorithm Design For Sequence Control Structure37 pages
- LESSON 5 - Introduction To Programming Part 1No ratings yetLESSON 5 - Introduction To Programming Part 126 pages
- FP - Topic 2 - Types, Operators and ExpressionsNo ratings yetFP - Topic 2 - Types, Operators and Expressions86 pages
- Referential Integrity Sample 2 Tables QuiresNo ratings yetReferential Integrity Sample 2 Tables Quires2 pages
- Writing in Typst - Typst Documentation 3No ratings yetWriting in Typst - Typst Documentation 312 pages
- 15r0710b300 Sunway TG and TG Te Programming r05 enNo ratings yet15r0710b300 Sunway TG and TG Te Programming r05 en181 pages
- Powershell Commandlets - AppLocker ModuleNo ratings yetPowershell Commandlets - AppLocker Module28 pages
- FPP - Question - Bank - II-I-CSE-SR22 AnswerkeyNo ratings yetFPP - Question - Bank - II-I-CSE-SR22 Answerkey56 pages
- Namma Kalvi 12th Computer Science Question Bank em 216860No ratings yetNamma Kalvi 12th Computer Science Question Bank em 21686020 pages
- ReferenceManual OrthoVista (English) 45No ratings yetReferenceManual OrthoVista (English) 4586 pages
- UHFReader86 UHF RFID Reader User's Manual v1.10No ratings yetUHFReader86 UHF RFID Reader User's Manual v1.1041 pages
- 010430-A00 Domain Standard Graphics Quick Reference GPR and CTM Dec89No ratings yet010430-A00 Domain Standard Graphics Quick Reference GPR and CTM Dec8990 pages
- II ISemester B.Tech R23 Course Structure& SyllabiNo ratings yetII ISemester B.Tech R23 Course Structure& Syllabi20 pages
