Given a Binary Tree T.
1. Find all paths from root to each of the leaves in T.
2. Find the longest path from root to a leaf (also called Max Depth or Height of the tree).
3. Find the path that has largest sum along the path in T.
4. Find distance (shortest) between given two nodes in T.
5. Diameter of T or Longest path between any two nodes in T.
6. Find mirror image tree of T.
7. Find min length path that sums to a given value.
8. Find the closest leaf from root.
Monthly Archives: October 2015
First non-repeating or unique character in a stream of characters
Given a stream of characters, find the first non-repeating i.e. unique character occurred.
For example, in a stream [a,c,b,a,d,a,…] first unique is ‘c’ but if another ‘c’ character comes to stream [a,c,b,a,d,a c,…] then first unique would be ‘b’.
C++ vs Java
The first difference is the syntax. Other than that, the major differences are:
C++
* OOP is optional.
* Compiled: produces non-portable native code.
* Manually managed memory. Garbage collection libraries are available.
* Source can be written to be portable, so a correctly written program can be compiled for any platform where a C++ compiler is available.
* Mostly used for medium-to-high performance applications, such as games.
How database indexing works?
Why is it needed?
When data is stored on disk based storage devices, it is stored as blocks of data. These blocks are accessed in their entirety, making them the atomic disk access operation. Disk blocks are structured in much the same way as linked lists; both contain a section for data, a pointer to the location of the next node (or block), and both need not be stored contiguously.
Due to the fact that a number of records can only be sorted on one field, we can state that searching on a field that isn’t sorted requires a Linear Search which requires N/2 block accesses (on average), where N is the number of blocks that the table spans. If that field is a non-key field (i.e. doesn’t contain unique entries) then the entire table space must be searched at N block accesses.
Whereas with a sorted field, a Binary Search may be used, this has log2 N block accesses. Also since the data is sorted given a non-key field, the rest of the table doesn’t need to be searched for duplicate values, once a higher value is found. Thus the performance increase is substantial.
Static vs Volatile in Java
Declaring a static variable in Java, means that there will be only one copy, no matter how many objects of the class are created. The variable will be accessible even with no Objects created at all. However, threads may have locally cached values of it.
When a variable is volatile and not static, there will be one variable for each Object. So, on the surface it seems there is no difference from a normal variable but totally different from static. However, even with Object fields, a thread may cache a variable value locally.
This means that if two threads update a variable of the same Object concurrently, and the variable is not declared volatile, there could be a case in which one of the thread has in cache an old value.
Even if you access a static value through multiple threads, each thread can have it’s local cached copy! To avoid this you can declare the variable as static volatile and this will force the thread to read each time the global value.
However, volatile is not a substitute for proper synchronisation! For instance:
Maximum number of overlapping intervals – Merge Overlapping Intervals – Max Task Load
Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time.
For example – { (0,2), (3, 7), (4,6), (7,8), (1,5) }. The maximum number of intervals overlapped is 3 during (4,5).
Floor and Ceiling of a Key in Sorted Array – Search Min Diff Element
Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x.
Weighted job/interval scheduling – Activity Selection Problem
Given N jobs where every job is represented by following three elements of it.
1) Start Time
2) Finish Time.
3) Weight representing Profit or Value Associated.
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.
Contiguous subarray with sum in a range
Given an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b]
Examples:
count([1,2,3], 0, 3) = 4 ( [1], [2], [3], [1, 2])
count([-2,5,-1], -2, 2) = 3 ( [-2], [-1], [-2, 5, -1] )
Count Inversions – Count Smaller on Right
Given an integer array, count the number of inversions.
Inversion count is the distance of order of elements in an array from the the sorted order i.e. it indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
In other words, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
Max Surpasser
For an array of integers, a surpasser of an integer element is an element on its right hand side that is larger than it. Given an array of integers, Output the max number of surpassers.
For example, {10,3,4,5,2}, the surpassers of 3 is 4 and 5, and 10 doesn’t have any surpasser.
Find the single number that duplicates one or more times
Find the single number that duplicates one or more times in an array in O(1) space and O(n) time without modifying the array
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
Walls and Gates – find shortest escape paths
You are given a m x n 2D grid initialized with these three possible values.
-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.
Assign binary operators to evaluate to target value
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
For example:
“232”, 8 -> [“2*3+2”, “2+3*2”]
“00”, 0 -> [“0+0+0”, “0-0”, “0*0”]
“102”, 2 -> [“1*0+2”]
“45435”, 9191 -> []
Add two number represented by Linked Lists
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
Longest sub-string with no duplicate chars
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.
Dutch National Flag (DNF) problem (3-way partitioning)
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}
Container With Most Water
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.