Girikon Interview Questions and Answers

Round duration - 180 min
Round difficulty - Hard

Q1. 
Longest Common Subsequence Problem Statement
Given two strings STR1 and STR2, determine the length of their longest common subsequence.
A subsequence is a sequence that can be derived from another sequen...read more
Ans. 
The problem involves finding the length of the longest common subsequence between two given strings.
• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the lengths of common subsequences of substrings.

• Iterate through the strings to fill the array and find the length of the longest common subsequence.

• Example: For input STR1 = 'abcde' and STR2 = 'ace', the longest common subsequence is 'ac
Answered by AI
Add your answer
Q2. 
0/1 Knapsack Problem Statement
A thief is planning to rob a store and can carry a maximum weight of 'W' in his knapsack. The store contains 'N' items where the ith item has a weight of 'wi' and a value of...read more
Ans. 
Yes, the 0/1 Knapsack problem can be solved using dynamic programming with a space complexity of not more than O(W).
• Use a 1D array to store the maximum value that can be stolen for each weight capacity from 0 to W.

• Iterate through each item and update the array based on whether including the item would increase the total value.

• The final value in the array at index W will be the maximum value that can be stolen.
Answered by AI
Add your answer
Q3. 
K Largest Elements Problem Statement
You are given an unsorted array containing 'N' integers. Your task is to find the 'K' largest elements from this array and return them in non-decreasing order.
Input:
T...read more
Ans. 
Yes, the problem can be solved in less than O(N*log(N)) time complexity using the Quick Select algorithm.
• Implement Quick Select algorithm to find the Kth largest element in O(N) time complexity.

• Partition the array around a pivot element and recursively search in the left or right partition based on the position of the pivot.

• Once you find the Kth largest element, return all elements greater than or equal to it in non-de
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Q1. 
Size of Largest BST in a Binary Tree
Given a binary tree with 'N' nodes, determine the size of the largest subtree that is also a Binary Search Tree (BST).
Explanation:
A Binary Search Tree (BST) is def...read more
Ans. 
Find the size of the largest BST subtree in a binary tree.
• Traverse the tree in a bottom-up manner to check if each subtree is a BST.

• Keep track of the size of the largest BST found so far.

• Recursively check if the current subtree is a BST and update the size accordingly.
Answered by AI
Add your answer
Q2. 
Matrix Chain Multiplication Problem
Given 'N' 2-dimensional matrices and an array ARR of length N + 1, where the first N integers denote the number of rows in each matrix and the last integer represents t...read more
Ans. 
Find the minimum number of multiplication operations required to multiply a series of matrices together.
• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the minimum number of operations needed to multiply matrices.

• Iterate through different combinations of matrices to find the optimal solution.

• Consider the dimensions of the matrices to determine the number of operations required.

• Calcu...read more
Answered by AI
Add your answer
Q3. 
Rotate Linked List Problem Statement
Given a linked list consisting of 'N' nodes and an integer 'K', your task is to rotate the linked list by 'K' positions in a clockwise direction.
Example:
Input:
Li...read more
Ans. 
Rotate a linked list by K positions in a clockwise direction.
• Traverse the linked list to find the length and the last node.

• Connect the last node to the head to form a circular linked list.

• Find the new head by moving (length - K) steps from the last node.

• Break the circular list at the new head to get the rotated linked list.
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Easy

Q1. 
Longest Palindromic Substring Problem Statement
You are provided with a string STR of length N. The task is to find the longest palindromic substring within STR. If there are several palindromic substring...read more
Ans. 
Given a string, find the longest palindromic substring within it.
• Iterate through the string and expand around each character to find palindromes

• Keep track of the longest palindrome found so far

• Return the longest palindromic substring
Answered by AI
Add your answer