Tuesday, August 30, 2016

Remove duplicates from infinite integers

You are given an infinite stream of integers. The stream of integers is unsorted and are provided by iterator so that you don't have the access to all the elements at once. You have to return another iterator from the input iterator so that there are no duplicates and the input order is maintained.

http://www.dsalgo.com/2013/03/remove-duplicate-infinite-integer.html

Sunday, August 28, 2016

Microsoft Cloud Computing Services

Overall Azure Services:
https://azure.microsoft.com/en-in/get-started/

Microsoft Azure specific Services:
https://azure.microsoft.com/en-in/documentation/articles/active-directory-whatis/
https://azure.microsoft.com/en-us/documentation/articles/key-vault-whatis/

Onedrive vs Sharepoint
http://blog.apterainc.com/bid/392491/What-s-the-Difference-between-OneDrive-and-SharePoint

Microsoft Azure Vault:
http://www.cio.com/article/2986308/cloud-security/is-byok-the-key-to-secure-cloud-computing.html

Office LockBox
http://en.share-gate.com/blog/office365-security-customer-lockbox
https://blogs.office.com/2015/04/21/announcing-customer-lockbox-for-office-365/

Cloud Computing Security
https://en.wikipedia.org/wiki/Cloud_computing_security

Encryption Algorithms:
https://en.wikipedia.org/wiki/Symmetric-key_algorithm
https://en.wikipedia.org/wiki/RSA_(cryptosystem)
https://en.wikipedia.org/wiki/Public-key_cryptography

David Malan System Design Topics

Monday, August 15, 2016

Graph Coloring

Vertex coloring is the most common graph coloring problem. The problem is, given m colors, find a way of coloring the vertices of a graph such that no two adjacent vertices are colored using same color. The other graph coloring problems like Edge Coloring (No vertex is incident to two edges of same color) and Face Coloring (Geographical Map Coloring) can be transformed into vertex coloring.

http://www.geeksforgeeks.org/graph-coloring-applications/

Sunday, August 14, 2016

K Centers Problem: Cities and Distances

Given n cities and distances between every pair of cities, select k cities to place warehouses (or ATMs or Cloud Server) such that the maximum distance of a city to a warehouse (or ATM or Cloud Server) is minimized.
For example consider the following four cities, 0, 1, 2 and 3 and distances between them, how do place 2 ATMs among these 4 cities so that the maximum distance of a city to an ATM is minimized.
http://www.geeksforgeeks.org/k-centers-problem-set-1-greedy-approximate-algorithm

Pending

Pending

Saturday, August 13, 2016

Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:
Secret number: "1807"
Friend's guess: "7810"

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".

http://www.programcreek.com/2014/05/leetcode-bulls-and-cows-java/

Guess Number higher or lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.

Return 6.
http://www.programcreek.com/2014/07/leetcode-guess-number-higher-or-lower-java/

The Celebrity Problem

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.

http://www.geeksforgeeks.org/the-celebrity-problem/

The Stock Span Problem

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate span of stock’s price for all n days.
The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.
For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}
http://www.geeksforgeeks.org/the-stock-span-problem/

Friday, August 12, 2016

Find maximum of minimum for every window size in a given array

Given an integer array of size n, find the maximum of the minimum’s of every window size in the array. Note that window size varies from 1 to n.

Example:

Input:  arr[] = {10, 20, 30, 50, 10, 70, 30}
Output:         70, 30, 20, 10, 10, 10, 10

First element in output indicates maximum of minimums of all
windows of size 1.
Minimums of windows of size 1 are {10}, {20}, {30}, {50}, {10},
{70} and {30}.  Maximum of these minimums is 70

http://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/

Design a stack with operations on middle element

How to implement a stack which will support following operations in O(1) time complexity?
1) push() which adds an element to the top of stack.
2) pop() which removes an element from top of stack.
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element.
Push and pop are standard stack operations.

http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/

Check if a given array can represent Preorder Traversal of Binary Search Tree

Given an array of numbers, return true if given array can represent preorder traversal of a Binary Search Tree, else return false. Expected time complexity is O(n).

