## Introduction

Programming needs a lot of practice from day one. Even if you think you are very good at it, you may be wrong. Prior to an interview, it is always better to surf some questions and find out if you know the correct answer. Plus, coding questions are famous for having multiple correct answers, but the interviewer asks for a specific one.

Coding questions have multiple correct answers, but certain answers can give you a positive edge and impress the interviewer. We have also provided some sample answers. The language we have used is written within brackets before the answer starts. Here are some of the popular coding interview questions:

**Q1) Find the duplicate elements in an array.**

**A: **(Python)

lst = [2, 3, 3, 4, 5, 6, 6]

empty_list = []

dup = []

for i in lst:

if i not in empty_list:

empty_list.append(i)

else:

if i not in dup:

i.append(dup)

else:

pass

print dup

**Q2) Sort an integer array using the QuickSort algorithm.**

**A: **(Python)

def partition(arr, lower, upper):

i = (lower-1)

pivot = arr[upper]

for j in range(lower, upper):

if arr[j] <= pivot:

i = i+1

arr[i], arr[j] = arr[j], arr[i]

arr[i+1], arr[upper] = arr[upper], arr[i+1]

return (i+1)

def quickSort(arr, lower, upper):

if len(arr) == 1:

return arr

if lower < upper:

pi = partition(arr, lower, upper)

quickSort(arr, lower, pi-1)

quickSort(arr, pi+1, upper)

arr = [10, 7, 8, 9, 1, 5]

n = len(arr)

quickSort(arr, 0, n-1)

print(“Sorted array is:”)

for i in range(n):

print(“%d” % arr[i]),

**Q3) How to reverse an array in JAVA?**

**A: **(Java)

public class revArray {

static void rev(int a[], int n)

{

int[] b = new int[n];

int j = n;

for (int i = 0; i < n; i++) {

b[j – 1] = a[i];

j = j – 1;

}

for (int k = 0; k < n; k++) {

System.out.println(b[k]);

}

}

public static void main(String[] args)

{

int [] arr = {10, 20, 30, 40, 50};

rev(arr, arr.length);

}

}

**Q4) Write a program to reverse a linked list.**

**A: **(Python)

class Node:

** **def __init__(self, data):

self.data = data

self.next = None

class Lnkdlst:

def __init__(self):

self.head = None

# Function to reverse the linked list

def reversefn(self):

prev = None

current = self.head

while(current is not None):

next = current.next

current.next = prev

prev = current

current = next

self.head = prev

def pushll(self, new_data):

new_node = Node(new_data)

new_node.next = self.head

self.head = new_node

def printLst(self):

temp = self.head

while(temp):

print temp.data,

temp = temp.next

llist = Lnkdlst()

llist.pushll(20)

llist.pushll(4)

llist.pushll(15)

llist.pushll(85)

llist.reversefn()

llist.printLst()

**Q5) Add two numbers that are represented by linked lists and print the result as a linked list.**

**A: **(Approach algorithm)

The solution can be achieved by implementing the fundamental addition method using the inked list values. As you traverse through the two linked lists, add the values, and store them in a new linked list. If one linked list runs out of nodes, add 0 instead. If the answer is more than 9, use the carryover method, i.e., add 1 to the next addition result and the sum divided by 10 as the current value to store.

For checking the program, visit https://www.geeksforgeeks.org/add-two-numbers-represented-by-linked-lists/

**Q6) Check if a given string or number is a palindrome.**

**A: **(Python)

def Palindrome(s):

return s == s[::-1]

s = “malayalam”

answer = Palindrome(s)

if answer == True:

print (“Yes”)

else:

print (“No”)

To check a number, convert the number to string using str() and follow the above steps.

**Q7) Find all permutations of a string using C.**

**A: **This program has many solutions. If you use C programming, you must write the permutation code yourself. For languages like Python, there is a library that will help you find all permutations (or combinations) and print them in a tuple.

(C)

#include <stdio.h>

#include <string.h>

void swap(char *x, char *y)

{

char temp;

temp = *x;

*x = *y;

*y = temp;

}

void permute(char *a, int l, int r)

{

int i;

if (l == r)

printf(“%s\n”, a);

else

{

for (i = l; i <= r; i++)

{

swap((a+l), (a+i));

permute(a, l+1, r);

swap((a+l), (a+i));

}

}

}

int main()

{

char str[] = “ABC”;

int n = strlen(str);

permute(str, 0, n-1);

return 0;

}

**Q8) Write a program to show in order traversal in a binary tree.**

**A: **(Python)

class Soln(obj):

def inTrav (self, root):

result = []

if root:

result = self.inTrav(root.left)

result.append(root.val)

result = result + self.inTrav(root.right)

return result

(The driver program is not provided here)

**Q9) Check if a given string contains only digits and no other elements.**

**A: **(Python)

str = “12345”

lst = []

for i in str:

if i.isdigit():

lst.append(True)

else:

lst.append(False)

if False in lst:

print “No”

else:

print “Yes”

lst.append(True)

Dynamic Programming Problems

Some programs are difficult not because you cannot solve the question. They are difficult because the solution you think works is not the one that the interviewer asks for.

