Toast Software Developer Interview Questions and Answers

1.5 hours Coding Round conducted on HackerRank.

Q1. Given an array of n numbers , find the kth largest find the sum from a th largest to bth largest n can be huge
Ans. 
Find the sum of kth to bth largest numbers in a huge array efficiently.
• Sort the array in descending order to easily find the kth and bth largest numbers.

• Use a priority queue or min heap to efficiently find the kth and bth largest numbers without sorting the entire array.

• Once you have the kth and bth largest numbers, iterate through the array and sum the numbers between them.
Answered by AI
Add your answer
Q2. Mostly elasticsearch related and company work related questions
Add your answer

Coding test was of 1:30 hour. Topic : Data structure and Algorithms, Platform : intervue.io

Q1. 1. number of island (leetcode question [Medium]) 2. bitonic subsequence in an array (dp question)
Add your answer
Q2. 1. bitwise OR of the sum of all the subsequence of the array [Hard] 2. course schedule II (leetcode question)
Ans. 
Two software development questions: bitwise OR of array subsequences and course schedule II.
• Question 1 requires finding the bitwise OR of the sum of all subsequences of an array.

• Question 2 is a LeetCode question about scheduling courses with prerequisites.

• For question 1, we can use dynamic programming to find all subsequences and then calculate the bitwise OR.

• For question 2, we can use a topological sort to determine t
Answered by AI
Add your answer
Q3. 1. oops, dbms, os questions 2. project discussions
Add your answer
Q4. HR : normal hr question (see the interviewbit hr question sheet it will be really very helpfull)
Add your answer
Q5. They have taken my last 10 min round just for clarifying the location preference and all.
Add your answer

Genric aptitude questions also computer fundamentals like dbms

DP questions, tree questions r there

Round duration - 60 minutes
Round difficulty - Medium

Medium level competitive programming question. Interviewer looked for the approach and working code.

Q1. 
Time to Burn Tree Problem
You are given a binary tree consisting of 'N' unique nodes and a start node where the burning will commence. The task is to calculate the time in minutes required to completely b...read more
Ans. 
Calculate the time in minutes required to completely burn a binary tree starting from a given node.
• Perform a depth-first search (DFS) to calculate the time taken to burn the entire tree.

• Track the time taken to burn each node based on its distance from the starting node.

• Consider the maximum time taken among all nodes as the total time to burn the entire tree.
Answered by AI
Add your answer

Round duration - 40 minutes
Round difficulty - Medium

Timing : Evening
Interviewer was frank. He checked for indepth knowledge of the subject.

Round duration - 60 Minutes
Round difficulty - Easy

Q1. 
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
Q2. 
Find the Second Largest Element
Given an array or list of integers 'ARR', identify the second largest element in 'ARR'.
If a second largest element does not exist, return -1.
Example:
Input:
ARR = [2,...read more
Ans. 
Find the second largest element in an array of integers.
• Iterate through the array to find the largest and second largest elements.

• Handle cases where all elements are identical.

• Return -1 if a second largest element does not exist.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

System Design Round

Q1. Design a system for Twitter, discussing its architecture, key components, and scalability considerations.
Ans. 
Design a scalable system for Twitter with key components and architecture.
• Use microservices architecture for scalability and fault isolation.

• Key components include user service, tweet service, timeline service, and notification service.

• Use a distributed database like Cassandra for storing tweets and user data.

• Implement a message queue like Kafka for handling real-time updates and notifications.

• Use a caching layer like ...read more
Answered by AI
Add your answer

Round duration - 30 Minutes
Round difficulty - Easy

It is just a formality

Round duration - 60 Minutes
Round difficulty - Easy

4 Questions which were of Easy, Medium, and Hard level.

Q1. 
Lowest Common Ancestor of a Binary Tree III
The structure of a binary tree has been modified so that each node includes a reference to its parent node.
Problem Statement
You are provided with two nodes,...read more
Ans. 
This question is about finding the lowest common ancestor of two nodes in a binary tree with parent references.
• Traverse from the given nodes to their respective root nodes and store the paths in two separate lists.

• Compare the two lists and find the last common node.

• Return the last common node as the lowest common ancestor.
Answered by AI
Add your answer
Q2. 
Maximum Subarray Problem Statement
Ninja has been given an array, and he wants to find a subarray such that the sum of all elements in the subarray is maximum.
A subarray 'A' is considered greater than a...read more
Ans. 
The problem is to find a subarray with the maximum sum in a given array.
• Iterate through the array and keep track of the maximum sum and the current sum.

• If the current sum becomes negative, reset it to 0.

• Update the maximum sum if the current sum is greater.

• Also keep track of the start and end indices of the subarray with the maximum sum.

• Return the subarray using the start and end indices.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Easy

Q1. 
Next Greater Element Problem Statement
Given a list of integers of size N, your task is to determine the Next Greater Element (NGE) for every element. The Next Greater Element for an element X is the firs...read more
Ans. 
The task is to find the next greater element for each element in an array.
• Iterate through the array from right to left.

• Use a stack to keep track of the elements that have a greater element to their right.

• For each element, pop elements from the stack until a greater element is found or the stack is empty.

• If a greater element is found, it is the next greater element for the current element.

• If the stack becomes empty, the...read more
Answered by AI
Add your answer
Q2. 
Trapping Rain Water Problem Statement
You are given a long type array/list ARR of size N, representing an elevation map. The value ARR[i] denotes the elevation of the ith bar. Your task is to determine th...read more
Ans. 
The question asks to find the total amount of rainwater that can be trapped in the given elevation map.
• Iterate through the array and find the maximum height on the left and right side of each bar.

• Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on both sides and subtracting the height of the bar.

• Sum up the amount of water trapped at each bar to get the total amo
Answered by AI
View 5 more answers

Round duration - 30 Minutes
Round difficulty - Easy

It is just a formality round, asked basic questions like relocation and joining date etc