Input:  pre[] = {2, 4, 3}
Output: true
    2
     \
      4
     /
    3
Input:  pre[] = {2, 4, 1}
Output: false
http://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/


Find the first circular tour that visits all petrol pumps

Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

1. The amount of petrol that every petrol pump has.
2. Distance from that petrol pump to the next petrol pump.

Calculate the first point from where a truck will be able to complete the circle (The truck will stop at each petrol pump and it has infinite capacity). Expected time complexity is O(n). Assume for 1 litre petrol, the truck can go 1 unit of distance.

For example, let there be 4 petrol pumps with amount of petrol and distance to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The first point from where truck can make a circular tour is 2nd petrol pump. Output should be “start = 1″ (index of 2nd petrol pump).

http://www.geeksforgeeks.org/find-a-tour-that-visits-all-stations/


Wednesday, August 10, 2016

Given a linked list of line segments, remove middle points

Given a linked list of co-ordinates where adjacent points either form a vertical line or a horizontal line. Delete points from the linked list which are in the middle of a horizontal or vertical line.
Input:  (0,10)->(1,10)->(5,10)->(7,10)
                                  |
                                (7,5)->(20,5)->(40,5)
Output: Linked List should be changed to following
        (0,10)->(7,10)
                  |
                (7,5)->(40,5)
http://www.geeksforgeeks.org/given-linked-list-line-segments-remove-middle-points/

Compare two strings represented as linked lists

Given two linked lists, represented as linked lists (every character is a node in linked list). Write a function compare() that works similar to strcmp(), i.e., it returns 0 if both strings are same, 1 if first linked list is lexicographically greater, and -1 if second string is lexicographically greater.

Examples:
Input: list1 = g->e->e->k->s->a
       list2 = g->e->e->k->s->b
Output: -1

Input: list1 = g->e->e->k->s->a
       list2 = g->e->e->k->s
Output: 1

Input: list1 = g->e->e->k->s
       list2 = g->e->e->k->s
Output: 0
http://www.geeksforgeeks.org/compare-two-strings-represented-as-linked-lists/

Find a triplet from three linked lists with sum equal to a given number

Given three linked lists, say a, b and c, find one node from each list such that the sum of the values of the nodes is equal to a given number.
For example, if the three linked lists are 12->6->29, 23->5->8 and 90->20->59, and the given number is 101, the output should be tripel “6 5 90″.
http://www.geeksforgeeks.org/find-a-triplet-from-three-linked-lists-with-sum-equal-to-a-given-number/

Construct a Maximum Sum Linked List out of two Sorted Linked Lists with common nodes

Given two sorted linked lists, construct a linked list that contains maximum sum path from start to end. The result list may contain nodes from both input lists. When constructing the result list, we may switch to the other input list only at the point of intersection (which mean the two node with the same value in the lists). You are allowed to use O(1) extra space.

Input:
List1 =  1->3->30->90->120->240->511
List2 =  0->3->12->32->90->125->240->249

Output: Following is maximum sum linked list out of two input lists
list =  1->3->12->32->90->125->240->511
we switch at 3 and 240 to get above maximum sum linked list
http://www.geeksforgeeks.org/maximum-sum-linked-list-two-sorted-linked-lists-common-nodes/

Monday, August 8, 2016

Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

Given an array arr[] of size n where every element is in range from 0 to n-1. Rearrange the given array so thatarr[i] becomes arr[arr[i]]. This should be done with O(1) extra space.

Examples:
Input: arr[]  = {3, 2, 0, 1}
Output: arr[] = {1, 0, 3, 2}

Input: arr[] = {4, 0, 2, 1, 3}
Output: arr[] = {3, 4, 2, 0, 1}

Input: arr[] = {0, 1, 2, 3}
Output: arr[] = {0, 1, 2, 3}
http://www.geeksforgeeks.org/rearrange-given-array-place/
http://www.geeksforgeeks.org/rearrange-array-arrj-becomes-arri-j/

Pending


