SDET-2

You have been given a string ‘A’ consisting of lower case English letters. Your task is to find the length of the longest palindromic subsequence in ‘A’.

A subsequence is a sequence generated from a string after deleting some or no characters of the string without changing the order of the remaining string characters. (i.e. “ace” is a subsequence of “abcde” while “aec” is not).

A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

Given the head node of the singly linked list and an integer ‘k’, , find the value at the kth node from the end of the linked list.

For example:

For the above-linked list, if k=2, then the value at the kth i.e second node from the end is ‘12’.

Note :

1.You don’t need to take any input. It has already been taken care of. Just implement the given function and return a pointer pointing to the k-th element from the last of the linked list.
2.It is guaranteed that k<=size of the linked list.

Given an array arr of length N consisting of positive and negative integers, return the length of the longest subarray whose sum is zero.

You are given a 'Binary Tree'.

Return the bottom view of the binary tree.

Note :

1. A node will be in the bottom-view if it is the bottom-most node at its horizontal distance from the root. 

2. The horizontal distance of the root from itself is 0. The horizontal distance of the right child of the root node is 1 and the horizontal distance of the left child of the root node is -1. 

3. The horizontal distance of node 'n' from root = horizontal distance of its parent from root + 1, if node 'n' is the right child of its parent.

4. The horizontal distance of node 'n' from root = horizontal distance of its parent from the root - 1, if node 'n' is the left child of its parent.

5. If more than one node is at the same horizontal distance and is the bottom-most node for that horizontal distance, including the one which is more towards the right.

Example:

Input: Consider the given Binary Tree:

Output: 4 2 6 3 7

Explanation:
Below is the bottom view of the binary tree.

1 is the root node, so its horizontal distance = 0.
Since 2 lies to the left of 0, its horizontal distance = 0-1= -1
3 lies to the right of 0, its horizontal distance = 0+1 = 1
Similarly, horizontal distance of 4 = Horizontal distance of 2 - 1= -1-1=-2
Horizontal distance of 5 = Horizontal distance of 2 + 1=  -1+1 = 0
Horizontal distance of 6 = 1-1 =0
Horizontal distance of 7 = 1+1 = 2

The bottom-most node at a horizontal distance of -2 is 4.
The bottom-most node at a horizontal distance of -1 is 2.
The bottom-most node at a horizontal distance of 0 is 5 and 6. However, 6 is more towards the right, so 6 is included.
The bottom-most node at a horizontal distance of 1 is 3.
The bottom-most node at a horizontal distance of 2 is 7.

Hence, the bottom view would be 4 2 6 3 7

You are given an array ‘A’ containing a permutation ‘N’ numbers (0 ≤ A[i] < N). You are also given another array ‘B’ containing a permutation ‘M’ numbers (0 ≤ B[j] < M) and it is also given that N ≤ M.

For each element in array ‘A’ you need to find the first greater element to the right of the element in array ‘B’ that has the same value as the current array A’s element. In other words, for each ‘i’ from 0 to N - 1 in array ‘A’, you need to find an index ‘j’ in array ‘B’ such that A[i] = B[j], now you need to print the element that lies on the right of the j’th index and is also greater than B[j]. Print -1 if there is no greater element.

Follow Up :

Can you solve it in O(N+M) time?

For Example :

If ‘N’ = 6, ‘A’ = {1, 2, 0, 3, 4, 5}, ‘M’ = 7 and ‘B’ = {3, 5, 0, 2, 1, 6, 4}.

Then, we will return {6, 6, 2, 5, -1, 6} because:
For i = 0, A[i] = 1 and the first element greater than 1 that lies to the right of it in array ‘B’ is 6.
For i = 1, A[i] = 2 and the first element greater than 2 that lies to the right of it in array ‘B’ is 6.
For i = 2, A[i] = 0 and the first element greater than 0 that lies to the right of it in array ‘B’ is 2.
For i = 3, A[i] = 3 and the first element greater than 3 that lies to the right of it in array ‘B’ is 5.
For i = 4, A[i] = 4 and there is no greater element to the right of 4 in array ‘B’.
For i = 5, A[i] = 5 and the first element greater than 5 that lies to the right of it in array ‘B’ is 6.

Find row with second maximum cost.

Had a discussion around internship that I did. Asked me about the project that I did there. Then we moved on to personal projects followed by HR questions like What was the most challenging part, Tell me about a time when your decision had a huge negative impact; How you dealt with non-collaborative teammates.