Nexus Senior Software Engineer 2 Interview Questions and Answers

Convert a sorted array to balanced binary search tree

• Find the middle element of the array and make it the root of the tree

• Recursively construct the left subtree using the left half of the array

• Recursively construct the right subtree using the right half of the array

• Repeat until all elements are added to the tree

Reverse a singly linked list in groups of k in­place

• Divide the linked list into groups of k nodes

• Reverse each group of k nodes

• Connect the reversed groups to form the final linked list

A recursive routine to calculate a ^ n

• The base case is when n is 0, in which case the result is 1

• For any other value of n, the result is a multiplied by the result of a^(n-1)

• The recursive function should call itself with a^(n-1) as the new input

Design optimal data structure for never-ending stream of numbers for insertion, deletion, searching, kth largest and kth smallest.

• Use a balanced binary search tree like AVL or Red-Black tree for efficient insertion, deletion, and searching.

• Maintain two heaps, one for kth largest and one for kth smallest.

• For finding kth largest, use a min heap of size k and for kth smallest, use a max heap of size k.

• Alternatively, use a...read more

Search an element in sorted rotated array.

• Use binary search to find the pivot point where the array is rotated.

• Divide the array into two subarrays and perform binary search on the appropriate subarray.

• Handle the cases where the target element is at the pivot point or not present in the array.

Find the Kth largest element in an array.

• Sort the array in descending order and return the element at index K-1.

• Use a max heap to find the Kth largest element efficiently.

• Implement a quickselect algorithm to find the Kth largest element in linear time.

Reverse a linked list in groups of n elements.

• Divide the linked list into groups of n elements.

• Reverse each group individually.

• Connect the reversed groups to form the final linked list.

• Handle cases where the number of elements is not a multiple of n.

• Example: 1->2->3->4->5->6->7->8, n=3 -> 3->2->1->6->5->4->8->7

Find the median of two sorted arrays.

• Merge the two arrays into one sorted array and find the median.

• Use binary search to find the median in O(log(min(m, n))) time complexity.

• Handle edge cases like empty arrays or arrays of different lengths.

Count number of paths from (0, 0) to (m, n) in a matrix while crossing through some indexes were not allowed.

• Use dynamic programming to solve the problem

• Create a 2D array to store the number of paths

• Traverse the matrix and update the array based on the allowed paths

• Return the value at the last index of the array

Boundary traversal of a tree is the process of visiting the nodes on the boundary of a tree in a specific order.

• The boundary traversal can be done in three steps: left boundary, leaf nodes, and right boundary.

• For the left boundary, start from the root and traverse down the left side of the tree until reaching a leaf node.

• For the leaf nodes, perform an inorder traversal to visit all the leaf nodes of the tree.

• For the ri...read more

Find the nearest greater value of a given value in a Binary Search Tree (BST).

• Start from the root node and compare the given value with the current node's value.

• If the given value is less than the current node's value, move to the left subtree.

• If the given value is greater than the current node's value, move to the right subtree.

• Keep track of the closest greater value encountered while traversing the tree.

• Return the cl...read more

Given an infinite staircase with a broken kth step, find the maximum height we can reach in n rounds of jumping i steps.

• We can start by jumping the maximum number of steps in each round until we reach the broken step.

• After reaching the broken step, we can discard the i steps that would land us on the broken step and jump the remaining steps.

• We can continue this pattern until we reach the maximum height we can reach wit...read more

Construct a binary tree of height h and merge bottom nodes to create a cone-like structure.

• A binary tree of height h has 2^h - 1 nodes.

• Start combining leaf nodes from the bottom level upwards.

• Each combination can be visualized as merging two nodes into one.

• For example, if h=3, the tree has 7 nodes, and you combine nodes at levels 2 and 1.

• The final structure resembles a cone as nodes are merged.