Coding Problems previously asked in Infosys interview for SP and DSE Role

(These problems were also asked in different companies interviews

including flipkart, amazon, Microsoft, IBM,etc)

##NOTE: Extracted from interview experiences shared by candidates online

1. Swap two numbers without using a third variable

2. It is related to hashmap like we have given N inputs in the form of a

character and an integer and in the last we have to arrange them
according to characters.

3. the Third one is to check whether a number is a palindrome or not if it is

then find the next palindrome number.

4. Do any binary tree traversal. In this, he did not tell me to write code but
only tell me to make a tree in the paint and draw recursion calls and side
by side write the output in the notepad

5. I have done all four coding questions and for all the coding questions he
asked me to dry run for any input step by step in the notepad.

6. After this he asked me 2-3 networking questions which I was not able to
answer.

7. After this he asked me oops the concept that is four pillars of oops and I
explained all four that is inheritance, Polymorphism, Abstraction, and
Encapsulation.

8. Write a code for Bubble Sort.

9. “A has a list of cities and the distance between each pair of cities. Write
a program to find the shortest possible route A can take such that A can
visit all the cities exactly once and then return to the origin city.”
(travelling salesman prob)
10. Write a code to reverse a linked list

11. Write a code to merge two sorted arrays without using extra space

12. Write code to calculate the factorial of a number.

13. Given a sorted array nums, remove the duplicates in-place such that
each element appears only once and returns the new length. Do not
allocate extra space for another array; you must do this by modifying the
input array in-place with O(1) extra memory.

14. Given a sorted array and a target value, find the element in the array that
is closest to the target value.
15. Reverse a singly linked list.

16. Given a string, find the first non-repeating character in it and return its
index. If it does not exist, return -1.

17. Given an array of integers, find the first repeated number in the array.

18. Given an array of positive numbers, find the minimum sub array whose
sum is greater than or equal to a given number ‘S’.

19. Solve the third problem from Binary Tree using BFS.

20. Given a list of natural numbers, find the largest increasing subsequence

from it.
21. Given the root of a binary tree, invert the tree, and return its root.

22. Given an array, find the next greater element (NGE) for every element.
The Next greater Element for an element x is the first greater element on
the right side of x in the array. Elements for which no greater element
exist, consider the next greater element as -1.

23. Given a string, find the largest subarray with equal character frequency.

24. Write a program to print the frequencies of elements in an array.

25. How do you swap two numbers without using a third variable?

26. Write code to find the next palindrome in O(1) time complexity.

27. Given a sentence, reverse the order of words in it.

28. Given a sorted 2D matrix, how would you search for an element?
 29. Find the first occurrence of the target value in a sorted array. (Duplicates
are allowed)

30. Given an array with positive and negative integers, find the maximum
subarray sum.

31. Given an array of integers, return the frequency of each element in the

array.

Candidate Experience:

I was provided with 2 DSA questions, and was given an option to pick
one and solve in 45 mins duration. Since there were some problems in
opening my coding assessment link, interviewer provided both questions
in virtual meet chat.

Question1 - you are given N(len of arrays), X(int), Y(int), Z(int), A(int[]),
B(int[]), sum = 0 and 3 arithmetic operations that can be performed
using A, B, X, Y, Z upon sum. Any operations including X, Y, Z is possible
only when their values are greater than 0. After N iterations you have to
obtain the maximum sum value that can be obtained.
Question2 - Find K-most frequent element in an array

32. find the total number of similar characters occurring in a string (e.g., for
the string "aaabbbcc", the output should be a=3, b=3, c=2). I wrote the
complete code, explained it to him, and also discussed the time
complexity.

33. Coding Question 1: Bit Manipulation

34. Problem: You are given a series of bulbs where each bulb glows based on
the number of times a switch is toggled (n).
Task: Determine the glowing pattern of the bulbs for a given number of
toggles.
Key Insight: The glowing pattern is derived from the binary
representation of n, where bulbs glow only when the binary pattern
consists of alternating bits starting from 1.

35. Coding Question 2: DFS in Graph

