Data Structures and Algorithms for Top Product Companies

Introduction

Preparing for placements at top product-based companies like Microsoft, Amazon, D.E. Shaw, Directi, Intel, Nutanix, and KPIT requires a strong grasp of Data Structures and Algorithms (DSA). These companies frequently test candidates on their problem-solving abilities, making DSA a crucial subject for aspirants.

In this guide, we cover essential DSA topics with problem sets ranging from basic to advanced levels, ensuring you’re ready to ace coding interviews.

Key Topics Covered:

• Arrays (1D & 2D)
• Stacks, Queues & Linked Lists
• Trees & Graphs
• Sorting Algorithms
• Dynamic Programming Problems
• Miscellaneous DSA Challenges

Each section includes practical problems, making it easier to build problem-solving intuition.

1. Arrays

1D Arrays

• Basic Array Operations (Insert, delete, and search elements)
• Finding Smallest & Largest Elements
• Sum of Elements in an Array
• Checking if Two Arrays Are Identical
• Sorting and Reversing an Array
• Finding Non-Repeating & Duplicate Elements
• K’th Smallest Element in an Unsorted Array
• Median of Two Sorted Arrays

2D Arrays (Matrices)

• Matrix Addition & Subtraction
• Transpose of a Matrix
• Matrix Rotation (90 degrees clockwise & anti-clockwise)
• Finding the Saddle Point of a Matrix
• Spiral Order Matrix Printing
• Maximum Square Submatrix with All 1s

2. Sorting Algorithms

Sorting is a crucial topic in coding interviews. Understanding various sorting techniques and their time complexities helps in optimizing solutions.

Popular Sorting Algorithms:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort
• Shell Sort
• Comb Sort

3. Stacks, Queues, and Linked Lists

Stacks

• Stack Implementation (Array & Linked List)
• Balanced Parenthesis Checker
• Sorting a Stack Using a Temporary Stack
• Infix to Postfix & Prefix Conversion

Queues

• Queue Implementation (Array & Linked List)
• Circular Queue Implementation
• Reverse First K Elements of a Queue

Linked Lists

• Reverse a Linked List
• Remove Duplicates from a Linked List
• Detect a Loop in a Linked List

4. Trees & Graphs

Trees

• Height of a Binary Tree
• Finding K’th Maximum Value in a BST
• Vertical Sum of a Tree
• Nodes at K Distance from Root

Graphs

• Depth-First Search (DFS)
• Breadth-First Search (BFS)
• Finding Shortest Path Between Two Vertices
• Checking if a Graph is a Tree

5. Dynamic Programming (DP) Problems

• 0/1 Knapsack Problem
• Subset Sum Problem
• Word Break Problem
• Minimum Jumps to Reach the End of an Array
• Two Player Coin Game

Dynamic programming is widely tested in coding interviews. Understanding memoization and tabulation techniques is key to solving these problems efficiently.

6. Miscellaneous DSA Challenges

• Sudoku Solver
• Rat in a Maze Problem
• Number of Islands (Graph Problem)
• Minimum Sum Partition Problem
• Treasure and Cities Problem

These problems require a combination of graph theory, recursion, and dynamic programming.

Sample questions in Data Structures

1. Reverse a Linked List

Problem Statement:

Write a program to reverse a singly linked list.

Solution:

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void reverse(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

// Helper functions omitted for brevity

C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

void reverse(Node*& head) {
    Node *prev = nullptr, *curr = head, *next = nullptr;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}

Java

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; this.next = null; }
}

public class ReverseLinkedList {
    static Node reverse(Node head) {
        Node prev = null, current = head, next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
}

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse(head):
    prev = None
    current = head
    while current:
        next = current.next
        current.next = prev
        prev = current
        current = next
    return prev

2. Implement a Stack using Arrays

Problem Statement:

Design a stack using an array with push, pop, and display operations.

C

#include <stdio.h>
#define MAX 100

int stack[MAX], top = -1;

void push(int x) {
    if (top == MAX - 1) { printf("Stack Overflow\n"); return; }
    stack[++top] = x;
}

int pop() {
    if (top == -1) { printf("Stack Underflow\n"); return -1; }
    return stack[top--];
}

C++

#include <iostream>
#define MAX 100
using namespace std;

class Stack {
    int top, arr[MAX];
public:
    Stack() { top = -1; }
    void push(int x) {
        if (top == MAX - 1) { cout << "Overflow\n"; return; }
        arr[++top] = x;
    }
    int pop() {
        if (top == -1) { cout << "Underflow\n"; return -1; }
        return arr[top--];
    }
};

Java

class Stack {
    int top = -1;
    int[] arr = new int[100];

    void push(int x) {
        if (top == 99) { System.out.println("Overflow"); return; }
        arr[++top] = x;
    }

    int pop() {
        if (top == -1) { System.out.println("Underflow"); return -1; }
        return arr[top--];
    }
}

Python

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        if not self.stack:
            print("Underflow")
            return -1
        return self.stack.pop()

3. Implement a Queue using Two Stacks

Problem Statement:

Implement a queue using two stacks with enqueue and dequeue operations.

C++

#include <stack>
#include <iostream>
using namespace std;

class Queue {
    stack<int> s1, s2;

public:
    void enqueue(int x) { s1.push(x); }

    int dequeue() {
        if (s1.empty() && s2.empty()) { cout << "Queue is Empty\n"; return -1; }
        if (s2.empty()) {
            while (!s1.empty()) { s2.push(s1.top()); s1.pop(); }
        }
        int x = s2.top(); s2.pop();
        return x;
    }
};

Java

import java.util.Stack;

class Queue {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();

    void enqueue(int x) { s1.push(x); }

    int dequeue() {
        if (s1.isEmpty() && s2.isEmpty()) { System.out.println("Queue is Empty"); return -1; }
        if (s2.isEmpty()) { while (!s1.isEmpty()) { s2.push(s1.pop()); } }
        return s2.pop();
    }
}

Python

class Queue:
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def enqueue(self, x):
        self.s1.append(x)

    def dequeue(self):
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        if not self.s2:
            print("Queue is Empty")
            return -1
        return self.s2.pop()

4. Find the Middle Element of a Linked List

Problem Statement:

Find the middle element of a singly linked list in O(n) time.

C

struct Node {
    int data;
    struct Node* next;
};

void findMiddle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    printf("Middle Element: %d\n", slow->data);
}

C++

void findMiddle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    cout << "Middle Element: " << slow->data << endl;
}

Java

void findMiddle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    System.out.println("Middle Element: " + slow.data);
}

Python

def find_middle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    print("Middle Element:", slow.data)

Conclusion

Mastering Data Structures and Algorithms is essential for cracking placement tests at top tech companies. By practicing these problems and understanding core concepts, you’ll be well-prepared for coding interviews.