Round 1 (Easy)
Questions: Given a dictionary D = { "ABC":"413", "EFG":"7634%ABC%" } and string S = %ABC%2345%EFG%, create a function which takes such an object and a string as input and returns the most normalized version of the string. In this case, the output should be 41323457634413.
Candidate's Approach
The candidate provided a recursive solution to normalize the string based on the given dictionary.
Interviewer's Feedback
No feedback provided.
Round 2 (Easy/Medium)
Questions: Suppose there are N nodes in a directed graph, where every node is an airport. An edge array is given as Array<[start_node,end_node]>. Given a random node 'AIRPORT', return the minimum number of new edges 'AIRPORT' has to make with other nodes such that after making those edges, we can travel to any node from the node 'AIRPORT'.
- Follow-up: Return such nodes in an array.
The candidate was able to provide the solution by creating an indegree array for each node, checking which nodes in the indegree array are zero (indicating entry points in the graph), and making edges with those nodes. If the 'AIRPORT' node itself has an indegree of zero, it is skipped.
Time Complexity: O(N) Space Complexity: O(N)
Candidate's Approach
The candidate created an indegree array for each node and identified the entry points (nodes with indegree zero) to connect to the 'AIRPORT'.
Interviewer's Feedback
No feedback provided.
Round 3 (Medium/Hard)
Questions: You are given an integer array 'Arr' of length 'n', a variable 'startingIndex', and a constant k. You have to perform a few operations.
Suppose, Arr = [3,2,3,4,5], startingIndex = 1, k = 4.
- For odd operation numbers, look to the left from the particular index to find an index where the integer is 1 greater than the current index integer.
- For even operation numbers, do the same but in the right direction.
Return the last attained index when no further jumps can be made.
The candidate provided a brute force solution with time complexity O(N^2) and space complexity O(1).
Candidate's Approach
The candidate described a brute force approach to find the last attained index based on the specified operations, achieving a time complexity of O(N^2) and space complexity of O(1). They expressed a desire for a better solution.
Interviewer's Feedback
No feedback provided.