Infosys, one of the largest IT services companies in the world, has been a leader in software development, consulting, and outsourcing for decades. It is also one of the most sought-after employers for aspiring software engineers, offering lucrative career opportunities, a dynamic work environment, and a chance to work with cutting-edge technologies.
Getting a job at Infosys requires candidates to go through a rigorous hiring process that includes multiple rounds of interviews. These interviews are designed to test a candidate’s problem-solving skills, technical knowledge, and ability to write code that solves complex problems. One of the crucial aspects of the Infosys technical interview is the ability to write and interpret pseudo code.
Pseudo code plays a significant role in the world of software development as it serves as a bridge between algorithmic thinking and code implementation. It helps developers plan the logic and structure of their programs before translating them into actual code. Pseudocode is a key element in many coding interviews, and it often acts as a starting point for developers to visualise and organise their thoughts.
The purpose of this article is to provide a comprehensive guide to pseudo code, focusing on its importance, how to write it effectively, and common pseudo code questions that candidates face during Infosys interviews. Whether you’re preparing for an Infosys interview or simply looking to strengthen your problem-solving skills, this guide will help you become proficient in writing and interpreting pseudo code.
Understanding Pseudo Code
Pseudo code is a simplified, high-level version of code written in plain English (or any other natural language). It is used to express the logic of an algorithm without focusing on the syntactical rules of a specific programming language. Pseudo code often mimics the structure of a program but uses natural language descriptions and simple statements to convey the logic.
The purpose of pseudo code is to outline the step-by-step process that the program will follow to solve a given problem. Since it doesn’t require strict adherence to programming language syntax, pseudo code is easy to read and understand by both technical and non-technical people. It also allows developers to concentrate on the core logic of the algorithm rather than getting bogged down by details like variable declarations, type definitions, or memory management.
In a coding interview, pseudo code is a valuable tool for showing the interviewer how you approach problem-solving. It helps you communicate your thought process clearly and allows the interviewer to evaluate your understanding of algorithms and data structures without the distractions of language-specific syntax.
Key Characteristics of Well-Written Pseudo Code
When writing pseudo code, it’s essential to keep a few characteristics in mind. Well-written pseudo code should be:
- Readable: The primary purpose of pseudo code is to be easily understandable. Anyone reading the pseudo code should be able to follow the logic without needing to know a specific programming language.
- Language-Agnostic: Pseudo code should avoid the use of any language-specific syntax. It should remain general and rely on plain English (or another language) to describe what needs to be done.
- Structured: The pseudo code should follow a clear structure that resembles programming constructs, such as loops, conditionals, and function calls. This ensures that the logic is easy to follow.
- Abstract: Pseudo code should focus on solving the problem and avoid unnecessary details like variable types, low-level memory management, or specific implementation concerns.
- Modular: If the solution involves multiple steps, break the pseudo code into smaller modules or functions to make it more organised and manageable.
Best Practices for Writing Pseudo Code
Writing pseudo code effectively requires some practice and adherence to best practices. These best practices will help you create pseudo code that is easy to follow and aligns with how real programs are structured:
Keep It Simple: Avoid making your pseudo code overly complicated. Focus on the essential logic, and avoid unnecessary technical details. For instance, instead of specifying variable types, focus on describing the operations that need to be performed.
Use Indentation: Just like actual code, pseudo code should be properly indented to maintain readability. Indentation is particularly important for nested loops, conditionals, and other control flow constructs.
Clear and Concise Language: Each step of the pseudo code should be short and to the point. Avoid long-winded explanations and focus on using simple, clear language to describe each operation.
Consistent Formatting: Use a consistent format throughout the pseudo code. For instance, if you’re using indentation or a particular naming convention for functions, maintain that consistency throughout the document.
Avoid Low-Level Details: Pseudo code should focus on the big picture and avoid delving into low-level details such as memory allocation or specific data types. The goal is to describe the algorithm, not the implementation specifics.
Use Plain Descriptions: When defining variables or functions, use plain language to describe their purpose. For example, instead of “x” or “y”, use “counter” or “sum” if that better represents the variable’s role in the algorithm.
By following these best practices, you can write pseudo code that effectively communicates your approach to problem-solving and is easy for others to understand.
Now that you know what pseudocode is, let’s see how it’s used in Infosys interviews.
Pseudo Code Questions in Infosys Interviews
During Infosys technical interviews, candidates are often asked to solve problems using pseudo code. These problems can range from basic algorithmic tasks to more advanced problems involving data structures and algorithms. Let’s take a closer look at the types of pseudo code questions you may encounter.
Basic Algorithms and Data Structures
1) Sorting Algorithms
Sorting algorithms are a staple of coding interviews, and Infosys is no exception. Sorting is the process of arranging items in a specific order, typically either ascending or descending. There are several sorting algorithms that you may need to know, including:
Bubble Sort: Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. The process continues until the list is sorted.
Pseudo Code for Bubble Sort:
css
for i = 0 to length(arr) – 1:
for j = 0 to length(arr) – i – 1:
if arr[j] > arr[j + 1]:
swap(arr[j], arr[j + 1])
In bubble sort, we keep passing through the list multiple times, swapping adjacent elements if they are out of order. The largest element “bubbles up” to the top in each pass.
Insertion Sort: Insertion sort builds the final sorted array one element at a time. It works by picking each element and inserting it into its correct position relative to the already sorted portion of the array.
Pseudo Code for Insertion Sort:
less
for i = 1 to length(arr):
key = arr[i]
j = i – 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j – 1
arr[j + 1] = key
In this algorithm, we assume that the first element is already sorted. Then, for each subsequent element, we compare it with the elements in the sorted portion and insert it into its correct position.
Merge Sort: Merge sort is a divide-and-conquer algorithm that recursively divides the array into two halves, sorts each half, and then merges the sorted halves to form the complete sorted array.
Pseudo Code for Merge Sort:
less
function mergeSort(arr):
if length(arr) > 1:
mid = length(arr) // 2
left = arr[0:mid]
right = arr[mid:]
mergeSort(left)
mergeSort(right)
merge(left, right, arr)
function merge(left, right, arr):
i = j = k = 0
while i < length(left) and j < length(right):
if left[i] < right[j]:
arr[k] = left[i]
i = i + 1
else:
arr[k] = right[j]
j = j + 1
k = k + 1
while i < length(left):
arr[k] = left[i]
i = i + 1
k = k + 1
while j < length(right):
arr[k] = right[j]
j = j + 1
k = k + 1
Merge sort divides the array into smaller subarrays, sorts them, and then merges them back together. It has a time complexity of O(n log n), making it more efficient than bubble sort and insertion sort for large datasets.
Quick Sort: Quick sort is another divide-and-conquer algorithm. It picks a “pivot” element, partitions the array around the pivot (so that elements smaller than the pivot come before it, and elements greater than the pivot come after it), and then recursively sorts the subarrays.
Pseudo Code for Quick Sort:
sql
function quickSort(arr, start, end):
if start < end:
pivot = partition(arr, start, end)
quickSort(arr, start, pivot – 1)
quickSort(arr, pivot + 1, end)
function partition(arr, start, end):
pivot = arr[end]
i = start – 1
for j = start to end – 1:
if arr[j] < pivot:
i = i + 1
swap(arr[i], arr[j])
swap(arr[i + 1], arr[end])
return i + 1
In quick sort, the array is divided into smaller subarrays based on a pivot element, and the process is repeated for each subarray. The algorithm efficiently sorts the array in O(n log n) time on average.
2) Searching Algorithms
Searching algorithms are used to find a specific element in a list or array. The two most common searching algorithms you may encounter in Infosys interviews are:
Linear Search: Linear search is the simplest search algorithm, where you check each element of the array or list sequentially until the target element is found or the list ends.
Pseudo Code for Linear Search:
arduino
function linearSearch(arr, target):
for i = 0 to length(arr) – 1:
if arr[i] == target:
return i
return -1
Linear search has a time complexity of O(n) because, in the worst case, you have to check every element in the list.
Binary Search: Binary search is a more efficient search algorithm, but it only works on sorted arrays. The idea is to repeatedly divide the array in half and check if the middle element is the target. If not, you determine whether the target is in the left or right half of the array and continue the search.
Pseudo Code for Binary Search:
vbnet
function binarySearch(arr, target):
start = 0
end = length(arr) – 1
while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
start = mid + 1
else:
end = mid – 1
return -1
Binary search has a time complexity of O(log n), making it much faster than linear search for large datasets. However, the array must be sorted for binary search to work.
3) Linked Lists
A linked list is a linear data structure in which elements are stored in nodes. Each node contains data and a reference (or pointer) to the next node in the sequence. Linked lists are commonly used when you need a dynamic data structure that can grow and shrink at runtime.
Traversal: Traversal refers to visiting each node in the linked list in order.
Pseudo Code for Linked List Traversal:
bash
function traverseLinkedList(head):
current = head
while current != null:
print(current.data)
current = current.next
This pseudo code starts at the head of the linked list and prints the data of each node until it reaches the end (null).
Insertion: Insertion can occur at the beginning, end, or in the middle of the linked list. The following pseudo code demonstrates how to insert a node at the head of the list.
Pseudo Code for Insertion at Head:
bash
function insertAtHead(head, data):
newNode = createNode(data)
newNode.next = head
head = newNode
return head
This code creates a new node, sets its “next” pointer to the current head, and updates the head to point to the new node.
Deletion: Deletion involves removing a node from the linked list. The following pseudo code demonstrates how to delete a node with a specific value.
Pseudo Code for Deletion:
lua
function deleteNode(head, target):
if head.data == target:
head = head.next
else:
current = head
while current.next != null and current.next.data != target:
current = current.next
if current.next != null:
current.next = current.next.next
return head
In this code, the target node is searched for in the list. If it’s found, the node is removed by adjusting the “next” pointer of the previous node.
4) Stacks and Queues
Stacks and queues are linear data structures that follow specific order rules for adding and removing elements.
Stacks: A stack follows the Last-In-First-Out (LIFO) principle, meaning the last element added is the first one to be removed. Common operations on stacks include:
Push: Adds an element to the top of the stack.
Pseudo Code for Push:
arduino
function push(stack, element):
stack[top + 1] = element
top = top + 1
Pop: Removes and returns the top element of the stack.
Pseudo Code for Pop:
arduino
function pop(stack):
if top == -1:
return “Stack is empty”
else:
top = top – 1
return stack[top + 1]
Queues: A queue follows the First-In-First-Out (FIFO) principle, meaning the first element added is the first one to be removed. Common operations on queues include:
Enqueue: Adds an element to the end of the queue.
Pseudo Code for Enqueue:
arduino
function enqueue(queue, element):
queue[rear + 1] = element
rear = rear + 1
Dequeue: Removes and returns the front element of the queue.
Pseudo Code for Dequeue:
arduino
function dequeue(queue):
if front > rear:
return “Queue is empty”
else:
front = front + 1
return queue[front – 1]
5) Trees
Trees are hierarchical data structures where each node has a value and references to its children. The most common type of tree used in interviews is the Binary Search Tree (BST), where each node has at most two children, and the left child is smaller than the parent, while the right child is greater.
In-order Traversal: Traversing the tree in in-order visits the left subtree, the root, and then the right subtree.
Pseudo Code for In-order Traversal:
php
function inOrderTraversal(root):
if root != null:
inOrderTraversal(root.left)
print(root.data)
inOrderTraversal(root.right)
Insertion: Inserting a new node into a binary search tree maintains the order property of the tree.
Pseudo Code for BST Insertion:
kotlin
function insertNode(root, data):
if root == null:
return createNode(data)
if data < root.data:
root.left = insertNode(root.left, data)
else:
root.right = insertNode(root.right, data)
return root
In this code, we recursively traverse the tree until we find the correct position to insert the new node, either as the left or right child.
Deletion: Deleting a node from a binary search tree can be more complicated, depending on whether the node has no children, one child, or two children.
Pseudo Code for BST Deletion:
kotlin
function deleteNode(root, target):
if root == null:
return root
if target < root.data:
root.left = deleteNode(root.left, target)
elif target > root.data:
root.right = deleteNode(root.right, target)
else:
if root.left == null:
return root.right
elif root.right == null:
return root.left
temp = findMin(root.right)
root.data = temp.data
root.right = deleteNode(root.right, temp.data)
return root
function findMin(root):
while root.left != null:
root = root.left
return root
In this code, we first find the node to delete. If the node has two children, we find the minimum value in the right subtree to replace the deleted node.
6) Graphs
Graphs are a more complex data structure used to represent relationships between objects. In a graph, objects are called vertices, and connections between them are called edges. There are two common traversal algorithms used in graphs:
Breadth-First Search (BFS): BFS explores the vertices of a graph level by level, visiting all the vertices at the present depth before moving on to the next level.
Pseudo Code for BFS:
c
function BFS(graph, start):
queue = []
visited = set()
enqueue(queue, start)
while queue is not empty:
node = dequeue(queue)
if node not in visited:
print(node)
visited.add(node)
for each neighbor of node:
if neighbor not in visited:
enqueue(queue, neighbor)
BFS uses a queue to keep track of the nodes to be explored. Starting from the “start” node, it explores all its neighbors before moving to the next level.
Depth-First Search (DFS): DFS explores as far as possible along each branch before backtracking. It uses recursion or a stack to keep track of nodes.
Pseudo Code for DFS:
php
function DFS(graph, node, visited):
if node not in visited:
print(node)
visited.add(node)
for each neighbor of node:
if neighbor not in visited:
DFS(graph, neighbor, visited)
DFS explores each branch of the graph deeply before moving on to the next unvisited node.
Problem-Solving and Logic
In addition to basic algorithms and data structures, Infosys interviewers often test candidates’ problem-solving and logical thinking through more advanced topics. Some of the key topics in this area include:
1) Recursion and Backtracking Problems
Recursion is a fundamental programming concept where a function calls itself to solve smaller instances of the same problem. Backtracking is a special type of recursion where you try all possible solutions and discard the ones that don’t work.
Example of Recursion: Solving the factorial of a number using recursion.
Pseudo Code for Factorial:
arduino
function factorial(n):
if n == 1:
return 1
else:
return n * factorial(n – 1)
This pseudo code defines a recursive function to calculate the factorial of a number. It keeps calling itself with a smaller input until it reaches the base case (n == 1).
Example of Backtracking: The N-Queens problem is a classic example of a backtracking problem. The task is to place N queens on an N x N chessboard such that no two queens threaten each other.
Pseudo Code for N-Queens Problem:
java
function solveNQueens(board, col):
if col >= N:
return true
for i = 0 to N – 1:
if isSafe(board, i, col):
board[i][col] = 1
if solveNQueens(board, col + 1):
return true
board[i][col] = 0
return false
The function recursively tries placing queens column by column. If placing a queen leads to a solution, the function returns true. If it leads to a dead end, the algorithm backtracks and tries a different position.
2) Dynamic Programming Problems
Dynamic programming (DP) is a technique used to solve problems by breaking them down into smaller subproblems and storing the results of these subproblems to avoid redundant work.
Example of Fibonacci Sequence using Dynamic Programming:
Pseudo Code for Fibonacci with DP:
less
function fibonacci(n):
if n <= 1:
return n
fib = array of size n + 1
fib[0] = 0
fib[1] = 1
for i = 2 to n:
fib[i] = fib[i – 1] + fib[i – 2]
return fib[n]
In this pseudo code, the Fibonacci sequence is calculated iteratively using a dynamic programming approach, where the results of previous calculations are stored in an array.
3) Greedy Algorithms
A greedy algorithm is one that makes the locally optimal choice at each step, with the hope of finding the global optimum. Greedy algorithms are used in optimization problems where the goal is to find the best solution.
Example of the Coin Change Problem:
Pseudo Code for Greedy Coin Change:
sql
function coinChange(coins, amount):
sort(coins in descending order)
result = []
for each coin in coins:
while amount >= coin:
result.append(coin)
amount = amount – coin
if amount == 0:
return result
else:
return “No solution”
This pseudo code solves the coin change problem by always taking the largest possible denomination of coins first. However, it works only if the coin denominations are such that a greedy solution leads to the correct answer.
4) Divide-and-Conquer Algorithms
Divide-and-conquer is a strategy of solving problems by dividing them into smaller subproblems, solving each subproblem, and then combining the results. Many sorting algorithms, such as merge sort and quick sort, use divide-and-conquer techniques.
Example of Merge Sort (Divide-and-Conquer):
Pseudo Code for Merge Sort:
less
function mergeSort(arr):
if length(arr) > 1:
mid = length(arr) // 2
left = arr[0:mid]
right = arr[mid:]
mergeSort(left)
mergeSort(right)
merge(left, right, arr)
function merge(left, right, arr):
i = j = k = 0
while i < length(left) and j < length(right):
if left[i] < right[j]:
arr[k] = left[i]
i = i + 1
else:
arr[k] = right[j]
j = j + 1
k = k + 1
while i < length(left):
arr[k] = left[i]
i = i + 1
k = k + 1
while j < length(right):
arr[k] = right[j]
j = j + 1
k = k + 1
Merge sort recursively divides the array into smaller parts, sorts each part, and then merges the sorted subarrays to produce the final sorted array.
To ace these questions, you need to practise and have a strong foundation in pseudo code. Let’s discuss some tips to help you do just that.
Tips for Tackling Pseudo Code Questions
Here are some tips to help you tackle pseudo code questions in Infosys interviews:
Problem-Solving Approach
When facing pseudo code questions in an interview, it’s essential to have a structured approach to problem-solving. Here are some tips for approaching pseudo code questions:
Understand the Problem Statement: Read the problem statement carefully to ensure you fully understand the requirements. Don’t rush into writing pseudo code before you’re clear on what the problem is asking.
Break the Problem Down: Decompose the problem into smaller subproblems. This makes it easier to manage and allows you to focus on solving one piece at a time.
Develop a Logical Flow: Plan the sequence of operations you will perform. Think about the control flow, such as loops and conditionals, and how the problem will be solved step by step.
Pseudo Code Writing Techniques
Writing pseudo code requires a different mindset than writing actual code. Here are some tips to help you write better pseudo code:
Use Clear and Concise Language: Pseudo code should be easy to read and understand. Avoid using complex language or over-complicating the logic. Keep your statements simple and to the point.
Consistent Indentation and Formatting: Use consistent indentation and formatting to maintain readability. This is particularly important for nested loops and conditionals, as proper indentation helps make the logic clearer.
Avoid Unnecessary Details: Pseudo code is meant to focus on the logic of the problem, not the details of implementation. Avoid specifying things like variable types or low-level optimizations unless they are relevant to the logic of the solution.
Interview Preparation Strategies
To succeed in Infosys interviews, you need to prepare thoroughly. Here are some strategies to help you prepare for pseudo code questions:
Practice with Sample Questions: The best way to prepare for pseudo code questions is to practise solving similar problems. Use coding practice platforms like iScalePro to access sample questions that are similar to those asked in Infosys interviews.
Time Management: In an interview, time is limited. Practice solving problems within a specific time frame to improve your speed and efficiency.
Practice on Paper or Whiteboard: In many coding interviews, you’ll be asked to write code or pseudocode on a whiteboard or paper rather than using a computer. Practice solving problems in this format to get comfortable with it.
Conclusion
Pseudocode is an essential tool for solving problems and demonstrating your problem-solving skills in technical interviews. It simplifies complex algorithms by allowing you to focus on the logic rather than the syntax of a programming language. In Infosys interviews, pseudo code questions often cover fundamental topics like sorting algorithms, data structures, recursion, and dynamic programming.
By mastering the art of writing pseudo code and practising common algorithmic problems, you can improve your chances of performing well in Infosys interviews. Remember to keep your pseudo code clear, concise, and focused on the problem at hand. By following the tips and techniques outlined in this guide, you’ll be well-prepared to tackle pseudo code questions in your Infosys interview.