Sunday, August 7, 2016

Given an integer matrix, find the length of the longest increasing path

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
Strategy: Dynamic Programming
This is a very classic DFS + memorialization problem. If we only use the DFS solution, it will end with many repeated calculations. Therefore, for each element in the matrix[i][j], we use a DP array dp[i][j] to denote the length of the maximum increasing path from this point. So along with the DFS, for a point in the matrix, if we've already found the longest increasing path, we don't have to repeatedly compute it again; we just need to return the length, which is dp[i][j].

One trick here is dp[i][j] stores the length of the longest increasing path. That is because the DFS from a point matrix[i][j] can guarantee the longest path from this point. Since we store this value in the dp[i][j], that can guarantee that dp[i][j] is the longest path from the point matrix[i][j].

http://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/
http://buttercola.blogspot.in/2016/06/leetcode-329-longest-increasing-path-in.html
http://adijo.github.io/2016/01/20/leetcode-longest-increasing-path-matrix/


Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
For example, given three people living at (0,0)(0,4), and (2,2):
1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0
The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.
Strategy:
best meeting point of one-dimension is at the middle point. for 2D is the same. find the mid-x and mid-y, it is the meeting place.
http://happycoding2010.blogspot.in/2015/11/leetcode-296-best-meeting-point.html
http://www.programcreek.com/2014/07/leetcode-best-meeting-point-java/

Zigzag Conversion of String

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

http://k2code.blogspot.in/2016/03/convert-string-to-zigzag-bottom-up.html
http://n00tc0d3r.blogspot.in/2013/06/zigzag-conversion.html

Saturday, August 6, 2016

Find the nearest smaller numbers on left side in an array

Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.

Examples:
Input:  arr[] = {1, 6, 4, 10, 2, 5} Output:         {_, 1, 1,  4, 1, 2}
First element ('1') has no element on left side. For 6,
there is only one smaller element on left side '1'.
For 10, there are three smaller elements on left side (1,
6 and 4), nearest among the three elements is 4.

Input: arr[] = {1, 3, 0, 2, 5}  Output:        {_, 1, _, 0, 2}
http://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/

Search in an almost sorted array

Given an array which is sorted, but after sorting some elements are moved to either of the adjacent positions, i.e., arr[i] may be present at arr[i+1] or arr[i-1]. Write an efficient function to search an element in this array. Basically the element arr[i] can only be swapped with either arr[i+1] or arr[i-1].

For example consider the array {2, 3, 10, 4, 40}, 4 is moved to next position and 10 is moved to previous position.

Example:

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2
Output is index of 40 in given array

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 90
Output: -1
-1 is returned to indicate element is not present
http://www.geeksforgeeks.org/search-almost-sorted-array/

Sort an array in wave form

Given an unsorted array of integers, sort the array into a wave like array. An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..

Examples:

 Input:  arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
 Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} OR
                 {20, 5, 10, 2, 80, 6, 100, 3} OR
                 any other array that is in wave form

 Input:  arr[] = {20, 10, 8, 6, 4, 2}
 Output: arr[] = {20, 8, 10, 4, 6, 2} OR
                 {10, 8, 20, 2, 6, 4} OR
                 any other array that is in wave form

 Input:  arr[] = {2, 4, 6, 8, 10, 20}
 Output: arr[] = {4, 2, 8, 6, 20, 10} OR
                 any other array that is in wave form

 Input:  arr[] = {3, 6, 5, 10, 7, 20}
 Output: arr[] = {6, 3, 10, 5, 20, 7} OR
                 any other array that is in wave form
http://www.geeksforgeeks.org/sort-array-wave-form-2/

Find common elements in three sorted arrays

Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:
ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80

ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Output: 5, 5
http://www.geeksforgeeks.org/find-common-elements-three-sorted-arrays/


Find the first repeating element in an array of integers

Given an array of integers, find the first repeating element in it. We need to find the element that occurs more than once and whose index of first occurrence is smallest.

Examples:

Input:  arr[] = {10, 5, 3, 4, 3, 5, 6}
Output: 5 [5 is the first element that repeats]

