SDE - 1

A Bitonic Sequence is a sequence of numbers that is first strictly increasing and then strictly decreasing.

A strictly ascending order sequence is also considered bitonic, with the decreasing part as empty, and same for a strictly descending order sequence.

For example, the sequences [1, 3, 5, 3, 2], [1, 2, 3, 4] are bitonic, whereas the sequences [5, 4, 1, 4, 5] and [1, 2, 2, 3] are not.

You are given an array 'arr' consisting of 'n' positive integers.

Find the length of the longest bitonic subsequence of 'arr'.

Example :

Input: 'arr' = [1, 2, 1, 2, 1]

Output: 3

Explanation: The longest bitonic subsequence for this array will be [1, 2, 1]. Please note that [1, 2, 2, 1] is not a valid bitonic subsequence, because the consecutive 2's are neither strictly increasing, nor strictly decreasing.

You are given an array ‘A’ of size ‘N’. Return true if an array can be divided into groups of pairs such that XOR of each pair is equal to 0.

A pair consists of two integers.

Example : Let the array be { 1, 2, 3, 4}

One of the ways to divide it into groups of pairs is { 1, 2 } and { 3, 4}.

You have a list of all-natural numbers and an ‘arr’. Your task is to find the Kth smallest natural number after removing all numbers in ‘arr’ from the list of all-natural numbers.

Note: ‘arr’ will be sorted in ascending order.

For example:

You are given, ‘arr’ = [1, 2, 4], ‘K’ = ‘5’, You have the natural numbers as [1, 2, 3, 4, 5, 6, 7 .. ], after removing all the integers in the array from natural numbers, we have, [3, 5, 6, 7, 8]. Here 8 is the 5th smallest number. Hence the answer is 8.

You are given a string ‘STR’. You need to find and return the minimum number of characters to be deleted from ‘STR’ so that the frequency of each character in the string becomes unique.

Example:

If the given string is “aaBBccc” then the frequency of characters: { a:2, B:2, c:3 }. Now, as ‘a’ and ‘B’ both have the same frequency 2, we need to delete one character either one ‘a’ or one ‘B’, to make their frequency different. After deleting any character we will get frequency as 1,2 and 3, as they all are different. Thus we got our solution as 1.

Bob lives with his wife in a city named Berland. Bob is a good husband, so he goes out with his wife every Friday to ‘Arcade’ mall.

‘Arcade’ is a very famous mall in Berland. It has a very unique transportation method between shops. Since the shops in the mall are laying in a straight line, you can jump on a very advanced trampoline from the shop i, and land in any shop between (i) to (i + Arr[i]), where Arr[i] is a constant given for each shop.

There are N shops in the mall, numbered from 0 to N-1. Bob's wife starts her shopping journey from shop 0 and ends it in shop N-1. As the mall is very crowded on Fridays, unfortunately, Bob gets lost from his wife. So he wants to know, what is the minimum number of trampoline jumps from shop 0 he has to make in order to reach shop N-1 and see his wife again. If it is impossible to reach the last shop, return -1.

How would you go about Designing Instagram?

What would your DB Scheme look like?
What would your query look like for fetching all recent photos of the given user?
How would you write the query for fetching all photos, for a user feed?

How would you go about solving Rubik’s Cube? (Only Approach)

Solve for steps needed to reach the solved state of the cube
Data Structure you will use
Algorithmic Paradigm
Time Complexity

The n-th term of Fibonacci series F(n), where F(n) is a function, is calculated using the following formula -

    F(n) = F(n - 1) + F(n - 2), 
    Where, F(1) = 1, F(2) = 1

Provided 'n' you have to find out the n-th Fibonacci Number. Handle edges cases like when 'n' = 1 or 'n' = 2 by using conditionals like if else and return what's expected.

"Indexing is start from 1"

Example :

Input: 6

Output: 8

Explanation: The number is ‘6’ so we have to find the “6th” Fibonacci number.
So by using the given formula of the Fibonacci series, we get the series:    
[ 1, 1, 2, 3, 5, 8, 13, 21]
So the “6th” element is “8” hence we get the output.

1) Explain Garbage Collection in Java, which algorithm is used for Garbage Collection?
2) Explain Function Programming in Java? Does it support higher-order functions?
3) What are Singleton Objects?
4) What do you understand by Composition in OOPS?
5) What is Aggregation in OOPS?
 

1) How would you go about building API’s in Java?
2) What is JVM?

Tell me something not there in your resume.