## Wednesday, November 9, 2016

### Design a Tic Tac Toe Game

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

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

**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**## Sunday, November 6, 2016

### 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

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

## Thursday, November 3, 2016

### 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

## Wednesday, November 2, 2016

### 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()

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);

}

1.The strcpy function copies src, including the terminating null character, to the location specified by dst.

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

Copies the first

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;

}

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

char *mystrdup(char *s)

{

char *result = (char*)malloc(strlen(s) + 1);

if (result == (char*)0)

{return (char*)0;}

strcpy(result, s);

return result;

}

strcmp(str1,str2) returns a -ve number if str1 is alphabetically less than str2,

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

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));

}

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);

Returns a pointer to the first occurrence of

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 *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;

}

int toUpper(int ch)

{

if(ch>='a' && c<='z')

return('A' + ch - 'a');

else

return(ch);

}

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

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()**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**

*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():**{

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 *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:**

**0 if both are equal**and +ve if str1 is alphabetically above str2.The**prototype**of strcmp() isint 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():**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 *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

## Sunday, October 16, 2016

### 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/

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

## Wednesday, October 12, 2016

### 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/

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/

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/

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

## Thursday, October 6, 2016

### 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/

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

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

## Tuesday, September 27, 2016

### 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

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

## Wednesday, September 14, 2016

### 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/

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[].

## Tuesday, September 13, 2016

### Behavioural Questions

Behavioral Questions

- Things u learn in 3 years of experience which makes u different from fresher guy?
- Project description
- 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.

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.

## 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

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

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

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

## Wednesday, August 17, 2016

### All about Memory Leak

How do you make sure that an API does not leak memory ?

https://www.careercup.com/question?id=16359670

https://www.careercup.com/question?id=16359670

## 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/

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## 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/

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/

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/

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/

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/

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/

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/

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/

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/

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/

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/

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 that*arr[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-array-arrj-becomes-arri-j/

## 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

The longest increasing path is

`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

Strategy:`(0,2)`

is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.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 RAnd 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/

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/

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/

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/

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/

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/

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/

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/

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).

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/

__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/

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/

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

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/

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/

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

### 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/

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/

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/

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 [http://www.geeksforgeeks.org/find-paths-from-corner-cell-to-middle-cell-in-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

### 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/

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

### 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/

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/

## Sunday, July 31, 2016

### 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/

http://www.geeksforgeeks.org/print-shortest-path-print-string-screen/

### 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/

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

http://tech-queries.blogspot.in/search/label/Arrays%2FStrings

http://www.geeksforgeeks.org/archives/category/c-arrays

http://k2code.blogspot.in/search/label/arrays

## Saturday, July 30, 2016

### 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}

## Friday, July 29, 2016

### Design a Version Control System like Git

### 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.

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/

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.

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

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 characters. Check whether the word exist in the matrix or not. If it exists then print its path. All movements are allowed (right, left, up, down and diagonally).

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

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 chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open. (Source : http://en.wikipedia.org/wiki/Knight%27s_tour)

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

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, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen’s problem asks how to place 8 queens on an ordinary 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 solving it for N queens in NxN chess board.

### Backtracking — SUDOKU Solver

The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a unique solution. (Source: Wiki — http://en.wikipedia.org/wiki/Sudoku)

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

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

## Wednesday, July 27, 2016

### Highway Billboard Problem

Suppose you’re managing construction of billboards on the Rocky & Bullwinkle Memorial Highway, a heavily traveled stretch of road that runs west-east for M miles. The possible sites for billboards are given by numbers x1 < x2 < · · · < xn, each in the interval [0, M], specifying their position in miles measured from the western end of the road. If you place a billboard at position xi , you receive a revenue of ri > 0.

Regulations imposed by the Highway Department require that no two billboards be within five miles or less of each other. You’d like to place billboards at a subset of the sites so as to maximize your total revenue, subject to this restriction.

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

Regulations imposed by the Highway Department require that no two billboards be within five miles or less of each other. You’d like to place billboards at a subset of the sites so as to maximize your total revenue, subject 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

http://algorithms.tutorialhorizon.com/dynamic-programming-rod-cutting-problem/

http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

_{i}, i=1,2,…,n, write an algorithm to find the maximum revenue r_{n}obtainable by cutting up the rod and selling the pieces.http://algorithms.tutorialhorizon.com/dynamic-programming-rod-cutting-problem/

http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

Subscribe to:
Posts (Atom)