You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (9 -> 9 -> 7) + (4 -> 3 -> 7)
Output: 1 -> 5 -> 3 -> 3
Given a string, find the length of the longest substring without repeating characters.
For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container.
From wiki, A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.[1] (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.)
Given a 2D array with rows sorted in ascending order. Find the median of the whole 2D array.
For example,
Given two sorted arrays find the element which would be kth in their merged and sorted combination.
For example, A=[1, 1, 2, 3, 10, 15] and B=[-1, 2, 3, 4, 6, 7] then k=8th smallest element would be 4 as it appears in 8th position of the merged sorted array=[-1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 10, 15].
Permutation means arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set {a,b,c}, namely: (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), and (c,b,a). These are all the possible orderings of this three element set.
Given an unbalanced binary tree, write code to select k sample node at random
You are given a list of n float numbers x_1, x_2, x_3, … x_n, where x_i > 0. A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise).
Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it’s self-intersecting)
e.g.
2 1 1 2 -> crosses
1 2 3 4 -> doesn’t cross
Given an array consisting of N Numbers.
Divide it into two Equal partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum. If number of elements are odd difference in partition size can be at most 1.
Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string
Given a 2D array of 1 and 0, Find the largest rectangle of 1’s or 0’s ie. rectangle (may not be square) which is made up of all 1’s or 0’s.
You are given an array with element represents the height of a tower with width equal to one unit. It started to rain. Find the amount of water trapped between towers?
For example, tower = [0, 1, 2, 1, 3, 2, 0, 2, 3] – then answer is 6 units between towers 3 and 7.
Given n non-negative integers representing the height of bars of width one of a histogram, find the maximum area rectangle of histogram i.e. the maximum area rectangle contained in the histogram.
For example, H = [4, 2, 1, 8, 6, 8, 5, 2] then the histogram has a rectangle of area of 20 showed in shaded.
Given a binary tree, find out the minimum length sum path form root to leaf with sum S. What about finding minimum length sum path for BST? How does BST improve the search?
For example, the min length path for sum S=13 in T1 is 2 (6–>7 not, 6–>4–>3). For T2 min length path for sum S=3 is 3 (3–> -2 –>3).
HeapSort
Heapsort is a O(nlgn) time comparison based sorting algorithm which can sort in-place (swap operations are done on the array itself) but is not stable (i.e. order of element is not maintained). I have discussed general theories behind the idea of building a generic heap data structure in a separate post.
Given a 2-dimensional array of integers, print the 2D array in spiral order.
For example:
A = [1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16]
Then spiral order output should be: [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10].
Given n numbers , n is very large. Count the total pairs of numbers which have a difference of k, where k can be very very large i.e. k>n . The solution should have as low of a computational time complexity as possible.
Given an input string S and a word w. Find the occurrences of the word w in the given string S in linear time. In other words, explain the linear time string matching using KMP matching algorithm.
For example, if S = “ABABAABA” and w = “ABA” then there are 3 occurrences of w in S at {0, 2, 5}.