Portfolio

Data Structures & Algorithms

I spend a lot of time answering algorithmic questions on Quora. Here are some of my more interesting answers:

• How do I find the mex (minimum excludant) from a set of integers (both positive and negative)?
• How do I find the longest consecutive sequence from an array of integers?
• How do I take a random sample of size k from a stream of n elements?
• How do I find the greatest sum from from the root to a leaf in a triangular graph of numbers?
• How do I identify a problem as a dynamic programming problem?
• Why is it when removing the root of a binary heap that we replace it with the rightmost element in the last level?
• How do I determine the order of visiting all leaves of a rooted tree, so that in each step I visit a leaf whose path from root contains the most unvisited nodes?
• What is the efficient algorithm to find the number of triangles possible in a given array or vector?
• What is the difference between a tree, a prefix tree, and a radix tree?
• What is the most appropriate algorithm to use to find the number of sub-words in a given word?
• In layman's terms, what is amortized time complexity?
• Given a dictionary of words, how can we efficiently find a pair words such that they don't have characters in common and sum of their length is maximum?
• Can every dynamic programming problem be solved using recursion with memoization?
• What is the maximal profit that M machines can earn over W weeks if each machine can manufacture either product A (300TL profit) or product B (500TL profit) for a given week, knowing that 30% of machines that manufacture product A and 60% of machines that manufacture product B wear out each week (and thus, cannot manufacture anything)?
• What is the efficient way to find all in order numbers in an array in O(N) time, where "in order" means all numbers in the array before it are less than it and all numbers after it are greater than it?
• How can we multiply two numbers represented by linked lists?
• Given a triangle, how do I find the minimum path sum from top to bottom?
• What are different algorithm for converting a string into palindrome string except appending the reverse of same string method?
• How do you find maximum element in stack in constant order time?
• How can I rotate the elements in an array efficiently?
• Why is cuckoo hashing not considered to be a perfect hash?
• When should one use selection sort and bubble sort? Is there any advantage of selection sort over bubble sort or vice versa?
• Why do Bloom Filters have multiple hash functions?
• Given n positive real numbers, how do I find whether there exists a triplet among this set such that the sum of the values in triplet is in the range (1, 2)?
• How can you count all the duplicates in a binary search tree in O(n) time and O(1) space?
• Two nodes of a binary search tree have been incorrectly swapped. How do you efficiently restore the tree to its correct state?
• What is the most efficient algorithm to find the kth smallest element in an array having n elements?
• What is the most efficient algorithm to check if a number is a Fibonacci Number?
• How I can optimize Burrows-Wheeler transform and inverse transform to work in O(n) time O(n) space?
• Given an array of n integers between 1 and n, how do I find one number that repeats in linear time?
• Given an integer array which might contain duplicates, how do I find if it is a sequence?
• Given an array A of k values which contain integer values in sorted (ascending) order, how do I find the top k values (ascending) which can either be a number from the array A, the sum of any two numbers from A, or the sum of any three numbers from A?