Design a Coffee Shop

OO design for a coffee shop

http://massivetechinterview.blogspot.in/2015/07/thought-works-oo-design-for-coffee-shop.html

Design a Tic Tac Toe Game

Write me a function for the game of tic-tac-toe in C

Useful Links:
http://www.codercaste.com/2011/01/26/how-to-code-a-tic-tac-toe-game-in-c-including-artificial-intelligence-opponent/
http://stackoverflow.com/questions/6572194/review-my-design-tic-tac-toe-game-using-oo-methodology

Efficient data structure for storing and calculating the total resistance

Given a Circuit (with resistors), we need to calculate the total resistance. Input will be like AB-5ohm, BC-6ohm, BC-10ohm, BC-20 ohm, CD-5 ohm. BC has been repeated twice implying they are in series. "Write a program  by implementing efficient data structure for storing and calculating the total resistance

Design a Chess Game

Object oriented design for chess game

Object Oriented design represents the real world objects in code.

https://xmruibi.gitbooks.io/interview-preparation-notes/content/OOD/DesignExamples/ChessGame.html

http://massivetechinterview.blogspot.in/2015/07/design-chess-game-using-oo-principles.html

Sort the Result Array

We have an integer array that is sorted in ascending order. We also have 3 ints A, B and C. We need to apply A*x*x + B*x + C for each element x in the array and return the corresponding sorted array.

Example: Input array = -1 0 1 2 3 4 and A = -1, B = 2, C = -1
Result of applying the formula to each element = -4 -1 0 -1 -4 -9
So expected result = -9 -4 -4 -1 -1 0 (sorted)

Time complexity :o(n), no extra space

Method: Parabolic Property
The equation given is parabolic. So the result of applying it to a sorted array will result in an array that will have a maximum/minimum with the sub-arrays to its left and right sorted.

In your case the maximum is 0 and the sub array to its left [-4 -1] is sorted in ascending order and the sub-array to its right [-1 -4 -9] is sorted in descending order.
All you need to do is merge these sorted arrays which is linear in time.

So the algorithm is:

Apply equation on each element
Find maximum/minimum
Merge subarrays

Useful Link:
http://stackoverflow.com/questions/4551599/sorting-result-array

Own vesions of String library functions

Write your own implementations for following string library functions

1.strstr()
2.strcpy()
3.strcmp()
4.substr()
5.strdup()
6.strlen()
7.strcat()
8.strchr()
9.toUpper() & isUpper()

Set-2
1.strncmp()
2.strncat()
3.strncpy()
4.strrchr()

strcpy()

Method 1:
char *mystrcpy(char *dst, const char *src)
{
  char *ptr;
  ptr = dst;
  while(*dst++=*src++);
  return(ptr);
}
Method 2:
char *my_strcpy(char dest[], const char source[])
{
  int i = 0;
  while (source[i] != '\0')
  {
    dest[i] = source[i];
    i++;
  }
  dest[i] = '\0';
  return(dest);
}
NOTE:
1.The strcpy function copies src, including the terminating null character, to the location specified by dst. No overflow checking is performed when strings are copied or appended. The behavior of strcpy is undefined if the source and destination strings overlap. It returns the destination string. No return value is reserved to indicate an error.

2.Note that the prototype of strcpy as per the C standards is
 char *strcpy(char *dst, const char *src);
 Notice the const for the source, which signifies that the function must not change the source string in anyway!.
strncpy()

char * strncpy ( char * destination, const char * source, size_t num );

Copy characters from string

Copies the first num characters of source to destination. If the end of the source C string (which is signaled by a null-character) is found before num characters have been copied, destination is padded with zeros until a total of num characters have been written to it.

No null-character is implicitly appended to the end of destination, so destination will only be null-terminated if the length of the C string in source is less than num.
char *(strncpy)(char *s1, const char *s2, size_t  n)
 {
     char *dst = s1;
     const char *src = s2;
     while (n > 0) {
         n--;
         if ((*dst++ = *src++) == '\0') {
             memset(dst, '\0', n);
             break;
         }
     }
     return s1;
 }

substr():

void mySubstr(char *dest, char *src, int position, int length)
{
  while(length > 0)
  {
    *dest = *(src+position);
    dest++;
    src++;
    length--;
  }
}
Alternative:
char *substr(const char *pstr, int start, int numchars)
{
char *pnew = (char *)malloc(numchars+1);
strncpy(pnew, pstr + start, numchars);
pnew[numchars] = '\0';
return pnew;
}

