Senior Software Developer Accolite interview experience

Interview rounds

Round

Medium

Video Call

Duration60 minutes

Interview date5 Jun 2020

Coding problem3

Technical interview round with questions on DSA, OS etc.

1. Left view of Binary Tree

Moderate

30m average time

60% success

0/80

Asked in companies

You have been given a Binary Tree of 'n' nodes, where the nodes have integer values

Print the left view of the binary tree.

Example :

If the input tree is as depicted in the picture:

The Left View of the tree will be:  2 35 2

Problem approach

A level order traversal based solution can be presented here. For each level, we need to print the first node i.e. the leftmost node of that level.
Steps :
1. Make a queue of node type and push the root node in the queue.
2. While the queue is not empty, do :
2.1 Determine the current size of the queue.
2.2 Run a for loop to traverse all nodes of the current level and do :
2.2.1 Remove the topmost node from the queue.
2.2.2 If i==0 (first node of that level) , print it.
2.2.3 Push the left and right child of the node if they exist.

Time Complexity : O(n), where n is number of nodes in binary tree

Try solving now

2. Binary Array Sorting

Easy

20m average time

85% success

0/40

Asked in companies

A binary array is an array consisting of only 0s and 1s.

You are given a binary array "arr" of size ‘N’. Your task is to sort the given array and return this array after sorting.

Problem approach

A two-pointer approach can be used for this question. Maintain two indexes. Initialize the first index left as 0 and second index right as n-1, where n is size of the array .
While left < right , do the following :
a) Keep incrementing index left while arr[left] =0
b) Keep decrementing index right while arr[right]=1
c) If left < right then exchange arr[left] and arr[right]

Try solving now

3. OOPS Question

Comparable vs Comparator in Java

Problem approach

1) Comparable provides a single sorting sequence. In other words, we can sort the collection on the basis of a single element such as id, name, and price. The Comparator provides multiple sorting sequences. In other words, we can sort the collection on the basis of multiple elements such as id, name, and price etc.
2) Comparable affects the original class, i.e., the actual class is modified. Comparator doesn't affect the original class, i.e., the actual class is not modified.
3) Comparable provides compareTo() method to sort elements. Comparator provides compare() method to sort elements.
4) Comparable is present in java.lang package. A Comparator is present in the java.util package.

Round

Medium

Video Call

Duration60 minutes

Interview date5 Jun 2020

Coding problem3

Technical Interview round with questions on DSA.

1. Permutations of a String

Moderate

15m average time

85% success

0/80

Asked in companies

You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.

String A is lexicographically less than string B, if either A is a prefix of B (and A ≠ B), or there exists such i (1 <= i <= min(|A|, |B|)), that A[i] < B[i], and for any j (1 <= j < i) A[i] = B[i]. Here |A| denotes the length of the string A.

For example :

If the string is “bca”, then its permutations in lexicographically increasing order are { “abc”, “acb”, “bac”, “bca”, “cab”, “cba” }.

Note:

Given string contains unique characters.

Problem approach

We can use the concept of backtracking.

According to the backtracking algorithm:
o Fix a character in the first position and swap the rest of the character with the first character. Like in ABC, in the first iteration three strings are formed: ABC, BAC, and CBA by swapping A with A, B and C respectively.
o Repeat step 1 for the rest of the characters like fixing second character B and so on.
o Now swap again to go back to the previous position. E.g., from ABC, we formed ABC by fixing B again, and we backtrack to the previous position and swap B with C. So, now we got ABC and ACB.
o Repeat these steps for BAC and CBA, to get all the permutations.

Algorithm
1. Define a string.
2. Fix a character and swap the rest of the characters.
3. Call the generatePermutation() for rest of the characters.
4. Backtrack and swap the characters again.

Try solving now

2. Maximum Of All Subarrays Of Size k.

Moderate

20m average time

80% success

0/80

Asked in companies

You are given an array consisting of N non-negative integers, and an integer K denoting the length of a subarray, your task is to determine the maximum elements for each subarray of size K.

Note:

A subarray is a contiguous subset of an array.

The array may contain duplicate elements.

The given array follows 0-based indexing.

It is guaranteed that there exists at least one subarray of size K.

Problem approach

The problem can be solved using the concept of sliding window.
We scan the array from 0 to n-1, and maintain a deque to keep "promising" elements.
At each i, we keep "promising" elements, which are potassumally max number in window [i-(k-1),i] or any subsequent window. This means:
1. If an element in the deque and it is out of i-(k-1), we discard them. We just need to remove from the head, as we are using a deque and elements are ordered as the sequence in the array
2. Now only those elements within [i-(k-1),i] are in the deque. We then discard elements smaller than a[i] from the tail. This is because if a[x] 3.As a result, elements in the deque are ordered in both sequence in array and their value. At each step the head of the deque is the max element in [i-(k-1),i]
The algorithm is amortized O(n) as each element is pushed and removed once.

Try solving now

3. OS Question

Print even and odd numbers in increasing order using two threads in Java

Problem approach

The idea is to create two threads and print even numbers with one thread and odd numbers with another thread. Below are the steps:

Create two threads T1 and T2 using the below syntax, where T1 and T2 are used to print odd and even numbers respectively.
Thread T1 = new Thread(new Runnable() {
public void run() { mt.printEvenNumber(); }
});

Thread T2 = new Thread(new Runnable() {
public void run() { mt.printOddNumber(); }
});

where,
printOddNumber() is used to print all the odd numbers till N,
printEvenNumber() is used to print all the even numbers till N.

Maintain a global counter variable and start both threads using the below function:
T1.start();
T2.start();

If the counter is even in the Thread T1, then wait for the thread T2 to print that even number. Otherwise, print that odd number, increment the counter and notify to the Thread T2 using the function notify().
If the counter is odd in the Thread T2, then wait for the thread T1 to print that even number. Otherwise, print that even number, increment the counter and notify the Thread T1 using the function notify().