Programming Interview Questions

Introduction

In this blog, we will be discussing programming interview questions. We are all aware of how important it is to have knowledge of basic programming to do well in interviews. The interview may be for any language, but the foundation remains the same: the question is how strong we are in programming logic foundations.

This blog features the top 30 programming interview questions. So without wasting any time let's get started with some important programming interview questions.

Also Read: Java OOPs Interview Questions

Programming Interview Questions

1. What are Data Structures?

A data structure is a storage used to store and organize data. It is a method of organizing data on a computer that can be accessed and updated quickly.

Choosing the right data structure for your project depends on your requirements and project. For example, if you want to store data in memory sequentially, you can use the Array data structure.

Must Read Algorithm Types

2. What is an Array?

An array is a linear data structure. Memory elements in an array are arranged in continuous memory. An array's elements are all of the same types. The type of elements stored in arrays depends on the programming language.

3. How can you find the peak element in an array?

The peak element is an element that is greater than both of its adjacent elements.

We can use a linear search to find the element that is greater than both of its neighbors. However, it takes O(n) time. 

Hence to optimize, we can use the binary search method to locate a peak in O(log N) time. 

1. If the mid element is greater than both neighbors, we return it.
2. If the mid element is smaller than the left neighbor, the peak element must be in the array's left half.
3. If the mid element is smaller than the right neighbor, the peak element must be in the array's right half.

4. How can you swap two elements without using any extra variable?

#include <iostream>
using namespace std;
int main() {
int a, b;
cin>>a>>b;


// swap without using extra variable
a = a - b;
b = a + b;
a = b - a;


return 0;
}

5. What is bubble sort?

The Bubble Sort algorithm compares each pair of adjacent elements when sorting. Each iteration brings the array's elements closer to the end, similar to how air bubbles rise to the surface of the water. Sorting is done in this case through passes or iteration. As a result, at the end of each iteration, the largest element is returned to its proper place in the list.

Step1: intialize k = 0 and loop till n-1 repeating Step 2

Step2: for j = k + 1 to n – k repeat