Note:
substr() is used to copy a substring starting from position upto length

strdup():

char *mystrdup(char *s)
{
    char *result = (char*)malloc(strlen(s) + 1);
    if (result == (char*)0)
             {return (char*)0;}
    strcpy(result, s);
    return result;
}
strcmp()

int (strcmp)(const char *s1, const char *s2)
 {
     unsigned char uc1, uc2;
     /* Move s1 and s2 to the first differing characters 
        in each string, or the ends of the strings if they
        are identical.  */
     while (*s1 != '\0' && *s1 == *s2) {
         s1++;
         s2++;
     }
     /* Compare the characters as unsigned char and
        return the difference.  */
     uc1 = (*(unsigned char *) s1);
     uc2 = (*(unsigned char *) s2);
     return ((uc1 < uc2) ? -1 : (uc1 > uc2));
 }

Note:

strcmp(str1,str2) returns a -ve number if str1 is alphabetically less than str2, 0 if both are equal and +ve if str1 is alphabetically above str2.The prototype of strcmp() is

 int strcmp( const char *string1, const char *string2 );

strncmp()
int (strncmp)(const char *s1, const char *s2, size_t  n)
 {
     unsigned char uc1, uc2;
     if (n == 0)
         return 0;
     while (n-- > 0 && *s1 == *s2)
    {
         if (n == 0 || *s1 == '\0')
             return 0;
         s1++;
         s2++;
     }
     uc1 = (*(unsigned char *) s1);
     uc2 = (*(unsigned char *) s2);
     return ((uc1 < uc2) ? -1 : (uc1 > uc2));
 }

strlen():

Method 1:
int my_strlen(char *string)
{
  int length;
  for (length = 0; *string != '\0', string++)
  {
    length++;
  }
  return(length);
}
Method 2: Pointer difference
int my_strlen(char *s)
{
  char *p=s;
  while(*p!='\0')
    p++;
  return(p-s);
}
Note:
The prototype of the strlen() function is
size_t strlen(const char *string);

strrchr()

const char * strchr ( const char * str, int character );
      char * strchr (       char * str, int character );

Locate first occurrence of character in string
Returns a pointer to the first occurrence of character in the C string str.
The terminating null-character is considered part of the C string. Therefore, it can also be located to retrieve a pointer to the end of a string.

char *(strrchr)(const char *s, int c)
 {
     const char *last = NULL;
         if (c == '\0')
         return strchr(s, c);
     while ((s = strchr(s, c)) != NULL) {
         last = s;
         s++;
     }
     return (char *) last;
 }

strcat():

char *myStrcat(char *s, const char *t)
{
    char *p = s;
    if (s == NULL || t == NULL)
        return s;   /* we need not have to do anything */
    while (*s)
        s++;
    while (*s++ = *t++);
    return p;
}
strncat()

 char *(strncat)(char *s1, const char *s2, size_t n)
 {
     char *s = s1;
     while (*s != '\0')
         s++;
     while (n != 0 && (*s = *s2++) != '\0') {
         n--;
         s++;
     }
     if (*s != '\0')
         *s = '\0';
     return s1;
 }

toUpper():
int toUpper(int ch)
{
    if(ch>='a' && c<='z')
        return('A' + ch - 'a');
    else
        return(ch);
}

isUpper():
int isUpper(int ch)
{
    if(ch>='A' && ch <='Z')
       return(1); //Yes, its upper!
    else
       return(0); // No, its lower!
}
Note:
Another way to do this conversion is to maintain a correspondance between the upper and lower case alphabets. The program below does that. This frees us from the fact that these alphabets have a corresponding integer values.

#include <string.h>
#define UPPER   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define LOWER   "abcdefghijklmnopqrstuvwxyz"

int toUpper(int c)
{
    const char *upper;
    const char *const lower = LOWER;
       
    // Get the position of the lower case alphabet in the LOWER string using the strchr() function ..
    upper = ( ((CHAR_MAX >= c)&&(c > '\0')) ? strchr(lower, c) : NULL);

      // Now return the corresponding alphabet at that position in the UPPER string ..
    return((upper != NULL)?UPPER[upper - lower] : c);
}

Useful Links:
http://en.wikibooks.org/wiki/C_Programming/Strings

Design Hit Counter

 If you are building a website, how do you count the number of visitors for the past 1 minute?

