OnGrid Software Developer Interview Questions and Answers

Efficient solution to find k closest stars to earth from a list of stars and their distances.

• Use a priority queue to store the distances of stars from earth.

• Iterate through the list of stars and add their distances to the priority queue.

• Pop k elements from the priority queue to get the k closest stars to earth.

Find Nth largest element in the BST

• Traverse the BST in reverse inorder and keep track of count

• If count equals N, return the current node's value

• If count exceeds N, stop traversing and return null

• If count is less than N, continue traversing

Find node in BST with value equal to or greater than input value.

• Start at root node

• If input value is less than current node value, move to left child

• If input value is greater than or equal to current node value, move to right child

• Repeat until node with desired value is found or null is reached

Program to check if a binary tree is balanced

• Calculate height of left and right subtrees recursively

• Check if the difference in height is not more than 1

• Repeat for all nodes in the tree

• Time complexity: O(nlogn) or O(n)

• Space complexity: O(h) where h is the height of the tree

Find max size of a sub-string with no duplicate characters in a given string.

• Use a sliding window approach with two pointers.

• Maintain a hash set to keep track of unique characters.

• Update the maximum length of the substring as you iterate through the string.

A hash table is a data structure that stores key-value pairs and uses a hash function to map keys to buckets.

• Hash function takes a key and returns an index to a bucket

• Collisions occur when multiple keys map to the same bucket

• Collision resolution techniques include chaining and open addressing

• Example: Dictionary in Python uses hash tables to store key-value pairs

WAP to find a continuous subset divisible by 7 from an array of numbers. Calculate algorithm complexity.

• Iterate through the array and calculate the prefix sum modulo 7 at each index.

• Store the prefix sum modulo 7 in a hash table with the index as the value.

• If a prefix sum modulo 7 is already in the hash table, the subarray between the two indices has a sum divisible by 7.

• Time complexity is O(n) and space complexity is O

Given a 2D array of integers, set rows and columns to 1 if they contain 1.

• Iterate through the array to find the index of 1

• Use two arrays to keep track of rows and columns with 1

• Iterate through the rows and columns arrays to set values to 1

Code to find sum of two numbers stored as linked list.

• Traverse both lists simultaneously and add corresponding nodes

• Keep track of carry and add it to next sum

• Create a new node for each sum and move to next node

Code to print elements on path from root to leaf node with max sum

• Traverse the tree and keep track of the maximum sum path

• Use recursion to traverse the tree

• Print the path when a leaf node with maximum sum is reached

Retrieving min element from a max heap has a time complexity of O(log n).

• The min element is always the leftmost leaf node in the last level of the heap.

• To retrieve it, swap it with the last element in the heap and remove it.

• Then, bubble down the new root to maintain the max heap property.

• Examples: retrieving the smallest number in a priority queue implemented as a max heap.

• Examples: retrieving the smallest element in a

The fastest method to sort an almost sorted array is shell sort.

• Shell sort has a time complexity of O(n log n) which is faster than bubble sort and insertion sort.

• Quick sort and merge sort have a time complexity of O(n log n) but they are not optimized for almost sorted arrays.

• Shell sort works by comparing elements that are far apart first and then gradually reducing the gap between them.