36. Problem: You are given a 2D grid representing a battlefield with warships
(represented as 1s) and water (represented as 0s).
Task: Determine the number of distinct warship groups (islands) in the
grid. Warships are considered connected if they are adjacent horizontally
or vertically.
Key Insight: This is a variation of the classic "Number of Islands"
problem. The solution involves using Depth First Search (DFS) to traverse
the grid and count connected components.

37. You are given an array/list consisting of 0 and 1 only. Your task is to find
the sum of the number of subarrays that contains only 1 and the number
of subarrays that contains only 0.
An array 'C' is a subarray of array 'D' if 'C' can be obtained from 'D' by
deletion of several elements from the beginning and several elements
from the end. Example
Let 'ARR' = [1,0,0] then the possible subarrays of 'ARR' will be: {1}, {0},
{0}, {1,0}, {0,0}, {1,0,0}.
Important Interview Problems to prepare:

Arrays:

1. https://www.geeksforgeeks.org/dsa/chocolate-distribution-problem/
2. https://leetcode.com/problems/search-in-rotated-sorted-
array/description/
3. https://leetcode.com/problems/next-permutation/description/
4. https://leetcode.com/problems/best-time-to-buy-and-sell-
stock/description/
5. https://www.interviewbit.com/problems/repeat-and-missing-number-
array/
6. https://leetcode.com/problems/kth-largest-element-in-an-
array/description/
7. https://leetcode.com/problems/maximum-product-
subarray/description/
8. https://www.geeksforgeeks.org/problems/kth-smallest-element5635/1
9. https://leetcode.com/problems/trapping-rain-water/description/
10. https://leetcode.com/problems/product-of-array-except-
self/description/

Strings:

1. https://www.geeksforgeeks.org/problems/consecutive-elements2306/1
2. https://www.geeksforgeeks.org/dsa/print-all-the-duplicates-in-the-
input-string/
3. https://leetcode.com/problems/longest-substring-without-repeating-
characters/description/

Matrix:

1. https://www.geeksforgeeks.org/dsa/zigzag-or-diagonal-traversal-of-
matrix/
2. https://leetcode.com/problems/spiral-matrix/
3. https://leetcode.com/problems/word-search/description/
 Searching & Sorting:
1. https://www.geeksforgeeks.org/majority-element/
2. https://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-
space/
3. https://practice.geeksforgeeks.org/problems/inversion-of-array-
1587115620/1
4. https://www.geeksforgeeks.org/searching-array-adjacent-differ-k/
5. https://www.geeksforgeeks.org/permute-two-arrays-sum-every-pair-
greater-equal-k/
6. https://www.geeksforgeeks.org/counting-sort/
7. https://www.geeksforgeeks.org/find-common-elements-three-
sorted-arrays/
8. https://practice.geeksforgeeks.org/problems/allocate-minimum-
number-of-pages0937/1

Backtracking:

1. https://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/
2. https://www.geeksforgeeks.org/printing-solutions-n-queen-problem/
3. https://practice.geeksforgeeks.org/problems/m-coloring-problem-
1587115620/1
4. https://www.geeksforgeeks.org/backtracking-set-1-the-knights-tour-
problem/
5. https://www.geeksforgeeks.org/backtracking-set-7-suduku/

Linkedlist:

1. https://leetcode.com/problems/reverse-linked-list/
2. https://leetcode.com/problems/merge-two-sorted-lists/
3. https://leetcode.com/problems/merge-two-sorted-lists/
4. https://www.geeksforgeeks.org/sort-a-linked-list-of-0s-1s-or-2s/
5. https://leetcode.com/problems/remove-nth-node-from-end-of-list/
6. https://practice.geeksforgeeks.org/problems/reverse-a-doubly-linked-
list/1
greedy:

1. https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-
1/
2. https://www.geeksforgeeks.org/greedy-algorithm-to-find-minimum-
number-of-coins/
3. https://www.geeksforgeeks.org/minimum-cost-for-acquiring-all-coins-
with-k-extra-coins-allowed-with-every-coin/
4. https://www.geeksforgeeks.org/job-sequencing-problem/
5. https://www.geeksforgeeks.org/fractional-knapsack-problem/