http://blog.gainlo.co/index.php/2016/09/12/dropbox-interview-design-hit-counter/

Group Shifted Strings

Given an array of strings (all lowercase letters), the task is to group them in such a way that all strings in a group are shifted versions of each other. Two string S and T are called shifted if,

S.length = T.length
and
S[i] = T[i] + K for
1 <= i <= S.length  for a constant integer K
For example strings {acd, dfg, wyz, yab, mop} are shifted versions of each other.

http://www.geeksforgeeks.org/group-shifted-string/

Count maximum points on same line

Given N point on a 2D plane as pair of (x, y) co-ordinates, we need to find maximum number of point which lie on the same line.

Examples:

Input : points[] = {-1, 1}, {0, 0}, {1, 1},
                    {2, 2}, {3, 3}, {3, 4}
Output : 4
Then maximum number of point which lie on same
line are 4, those point are {0, 0}, {1, 1}, {2, 2},
{3, 3}

http://www.geeksforgeeks.org/count-maximum-points-on-same-line/

Assembly Line Scheduling

A car factory has two assembly lines, each with n stations. A station is denoted by Si,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by ai,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station Si,j, it will continue to station Si,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time ti,j. Each assembly line takes an entry time ei and exit time xi which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

http://www.geeksforgeeks.org/dynamic-programming-set-34-assembly-line-scheduling/

Happy Numbers

What is an happy number can be shown in the following example:

19 is a happy number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

http://www.programcreek.com/2014/04/leetcode-happy-number-java/
http://getprogramcode.com/2013/12/java-program-to-check-for-a-happy-number/

Caterpillars and Uneaten Leaves

K caterpillars are eating their way through N leaves, each caterpillar falls from leaf to leaf in a unique sequence, all caterpillars start at a twig at position 0 and falls onto the leaves at position between 1 and N. Each caterpillar j has as associated jump number Aj. A caterpillar with jump number j eats leaves at positions that are multiple of j. It will proceed in the order j, 2j, 3j…. till it reaches the end of the leaves and it stops and build its cocoon.

Given a set A of K elements K<-15, N<=10^9, we need to determine the number of uneaten leaves.

Input:

N= No of uneaten leaves.

K= No. of caterpillars

A = Array of integer jump numbers

Output: The integer nu. Of uneaten leaves.

Sample Input:10, 3, 2, 4, 5

Output: 4

Explanation:

[2, 4, 5] is a j member jump numbers, all leaves which are multiple of 2, 4, and 5 are eaten, leaves 1,3,7,9 are left, and thus the no. 4

http://codereview.stackexchange.com/questions/95145/caterpillar-uneaten-leaves
http://stackoverflow.com/questions/27248327/caterpillars-and-leaves-can-we-do-better-than-onc
http://qa.geeksforgeeks.org/219/uneaten-leaves-problem

Design a logging System

Design Redis

http://massivetechinterview.blogspot.in/2016/03/redis-architecture.html

Design Google Maps, Calender, Big Table, File System, Spanner

http://massivetechinterview.blogspot.in/2015/10/google-file-system.html
http://massivetechinterview.blogspot.in/2015/10/google-map-architecture.html
http://massivetechinterview.blogspot.in/2015/10/google-calendar-architecture.html
http://massivetechinterview.blogspot.in/2015/10/google-bigtable-architecture.html
http://massivetechinterview.blogspot.in/2015/10/google-spanner-architecture.html

Pending

Design a generic automated test suite

Design a generic automated test suite.

Active and Inactive cells after k Days

Given a binary array of size n where n > 3. A true (or 1) value in the array means active and false (or 0) means inactive. Given a number k, the task is to find count of active and inactive cells after k days. After every day, status of i’th cell becomes inactive if its left and right cells have same value, i.e., either both are 0 or both are 1.
Since there are no cells before leftmost and after rightmost cells, the value cells before leftmost and after rightmost cells is always considered as 0 (or inactive).

http://www.geeksforgeeks.org/active-inactive-cells-k-days/

Maximize value of (arr[i] – i) – (arr[j] – j) in an array

Given an array, arr[] find the maximum value of (arr[i] – i) – (arr[j] – j) where i is not equal to j. Where i and j vary from 0 to n-1 and n is size of input array arr[].

http://www.geeksforgeeks.org/maximize-value-of-arri-i-arrj-j-in-an-array/

Behavioural Questions