Input:  arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10}
Output: 6 [6 is the first element that repeats]

http://www.geeksforgeeks.org/find-first-repeating-element-array-integers/

Find the closest pair from two sorted arrays

Find the closest pair from two sorted arrays
Given two sorted arrays and a number x, find the pair whose sum is closest to x and the pair has an element from each array.

We are given two arrays ar1[0…m-1] and ar2[0..n-1] and a number x, we need to find the pair ar1[i] + ar2[j] such that absolute value of (ar1[i] + ar2[j] – x) is minimum.

Example:

Input:  ar1[] = {1, 4, 5, 7};
        ar2[] = {10, 20, 30, 40};
        x = 32    
Output:  1 and 30

Input:  ar1[] = {1, 4, 5, 7};
        ar2[] = {10, 20, 30, 40};
        x = 50    
Output:  7 and 40
http://www.geeksforgeeks.org/given-two-sorted-arrays-number-x-find-pair-whose-sum-closest-x/


Find a pair with maximum product in array of Integers

Find a pair with maximum product in array of Integers
Given an array with both +ive and -ive integers, return a pair with highest product.

Examples:
Input: arr[] = {1, 4, 3, 6, 7, 0}   Output: {6,7}
Input: arr[] = {-1, -3, -4, 2, 0, -5} Output: {-4,-5}
http://www.geeksforgeeks.org/return-a-pair-with-maximum-product-in-array-of-integers/

Variation 1:
Find the largest pair sum in an unsorted array
Given an unsorted of distinct integers, find the largest pair sum in it. For example, the largest pair sum in {12, 34, 10, 6, 40} is 74.
http://www.geeksforgeeks.org/find-the-largest-pair-sum-in-an-unsorted-array/

Search an element in an array where difference between adjacent elements is 1

Given an array where difference between adjacent elements is 1, write an algorithm to search for an element in the array and return the position of the element (return the first occurrence).

Examples:
Let element to be searched be x
Input: arr[] = {8, 7, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3}
       x = 3
Output: Element 3 found at index 7
Input: arr[] =  {1, 2, 3, 4, 5, 4}
       x = 5
Output: Element 5 found at index 4

http://www.geeksforgeeks.org/search-an-element-in-an-array-where-difference-between-adjacent-elements-is-1/

Find the element that appears once in a sorted array

Given a sorted array in which all elements appear twice (one after one) and one element appears only once. Find that element in O(log n) complexity.

Example:

Input:   arr[] = {1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8}
Output:  4

Input:   arr[] = {1, 1, 3, 3, 4, 4, 5, 5, 7, 7, 8}
Output:  8

http://www.geeksforgeeks.org/find-the-element-that-appears-once-in-a-sorted-array/

Sort n numbers in range from 0 to n^2 – 1 in linear time

Given an array of numbers of size n. It is also given that the array elements are in range from 0 to n2 – 1. Sort the given array in linear time.

Examples:
Since there are 5 elements, the elements can be from 0 to 24.
Input: arr[] = {0, 23, 14, 12, 9}
Output: arr[] = {0, 9, 12, 14, 23}

Since there are 3 elements, the elements can be from 0 to 8.
Input: arr[] = {7, 0, 2}
Output: arr[] = {0, 2, 7}
http://www.geeksforgeeks.org/sort-n-numbers-range-0-n2-1-linear-time/

Find k closest elements to a given value

Given a sorted array arr[] and a value X, find the k closest elements to X in arr[].
Examples:

Input: K = 4, X = 35
arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56}
Output: 30 39 42 45

Method:
1) Start from the first element and search for the crossover point (The point before which elements are smaller than or equal to X and after which elements are greater). We will use Binary search for this.This step takes O(logn) time.
2) Once we find the crossover point, we can compare elements on both sides of crossover point to print k closest elements. This step takes O(k) time.
Time: For k elements it takes O(Logn + k) time.
http://www.geeksforgeeks.org/find-k-closest-elements-given-value/

Find Maximum number possible by doing at-most K swaps

