About Course

This course provides Problem Solving skills as required by companies for Campus Recruitment and also for other Competitive exams. The contents of this course include analyzing and solving the problem, basic methodology in programming, problem solving skills etc…

Course Syllabus

Sorting

Problem 1

Sort elements by their frequency and index: Given an integer array, sort its element by their frequency and index. i.e., if two elements have different frequencies, then the one which has more frequency should come first; otherwise, the one which has less index should come first.

Input: [3, 3, 1, 1, 1, 8, 3, 6, 8, 7, 8]

Output:  [3, 3, 3, 1, 1, 1, 8, 8, 8, 6, 7]

Problem 2

Find the largest number possible from a set of given numbers where the numbers append to each other in any order to form the largest number

Input:  { 10, 68, 75, 7, 21, 12 }

Output:  77568211210

Searching

Problem 1

Given a sorted array ar[] and a target value, return the index of the first element in the array, which is greater than or equal to the target value, i.e., findthe ceil of the given target in ar[].

Problem 2

Given an array of sorted integers which represent box sizes and an integer representing an item size, find best fit box for the item, say ar=[1,2,5,6,8,9,15, 18, 20]and size=7, we should return 8 as outcome.

Stack

Problem 1

Implement two stacks in a single array.

Problem 2

Design a data structure for peek(), push(), pop() and getMin() operations. Make sure that all the mentioned operations take only O(1) time to execute.

Queue

Problem 1

Implement a queue using stack data structure

Problem 2

Design a Queue Data Structure ,which supports following operations enque, deque, and getMin() which takes O(1) time complexity.

Linked List

Problem 1

Reverse a singly linked list – Iterative and Recursive.

Input:  6->20->3->14->5->NULL

Output:  5->14->3->20->6->NULL

Problem 2

Find the midpoint of a linked-list.

Input:  1->2->3->4->5->NULL

Output:  3

If there are even nodes, then there would be two middle nodes, we need to print the second middle element.

Input:  1->2->3->4->5->6 ->NULL

Output:  4

Problem 3

Reverse second half of singly linked list

Input:  6->20->3->14->5->NULL

Output:  6->20->3->5->14->NULL

Trees

Problem 1

Convert a Binary Tree into its Mirror Tree. Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.

Problem 2

Print Left View of a Binary Tree Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side.

Graphs

Problem 1

Topological sorting using dfs.

Problem 2

Detect a cycle in a directed graph/ undirected graph.

Books and Materials

Text Books:

• Reema Thareja., Data Structures Using C, 2nd Edition, Oxford University Press, NewDelhiIndia, 2014.

Reference Books:

• Samanta Debasis., Classic Data Structures, 2nd Edition, Prentice Hall of India, NewDelhi,India, 2012.
• Ellis Horowitz., SartajSahni, Susan Anderson-Freed., Fundamentals of Data Structurein C, 2nd Edition University Press, India, 2008.

Online Resources

• https://sonucgn.files.wordpress.com/2018/01/data-structures-by-d-samantha.pdf
• https://caucse.club/wp-content/uploads/2022/05/Fundamentals-of-Data-Structures-in-C-EllisHorowitz-Sartaj-Sahni-etc.-.pdf
• https://www.mygreatlearning.com/blog/data-structures-using-c/
• https://www.youtube.com/watch?v=Db9ZYbJONHc