Behavioral Questions

1. Things u learn in 3 years of experience which makes u different from fresher guy?
2. Project description
3. Discussion about my project details and challenging task

Miscellaneous Interview Questions

1. Draw the recursion stack of any program and find in what order one function is called and stored in the stack and in what order it is returned back to its callee function. And to prove what is the space complexity through that recursion stack.

2.

Design a Server to keep track of shares and clients

Design an object oriented design system for an server that keeps track of shares and clients can ask the server to get the most up to date information about value of the shares.

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

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

Shared Web Hosting
https://en.wikipedia.org/wiki/Shared_web_hosting_service

Virtual Private Service
https://en.wikipedia.org/wiki/Virtual_private_server

Scalability: Veritcal and Horizontal Scaling
https://en.wikipedia.org/wiki/Scalability
http://www.thoughtsoncloud.com/2014/04/explain-vertical-horizontal-scaling-cloud/

Load Balancing
https://en.wikipedia.org/wiki/Load_balancing_(computing)

Data Redundancy:
https://en.wikipedia.org/wiki/RAID

DNS
https://en.wikipedia.org/wiki/Name_server

Sessions & Cookies
https://en.wikipedia.org/wiki/Session_(computer_science)
https://en.wikipedia.org/wiki/HTTP_cookie

All about Memory Leak

How do you make sure that an API does not leak memory ?
https://www.careercup.com/question?id=16359670

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/

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

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/

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/

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/

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

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

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/

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.

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/

Cloud Computing

http://dotnetanalyst.com/FAQs/Index

Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges for consecutive numbers.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

http://www.programcreek.com/2014/07/leetcode-summary-ranges-java/

Print shortest path to print a string on screen

Given a screen containing alphabets from A-Z, we can go from one character to another characters using a remote. The remote contains left, right, top and bottom keys.
http://www.geeksforgeeks.org/print-shortest-path-print-string-screen/

Design a Mine Sweeper Game [CCIB]

http://www.geeksforgeeks.org/cpp-implementation-minesweeper-game/

Concurrent Merge Sort in Shared Memory

Given a number ‘n’ and a n numbers, sort the numbers using Concurrent Merge Sort. (Hint: Try to use shmget, shmat system calls).
http://www.geeksforgeeks.org/concurrent-merge-sort-in-shared-memory/

Array Resources for Interviews

I will update useful links in internet to study questions related to Arrays.

http://tech-queries.blogspot.in/search/label/Arrays%2FStrings
http://www.geeksforgeeks.org/archives/category/c-arrays
http://k2code.blogspot.in/search/label/arrays

Group multiple occurrence of array elements ordered by first occurrence

Given an unsorted array with repetitions, the task is to group multiple occurrence of individual elements. The grouping should happen in a way that the order of first occurrences of all elements is maintained.

Examples:

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

Input: arr[] = {4, 6, 9, 2, 3, 4, 9, 6, 10, 4}
Output:        {4, 4, 4, 6, 6, 9, 9, 2, 3, 10}

http://www.geeksforgeeks.org/group-multiple-occurrence-of-array-elements-ordered-by-first-occurrence/

Design a Version Control System like Git

http://stackoverflow.com/questions/1452890/git-design-decision-on-storing-content-rather-than-differences

http://stackoverflow.com/questions/10783263/how-revision-control-system-restores-revision

Length of shortest chain to reach a target word

Given a dictionary, and two words ‘start’ and ‘target’ (both of same length). Find length of the smallest chain from ‘start’ to ‘target’ if it exists, such that adjacent words in the chain only differ by one character and each word in the chain is a valid word i.e., it exists in the dictionary. It may be assumed that the ‘target’ word exists in dictionary and length of all dictionary words is same.

Example:

Input:  Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}
             start = TOON
             target = PLEA
Output: 7
Explanation: TOON - POON - POIN - POIE - PLIE - PLEE - PLEA

http://www.geeksforgeeks.org/length-of-shortest-chain-to-reach-a-target-word/

Print all Jumping Numbers smaller than or equal to a given value

A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1.
All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.

Given a positive number x, print all Jumping Numbers smaller than or equal to x. The numbers can be printed in any order.

Example:

Input: x = 20
Output:  0 1 2 3 4 5 6 7 8 9 10 12

Input: x = 105
Output:  0 1 2 3 4 5 6 7 8 9 10 12
         21 23 32 34 43 45 54 56 65
         67 76 78 87 89 98 101

