Uniworth Interview Questions and Answers

Merge Sort is a divide and conquer algorithm that sorts an array by dividing it into two halves, sorting them separately, and then merging the sorted halves.

• Divide the array into two halves

• Recursively sort the two halves

• Merge the sorted halves

Find pairs of integers in a BST whose sum is equal to a given number.

• Traverse the BST and store the values in a hash set.

• For each node, check if (X - node.value) exists in the hash set.

• If yes, add the pair (node.value, X - node.value) to the result.

• Continue traversal until all nodes are processed.

Merge overlapping time intervals into mutually exclusive intervals.

• Sort the intervals based on their start time.

• Iterate through the intervals and merge overlapping intervals.

• Output the mutually exclusive intervals.

• Example: [(1,3), (2,6), (8,10), (15,18)] -> [(1,6), (8,10), (15,18)]

Different types of hashing and alternative for Linear Chaining

• Different types of hashing include division, multiplication, and universal hashing

• Alternative for Linear Chaining is Open Addressing

• Open Addressing includes Linear Probing, Quadratic Probing, and Double Hashing

An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees differ by at most one.

• AVL tree is a binary search tree with additional balance factor for each node.

• The balance factor is the difference between the heights of the left and right subtrees.

• Insertion and deletion operations in AVL tree maintain the balance factor to ensure the tree remains balanced.

• Rotations are performed ...read more

Find the minimum number of squares whose sum equals to a given number n.

• Use dynamic programming to solve the problem efficiently.

• Start with finding the square root of n and check if it is a perfect square.

• If not, then try to find the minimum number of squares required for the remaining number.

• Repeat the process until the remaining number becomes 0.

• Return the minimum number of squares required for the given number n.

Insertion sort for a singly linked list.

• Traverse the list and compare each node with the previous nodes

• If the current node is smaller, swap it with the previous node

• Repeat until the end of the list is reached

• Time complexity is O(n^2)

Implemented a new customer feedback system that increased customer satisfaction by 20%

• Implemented a new customer feedback system to gather insights and improve customer experience

• Analyzed feedback data to identify common issues and areas for improvement

• Implemented changes based on feedback to address customer concerns and enhance overall satisfaction

• Trained team members on how to effectively use the new system and inte...read more

Reverse a binary search tree while maintaining parent-child relationship.

• Start by swapping the left and right child of each node recursively.

• Use a depth-first search approach to traverse the tree.

• Make sure to update the parent-child relationships accordingly.

To find min and max element in stack in O(1), we can use an auxiliary stack.

• Create an auxiliary stack to keep track of the minimum and maximum elements.

• Push the first element to both the main and auxiliary stack.

• For each subsequent element, compare it with the top element of the auxiliary stack and push the smaller element to the auxiliary stack.

• To get the minimum element, simply return the top element of the auxiliary...read more

Given an array, find the next minimum element for each element.

• Iterate through the array

• For each element, compare it with the elements on its right

• Find the minimum element greater than the current element

• If no such element exists, assign -1

• Build the resultant array

Find median of input stream in minimum time complexity using online algorithm.

• Use two heaps, one max heap for elements smaller than current median and one min heap for elements greater than current median.

• Maintain balance between the two heaps by ensuring that the size difference is at most 1.

• If the size of both heaps is equal, median is the average of the top elements of both heaps. Else, median is the top element of ...read more

To make a copy of a linked list with two pointers, iterate through the original list and create a new node for each element.

• Iterate through the original linked list

• Create a new node for each element

• Set the 'next' pointer of each new node

• Set the 'arbitrary' pointer of each new node

Reverse the nodes of a linked list in pairs of n

• Iterate through the linked list in pairs of n

• Reverse the nodes within each pair

• Connect the reversed pairs together

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

To check if a singly linked list is a palindrome, reverse the second half and compare it with the first half.

• Traverse the linked list to find the middle node

• Reverse the second half of the linked list

• Compare the reversed second half with the first half to check for palindrome

Given a preorder of binary tree with leaf nodes represented by N, construct the tree.

• Start by creating an empty stack.

• Iterate through the preorder list.

• If the current element is N, create a leaf node and push it onto the stack.

• If the current element is not N, create a new node and set its left child to the top of the stack.

• Pop the top of the stack and set it as the right child of the new node.

• Push the new node onto the...read more

The question asks to find the maximum occupancy word in each line of a given multiline string and also count the occupancy of capital and small letters separately.

• Split the multiline string into individual lines

• For each line, split it into words

• Initialize variables to store the maximum occupancy word and its count

• Iterate through each word and count the occupancy of each letter

• If the current word has a higher occupancy ...read more

Function to check if a string of parenthesis is balanced

• Use a stack to keep track of opening parenthesis

• If a closing parenthesis is encountered, pop from stack and check if it matches

• If stack is empty and a closing parenthesis is encountered, return False

• If all parenthesis are matched and stack is empty, return True

Count the occurrences of words in a paragraph.

• Split the paragraph into words using whitespace as a delimiter.

• Create a dictionary to store the count of each word.

• Iterate through the words and increment the count in the dictionary.

• Return the dictionary with the word counts.

Find common elements out of two sorted array

• Use two pointers to traverse both arrays simultaneously

• Compare elements at each pointer and move the pointer of the smaller element

• If elements are equal, add to common elements list and move both pointers

• Stop when either pointer reaches end of array

Convert a Binary Search Tree to a Doubly Linked List.

• Create a DLL node class with left, right, and data fields.

• Traverse the BST in-order and add each node to the DLL.

• Adjust the left and right pointers of each node to create the DLL.

• Return the head of the DLL.

The task is to fill the 'next' field of each node in a binary tree to point to the next node at the same level.

• Use a level order traversal to process the tree nodes.

• Maintain a queue to store the nodes at each level.

• For each node, set its 'next' field to the next node in the queue.

• If a node is the last node at its level, set its 'next' field to NULL.

To find anagrams of a given word in a dictionary, use a hash table to store sorted versions of each word as keys and their corresponding original words as values.

• Create a hash table to store the anagrams

• Iterate through each word in the dictionary

• Sort the characters of the word and use it as a key in the hash table

• If the key already exists, add the word to the list of values for that key

• Print the list of values for the

Suggest a data structure for efficient search of a string in 10 files and print line number and file if string appears more than once.

• Use a hash table to store the file name and line number of each occurrence of the string.

• Iterate through each file and for each line, check if the string is present and update the hash table accordingly.

• Print the hash table entries for the string.

Amazon is the right place for me because of its innovative culture, vast resources, and opportunities for growth.

• Amazon's innovative culture aligns with my passion for pushing boundaries and finding creative solutions.

• The company's vast resources provide the necessary tools and support to develop and deliver high-quality software.

• Amazon offers numerous opportunities for growth and career advancement, allowing me to con...read more