Dynamic programming is a method used in high-level programming skills that use short and concise programs but are advantageous because of fewer time complexities and less time needed to run the program.

Here are some of the famous dynamic programming questions. These questions are primarily asked by top-level companies, like Google, Microsoft, and Amazon. These programs used knowledge of data structures, algorithms, and non-recursive methods.

**Q10) Find the longest common subsequence.**

**A: **(Python)

def lcs(X, Y):

m = len(X)

n = len(Y)

L = [[None]*(n + 1) for i in range(m + 1)]

for i in range(m + 1):

for j in range(n + 1):

if i == 0 or j == 0 :

L[i][j] = 0

elif X[i-1] == Y[j-1]:

L[i][j] = L[i-1][j-1]+1

else:

L[i][j] = max(L[i-1][j], L[i][j-1])

return L[m][n]

X = “ABBSHGD”

Y = “GUEYYYEFW”

print(lcs(X, Y))

**Q11) Implement the Word Break problem.**

**A: **(Python)

def wrdBr(wordLst, word):

if word == ‘’:

return True

else:

wordLen = len(word)

return any([(word[:i] in wordLst) and wrdBr(wordLst, word[i:]) for i in range(1, wordLen+1)])

(The driver program is not provided here)

**Q12) Find the longest path in a matrix.**

**A: (**Python)

n = 3

def findLong(i, j, mat, dp):

if (i<0 or i>= n or j<0 or j>= n):

return 0

if (dp[i][j] != -1):

return dp[i][j]

x, y, z, w = -1, -1, -1, -1

if (j<n-1 and ((mat[i][j] +1) == mat[i][j + 1])):

x = 1 + findLong(i, j + 1, mat, dp)

if (j>0 and (mat[i][j] +1 == mat[i][j-1])):

y = 1 + findLong(i, j-1, mat, dp)

if (i>0 and (mat[i][j] +1 == mat[i-1][j])):

z = 1 + findLong(i-1, j, mat, dp)

if (i<n-1 and (mat[i][j] +1 == mat[i + 1][j])):

w = 1 + findLong(i + 1, j, mat, dp)

dp[i][j] = max(x, max(y, max(z, max(w, 1))))

return dp[i][j]

def finLongOverAll(mat):

result = 1 # Initialize result

dp =[[-1 for i in range(n)]for i in range(n)]

for i in range(n):

for j in range(n):

if (dp[i][j] == -1):

findLong(i, j, mat, dp)

result = max(result, dp[i][j]);

return result

mat = [[1, 2, 9],

[5, 3, 8],

[4, 6, 7]]

print(finLongOverAll(mat))

**Q13) Implement the Coin Change Problem**

**A: **(Python)

def count(S, m, n):

table = [[0 for x in range(m)] for x in range(n+1)] for i in range(m):

table[0][i] = 1

for i in range(1, n+1):

for j in range(m):

x = table[i – S[j]][j] if i-S[j] >= 0 else 0

y = table[i][j-1] if j >= 1 else 0

table[i][j] = x + y

return table[n][m-1]

arr = [1, 2, 3]

m = len(arr)

n = 4

print(count(arr, m, n))

**Q14) Implement the Dice throw Problem**

**A: **(Python)

def findWay(m,n,x):

table=[[0]*(x+1) for i in range(n+1)]

for j in range(1,min(m+1,x+1)):

table[1][j]=1

for i in range(2,n+1):

for j in range(1,x+1):

for k in range(1,min(m+1,j)):

table[i][j]+=table[i-1][j-k]

return table[-1][-1]

print (findWay(4,2,1))

print (findWay(2,2,3))

print (findWay(6,3,8))

print (findWay(4,2,5))

print (findWay(4,3,5))

**Q15) Implement the Subset Sum Problem.**

**A: **(Python)

def isSubsetSum(set, n, sum):

subset =([[False for i in range(sum + 1)]

for i in range(n + 1)])

for i in range(n + 1):

subset[i][0] = True

for i in range(1, sum + 1):

subset[0][i]= False

for i in range(1, n + 1):

for j in range(1, sum + 1):

if j<set[i-1]:

subset[i][j] = subset[i-1][j]

if j>= set[i-1]:

subset[i][j] = (subset[i-1][j] or

subset[i – 1][j-set[i-1]])

return subset[n][sum]

if __name__==’__main__’:

set = [3, 34, 4, 12, 5, 2]

sum = 9

n = len(set)

if (isSubsetSum(set, n, sum) == True):

print(“Found a subset”)

else:

print(“No subset”)

### Conclusion

These are some of the most promising and popular coding interview questions asked. The difficulty of the interview questions depends on the company and the job role. Overall, these questions should be enough for the quick preparation of an interview. It is always important to look at and solve such problems regularly. Many such problems and solutions are available on the internet.

Dynamic programming concepts are the most difficult to tackle. And this turns out to be the knockout blow by the interviewer. In order to solve such problems, you need to practice hard the dynamic programming questions. There are not millions of questions on dynamic programming, and even if there are, they use similar algorithms. Hence, practicing around 50 problems might give you the edge over other candidates.