Note: Order of output doesn't matter, 
i,e., numbers can be printed in any order

http://www.geeksforgeeks.org/print-all-jumping-numbers-smaller-than-or-equal-to-a-given-value/

Minimize Cash Flow among a given set of friends who have borrowed money from each other

Given a number of friends who have to give or take some amount of money from one another. Design an algorithm by which the total cash flow among all the friends is minimized.
http://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/

Find the minimum cost to reach destination using a train

There are N stations on route of a train. The train goes from station 0 to N-1. The ticket cost for all pair of stations (i, j) is given where j is greater than i. Find the minimum cost to reach the destination.

Consider the following example:

Input: 
cost[N][N] = { {0, 15, 80, 90},
              {INF, 0, 40, 50},
              {INF, INF, 0, 70},
              {INF, INF, INF, 0}
             };
There are 4 stations and cost[i][j] indicates cost to reach j 
from i. The entries where j < i are meaningless.

Output:
The minimum cost is 65
The minimum cost can be obtained by first going to station 1 
from 0. Then from station 1 to station 3.

http://www.geeksforgeeks.org/find-the-minimum-cost-to-reach-a-destination-where-every-station-is-connected-in-one-direction/

Backtracking — Search a Word In a Matrix

 Given a 2D matrix of char­ac­ters. Check whether the word exist in the matrix or not. If it exists then print its path. All move­ments are allowed (right, left, up, down and diagonally).

http://algorithms.tutorialhorizon.com/backtracking-search-a-word-in-a-matrix/

Backtracking — Knight’s Tour Problem

A knight’s tour is a sequence of moves of a knight on a chess­board such that the knight vis­its every square only once. If the knight ends on a square that is one knight’s move from the begin­ning square (so that it could tour the board again imme­di­ately, fol­low­ing the same path), the tour is closed, oth­er­wise it is open. (Source : http://en.wikipedia.org/wiki/Knight%27s_tour)

http://algorithms.tutorialhorizon.com/backtracking-knights-tour-problem/

Backtracking — N Queens Problem

Backtracking — N Queens Problem

In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks how to place 8 queens on an ordi­nary chess board so that none of them can hit any other in one move.(Source: http://www.math.utah.edu/~alfeld/queens/queens.html)

Here we are solv­ing it for N queens in NxN chess board.

http://algorithms.tutorialhorizon.com/backtracking-n-queens-problem/

Backtracking — SUDOKU Solver

The objec­tive is to fill a 9×9 grid with dig­its so that each col­umn, each row, and each of the nine 3×3 sub-grids that com­pose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) con­tains all of the dig­its from 1 to 9. The puz­zle set­ter pro­vides a par­tially com­pleted grid, which for a well-posed puz­zle has a unique solu­tion. (Source: Wiki — http://en.wikipedia.org/wiki/Sudoku)

http://algorithms.tutorialhorizon.com/backtracking-sudoku-solver/

Highway Billboard Problem

Sup­pose you’re man­ag­ing con­struc­tion of bill­boards on the Rocky & Bull­win­kle Memo­r­ial High­way, a heav­ily trav­eled stretch of road that runs west-east for M miles. The pos­si­ble sites for bill­boards are given by num­bers x1 < x2 < · · · < xn, each in the inter­val [0, M], spec­i­fy­ing their posi­tion in miles mea­sured from the west­ern end of the road. If you place a bill­board at posi­tion xi , you receive a rev­enue of ri > 0.

Reg­u­la­tions imposed by the High­way Depart­ment require that no two bill­boards be within five miles or less of each other. You’d like to place bill­boards at a sub­set of the sites so as to max­i­mize your total rev­enue, sub­ject to this restriction.

http://algorithms.tutorialhorizon.com/dynamic-programming-highway-billboard-problem/

Rod Cutting Problem

Given a rod of length n inches and a table of prices p_i, i=1,2,…,n, write an algo­rithm to find the max­i­mum rev­enue r_n obtain­able by cut­ting up the rod and sell­ing the pieces.
http://algorithms.tutorialhorizon.com/dynamic-programming-rod-cutting-problem/
http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

C++ Interview Topics/Links

Overall:
http://www.geeksforgeeks.org/c-plus-plus/

Questions:
http://www.cppforschool.com/tutorials.html 
http://java-questions.com/oops_interview_questions.html
http://java-success.blogspot.in/p/core-java-q.html