Innovaccer Data Engineer 2 Interview Questions and Answers

Binary Search has a time complexity of O(log n) and is derived from dividing the search space in half at each step.

• Binary Search is a search algorithm that works on sorted arrays.

• It starts by comparing the target value to the middle element of the array.

• If the target value is smaller, the search continues on the lower half of the array.

• If the target value is larger, the search continues on the upper half of the array.

• T...read more

QuickSort is a sorting algorithm that uses divide and conquer approach.

• Choose a pivot element from the array

• Partition the array into two sub-arrays, one with elements less than the pivot and one with elements greater than the pivot

• Recursively apply the above steps to the sub-arrays

• Combine the sorted sub-arrays to get the final sorted array

Code for Fibonacci Series using Recursion, Iteration and Dynamic Programming

• Recursion: Define a function that calls itself with the previous two numbers in the series as arguments

• Iteration: Use a loop to calculate the series by adding the previous two numbers in each iteration

• Dynamic Programming: Store the previous two numbers in variables and use them to calculate the next number in the series

Implementing a Queue using Stacks

• Use two stacks to implement a queue

• Push elements onto the first stack

• When dequeuing, pop all elements from the first stack and push onto the second stack

• Pop the top element from the second stack to dequeue

• If the second stack is empty, pop all elements from the first stack and push onto the second stack

MergeSort is a divide and conquer algorithm that sorts an array of strings.

• Divide the array into two halves

• Recursively sort the two halves

• Merge the sorted halves

Counting Sort is a sorting algorithm that sorts elements by counting the number of occurrences of each unique element.

• Count the occurrences of each element in the array

• Calculate the cumulative sum of the counts

• Place each element in the sorted array based on its count and cumulative sum

• Time complexity is O(n+k) where n is the number of elements and k is the range of input

• Example: Sort an array of strings based on their

Chrome uses an algorithm to predict and suggest words based on user input.

• Chrome's algorithm uses a combination of user history, bookmarks, and popular searches to predict and suggest words.

• The algorithm also takes into account the frequency and recency of the user's input.

• Chrome's suggestion feature is powered by Google's Autocomplete API, which uses machine learning to predict and suggest words.

• The suggestions are di...read more