Step3: if A[j] > A[k]

           Swap A[j] and A[k]

           [end of inner for loop

           [end of outer for loop]

Step4: end

In the best-case scenario, the bubble sort has a complexity of O(N*N).The worst-case time complexity of bubble sort in quadratic o(N*N).

6. What is merge sort?

The merge sort algorithm employs the "divide and conquer" strategy, in which we divide the problem into subproblems and solve each one individually.

These subproblems are then combined or merged to form a complete solution.

• By dividing the list on the middle element, the list is divided into two arrays of equal length. The list is considered sorted if the number of elements in it is either 0 or 1.
• Each sublist is sorted individually using a recursive merge sort.
• The sorted sublists are then combined or merged to form the final sorted list.

Psudeocode-

Declare an array Arr of length N

If N=1, Arr is already sorted

If N>1,

Left = 0, right = N-1

Find middle = (left + right)/2

Call merge_sort(Arr,left,middle) =>sort first half recursively

Call merge_sort(Arr,middle+1,right) => sort second half recursively

Call merge(Arr, left, middle, right) to merge sorted arrays in above steps.

Exit

7. What is the difference between comparison-based and non-comparison-based sorting algorithms?

Following are the point of difference between the two-

1. Speed - Because there is no comparison, non-comparison sorting is usually faster than comparison sorting. The speed limit for a comparison-based sorting algorithm is O(NlogN), whereas the limit for non-comparison-based algorithms is O(n), i.e., linear time.
2. Memory -The best case for memory complexity with the comparison-based sorting is O(1); on the other hand, memory complexity for the non-comparison-based sorting algorithm is always O(n).
3. Comparator-based sorting algorithms, such as QuickSort, MergeSort, or HeapSort, require a comparator to sort elements, such as when sorting an array of Strings, whereas non-comparison-based sorting algorithms do not

8. What is a string?

A string is a contiguous sequence of symbols or values, such as a character string or a binary digit string. A string can contain any visible or invisible sequence of characters, and characters can be repeated. The length of a string is the number of characters in it.

9. In Java, what is the distinction between String, StringBuilder, and StringBuffer?

The main distinction is that string is immutable, whereas StringBuilder and StringBuffer are both mutable. Also, unlike StringBuffer, StringBuilder is not synchronized, so it is faster and should be used for temporary String manipulation.

10. How can you check if two strings are anagrams or not?

There are two possibilities for solving this problem.

Method 1: Count the frequency of alphabets in both strings and store the results in the appropriate arrays. Return true if these two arrays are equal. Otherwise, return false.

Method 2: Sort both strings and compare whether or not they are equal. Return true if they are equal. Otherwise, return false.

11. Write a program to check if a string is a palindrome?

A palindrome string is a string that reads the same forward and backward.

1. We simply match the first character with the last, the second with the second last, and so on.
2. This process terminates when it reaches the middle of the string or if any character in the string does not satisfy the given conditions, i.e., they are not matched.

for(i=0;i < len ;i++){
        if(str[i] != str[len-i-1]){
            temp = 1;
        break;
   }
}

12. What is a linked list data structure?

A Linked List is a linear data structure comprised of connected nodes, each with corresponding data and a pointer to the next node's address.

The head is the first node in a linked list and serves as an access point. The last node, on the other hand, is known as the tail, and it points t a NULL value indicating the end of a linked list.

13. How can you find the middle element of a linked list?

We can find the middle element of the linked list by traversing the linked list twice. First time for finding the length of the linked list and then traversing the linked list for (N/2) length.

A better approach would be using two-pointers.

1. We will use two pointers, "slow" and "fast" Set both pointers to the head node at first.
2. Traverse the linked list using a loop (fast!= NULL, and fast->next!= NULL) until the fast pointer reaches the last node of the linked list.
3. The slow pointer moves one node per iteration, while the fast pointer moves two nodes.
4. When the fast pointer reaches the last node, the slow pointer points to the middle node.

if(head == NULL){
return NULL;
}
struct node *slow, *fast;
slow = fast = head;

while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
return slow->data;

14. What are the disadvantages of a linked list?

A node in a linked list takes more space.

We have to traverse the linked list starting from the head to find a particular element. Consequently, reversing the linked list is difficult.

15. What is a stack?

A stack is a conceptual structure made up of a collection of homogeneous elements that operates on the last in, first out principle (LIFO). It is a popular abstract data type with two major operations: push and pop. Push and pop operations are performed on the topmost element, which is the most recently added item to the stack. The push operation adds an element to the stack, whereas the pop operation removes an element from the top position of the stack. The stack concept is used in computer programming and memory organization.

16. What are infix, postfix, and prefix expressions?

Infix:

The operator appears between two operands in the infix expression. T. For example, 2 + 3, a * b, 6 / 3, and so on.

We can read it as two is added to three.

operator > operand1 > operand2 

Prefix:

The operator comes before the two operands in prefix expression. For example: + 6 8, * x y, - 3 2, and so on.

We can read it as Add two and three.

operand 1 > operand 2 > operator

Postfix:

The operator comes after the two operands in postfix expression. For example, 5 7 +, a b *, 12 6 /, and so on.

We can read it as 2 and 3 are added.

operator > operand 1 > operand 2 

17. How can we reverse a string using a stack?

We can reverse a string by the following steps.

1. Make an empty stack 
2. Push all characters of string one by one to stack 
3. Pop all characters from the stack and put them back into the string

18. What is a queue data structure?

Queue, like stack data structure, is a linear data structure in which the first element is inserted from one end, called the REAR (also called the tail), and the existing element is removed from the other end, called the FRONT (also called the head).

19. What are LIFO and FIFO?

LIFO is an acronym that stands for Last-in, First-Out. The LIFO technique, as the name implies, allows the data that was entered last to exit first.

The stack data structure in data structures employs the LIFO technique for data maintenance.

FIFO is an acronym that stands for First-in, First-Out. As the name implies, the data entered first will also exit first in the FIFO technique.

The queue data structure in data structures employs the FIFO technique for data maintenance.

20. What is a Doubly Linked List?

Doubly Linked List are a type of linked list in which traversal across the data elements is possible in both directions.

This is made possible by the presence of two links in each node, one to the node next to it and one to the node before it.

21. What is a binary tree?

A Binary Tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child, and the topmost node in the tree is called the root.

22. Define perfect, complete, and full binary trees.

• In a full binary tree, every node has 0 or 2 children.
• A Binary Tree is Complete if all levels are completely filled except the last, and the last level has all keys as far to the left as possible.
• A binary tree is a Perfect Binary Tree with all internal nodes having two children and all leaf nodes at the same level.

23. What is a binary search algorithm?

It is a method of searching. It employs the divide and conquer strategy. Only sorted data can be used for binary search. Completion takes O(log n) time.

It splits the given array in half and checks the middle element. If the middle element is less than the element to be searched, the algorithm chooses the second half of the array while discarding the first.

24. What is a graph?

A graph is a data structure consisting of a finite number of nodes (or vertices) and the edges that connect them.

An edge is a pair (x,y) that communicates that the x vertex connects to the y vertex.

25. What is a directed and undirected graph?

Edges in directed graphs connect nodes at one end to nodes at the other. Edges in undirected graphs simply connect the nodes at each end.

26. What is DFS?

The DFS Algorithm is used to traverse or search trees or graph data structures. Starting at the root (choosing an arbitrary node as the root for a graph), one explores each branch as far as possible before backtracking.

Pseudocode- 

procedure dfs(vertex v)

{

    visit(v);

    for each neighbor u of v

        if u is undiscovered

            call dfs(u);

}

27. What is the graph coloring problem?

Graph coloring (also known as vertex coloring) is a method of coloring the vertices of a graph so that no two adjacent vertices share the same color. This post will go over a greedy algorithm for graph coloring that aims to reduce the total number of colors used.

28. What is topological sorting?

A Topological sort of a directed graph is a linear ordering of its vertices in which u comes before v in the ordering for every directed edge uv from vertex u to vertex v. A topological ordering is only possible if the graph has no directed cycles, i.e. if the graph is a DAG.

29. What is overloading and overriding?

Function overloading is a concept in which two or more functions in the same class with the same name are defined with the condition that their parameters differ in number or type.

Function overriding is a concept in which two functions with the same name and parameters are defined, with the condition that one function must be present in a base class and the other function in a derived class.

30. What does the degree of a vertex in a graph mean?

It's defined as the number of edges that intersect a vertex. If the degree of vertex v is zero, it means that v does not belong to any edge, and this node is referred to as an isolated vertex.