400+ Afsha Infotech Interview Questions and Answers
Q1. Painter's Partition Problem Statement
Given an array/list representing boards, where each element denotes the length of a board, and a number ‘K’ of available painters, determine the minimum time required to pa...read more
Determine the minimum time required to paint all boards with given constraints.
Use binary search to find the minimum and maximum possible time to paint all boards.
Iterate through the boards and assign them to painters based on the time constraints.
Calculate the total time taken to paint all boards with the assigned painters.
Q2. Special Numbers Problem Statement
Your task is to find the total count of special numbers within a range from 1 to a given integer, 'MAXVAL'. A special number is defined as a number whose digits, when rotated 1...read more
Count the total number of special numbers within a given range by rotating digits 180 degrees.
Create a function to check if a number is a special number by rotating its digits.
Iterate through the range from 1 to MAXVAL and count the special numbers.
Handle the digit rotation mapping for 0, 1, 6, 8, 9.
Return the count of special numbers for each test case.
Q3. Chocolate Distribution Problem
You are given an array/list CHOCOLATES
of size 'N', where each element represents the number of chocolates in a packet. Your task is to distribute these chocolates among 'M' stude...read more
Distribute chocolates among students to minimize the difference between the largest and smallest number of chocolates.
Sort the array of chocolates.
Use sliding window technique to find the minimum difference between the largest and smallest number of chocolates.
Return the minimum difference as the output.
Q4. Say you have three tables WORK, USERS, MANAGERS WORK - work_id - user_id - how_much USERS - user_id - team MANAGERS - manager_id - team If I am a manager, write a select statement to retrieve the work of all us...
read moreWrite a select statement to retrieve work of all users who belong to my team.
Join USERS and WORK tables on user_id
Join MANAGERS and USERS tables on team
Filter by manager_id
Q5. If your Wi-Fi router is not working then what you will do to fix it?
I will troubleshoot the router by checking the power supply, resetting the router, and checking the network settings.
Check if the router is properly plugged in and receiving power
Reset the router by turning it off and on again
Check the network settings and make sure they are correct
Try connecting to the router with a different device
If all else fails, contact the internet service provider for assistance
Q6. Minimum and Maximum Candy Cost Problem
Ram is in Ninjaland, visiting a unique candy store offering 'N' candies each with different costs. The store has a special offer: for every candy you purchase, you can tak...read more
Find minimum and maximum cost to purchase all candies with special offer of free candies.
Iterate through the candy costs array and sort it in ascending order.
For minimum cost, start from the lowest cost candy and take free candies until reaching the next higher cost candy.
For maximum cost, start from the highest cost candy and take free candies until reaching the next lower cost candy.
Q7. Min Steps to One Using Dynamic Programming
Given a positive integer N
, your task is to determine the minimum number of steps required to reduce N
to 1.
Allowed Operations:
1) Subtract 1 from it: n = n - 1
2) If ...read more
Find the minimum number of steps to reduce a positive integer to 1 using given operations.
Use dynamic programming to store the minimum steps for each number from 1 to N.
Iterate through each number from 1 to N and calculate the minimum steps based on the given operations.
Consider the cases where you can either subtract 1, divide by 2, or divide by 3 to find the minimum steps.
Return the minimum steps needed to reduce the number to 1 for each test case.
Q8. Problem Statement: Minimize the Maximum
You are given an array of integers and an integer K
. For each array element, you can adjust it by increasing or decreasing it by a value of K
. Your goal is to minimize th...read more
Given an array of integers and an integer K, minimize the difference between the maximum and minimum elements after adjusting each element by +/- K.
Sort the array in non-decreasing order.
For each element, calculate the difference between the current element and the next element.
Adjust the element by adding or subtracting K to minimize the difference.
Return the minimum possible difference between the maximum and minimum elements.
Q9. Longest Palindromic Substring Problem Statement
You are provided with a string STR
of length N
. The goal is to identify the longest palindromic substring within this string. In cases where multiple palindromic ...read more
Identify the longest palindromic substring in a given string.
Iterate through the string and expand around each character to find palindromes
Keep track of the longest palindrome found
Return the longest palindrome with the smallest start index
Q10. Hotel Room Booking Problem
You are managing a hotel with 10 floors numbered from 0 to 9. Each floor contains 26 rooms labeled from A to Z. You will receive a sequence of strings representing room bookings where...read more
Given a sequence of room bookings and freeings, find the room that is booked the most times.
Create a hashmap to store the count of each room booking.
Iterate through the sequence of bookings and freeings, updating the count in the hashmap.
Find the room with the highest count and return it. In case of a tie, return the lexicographically smaller room.
Example: For input n = 6, Arr[] = {"+1A", "+3E", "-1A", "+4F", "+1A", "-3E"}, the output would be "1A".
Q11. Minimum Character Deletion Problem Statement
You have been provided a string STR
. Your task is to find and return the minimum number of characters that need to be deleted from STR
so that each character's frequ...read more
Q12. Spell Checker Problem Statement
You are provided with a list of strings, DICTIONARY[]
, representing the correct spellings of words, and a query string QUERY
that may contain misspelled words. Your task is to ve...read more
Implement a spell checker function that suggests correct spellings from a dictionary for a given query string.
Iterate through the dictionary to check for matching prefixes with the query string.
Return a list of suggestions if the query string is misspelled, otherwise return an empty list.
Ensure all strings are in lowercase and within the specified constraints.
Handle multiple test cases as per the input format.
Example: For DICTIONARY[] = {"ninja", "ninjas", "nineteen", "ninny"...read more
Q13. Shopping Spree Problem Statement
Preeti plans to shop for her father's birthday at a store with unlimited quantities of N different items. She has a budget that allows her to buy a maximum of K items. Help Pree...read more
Calculate the number of ways Preeti can purchase items within budget, considering distinct ways.
Use dynamic programming to calculate the number of ways to purchase items within budget
Consider different scenarios where Preeti buys different quantities of each item
Return the result modulo 10^9 + 7 to handle large answers
Q14. Boyer Moore Algorithm for Pattern Searching
You are given a string text
and a string pattern
. Your task is to find all occurrences of pattern
in the string text
and return an array of indexes of all those occur...read more
Implement Boyer Moore Algorithm to find all occurrences of a pattern in a text string.
Implement Boyer Moore Algorithm for efficient pattern searching.
Iterate through the text string and compare the pattern with each substring of the text.
Return an array of indexes where the pattern is found in the text.
If pattern not found, return an array containing -1.
Q15. Farthest Distance From Lands Problem Statement
Given a binary square matrix 'ARR' with 'N' rows and 'N' columns, where '0' represents water and '1' represents land.
Determine the water cell whose distance to th...read more
Find the water cell farthest from land in a binary matrix using Manhattan distance.
Iterate through the matrix to find all land cells and water cells
Calculate the Manhattan distance of each water cell to the nearest land cell
Return the maximum distance found
Q16. Bridge in Graph Problem Statement
Given an undirected graph with V vertices and E edges, your task is to find all the bridges in this graph. A bridge is an edge that, when removed, increases the number of conne...read more
Find all the bridges in an undirected graph.
Use Tarjan's algorithm to find bridges in the graph.
A bridge is an edge whose removal increases the number of connected components.
Check for bridges by removing each edge and checking the number of connected components.
Return the edges that are bridges in non-decreasing order.
Q17. Running Median Problem
Given a stream of integers, calculate and print the median after each new integer is added to the stream.
Output only the integer part of the median.
Example:
Input:
N = 5
Stream = [2, 3,...read more
Calculate and print the median after each new integer is added to the stream.
Use two heaps - a max heap to store the smaller half of the numbers and a min heap to store the larger half.
Keep the sizes of the two heaps balanced or differ by at most 1 to get the median efficiently.
When a new integer is added, compare it with the current median and insert it into the appropriate heap.
If the sizes of the heaps differ by more than 1, rebalance them by moving an element from one hea...read more
Q18. The Skyline Problem
Compute the skyline of given rectangular buildings in a 2D city, eliminating hidden lines and forming the outer contour of the silhouette when viewed from a distance. Each building is descri...read more
Compute the skyline of given rectangular buildings in a 2D city, eliminating hidden lines and forming the outer contour of the silhouette.
Iterate through the buildings and create a list of critical points (x, y) where the height changes.
Sort the critical points based on x-coordinate and process them to form the skyline.
Merge consecutive horizontal segments of equal height into one to ensure no duplicates in the output.
Q19. Shortest Alternate Colored Path Problem
Given a directed graph consisting of 'N' nodes labeled from '0' to 'N-1'. Each edge in the graph is colored either 'red' or 'blue'. The graph may include self-edges and p...read more
The task is to compute the shortest path from node '0' to each node in a directed graph with alternating colored edges.
Create a graph using the given red and blue edges.
Use Breadth First Search (BFS) to find the shortest path from node '0' to each node with alternating colored edges.
If no such path exists, set the answer to -1.
Return the array of shortest path lengths for each node.
Q20. Covid Vaccination Distribution Problem
As the Government ramps up vaccination drives to combat the second wave of Covid-19, you are tasked with helping plan an effective vaccination schedule. Your goal is to ma...read more
Given constraints, find max vaccines administered on a specific day during a vaccination drive.
Iterate through each test case and calculate the maximum number of vaccines distributed on the specified day.
Distribute vaccines evenly across days while maximizing the number on the specified day.
Ensure that the sum of vaccines administered does not exceed the maximum allowed.
Consider edge cases like when the number of days is equal to the maximum number of vaccines available.
Q21. Alien Dictionary Problem Statement
You are provided with a sorted dictionary (by lexical order) in an alien language. Your task is to determine the character order of the alien language from this dictionary. Th...read more
Given a sorted alien dictionary, determine the character order of the alien language.
Create a graph data structure to represent the relationships between characters based on the given dictionary.
Perform a topological sort on the graph to determine the character order of the alien language.
Return the character array obtained from the topological sort as the final output.
Q22. Count Ways to Reach the N-th Stair Problem Statement
You are provided with a number of stairs, and initially, you are located at the 0th stair. You need to reach the Nth stair, and you can climb one or two step...read more
Count the number of distinct ways to climb to the Nth stair by climbing one or two steps at a time.
Use dynamic programming to solve the problem efficiently.
The number of ways to reach the Nth stair is the sum of the number of ways to reach the (N-1)th stair and the (N-2)th stair.
Handle base cases where N=0 and N=1 separately.
Apply modulo 10^9+7 to avoid overflow in the final result.
Q23. Problem: Ninja's Robot
The Ninja has a robot which navigates an infinite number line starting at position 0 with an initial speed of +1. The robot follows a set of instructions which includes ‘A’ (Accelerate) a...read more
Determine the minimum length of instruction sequence for a robot to reach a given target on an infinite number line.
Start at position 0 with speed +1, update position and speed based on 'A' and 'R' instructions
For each test case, find the shortest sequence of instructions to reach the target
Consider both positive and negative positions for the robot
Q24. Find the Longest Palindromic Substring
Given a string ‘S’ composed of lowercase English letters, your task is to identify the longest palindromic substring within ‘S’.
If there are multiple longest palindromic ...read more
Find the longest palindromic substring in a given string, returning the rightmost one if multiple exist.
Use dynamic programming to check for palindromes within the string.
Keep track of the longest palindromic substring found so far.
Return the rightmost longest palindromic substring if multiple exist.
Q25. Swap And Maximize Problem Statement
You are given a circular array consisting of N integers. Your task is to find the maximum sum of the absolute differences between adjacent elements by rearranging the array e...read more
Find the maximum sum of absolute differences between adjacent elements in a circular array by rearranging the elements.
Sort the array in non-decreasing order.
Alternate between picking the smallest and largest elements to maximize the sum of absolute differences.
Calculate the sum of absolute differences between adjacent elements in the rearranged array.
Q26. Pattern Matching Problem Statement
Given a pattern as a string and a set of words, determine if the pattern and the words list align in the same sequence.
Input:
T (number of test cases)
For each test case:
patte...read more
Given a pattern and a list of words, determine if the words align with the pattern.
Create a mapping between characters in the pattern and words in the list.
Check if the mapping preserves the order of characters in the pattern.
Return 'True' if the sequence of words matches the order of characters in the pattern, otherwise return 'False'.
Q27. a / b c / / d e f g Print the nodes in the following order: a, b, c, g, f, e, d, h, i, j, k, l ,m, n, o and so on. Which all data structures are used? Can we use just 1?
Multiple data structures are used to print nodes in a specific order. One data structure cannot be used alone.
The given order suggests a depth-first search traversal of a tree-like structure.
A stack can be used to keep track of the nodes to be visited.
A queue can be used to store the children of a node in the order they are visited.
An array can be used to store the nodes in the required order.
A linked list can be used to connect the nodes in the required order.
Using just one ...read more
Q28. How do you make business decisions? Followed by - Estimate number of call centre operators for uber?. Then we had a brief discussion around how to measure Maps accuracy? Why is it important? A bit of strategy w...
read moreBusiness decisions are made by analyzing data, considering goals and objectives, and evaluating potential risks and benefits.
Gather and analyze relevant data
Consider company goals and objectives
Evaluate potential risks and benefits
Consult with stakeholders and experts
Use frameworks and models to guide decision-making
Continuously monitor and evaluate decisions for effectiveness
Q29. Median in a Stream Problem Statement
Your task is to determine the median of integers as they are read from a data stream. The median is the middle value in the ordered list of numbers. If the list length is ev...read more
Find median of integers in a data stream as they are read. Return medians after each new element.
Use a min heap to store the larger half of the numbers and a max heap to store the smaller half.
Keep the sizes of the two heaps balanced to efficiently find the median.
If the total number of elements is odd, the median is the top element of the max heap.
If the total number of elements is even, the median is the average of the top elements of both heaps.
Q30. Connecting Ropes with Minimum Cost
You are given 'N' ropes, each of varying lengths. The task is to connect all ropes into one single rope. The cost of connecting two ropes is the sum of their lengths. Your obj...read more
Connect ropes with minimum cost by merging two smallest ropes at a time.
Sort the array of rope lengths in ascending order.
Merge the two smallest ropes at a time and update the cost.
Repeat until all ropes are merged into one.
Return the total cost as the minimum cost to connect all ropes.
Q31. Majority Element - II Problem Statement
Given an array/list ARR
of integers with length 'N', identify all elements that appear more than floor(N/3)
times within the array/list.
Input:
T (number of test cases)
Fo...read more
Q32. If you had an opportunity to design the Google Suggest system, please let us know how you would approach it and how you would execute the plan in terms of settings up systems like(data stores or databases, inde...
read moreDesigning Google Suggest system
I would start by analyzing user search patterns and frequently searched keywords
Then, I would create a database of these keywords and their associated search results
I would use indexing services to quickly retrieve relevant results for each keyword
I would also implement machine learning algorithms to improve the accuracy of suggestions over time
Q33. Given n pens and n tops, each pen (and each top) having a size different than the other and each pen fitting exactly one top, find the largest pen using minimum number of comparisons. A comparison involves pick...
read moreFind largest pen using minimum comparisons with tops.
Divide pens into two groups and compare largest pen from each group with largest top.
Repeat the process with the group containing the largest pen until only one pen is left.
The remaining pen is the largest pen.
Total number of comparisons required is 2n-3.
Q34. How do you find out if a number is a power of 2? And how do you know if it is an odd number? Write code in the language of your choice
Check if a number is a power of 2 and odd.
To check if a number is a power of 2, use bitwise AND operator with the number and its predecessor. If the result is 0, it is a power of 2.
To check if a number is odd, use modulus operator with 2. If the result is 1, it is odd.
Example code in Python:
def is_power_of_two(num):
return num & (num - 1) == 0
def is_odd(num):
return num % 2 == 1
Q35. Shortest Path in an Unweighted Graph
The city of Ninjaland is represented as an unweighted graph with houses and roads. There are 'N' houses numbered 1 to 'N', connected by 'M' bidirectional roads. A road conne...read more
Implement a function to find the shortest path in an unweighted graph from house 'S' to house 'T'.
Use Breadth First Search (BFS) algorithm to find the shortest path in an unweighted graph.
Create a queue to store the current house and its neighbors, and a visited set to keep track of visited houses.
Start BFS from house 'S' and stop when reaching house 'T'.
Return the path from 'S' to 'T' once 'T' is reached.
If multiple shortest paths exist, any one can be returned.
Example: For ...read more
Q36. Given a source array of integers with possible duplicates and a target integer, write algorithm to find out 2 numbers in source array whose sum is equal to target integer
Algorithm to find 2 numbers in an array whose sum is equal to a target integer
Use a hash table to store the difference between target and each element in the array
Iterate through the array and check if the current element exists in the hash table
Return the pair of elements that sum up to the target integer
Q37. Given n dice, each of 'a' sides and a sum b, return the number of ways in which the sum b can be obtained. How can you reduce the time complexity and space complexity?
Given n dice with 'a' sides and sum b, return no. of ways to obtain b. Optimize time and space complexity.
Use dynamic programming to reduce time complexity
Create a 2D array to store the number of ways to obtain each sum for each number of dice
Use rolling arrays to optimize space complexity
Example: n=2, a=6, b=7 -> 6 ways to obtain sum 7
Example: n=3, a=4, b=8 -> 21 ways to obtain sum 8
Q38. Remove K Corner Elements - Problem Statement
Given an array "arr" consisting of "N" integer elements, your task is to remove "K" elements from the beginning or the end of the array. You must return the maximum ...read more
Given an array, remove K elements from beginning or end to maximize sum of remaining elements.
Iterate through all possible combinations of removing K elements from beginning and end
Calculate sum of remaining elements for each combination
Return the maximum sum obtained
Q39. Minimum Time To Solve The Problems
Given 'N' subjects, each containing a certain number of problems, and 'K' friends, assign subjects to friends such that each subject goes to exactly one friend, maintaining co...read more
Assign subjects to friends to minimize maximum workload, find minimum time for most loaded friend.
Sort subjects in descending order
Assign subjects to friends one by one until all subjects are assigned
The maximum workload will be the sum of problems assigned to the friend with the most problems
Return the maximum workload as the minimum time required
Q40. Find All Anagrams Problem Statement
Given a string STR and a non-empty string PTR, identify all the starting indices of anagrams of PTR within STR.
Explanation:
An anagram of a string is another string that can...read more
Q41. Which technical skills are required to program efficiently ?
The technical skills required to program efficiently include programming languages, algorithms, data structures, debugging, and problem-solving.
Proficiency in programming languages such as Java, Python, C++, etc.
Knowledge of algorithms and their efficiency, including sorting, searching, and graph algorithms.
Understanding of data structures like arrays, linked lists, stacks, queues, trees, and hash tables.
Ability to debug and troubleshoot code to identify and fix errors.
Strong...read more
Q42. Sum of LCM Problem Statement
Given an integer 'N', calculate and print the sum of the least common multiples (LCM) for each integer from 1 to N with N.
The sum is represented as:LCM(1, N) + LCM(2, N) + ... + LC...read more
Calculate and print the sum of least common multiples (LCM) for each integer from 1 to N with N.
Iterate from 1 to N and calculate LCM of each number with N
Sum up all the calculated LCMs to get the final result
Implement a function to calculate LCM of two numbers
Q43. Which is faster: finding an item in a hashtable or in a sorted list? And Why?
Hashtable is faster for finding an item than a sorted list.
Hashtable has constant time complexity O(1) for finding an item.
Sorted list has logarithmic time complexity O(log n) for finding an item.
Hashtable uses hashing to directly access the item's location.
Sorted list requires binary search to find the item's location.
Hashtable is ideal for large datasets with frequent lookups.
Sorted list is ideal for datasets that require frequent insertions and deletions.
Q44. Given 2 machines, each having 64 GB RAM, containing all integers (8 byte), sort the entire 128 GB data. You may assume a small amount of additional RAM. Extend this to sort data stored in 1000 machines
Sort 128 GB data on 2 machines with 64 GB RAM each. Extend to 1000 machines.
Use external sorting algorithm like merge sort or quick sort
Divide data into smaller chunks and sort them individually
Merge sorted chunks using additional RAM
For 1000 machines, use distributed sorting algorithms like MapReduce or Hadoop
Ensure data consistency and fault tolerance in distributed sorting
Q45. Explain the difference between ArrayList and LinkedList in Java. ArrayList is implemented as a dynamic array, while LinkedList is a doubly linked list. ArrayList provides fast random access (O(1) complexity) bu...
read moreArrayList is preferred for frequent retrieval operations, while LinkedList is suitable for frequent insertions/deletions.
Use ArrayList when you need fast random access and retrieval operations, such as searching for elements in a list.
Choose LinkedList when you need fast insertions/deletions, especially at the beginning or end of the list.
Consider memory overhead and performance trade-offs when deciding between ArrayList and LinkedList.
For example, if you have a list of stude...read more
Q46. 1. There is a train that passes the following path: L / \ ... L / \ ... L Each junction tells us the path it is going to take. Once the train passes it'll change the switch at the function. We dont care after t...
read moreDetermining the state of switches/junctions after N trains have passed through them.
Create an array to represent the state of each switch/junction
Iterate through each train and update the state of the corresponding switch/junction
Use a loop to simulate the passing of trains and updating of switches/junctions
Return the final state of the switches/junctions
Q47. You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eg...
read moreTo find the highest floor an egg can be dropped without breaking using 2 identical eggs and a 100-story building.
Start by dropping the first egg from the 50th floor, if it breaks, use the second egg to test floors below 50, if it doesn't break, test floors above 50.
If the first egg doesn't break, drop it from a higher floor and repeat the process until it breaks.
The highest floor tested without breaking the egg is the answer.
This problem can be solved using binary search algo...read more
Q48. You are in the middle of a quarter (month) and are looking at huge deficit on achievement vs target, how do you approach( think from behavioural as well as business action perspective) Give an example where you...
read moreIn the face of a deficit in achieving sales targets, I would approach the situation by analyzing the reasons behind the shortfall and taking appropriate actions to address them.
Identify the reasons for the deficit by analyzing sales data, market trends, and customer feedback.
Develop a plan to address the identified issues, such as revising sales strategies, offering incentives to the sales team, or targeting new customer segments.
Communicate the revised plan to the sales team...read more
Q49. What are the advantages and disadvantages of using Java’s synchronized keyword for thread synchronization? The synchronized keyword ensures that only one thread can access a block of code at a time. It prevents...
read moreReentrantLock should be used instead of synchronized when more flexibility and control over locking mechanisms is needed.
Use ReentrantLock when you need to implement custom locking strategies or require advanced features like tryLock() and lockInterruptibly()
ReentrantLock supports fair locking mechanisms, ensuring that threads acquire the lock in the order they requested it
ReentrantLock allows for more fine-grained control over locking and unlocking, reducing the chances of d...read more
Q50. What is the difference between == and .equals() in Java? == checks for reference equality, meaning it compares memory addresses. equals() checks for value equality, which can be overridden in user-defined class...
read moreIn Java, == checks for reference equality while equals() checks for value equality. Misuse of == can lead to logical errors.
Override equals() when you want to compare the actual content of objects in user-defined classes.
Override hashCode() alongside equals() to ensure consistent behavior in hash-based collections.
Implement Comparable interface and override compareTo() for natural ordering of objects.
Q51. How does the Java garbage collector work? Garbage collection in Java automatically reclaims memory occupied by unused objects. The JVM has different types of GC algorithms, including Serial, Parallel, CMS, and...
read moreGarbage collection in Java automatically reclaims memory occupied by unused objects using different algorithms and memory regions.
Force garbage collection in Java using System.gc() or Runtime.getRuntime().gc()
Not recommended to force garbage collection as it can cause performance issues and disrupt the JVM's optimization
Example: System.gc();
Q52. What are the main features of Java 8? Java 8 introduced lambda expressions, enabling functional-style programming. The Stream API allows efficient data processing with map, filter, and reduce operations. Defaul...
read moreLambda expressions in Java 8 improve readability and maintainability by allowing concise and functional-style programming.
Lambda expressions reduce boilerplate code by providing a more compact syntax for implementing functional interfaces.
They make code more readable by focusing on the behavior being passed as an argument, rather than the mechanics of how it is implemented.
Lambda expressions enable developers to write more modular and reusable code, leading to better maintain...read more
Q53. Palindrome String Validation
Determine if a given string 'S' is a palindrome, considering only alphanumeric characters and ignoring spaces and symbols.
Note:
The string 'S' should be evaluated in a case-insensi...read more
Q54. Minimum Removals Problem Statement
Given an integer array ARR
of size N
and an integer K
, determine the minimum number of elements that need to be removed so that the difference between the maximum and minimum ...read more
Q55. Dijkstra's Shortest Path Problem
Given an undirected graph with ‘V’ vertices (labeled 0, 1, ... , V-1) and ‘E’ edges, where each edge has a weight representing the distance between two connected nodes (X, Y).
Y...read more
Dijkstra's algorithm is used to find the shortest path from a source node to all other nodes in a graph with weighted edges.
Implement Dijkstra's algorithm to find the shortest path distances from the source node to all other nodes
Use a priority queue to efficiently select the next node with the shortest distance
Update the distances of neighboring nodes if a shorter path is found
Handle disconnected vertices by assigning a large value (e.g., 2147483647) as the distance
Ensure no...read more
Q56. In google adwords there are about 30 million ads from 42 lanuages . What will I do review the ads and reject ads that do not comply with specific rules
Reviewing 30 million ads from 42 languages in Google AdWords and rejecting non-compliant ads requires a systematic approach.
Create a set of specific rules and guidelines for ad compliance
Use automated tools to filter out ads that violate the rules
Assign a team of reviewers to manually check the remaining ads
Ensure that the reviewers are fluent in the languages of the ads they are reviewing
Regularly update the rules and guidelines to keep up with changes in the industry
Provide...read more
Q57. Binary Strings Without Consecutive 1s Problem Statement
Given an integer K, your task is to generate all binary strings of length K such that there are no consecutive 1s in the string.
This means the binary str...read more
Q58. If I were a Product Manager of google maps, how would I improve the location accuracy. Why is it important and what could be the solutions? How would I rank solutions?
Improving location accuracy for Google Maps as a Product Manager
Collect more data from GPS and Wi-Fi signals
Use machine learning algorithms to improve accuracy
Partner with mobile network providers to access cell tower data
Implement crowd-sourced data collection from users
Prioritize solutions based on cost, feasibility, and impact on user experience
Q59. Distance Between Two Nodes in a Binary Tree
Given a binary tree and the values of two distinct nodes, determine the distance between these two nodes in the tree. The distance is defined as the minimum number of...read more
Q60. Convert Binary Tree to Mirror Tree
Convert a given binary tree into its mirror tree, where the left and right children of all non-leaf nodes are interchanged.
Input:
An integer ‘T’ denoting the number of test c...read more
Q61. Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The vi...
read moreQ62. Maximum Sum Path from Leaf to Root Problem
You are tasked with finding the path from a leaf node to the root node in a binary tree, such that this path has the maximum sum among all root-to-leaf paths.
Input:
T...read more
Find the path from a leaf node to the root node in a binary tree with the maximum sum.
Traverse the binary tree from leaf to root while keeping track of the sum along the path.
Compare the sums of all root-to-leaf paths and return the path with the maximum sum.
Use recursion to traverse the tree efficiently and update the sum as you go.
Consider edge cases like null nodes and negative values in the tree.
Q63. Intersection of Linked List Problem
You are provided with two singly linked lists containing integers, where both lists converge at some node belonging to a third linked list.
Your task is to determine the data...read more
Q64. How would you change the format of all the phone numbers in 1000 static html pages?
Use a script to iterate through each HTML page, locate phone numbers, and update their format.
Write a script using a programming language like Python or JavaScript to iterate through each HTML page
Use regular expressions to locate phone numbers in the pages
Update the format of the phone numbers as needed (e.g. adding country code, changing separators)
Save the updated HTML pages with the new phone number format
Q65. If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)? If you look at a clock and the time is...
read moreProbability and clock angle calculation
Use probability formula to calculate probability of observing a car in 10 minutes
To calculate clock angle, use the formula: |(30*H) - (11/2)*M| where H is hour and M is minute
Answer to clock angle question is 7.5 degrees
Q66. BFS Traversal in a Graph
Given an undirected and disconnected graph G(V, E) where V vertices are numbered from 0 to V-1, and E represents edges, your task is to output the BFS traversal starting from the 0th ve...read more
BFS traversal of an undirected and disconnected graph starting from vertex 0.
Implement BFS algorithm to traverse the graph starting from vertex 0.
Use a queue to keep track of visited nodes and their neighbors.
Ensure to print the nodes in numerical sort order when multiple neighbors are present.
Handle disconnected components by checking for unvisited nodes.
Output the BFS traversal sequence for each test case in a separate line.
Q67. Consecutive Elements
Given an array arr
of N
non-negative integers, determine whether the array consists of consecutive numbers. Return true if they do, and false otherwise.
Input:
The first line of input conta...read more
Q68. What are some of the most popular Data interchange formats when using APIs
JSON and XML are the most popular data interchange formats when using APIs.
JSON (JavaScript Object Notation) is a lightweight format that is easy to read and write. It is widely used in web APIs.
XML (Extensible Markup Language) is a more complex format that is also widely used in web APIs.
Other formats include CSV (Comma Separated Values), YAML (YAML Ain't Markup Language), and Protocol Buffers.
Q69. Given a string of L, M, R, where L means turn to left, R means turn to right and M means take 1 step forward where you are directed. Now suppose you start from origin, and one letter in the string is wrong, tha...
read moreThe maximum distance that can be reached if one instruction in a string of L, M, R is wrong.
The maximum distance can be reached by following the correct instructions and then taking the opposite direction of the wrong instruction.
For example, if the string is 'LMRM', the correct path would be 'LMR' and then taking a step in the opposite direction of 'M'.
Calculate the distance by summing up the steps taken in the correct path and subtracting the step taken in the wrong directi...read more
Q70. Delete Leaf Nodes with Value X
Given a binary tree where each node contains an integer value, and an integer X, your task is to delete all leaf nodes that have the value X. Continue to remove newly formed leave...read more
Delete all leaf nodes with value X in a binary tree until no such leaves exist.
Traverse the tree in postorder fashion to delete leaf nodes with value X
Recursively call the function on left and right subtrees
Update the root of the tree after removing leaf nodes with value X
Q71. Maximum Time Problem Statement
You are given a string that represents time in the format hh:mm
. Some of the digits are blank (represented by ‘?’
). Your task is to fill in ‘?’
such that the time represented by t...read more
Given a string representing time with some digits as '?', fill in '?' to get maximum time.
Iterate through each digit of the input string and replace '?' with the maximum possible digit based on the position.
For the first digit (hours), if it is '?', replace it with '2' if the second digit is also '?', else replace it with '1'.
For the second digit (hours), if it is '?', replace it with '3' if the first digit is '2', else replace it with '9'.
For the third digit (minutes), if it...read more
Q72. Problem: Search In Rotated Sorted Array
Given a sorted array that has been rotated clockwise by an unknown amount, you need to answer Q
queries. Each query is represented by an integer Q[i]
, and you must determ...read more
Search for integers in a rotated sorted array efficiently using binary search.
Use binary search to efficiently find the index of each query integer in the rotated sorted array.
Handle the rotation of the array by finding the pivot point first.
Check which half of the array the query integer falls into based on the pivot point.
Return the index of the query integer if found, else return -1.
Q73. Sum of Bit Difference Among All Pairs Problem Statement
Given an array of integers, determine the sum of bit differences among all possible pairs that can be formed using the elements of the array.
The bit diff...read more
Calculate sum of bit differences among all pairs in an array of integers.
Iterate through all pairs of elements in the array
Convert each pair of elements to binary representation
Count the differing bits in the binary representations
Sum up the differing bits for all pairs to get the final result
Q74. Tell about ur strength? Tell about long term goal?
My strength lies in my problem-solving skills and ability to work well in a team. My long term goal is to become a lead developer and contribute to innovative projects.
Strong problem-solving skills
Effective team player
Long term goal of becoming a lead developer
Contribute to innovative projects
Q75. In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of...
read moreIn a country where families keep having children until they have a boy, what is the proportion of boys to girls?
The proportion of boys to girls is not 50:50
The probability of having a boy or a girl is always 50%
The more girls a family has, the higher the probability of having a boy in the next pregnancy
The proportion of boys to girls will depend on the number of families and their fertility rates
Q76. Ninja and the Bulbs Challenge
Ninja owns an electronic shop and possesses 'N' bulbs. To verify the quality of the bulbs, Ninja performs a unique technique. After 'N' rounds of this process, bulbs that remain on...read more
Determine the number of good quality bulbs remaining after 'N' rounds of a unique technique.
In each round, bulbs are toggled based on their position (e.g. every second bulb, every third bulb, etc.)
At the end of 'N' rounds, count the bulbs that remain on to determine the number of good quality bulbs.
Example: For N = 4, bulbs 1 and 4 remain on, so the output is 2.
Q77. Wildcard Queries Problem Statement
Given a dictionary D
with N
words, each of a fixed length L
and consisting only of lowercase English alphabets, answer Q
queries. Each query consists of a word W
of the same l...read more
Given a dictionary and queries with wildcard characters, determine how many words in the dictionary can match each query.
Iterate through each query and dictionary word to check for matches
Replace '?' with all possible lowercase letters and compare with dictionary words
Count the number of matches for each query
Q78. How will improve the revenue of the cafeteria of the office.
By introducing new menu items, optimizing pricing strategy, and improving the overall dining experience.
Conduct a survey to understand the preferences of employees
Introduce healthy and affordable meal options
Offer discounts for bulk orders or loyalty programs
Partner with local vendors to source fresh ingredients
Improve the ambiance and seating arrangements
Implement online ordering and delivery services
Q79. Subset OR Problem Statement
You are given an array/list ARR
of N
positive integers. Your task is to determine the size of the smallest subset that achieves the maximum possible OR value among all subsets.
Input...read more
Find the size of the smallest subset with maximum OR value among all subsets of an array of positive integers.
Iterate through all possible subsets of the array
Calculate the OR value for each subset
Track the size of the smallest subset with maximum OR value
Q80. Problem Statement: Delete Node In A Linked List
Given a singly linked list of integers and a reference to a node, your task is to delete that specific node from the linked list. Each node in the linked list has...read more
Given a singly linked list of integers and a reference to a node, delete the specified node from the linked list.
Traverse the linked list to find the node to be deleted.
Update the pointers to skip over the node to be deleted.
Print the modified linked list after deletion.
Ensure the node to be deleted is not the tail node.
Q81. Maximum Subarray Sum Problem Statement
Given an array ARR
consisting of N
integers, your goal is to determine the maximum possible sum of a non-empty contiguous subarray within this array.
Example of Subarrays:...read more
Find the maximum sum of a contiguous subarray within an array of integers.
Use Kadane's algorithm to find the maximum subarray sum efficiently.
Initialize two variables: maxEndingHere and maxSoFar.
Iterate through the array and update the variables accordingly.
Return the maxSoFar as the result.
Q82. Ways To Make Coin Change
Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make the c...read more
The task is to find the total number of ways to make change for a specified value using given denominations.
Use dynamic programming to solve this problem efficiently.
Create a 2D array to store the number of ways to make change for each value up to the specified value.
Initialize the array with base cases and then iterate through the denominations to fill up the array.
The final answer will be in the last cell of the array.
Example: For N=3, D=[1, 2, 3], V=4, the output should be...read more
Q83. Count Distinct Bitwise OR of All Subarrays
Given an array of positive integers, determine the number of distinct values obtained by applying the bitwise OR operation on all possible subarrays.
Explanation:
A su...read more
Count distinct values obtained by applying bitwise OR operation on all possible subarrays of an array of positive integers.
Use a set to store distinct values obtained by bitwise OR operation on all subarrays.
Iterate through all subarrays efficiently to calculate distinct values.
Optimize the solution to handle large input sizes efficiently.
Q84. House Robber Problem Statement
Mr. X is a professional robber with a plan to rob houses arranged in a circular street. Each house has a certain amount of money hidden, separated by a security system that alerts...read more
House Robber problem - determine maximum amount of money to rob without triggering alarm in circular arrangement of houses.
Use dynamic programming to keep track of maximum money robbed at each house.
Consider two cases: robbing the first house and not robbing the first house.
Handle circular arrangement by considering the first and last house separately.
Example: For arr[] = {2, 3, 2}, the output is 3. Mr. X robs house 2.
Example: For arr[] = {1, 2, 3, 1}, the output is 4. Mr. X ...read more
Q85. Rat in a Maze Problem Statement
You need to determine all possible paths for a rat starting at position (0, 0) in a square maze to reach its destination at (N-1, N-1). The maze is represented as an N*N matrix w...read more
Find all possible paths for a rat in a maze to reach its destination, given a matrix representation of the maze.
Use backtracking to explore all possible paths from the starting position to the destination.
Keep track of the current path and explore all possible directions at each step.
Terminate the exploration when reaching the destination and add the path to the result list.
Sort the result list of paths in alphabetical order before returning.
Q86. Which data structure will be better suited chain type data.
Linked List is the best-suited data structure for chain type data.
Linked List is a dynamic data structure that can grow or shrink during runtime.
It allows efficient insertion and deletion operations.
Each node in the linked list contains a reference to the next node.
Examples of chain type data include a list of songs in a playlist or a list of tasks in a to-do list.
Q87. Validate BST Problem Statement
Given a binary tree with N
nodes, determine whether the tree is a Binary Search Tree (BST). If it is a BST, return true
; otherwise, return false
.
A binary search tree (BST) is a b...read more
Validate if a binary tree is a Binary Search Tree (BST) based on given properties.
Check if the left subtree of a node contains only nodes with data less than the node's data.
Verify if the right subtree of a node contains only nodes with data greater than the node's data.
Ensure that both the left and right subtrees are also binary search trees.
Traverse the tree in level order form to validate the BST properties.
Return true if the binary tree is a BST, otherwise return false.
Q88. Sliding Window Maximum Problem Statement
You are given an array/list of integers with length 'N'. A sliding window of size 'K' moves from the start to the end of the array. For each of the 'N'-'K'+1 possible wi...read more
The problem involves finding the maximum element in each sliding window of size 'K' in an array of integers.
Use a deque to store indices of elements in the current window in decreasing order of their values.
Remove indices that are out of the current window from the front of the deque.
Add the maximum element (at the front of the deque) to the result for each window.
Q89. Name some popular APIs for each of these Social Commerce service(llike a photo service etc)
Popular APIs for Social Commerce services
Facebook Graph API for social media integration
Instagram API for photo sharing and tagging
Twitter API for real-time updates and customer engagement
Pinterest API for product discovery and sharing
Google Maps API for location-based services
PayPal API for secure payment processing
Q90. Count Palindrome Words in a String
Given a string 'S' consisting of words, your task is to determine the number of palindrome words within 'S'. A word is considered a palindrome if it reads the same backward as...read more
Count the number of palindrome words in a given string.
Split the string into words using whitespace as delimiter.
Check each word if it is a palindrome by comparing it with its reverse.
Increment a counter for each palindrome word found.
Output the final count of palindrome words for each test case.
Q91. Sudoku Solver
Given a 9x9 Sudoku board, your task is to fill the empty slots and return the completed Sudoku solution.
A Sudoku is a grid composed of nine 3x3 smaller grids. The challenge is to fill in the numb...read more
Implement a Sudoku solver for a 9x9 grid with constraints on row, column, and 3x3 grid.
Create a recursive function to solve the Sudoku puzzle by trying out different numbers in empty slots.
Use backtracking to backtrack and try different numbers if a conflict is encountered.
Ensure each number appears only once in each row, column, and 3x3 grid.
Implement a function to check if a number can be placed in a particular position based on Sudoku rules.
Test the solver with different S...read more
Q92. Why is Java a platform independent language?
Java is platform independent due to its bytecode and JVM implementation.
Java code is compiled into bytecode, which can run on any platform with a Java Virtual Machine (JVM)
JVM acts as an interpreter, translating bytecode into machine code specific to the underlying platform
This allows Java programs to be written once and run anywhere, without the need for recompilation
Q93. What is Java? Features of Java? Ans-java is a high level programing language and it is platform independent. Java is a collection of objects It was developed by sun Microsystem.There are lot of application,webs...
read moreJava is a high-level, object-oriented programming language that is platform-independent and widely used for developing applications, websites, and games.
Developed by Sun Microsystems
Collection of objects
High performance and multi-threaded
Used for developing Android apps, enterprise applications, and web applications
Q94. You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seco...
read moreStay calm, grab onto the side of the blender and wait for someone to rescue you.
Stay calm and don't panic
Grab onto the side of the blender
Wait for someone to rescue you
Try to make noise to attract attention
Q95. What do you know about software engineering and theoretically knowledge
Software engineering is the process of designing, developing, testing, and maintaining software.
It involves using engineering principles to create high-quality software
It includes various stages such as requirements gathering, design, coding, testing, and maintenance
Theoretical knowledge includes understanding of algorithms, data structures, programming languages, and software design patterns
Examples of software engineering practices include Agile, Waterfall, and DevOps metho...read more
Q96. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than...
read moreA pirate must divide 100 gold coins among 5 pirates, but if fewer than half agree, he gets killed. How can he maximize his share and live?
The top pirate should offer 1 coin to the lowest ranked pirate, and keep 99 for himself.
The second-lowest ranked pirate will vote for this plan, as he will get nothing if the top pirate is killed.
The third-lowest ranked pirate will also vote for this plan, as he will get nothing if the second-lowest ranked pirate's plan is chosen.
The top pi...read more
Q97. What are Static Binding and Dynamic Binding?
Static binding is resolved at compile time, while dynamic binding is resolved at runtime.
Static binding is also known as early binding, where the method call is resolved at compile time based on the type of the object.
Dynamic binding is also known as late binding, where the method call is resolved at runtime based on the actual type of the object.
Example of static binding: method overloading.
Example of dynamic binding: method overriding.
Q98. In a singly linked list if there is a pointer S on the first element and pointer L is on the last element. Then which operation will take more time based on the length of the list? 1) Adding element at the firs...
read moreAdding an element at the end of a singly linked list takes more time based on the length of the list.
Adding an element at the end requires traversing the entire list to reach the last element.
Adding an element at the first only requires updating the next pointer of the new element and the head pointer.
Exchanging the first two elements and deleting the element from the end can be done in constant time.
Q99. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighing?
Use a balance to find the heavier ball among eight balls with only two weighings.
Divide the eight balls into three groups of three, three, and two balls.
Weigh the two groups of three balls against each other.
If the two groups weigh the same, the heavier ball is in the group of two balls.
If one group of three balls weighs more, select two balls from that group and weigh them against each other.
If they weigh the same, the heavier ball is the remaining one. If they don't, the he...read more
Q100. How to go about identifying the target segment? Call out the key Features? What would be the MVP plans?
Identifying target segment involves analyzing customer needs and preferences to create a profile. Key features should align with customer needs.
Conduct market research to understand customer needs and preferences
Analyze customer data to create a customer profile
Identify common characteristics among customers to create target segments
Align key features with customer needs and preferences
Create MVP plans based on target segment and key features
Continuously gather feedback to re...read more
More about working at Google
Top HR Questions asked in Afsha Infotech
Interview Process at Afsha Infotech
Top Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month