SDE - 1

You are given an array of strings. Your task is to find the number of unique strings.

A string is considered unique if it cannot be formed from any other string, present in the array, even after applying the following operations any number of times and in any order:

1. Swapping two characters present at odd indices.

2. Swapping two characters present at even indices.

Note:

Strings contain only lowercase English alphabets.

Example:

Let the array of strings be [“abcd”, “cbad”, “bdac”, “adcb”]. From the given array, strings “abcd”, “cbad”, and “adcb” can be transformed into one another by applying the given operations. But “bdac” cannot be transformed into any other string. Hence, there are only 2 unique strings in the array.

You are given two Strings 'P' and 'Q' of equal length.

Your task is to return 1 if String 'P' can be converted into String 'Q' by cyclically rotating it to the right any number of times ( Possibly Zero ), else return 0.

A cyclic rotation to the right on String 'A' consists of taking String 'A' and moving the rightmost character to the leftmost position. For example, if 'A' = "pqrst", then it will be "tpqrs" after one cyclic rotation on 'A'.

For example:

Consider the two strings 'P' = "abfyg" and 'Q' = "gabfy" 

If we cyclically rotate String 'P' to the right once. The resulting string P becomes "gabfy" which is equal to String 'Q'. 

Therefore it is possible to convert String 'P' to String 'Q'.

You are given a vector of 'N' integers denoting the number of buses that can be boarded from the i-th position. The bus stops only at stops whose number is a multiple of the bus stop number from which the bus originates. You need to find the number of buses originating from each bus stop from 1 to 'N'.

For example:

If 'N' = 4 and the given vector is: [1 3 4 3].

1 bus can be boarded from the first bus stop which means that 1 bus originates from the first bus stop.

3 buses can be boarded from the second bus stop which means that (3 - 1 = 2) buses originate from the second bus stop. This is because the bus originating from the first stop will stop at the second stop as well.

4 buses can be boarded from the third bus stop which means that (4-1 = 3) buses originate from the third bus stop. This is because the bus originating from the first stop will stop at the third stop as well.

3 buses can be boarded from the fourth bus stop which means that (3-3 = 0) buses originate from the fourth bus stop. This is because the buses originating from the first and second stop will stop at the fourth stop as well.

So the final vector would be: [1 2 3 0].

Note:

The given vector uses 1-based indexing.

What is a process?
What is a program?
Difference between a program and a process.
What is a thread?
What are the different states in a process life cycle?

You are given an array of 'N' integers denoting the heights of the mountains. You need to find the length of the longest subarray which has the shape of a mountain.

A mountain subarray is defined as a subarray which consists of elements that are initially in ascending order until a peak element is reached and beyond the peak element all other elements of the subarray are in decreasing order.

Example:

If the given array is: [1 3 1 4]. The longest mountain subarray would be 3. This is because the longest mountain is  [1 3 1] having length 3.

The interview discussed the tech skills and projects mentioned in my resume. Since I had recently started one NLP based project, the interviewer asked me a challenge that I might face in that domain and how I am planning to overcome it. I thought for a while and gave a simple answer which I could think of at that time.

Explain the internal working of HashMaps in Java.
What is the importance of hash code function?
How does Java work internally (JVM and its use)
How is Java different from Python?

What is an abstract method?
What is polymorphism?
What is encapsulation?

What are semaphores?
What are the different types of semaphores?
What is a mutex?
What is a deadlock and how to handle it?

You are given an array consisting of 'N' distinct positive integers and a number 'K'. Your task is to find the kth largest element in the array.

Example:

Consider the array {2,1,5,6,3,8} and 'K' = 3, the sorted array will be {8, 6, 5, 3, 2, 1}, and the 3rd largest element will be 5.

Note:

1) Kth largest element in an array is the kth element of the array when sorted in non-increasing order. 

2) All the elements of the array are pairwise distinct.

Describe the ACID properties in DBMS.

Design and implement a data structure which supports the following operations:

insert(X): Inserts an element X in the data structure and returns true if the element was not present, and false otherwise.

remove(X): Removes the element X from the data structure, if present. Returns true if the element was present and false otherwise.

search(X): Search the element X in the data structure. Returns true if the element was present and false otherwise.

getRandom(): Return a random element present in the data structure.

Four types of queries denote these operations:

Type 1: for insert(X) operation.
Type 2: for remove(X) operation.
Type 3: for search(X) operation.
Type 4: for getRandom() operation.

Note:

It is guaranteed that at least one element will be present in the data structure when getRandom() operation is performed.

Follow Up:

Can you implement every operation such that it works in O(1) time?

You are provided with a Binary Search Tree (BST), all you have to do is to convert it into the sorted doubly linked list (DLL).

For Example:

Consider the above BST, it will be converted into the below sorted DLL.

Here, 20 is the head node and 80 is the tail node.

What would your dream project be like?