SDE - 1 Josh Technology Group interview experience

Interview rounds

Round

Hard

Online Coding Interview

Duration180 min

Interview date7 Sep 2021

Coding problem3

1. Longest Common Subsequence

Moderate

0/80

Asked in companies

You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters. A common subsequence of two Strings is a subsequence that is common to both Strings.

Problem approach

In order to find out the complexity of brute force approach, we need to first know the number of possible different subsequences of a string with length n, i.e., find the number of subsequences with lengths ranging from 1,2,..n-1. Recall from theory of permutation and combination that number of combinations with 1 element are nC1. Number of combinations with 2 elements are nC2 and so forth and so on. We know that nC0 + nC1 + nC2 + … nCn = 2n. So a string of length n has 2n-1 different possible subsequences since we do not consider the subsequence with length 0. This implies that the time complexity of the brute force approach will be O(n * 2n). Note that it takes O(n) time to check if a subsequence is common to both the strings. This time complexity can be improved using dynamic programming.

It is a classic computer science problem, the basis of diff (a file comparison program that outputs the differences between two files), and has applications in bioinformatics.

Try solving now

2. 0 1 Knapsack

Easy

15m average time

85% success

0/40

Asked in companies

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are N items and the ith item weighs wi and is of value vi. Considering the constraints of the maximum weight that a knapsack can carry, you have to find and return the maximum value that a thief can generate by stealing items.

Problem approach

In Fractional Knapsack, we can break items for maximizing the total value of knapsack. This problem in which we can break an item is also called the fractional knapsack problem.

A brute-force solution would be to try all possible subset with all different fraction but that will be too much time taking.

An efficient solution is to use the Greedy approach. The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can’t add the next item as a whole and at the end add the next item as much as we can. Which will always be the optimal solution to this problem.
A simple code with our own comparison function can be written as follows, please see the sort function more closely, the third argument to sort function is our comparison function which sorts the item according to value/weight ratio in non-decreasing order.
After sorting we need to loop over these items and add them in our knapsack satisfying above-mentioned criteria.

Try solving now

3. K Largest Element

Moderate

10m average time

90% success

0/80

Asked in companies

You are given an unsorted array containing ‘N’ integers. You need to find ‘K’ largest elements from the given array. Also, you need to return the elements in non-decreasing order.

Problem approach

1) Sort the elements in descending order in O(n*log(n))
2) Print the first k numbers of the sorted array O(k).

Try solving now

Round

Medium

Online Coding Test

Duration60 Minutes

Interview date7 Sep 2021

Coding problem3

1. Size of Largest BST in Binary Tree

Easy

10m average time

90% success

0/40

Asked in companies

You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to return the size of the largest subtree of the binary tree which is also a BST.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Example:

Given binary tree:

In the given binary tree, subtree rooted at 2 is a BST and its size is 3.

Problem approach

In method 1, we traverse the tree in top-down manner and do BST test for every node. If we traverse the tree in bottom-up manner, then we can pass information about subtrees to the parent. The passed information can be used by the parent to do BST test (for parent node) only in constant time (or O(1) time). A left subtree need to tell the parent whether it is BST or not and also needs to pass maximum value in it. So that we can compare the maximum value with the parent’s data to check the BST property. Similarly, the right subtree need to pass the minimum value up the tree. The subtrees need to pass the following information up the tree for the finding the largest BST.
1) Whether the subtree itself is BST or not (In the following code, is_bst_ref is used for this purpose)
2) If the subtree is left subtree of its parent, then maximum value in it And if it is right subtree then minimum value in it.
3) Size of this subtree if this subtree is BST
max_ref is used for passing the maximum value up the tree and min_ptr is used for passing minimum value up the tree.

Try solving now

2. Matrix Chain Multiplication

Easy

0/40

Asked in companies

You are given ‘N’ 2-D matrices and an array/list “ARR” of length ‘N + 1’ where the first ‘N’ integers denote the number of rows in the Matrices and the last element denotes the number of columns of the last matrix. For each matrix, the number of columns is equal to the number of rows of the next matrix. You are supposed to find the minimum number of multiplication operations that need to be performed to multiply all the given matrices.

Note :

You don’t have to multiply the matrices, you only have to find the minimum number of multiplication operations.

For Example :

ARR = {2, 4, 3, 2}

Here, we have three matrices with dimensions {2X4, 4X3, 3X2} which can be multiplied in the following ways:
a. If the order of multiplication is (2X4, 4X3)(3X2), then the total number of multiplication operations that need to be performed are: (2*4*3) + (2*3*2) = 36

b. If the order of multiplication is (2X4)(4X3, 3X2), then the total number of multiplication operations that need to be performed are  (2*4*2) + (4*3*2) = 40

Try solving now

3. Rotate Linked List

Moderate

25m average time

65% success

0/80

Asked in companies

You are given a linked list having ‘n’ nodes and an integer ‘k’.

You have to rotate the linked list to the right by ‘k’ positions .

Example :

Input: linked list = [1 2 3 4] , k = 2

Output: 3 4 1 2

Explanation:
We have to rotate the given linked list to the right 2 times. After rotating it to the right once it becomes 4->1->2->3. After rotating it to the right again, it becomes 3->4->1->2.

Problem approach

To rotate a linked list by k, we can first make the linked list circular and then moving k-1 steps forward from head node, making (k-1)th node’s next to null and make kth node as head.

Try solving now

Round

Easy

Face to Face

Duration45 minutes

Interview date7 Sep 2021

Coding problem2

1. System Design Question

We have to code a todo alike app called PROJECT PLANNER with raw HTML, CSS & JS in 2:30-3:00 Hours, all the instructions related to UI Design+functionality and scoring criteria about the app was told before starting the code.
An additional feature like integrating local storage was in good to have section.

Problem approach

Proper understanding of system designs

2. Longest Palindromic Substring

Moderate

20m average time

80% success

0/80

Asked in companies

You are given a string ('STR') of length 'N'. Find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

Note:

A substring is a contiguous segment of a string.

For example : The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome, there is another palindromic substring of length 3 is "bab" since "aba" starting index is less than "bab", so "aba" is the answer.

Problem approach

The time complexity can be reduced by storing results of sub-problems. The idea is similar to this post.

Maintain a boolean table[n][n] that is filled in bottom up manner.
The value of table[i][j] is true, if the substring is palindrome, otherwise false.
To calculate table[i][j], check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true.
Otherwise, the value of table[i][j] is made false.
We have to fill table previously for substring of length = 1 and length =2 because
as we are finding , if table[i+1][j-1] is true or false , so in case of
(i) length == 1 , lets say i=2 , j=2 and i+1,j-1 doesn’t lies between [i , j]
(ii) length == 2 ,lets say i=2 , j=3 and i+1,j-1 again doesn’t lies between [i , j].

Try solving now