Linedata Software Developer Interview Questions and Answers

Round duration - 60 minutes
Round difficulty - Easy

There was 2 coding questions
Based on ds and algorithms

Q1. 
Ninja's Pattern with Powers of 2
Ninja, who loves playing with numbers, sets out to arrange numbers within 'N' rows. The unique arrangement follows these rules: the first row contains 1 number, the second...read more
Ans. 
Generate a pattern of numbers in rows following a specific sequence based on powers of 2.
• Start with 1 number in the first row, 2 numbers in the second row, 4 numbers in the third row, and so on based on powers of 2.

• Fill the pattern with numbers in increasing sequence from 1 to 9, recycling back to 1 after reaching 9.

• Output the pattern for a given number 'N' of rows.

• Example: For N = 4, the pattern would be 1, 23, 4567,
Answered by AI
Add your answer
Q2. 
Validate Binary Search Tree (BST)
You are given a binary tree with 'N' integer nodes. Your task is to determine whether this binary tree is a Binary Search Tree (BST).
BST Definition:
A Binary Search Tr...read more
Ans. 
Validate if a given binary tree is a Binary Search Tree (BST) or not.
• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Check if the right subtree of a node contains only nodes with data greater than the node's data.

• Recursively check if both the left and right subtrees are also binary search trees.

• Example: For a node with data 4, left subtree nodes (2, 1, 3) are smaller and righ
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

There was 2 coding questions based on ds and algorithms

