Given an array of integers and a value. Find all the pairs that sums up to the value in O(n) time with only one pass over the array. Can you do it efficiently without any space constraint?
Daily Archives: June 6, 2014
Smallest Difference between 2 elements from 2 different array
Given two arrays. Find the smallest difference between two elements from both of the arrays.
For example: A=[0, -6, 4, 6, 5, -2], and A=[-4, 8, 2, 3, 10, 9] then then the smallest difference between two elements of the two array is 1 with pairs (4, 3) from the arrays repectively.
Longest palindrom by deleting/inserting elements
Given a string. Find minimum number of insertion (or deletions) required to make it a palindrom.
For example, S=”abacba” can be transformed into the longest palindrom P1=”abacaba” just by inserting 1 char.
Prime numbers less than equal to N in O(n) time
Given an integer N, find all the prime numbers less than in sorted order.
Median of a stream of integer
Given that integers are read from a data stream. Find median of elements read so for in efficient way.
For example, median of the stream, A = [1, 5, 3, 2, 6, 2, 3] is = 3.
Max/Min Heap
Heap is a special data structure that has a shape of a complete binary tree (except possibly the deepest internal node) with a special property. We call it ‘Heap Property’.
Heap property
All nodes are either greater than or equal to (for max heap) or less than or equal to (for min heap) each of its children.