Tata1mg interview experience Real time questions & tips from candidates to crack your interview
SDE - 1
Tata1mg
1 rounds | 2 Coding
problems
Rejected
Interview preparation journey
Preparation
Duration: 12 months
Topics: DSA, OOPS, OS, CN, Algorithms, DBMS, Dynamic Programming, Graphs
Tip 1 : Do regular preactice of DSA
Tip 2 : Do Extra Subjects (core engineering subjects)
Tip 3 : Prepare some Projects
Application process
Where: Campus
Eligibility: 7 CGPA
Tip 1 : Do Mention coding profiles in the resume
Tip 2 : Do add a summary of the projects
Interview rounds
01
Round
Hard
Online Coding Test
Duration60 minutes
Interview date5 Jan 2022
Coding problem2
1. Longest Repeating Non-Overlapping Substring.
Easy
0/40
Asked in company
You are given a string ‘str’, you need to find the longest repeating and non-overlapping substring in the given string.
A substring of a string can be defined as a contiguous subsequence of that string. In other words, a string X is said to be a substring of the string S if X = S[a...b] = S[a]S[a+1]…..S[b] and 0 <= a <= b <= len(S) (0-based indexing).
You can return any such substring if more than one such substring exists in the string. If there is no such substring, return -1.
Note:
1. Repeating substrings in a string means those substrings which occur more than once in a string. For example, in the string “abaaba”, substrings “a”, “b”, “ab”, “ba”, “aba” are repeating.
2. Two substrings are called Non-overlapping substrings, if the intersection of all the indices of first substring i.e. [L1, R1] where L1 and R1 are the starting and ending index of the first substring respectively, and indices of the second substring i.e. [L2, R2] where L2 and R2 are the starting and ending indices respectively of the second substring, is NULL.
3. For example, in the string “abaaba”, two non-overlapping strings are “ab” lying in the interval [0, 1] (0-based indexing) and “aba” lying in the interval [3, 5] (0-based indexing).
Problem approach
The problem can be solved easily by taking all the possible substrings and for all the substrings check it for the remaining(non-overlapping) string if there exists an identical substring. There are O(n2) total substrings and checking them against the remaining string will take O(n) time. So overall time complexity of above solution is O(n3).
Dynamic Programming : This problem can be solved in O(n2) time using Dynamic Programming. The basic idea is to find the longest repeating suffix for all prefixes in the string str.
2. Maximum XOR With an Element From Array
Hard
50m average time
50% success
0/120
Asked in companies
You are given an array/list ‘ARR’ consisting of ‘N’ non-negative integers. You are also given a list ‘QUERIES’ consisting of ‘M’ queries, where the ‘i-th’ query is a list/array of two non-negative integers ‘Xi’, ‘Ai’, i.e ‘QUERIES[i]’ = [‘Xi’, ‘Ai’].
The answer to the ith query, i.e ‘QUERIES[i]’ is the maximum bitwise xor value of ‘Xi’ with any integer less than or equal to ‘Ai’ in ‘ARR’.
You should return an array/list consisting of ‘N’ integers where the ‘i-th’ integer is the answer of ‘QUERIES[i]’.
Note:
1. If all integers are greater than ‘Ai’ in array/list ‘ARR’ then the answer to this ith query will be -1.
Problem approach
For each node we have to traverse the tree for every query find the xor of all the nodes of the sub-tree. So the complexity of the code will be O(N * Q).
Efficient approach: If we pre-compute the xor of all the nodes of the sub-tree by traversing the total tree once and first computing the xor of all the nodes of the sub-tree of the child node first and then using the value of the child node for computing the xor of all the nodes of the sub-tree of the parent node. In this way we can compute the xor in O(N) time and store them for queries. When a query is asked we will print the pre-computed value in O(1) time.
Here's your problem of the day 
Solving this problem will increase your chance to get selected in this company
Skill covered: Programming
What is recursion?
Choose another skill to practice
Similar interview experiences
SDE - 1
4 rounds | 8 problems
Interviewed by Tata1mg
Rejected
1268 views
1 comments
0 upvotes
SDE - 1
3 rounds | 5 problems
Interviewed by Tata1mg
Rejected
1312 views
0 comments
0 upvotes
SDE - 1
1 rounds | 3 problems
Interviewed by Tata1mg
Rejected
1637 views
1 comments
0 upvotes
SDE - 1
4 rounds | 12 problems
Interviewed by Tata1mg
Selected 0 views
0 comments
0 upvotes
Companies with similar interview experiences
SDE - 1
5 rounds | 12 problems
Interviewed by Amazon
Selected 114579 views
24 comments
0 upvotes
SDE - 1
4 rounds | 5 problems
Interviewed by Microsoft
Selected 57825 views
5 comments
0 upvotes
SDE - 1
3 rounds | 7 problems
Interviewed by Amazon
Selected 34961 views
7 comments
0 upvotes