Q1. 
Zig-Zag Array Rearrangement
You are provided with an array of distinct elements, and your task is to rearrange the array elements in a zig-zag manner. Specifically, for every odd index i, the element ARR[...read more
Ans. 
Rearrange array elements in a zig-zag manner where every odd index element is greater than its neighbors.
• Iterate through the array and swap elements to satisfy the zig-zag condition.

• Ensure that for every odd index i, ARR[i] > ARR[i-1] and ARR[i] > ARR[i+1].

• Multiple correct answers may exist for a given array.
Answered by AI
Add your answer
Q2. 
Flatten a Linked List
You are provided with a linked list of 'N' nodes. Each node contains two pointers: NEXT, pointing to the next node in the list, and CHILD, pointing to a linked list. Each child linke...read more
Ans. 
Flatten a linked list of sorted child linked lists into a single sorted linked list.
• Traverse the linked list and maintain a priority queue to keep track of the next smallest element.

• Merge the child linked lists into the priority queue while traversing the main linked list.

• Pop elements from the priority queue to create the final flattened linked list.
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Medium

My interview started at 9:30 and it took around 45 minutes to complete my interview.This was held on Amazon Chime and the interview lasted for 1 hour. Firstly the interviewer asked to introduce about myself, later asked regarding the projects I have mentioned in my resume. Then started displaying the coding question. The first question is number of islands in a matrix.

Q1. 
Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in t...read more
Ans. 
Count the number of islands in a 2D matrix of 1s and 0s.
• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid redundant traversal.

• Increment the island count each time a new island is encountered.

• Consider edge cases like when the matrix is empty or all cells are water (0s).
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Easy

Two coding questions were asked and 90 minutes of time was allotted to solve both the problems

Q1. 
Find All Pairs Adding Up to Target
Given an array of integers ARR of length N and an integer Target, your task is to return all pairs of elements such that they add up to the Target.
Input:
The first line ...read more
Ans. 
Given an array of integers and a target, find all pairs of elements that add up to the target.
• Iterate through the array and for each element, check if the target minus the element exists in a hash set.

• If it exists, add the pair to the result. If not, add the element to the hash set.

• Handle cases where the same element is used twice to form a pair.

• Return (-1, -1) if no pair is found.
Answered by AI
Add your answer
Q2. 
Shortest Path in a Binary Matrix Problem Statement
Given a binary matrix of size N * M where each element is either 0 or 1, find the shortest path from a source cell to a destination cell, consisting only...read more
Ans. 
Find the shortest path in a binary matrix from a source cell to a destination cell consisting only of 1s.
• Use Breadth First Search (BFS) algorithm to find the shortest path in the binary matrix.

• Keep track of visited cells to avoid revisiting them.

• Update the path length as you traverse the matrix.

• Return -1 if no valid path exists from source to destination.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

The duration was approx 1 hour. The interview was taken by a young SDE-2.

Q1. 
Character Frequency Problem Statement
You are given a string 'S' of length 'N'. Your task is to find the frequency of each character from 'a' to 'z' in the string.
Example:
Input:
S : abcdg
Output:
1...read more
Ans. 
The task is to find the frequency of each character from 'a' to 'z' in a given string.
• Create an array of size 26 to store the frequency of each character from 'a' to 'z'.

• Iterate through the string and increment the count of the corresponding character in the array.

• Print the array of frequencies as the output.
Answered by AI
Add your answer
Q2. 
Fire in the Cells Problem Statement
Given a matrix MAT of size N * M, where each cell is either on fire or safe, determine if a person can reach an escape cell without being burnt. The person starts from ...read more
Ans. 
Determine if a person can reach an escape cell without encountering fire in a matrix.
• Check if the person can reach an escape cell without encountering fire by simulating the movement of the person and fire spread.

• If the person can reach an escape cell, return the time taken; otherwise, return -1.

• Consider the constraints and edge cases while implementing the solution.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Hard

The interviewer introduced himself and asked me to introduce myself.
I told him about the different projects that I had done and the work in the previous company.
I had worked on AWS(Amazon Web Services) so he asked me all the AWS services that I had worked with and to explain one of them. 
I explained about the working of ECS(Elastic Container Service).
After this, he moved to the coding questions.

Q1. 
Maximum 0-1 Distance Problem Statement
Given a binary matrix of size N*M, find the maximum distance 'di' for every 0-cell to its nearest 1-cell, where the distance is measured using Manhattan distance. Th...read more
Ans. 
Find the maximum Manhattan distance from a 0-cell to its nearest 1-cell in a binary matrix.
• Iterate through the matrix to find all 0-cells and calculate their distances to nearest 1-cells using Manhattan distance formula

• Keep track of the maximum distance found so far and update it if a larger distance is encountered

• Return the maximum distance as the final result
Answered by AI
Add your answer
Q2. 
Search for Indices with Given Difference and Distance
You are provided with an array containing 'N' non-negative integers, along with two other non-negative integers 'K' and 'M'. Your task is to identify ...read more
Ans. 
Find a pair of indices in an array with given difference and distance constraints.
• Iterate through the array and check all possible pairs of indices to satisfy the conditions

• Use nested loops to compare each pair of indices and their corresponding elements

• Return 'valid' if a pair of indices is found that meets the conditions, otherwise return 'invalid'
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

The interviewer was a very senior person with at least 10-15 years of experience. He introduced himself and asked me to tell him about myself. (Leadership principle questions followed)
 

Q1. 
Special Binary Tree Problem Statement
Determine whether an arbitrary binary tree is special. A binary tree is called special if every node in this tree has either zero or two children.
Example:
Input:
...read more
Ans. 
Determine if a binary tree is special if every node has zero or two children.
• Traverse the tree and check if each node has either 0 or 2 children.

• Use a recursive approach to check children of each node.

• If any node has only one child, return false immediately.

• Example: For the given input, the output should be true.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

The interview started with introductions and some Leadership principle questions. The interviewer was again a senior person with at least 10-15 years of experience.

I was asked to explain some AWS services.
He asked me to tell about a time when I had a tight deadline and how I worked during it.
He asked me about a time when I took initiative and came up with something new which helped the entire team.
I had prepared well for the LP questions and was able to answer everything.
After this, we move on to coding questions.

Q1. 
Word Presence in Sentence
Determine if a given word 'W' is present in the sentence 'S' as a complete word. The word should not merely be a substring of another word.
Input:
The first line contains an in...read more
Ans. 
Check if a given word is present in a sentence as a complete word.
• Split the sentence into words using spaces as delimiter.

• Check if the given word matches any of the words in the sentence.

• Ensure that the word is not just a substring of another word in the sentence.
Answered by AI
Add your answer
Q2. 
LRU Cache Design Question
Design a data structure for a Least Recently Used (LRU) cache that supports the following operations:
1. get(key) - Return the value of the key if it exists in the cache; otherw...read more
Ans. 
Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.
• Use a combination of hashmap and doubly linked list to implement the LRU cache.

• Keep track of the least recently used item and update it accordingly.

• Ensure to handle cache capacity by evicting the least recently used item when the cache is full.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

Online test which can be attempted anytime between 22 May 2020, 06:00 AM and 25 May 2020, 01:00 AM

Q1. 
Postfix Expression Evaluation Problem Statement
Given a postfix expression, your task is to evaluate the expression. The operator will appear in the expression after the operands. The output for each expr...read more
Ans. 
Evaluate postfix expressions by applying operators to operands in a given order.
• Iterate through the postfix expression and push operands onto a stack

• When an operator is encountered, pop the required number of operands from the stack, apply the operator, and push the result back onto the stack

• Continue until the entire expression is evaluated and the final result is left on the stack
Answered by AI
Add your answer
Q2. 
Dice Throws Problem Statement
You are given D dice, each having F faces numbered from 1 to F. The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up num...read more
Ans. 
The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers equals the given 'target' sum.
• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the number of ways to achieve each sum with different number of dice.

• Iterate through the dice and sum possibilities to fill up the array.

• Return the result modulo 10^9 + 7.

• Optimize the solution ...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

June 25 2020
Timing: 12:00 pm to 1:00 pm
This round was completely devoted to coding. I was asked to introduce myself and then 2 coding questions were asked.

Q1. 
Find First and Last Positions of an Element in a Sorted Array
Given a sorted array ARR consisting of N integers and an integer X, find the first and last positions of occurrence of X in the array.
Note:
...read more
Ans. 
Find the first and last positions of an element in a sorted array efficiently.
• Use binary search to find the first occurrence of X in the array.

• Use binary search to find the last occurrence of X in the array.

• Handle cases where X is not present or present only once.

• Return the first and last positions as 0-based indices.
Answered by AI
Add your answer
Q2. 
Maze with N Doors and 1 Key Problem Statement
You are given an N x N maze where some cells have doors, and you have a key that can be used only once to open a door. Determine if there exists a path from t...read more
Ans. 
Determine if there exists a path from the top-left cell to the bottom-right cell of a maze with N doors and 1 key.
• Use depth-first search (DFS) or breadth-first search (BFS) to explore possible paths through the maze.

• Keep track of the cells visited and use the key only once to open doors.

• Check if the bottom-right cell is reachable after traversing the maze.

• Handle edge cases such as the top-left and bottom-right cells ha...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

9th July 2020
6:30PM to 7:30PM

Round duration - 60 minutes
Round difficulty - Easy

23-July 2020
4:00 PM to 5:00 PM
Coding questions + Several questions on computer fundamentals and networking were asked in a rapid-fire manner.

Q1. 
Stock Trading Maximum Profit Problem
Given the stock prices for 'N' days, your goal is to determine the maximum profit that can be achieved. You can buy and sell the stocks any number of times but can onl...read more
Ans. 
The goal is to determine the maximum profit that can be achieved by buying and selling stocks on different days.
• Iterate through the stock prices and buy on the days when the price is lower than the next day's price, and sell on the days when the price is higher than the next day's price.

• Calculate the profit by summing up the differences between buying and selling prices.

• Repeat the process for each test case and output
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

6- Aug 2020
3:00 PM to 4:00 PM
Resceduled to: @5:30 PM
Projects, Fundamentals check, Behavioral, Coding

Q1. 
Path Counting in Directed Graph
Given a directed graph with a specified number of vertices V and edges E, your task is to calculate the total number of distinct paths from a given source node S to all ot...read more
Ans. 
Calculate total number of distinct paths from a given source node to all other nodes in a directed graph.
• Use dynamic programming to keep track of the number of paths from the source node to each node.

• Consider the modulo operation to handle large numbers efficiently.

• Start by initializing the number of paths from the source node to itself as 1.

• Iterate through all edges and update the number of paths for each destination ...read more
Answered by AI
Add your answer

Round duration - 120 minutes
Round difficulty - Medium

10 min for debugging
40 min for problems(coding)
40 min for pyschometric
30 min for aptitude

Q1. 
Total Unique Paths Problem Statement
You are located at point ‘A’, the top-left corner of an M x N matrix, and your target is point ‘B’, the bottom-right corner of the same matrix. Your task is to calcula...read more
Ans. 
The task is to calculate the total number of unique paths from the top-left to bottom-right corner of an M x N matrix by moving only right or down.
• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of unique paths for each cell in the matrix.

• Initialize the first row and first column with 1 as there is only one way to reach each cell in the first row and column.

• For each cell ...read more
Answered by AI
Add your answer
Q2. 
Most Frequent Word Problem Statement
You are given two strings 'A' and 'B' composed of words separated by spaces. Your task is to determine the most frequent and lexicographically smallest word in string ...read more
Ans. 
Find the most frequent and lexicographically smallest word in string 'A' that is not present in string 'B'.
• Split strings 'A' and 'B' into words

• Count frequency of each word in 'A'

• Check if word is not in 'B' and is the most frequent and lexicographically smallest

• Return the word or -1 if no such word exists
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Easy

timing was 4 pm . we connected on amazon chime. Initially he asked me a few things from resume then moved on to problem solving.

Q1. 
Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in t...read more
Ans. 
Count the number of islands in a 2D matrix of 1s and 0s.
• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid redundant traversal.

• Increment the island count each time a new island is encountered.

• Consider all eight possible directions for connectivity while traversing the matrix.

• Handle edge ca...read more
Answered by AI
Add your answer
Q2. 
Largest Rectangle in Histogram Problem Statement
You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.
...read more
Ans. 
Find the area of the largest rectangle that can be formed within the bounds of a given histogram.
• Iterate through the histogram bars and maintain a stack to keep track of increasing heights.

• Calculate the area of the rectangle formed by each bar as the smallest height in the stack times the width.

• Update the maximum area found so far and return it as the result.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Hard

This was an online coding round where we were supposed to solve 2 questions under 90 minutes . Both the questions in my set were related to Graphs and were quite tricky and heavy to implement.

Q1. 
Path Counting in Directed Graph
Given a directed graph with a specified number of vertices V and edges E, your task is to calculate the total number of distinct paths from a given source node S to all ot...read more
Ans. 
Calculate the total number of distinct paths from a given source node to all other nodes in a directed graph.
• Use dynamic programming to keep track of the number of paths from the source node to each node in the graph.

• Consider using modular arithmetic to handle large numbers and prevent overflow.

• Start by initializing the number of paths from the source node to itself as 1.

• Iterate through the edges of the graph and updat...read more
Answered by AI
View 2 more answers
Q2. 
Course Schedule II Problem Statement
You are provided with a number of courses 'N', some of which have prerequisites. There is a matrix named 'PREREQUISITES' of size 'M' x 2. This matrix indicates that fo...read more
Ans. 
Given courses with prerequisites, determine a valid order to complete all courses.
• Use topological sorting to find a valid order of courses.

• Create a graph with courses as nodes and prerequisites as edges.

• Start with courses that have no prerequisites and remove them from the graph.

• Continue this process until all courses are taken or there are no valid courses left.

• If there is a cycle in the graph, it is impossible to com
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

This was a Data Structures and Algorithms round with some standard questions . I was expected to come up with an
efficient approach and code it as well .

Q1. 
Merge Intervals Problem Statement
You are provided with 'N' intervals, each containing two integers denoting the start time and end time of the interval.
Your task is to merge all overlapping intervals a...read more
Ans. 
Merge overlapping intervals and return sorted list of merged intervals.
• Sort the intervals based on start times.

• Iterate through intervals and merge overlapping intervals.

• Return the merged intervals in sorted order.
Answered by AI
Add your answer
Q2. 
Longest Route Problem Statement
Given a 2-dimensional binary matrix called Mat of size N x M that consists solely of 0s and 1s, find the length of the longest path from a specified source cell to a destina...read more
Ans. 
Find the length of the longest path from a source cell to a destination cell in a binary matrix.
• Use depth-first search (DFS) to explore all possible paths from source to destination.

• Keep track of visited cells to avoid revisiting them.

• Return the length of the longest path found, or -1 if no path exists.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was also a DSA round where I was asked to code only one of the questions but I eventually ended up coding both
as I had some spare time and explained my approches very smoothly to the interviewer . This round went preety well .

Q1. 
Longest Increasing Subsequence Problem Statement
Given an array of integers with 'N' elements, determine the length of the longest subsequence where each element is greater than the previous element. This...read more
Ans. 
Find the length of the longest strictly increasing subsequence in an array of integers.
• Use dynamic programming to solve this problem efficiently.

• Initialize an array to store the length of the longest increasing subsequence ending at each index.

• Iterate through the array and update the length of the longest increasing subsequence for each element.

• Return the maximum value in the array as the result.
Answered by AI
Add your answer
Q2. 
Search In Rotated Sorted Array Problem Statement
Given a rotated sorted array ARR of size 'N' and an integer 'K', determine the index at which 'K' is present in the array.
Note:
1. If 'K' is not present...read more
Ans. 
Given a rotated sorted array, find the index of a given integer 'K'.
• Use binary search to find the pivot point where the array is rotated.

• Then perform binary search on the appropriate half of the array to find 'K'.

• Handle cases where 'K' is not present in the array by returning -1.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was also a DSA round with 2 questions of Medium to Hard difficulty . I was expected to follow some clean code and OOPS principles to write the code in this round .

Q1. 
Rank from Stream Problem Statement
Given an array of integers ARR and an integer K, determine the rank of the element ARR[K].
Explanation:
The rank of any element in ARR is defined as the number of elem...read more
Ans. 
Given an array and an index, find the number of elements smaller than the element at that index appearing before it in the array.
• Iterate through the array up to index K and count the number of elements smaller than ARR[K].

• Return the count as the rank of ARR[K].

• Handle edge cases like empty array or invalid index K.
Answered by AI
Add your answer
Q2. 
LRU Cache Design Question
Design a data structure for a Least Recently Used (LRU) cache that supports the following operations:
1. get(key) - Return the value of the key if it exists in the cache; otherw...read more
Ans. 
Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.
• Implement a doubly linked list to maintain the order of recently used keys.

• Use a hashmap to store key-value pairs for quick access.

• Update the order of keys in the linked list on get and put operations.

• Evict the least recently used key when the cache reaches its capacity.
Answered by AI
Add your answer