• Example: If the array is [1, 3,...read more

A zombie process is a process that has completed execution but still has an entry in the process table.

• Zombie processes occur when a parent process does not properly wait for its child process to terminate.

• The zombie process remains in the process table until the parent process reads its exit status.

• Zombie processes do not consume system resources but can accumulate if not properly handled.

• They can be identified using ...read more

Hash tables have complexities related to collisions, resizing, and choosing a good hash function.

• Collisions occur when two keys map to the same index, requiring a collision resolution strategy.

• Resizing can be expensive as all elements need to be rehashed and moved to new locations.

• Choosing a good hash function is important to minimize collisions and ensure even distribution of keys.

• Examples of collision resolution stra...read more

Algorithm to find any three numbers in an array that sum to zero.

• Sort the array in ascending order.

• Loop through the array and fix the first number.

• Use two pointers to find the other two numbers that sum to the negative of the fixed number.

• If found, return the three numbers.

• If not found, move to the next number and repeat the process.

• Time complexity: O(n^2)

Returning kth smallest element in a BST with time complexity logn.

• Perform in-order traversal and keep track of count until kth element is reached

• If kth element is found, return it

• If kth element is not found, continue traversal

• If traversal is complete and kth element is not found, return null

• Time complexity is logn as we only traverse the height of the tree

Check if a Binary Tree is a Binary Search Tree

• Inorder traversal of BST should be in ascending order

• Check if left child is less than parent and right child is greater than parent

• Recursively check left and right subtrees

• Use min and max values to check if nodes are within valid range

Sort a large file of numbers with limited memory

• Use external sorting algorithms like merge sort or quick sort

• Divide the file into smaller chunks that can fit into memory

• Sort each chunk and merge them together using a priority queue

• Consider using disk-based sorting techniques like replacement selection

• Optimize I/O operations to minimize disk access

Implement a phone book with search by name or phone number and prefix.

• Create an array of strings to store contacts

• Implement a function to add contacts to the array

• Implement a function to search by name or phone number

• Implement a function to search by prefix

• Use regular expressions to match prefixes

Find Pythagorean triplets in an array of integers.

• Loop through the array and pick two numbers at a time.

• Calculate the sum of squares of the two numbers.

• Check if the sum is a perfect square.

• If yes, then it is a Pythagorean triplet.

• Repeat until all possible combinations are checked.

Compute the nearest palindrome number greater than given number.

• Convert the given number to string and reverse it.

• Add the reversed string to the original number and check if it's a palindrome.

• If not, repeat the process until a palindrome is found.

• If the original number is already a palindrome, add 1 to it and repeat the process.

Find minimum window in a string which contains all characters from another string.

• Use a sliding window approach

• Create a frequency map of characters in pat

• Iterate through str and update frequency map

• Keep track of minimum window that contains all characters

• Return minimum window

Arrange balls in 4 jars to maximize probability of user losing money when drawing a red ball.

• Place all red balls in one jar and the rest in the other jars

• Ensure that the jar with red balls has the highest probability of being chosen

• Randomize the placement of the jars to add an element of chance

Code to check if a tree is BST or not

• Check if left subtree is BST

• Check if right subtree is BST

• Check if max value in left subtree is less than root

• Check if min value in right subtree is greater than root

Modify code to find maximum BST subtree and maximum BST tree in a given tree.

• Create a function to check if a given tree is a BST

• Traverse the tree and check if each subtree is a BST

• Keep track of the maximum BST subtree found so far

• To find maximum BST tree, check if each node can be the root of a BST

• Keep track of the maximum BST tree found so far

Algorithm to determine valid variables on a given line of code.

• Create a stack to keep track of variable declarations

• Traverse the code line by line

• When encountering a variable declaration, push it onto the stack

• When encountering a closing brace, pop all variables declared within that scope

• Return all variables still on the stack when reaching the given line number

Implement LRU cache with put, get, and remove operations.

• LRU stands for Least Recently Used.

• The cache should have a maximum capacity.

• When the cache is full, the least recently used item should be removed.

• When an item is accessed, it should be moved to the front of the cache.

• Use a doubly linked list and a hash map to implement the cache efficiently.

next_permutation function generates the next greater lexicographic permutation of a sequence

• The function modifies the sequence to its next permutation if possible

• If the sequence is already the largest permutation, it rearranges it to the smallest permutation

• The function returns true if a next permutation exists, else false

• The sequence must be sorted in non-descending order before calling the function

Given n sequences with start, stop and score, find maximum subset of non-overlapping sequences with maximum total score.

• Sort the sequences by their end points.

• Use dynamic programming to find the maximum sum of non-overlapping sequences.

• Keep track of the previous non-overlapping sequence with maximum sum.

• Return the maximum sum and the corresponding non-overlapping sequences.