Given a positive integer, find maximum integer possible by doing at-most K swap operations on its digits.

http://www.geeksforgeeks.org/find-maximum-number-possible-by-doing-at-most-k-swaps/

Pending


Matrix Transpose inplace

Inplace (Fixed space) M x N size matrix transpose
Given an M x N matrix, transpose the matrix without auxiliary memory.It is easy to transpose matrix using an auxiliary array. If the matrix is symmetric in size, we can transpose the matrix inplace by mirroring the 2D array across it’s diagonal (try yourself). How to transpose an arbitrary size matrix inplace? See the following matrix,

a b c       a d g j
d e f  ==>  b e h k
g h i       c f i l
j k l

http://www.geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/

Friday, August 5, 2016

Find frequency of each element in a limited range array in less than O(n) time

Find frequency of each element in a limited range array in less than O(n) time
Given an sorted array of positive integers, count number of occurrences for each element in the array. Assume all elements in the array are less than some constant M.

Do this without traversing the complete array. i.e. expected time complexity is less than O(n).

http://www.geeksforgeeks.org/find-frequency-of-each-element-in-a-limited-range-array-in-less-than-on-time/

Find Square and cubic root of a number

Given a number n, find the cube root of n.
Examples:

Input:  n = 3
Output: Cubic Root is 1.442250

Input: n = 8
Output: Cubic Root is 2.000000
http://www.geeksforgeeks.org/find-cubic-root-of-a-number/

Square root of an integer:
http://www.geeksforgeeks.org/square-root-of-an-integer/

Find paths from corner cell to middle cell in maze

Given a square maze containing positive numbers, find all paths from a corner cell (any of the extreme four corners) to the middle cell. We can move exactly n steps from a cell in 4 directions i.e. North, East, West and South where n is value of the cell,
We can move to mat[i+n][j], mat[i-n][j], mat[i][j+n], and mat[i][j-n] from a cell mat[i][j] where n is value of mat[i][j].
Example
Input:  9 x 9 maze
[ 3, 5, 4, 4, 7, 3, 4, 6, 3 ]
[ 6, 7, 5, 6, 6, 2, 6, 6, 2 ]
[ 3, 3, 4, 3, 2, 5, 4, 7, 2 ]
[ 6, 5, 5, 1, 2, 3, 6, 5, 6 ]
[ 3, 3, 4, 3, 0, 1, 4, 3, 4 ]
[ 3, 5, 4, 3, 2, 2, 3, 3, 5 ]
[ 3, 5, 4, 3, 2, 6, 4, 4, 3 ]
[ 3, 5, 1, 3, 7, 5, 3, 6, 4 ]
[ 6, 2, 4, 3, 4, 5, 4, 5, 1 ]

Output:
(0, 0) -> (0, 3) -> (0, 7) -> 
(6, 7) -> (6, 3) -> (3, 3) -> 
(3, 4) -> (5, 4) -> (5, 2) -> 
(1, 2) -> (1, 7) -> (7, 7) ->
(7, 1) -> (2, 1) -> (2, 4) -> 
(4, 4) -> MID
http://www.geeksforgeeks.org/find-paths-from-corner-cell-to-middle-cell-in-maze/

Convert matrix to 1d array

A n*n matrix is given which is containing elements in which each row alone is sorted. column is not sorted. We have to convert it into a single dimensional array which will hold all the elements of the array in a sorted manner.

Wednesday, August 3, 2016

Rearrange positive and negative numbers

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

For example, if the input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9], then the output should be [9, -7, 8, -3, 5, -1, 2, 4, 6]

Strategy: Partition in Quick Sort
http://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers-publish/

Variation 2:
Given an array of positive and negative numbers, arrange them such that all negative integers appear before all the positive integers in the array without using any additional data structure like hash table, arrays, etc. The order of appearance should be maintained.

Examples:

Input:  [12 11 -13 -5 6 -7 5 -3 -6]
Output: [-13 -5 -7 -3 -6 12 11 6 5]
http://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers/

Monday, August 1, 2016