Amazon Interview Experience

Coding Round - 3 Questions

Q1 Write a program to return true if the string formed after concatenating characters of linked list forms a palindrome.
The program should be in O(n) time complexity and O(1) space complexity

Q2 Write a program to check if one binary tree is a sub-tree of another binary tree.

Q3 Write a program to print the first non repeating character of the string.

Interview - 1

Q1 Given the arrival time and departure time of various guests. Calculate the minimum number of chairs such that all the guests can be accommodated.
Answer
Sort the arrival time and sort the departure time, keep a count initialized to 0. Compare the first element of arrival time with the first element of departure time. Increment the arrival index and check if the arrival count is greater than the departure count, increment count and arrival index.
Keep doing this for both the arrival and departure index to get the final count.


Q2 Write a program to find the longest sub-string of k characters in a given string.
Time complexity should be O(n) - linear time