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

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/

Wednesday, July 27, 2016

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 pi, i=1,2,…,n, write an algo­rithm to find the max­i­mum rev­enue rn 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

Find The Longest Sequence Of Prefix Shared By All The Words In A String

Write an algo­rithm to find The Longest Sequence Of Pre­fix Shared By All The Words In A String. This prob­lem is bit tricky, it looks dif­fi­cult but actu­ally it is sim­ple problem.

http://algorithms.tutorialhorizon.com/find-the-longest-sequence-of-prefix-shared-by-all-the-words-in-a-string/


C++ specific Concepts

static:
http://www.cprogramming.com/tutorial/statickeyword.html
http://quiz.geeksforgeeks.org/c-static-keyword-question-1/
http://quiz.geeksforgeeks.org/c-plus-plus/static-keyword/

friend:
http://www.cprogramming.com/tutorial/friends.html
http://www.tutorialspoint.com/cplusplus/cpp_friend_functions.htm
http://quiz.geeksforgeeks.org/c-plus-plus/friend-function-and-class/

Const:
http://www.studytonight.com/cpp/const-keyword.php

namespace:
http://www.cplusplus.com/doc/tutorial/namespaces/

virtual function:
http://stackoverflow.com/questions/2391679/why-do-we-need-virtual-functions-in-c?rq=1
http://www.studytonight.com/cpp/virtual-functions.php
http://www.programcreek.com/2011/01/a-simple-example-of-c-virtual-keyword/
http://quiz.geeksforgeeks.org/c-plus-plus/virtual-functions/

Copy Constructor:
http://www.studytonight.com/cpp/copy-constructor-in-cpp.php

Reference types in C++ vs Pointers in C:
http://www.tutorialspoint.com/cplusplus/cpp_references.htm
http://www.cprogramming.com/tutorial/references.html

Interface vs Abstract Class:
http://www.brushupmyskill.com/2016/01/differences-between-interface-and.html

Advanced C++ Topics

Smart pointers:
http://www.geeksforgeeks.org/smart-pointers-cpp/
https://dsalgointerview.wordpress.com/2014/03/11/smart-pointers/

Unique Pointers:
https://dsalgointerview.wordpress.com/2014/03/11/unique_ptr/

Move semantics and rvalue references in C++11:
http://www.cprogramming.com/c++11/rvalue-references-and-move-semantics-in-c++11.html
http://blog.smartbear.com/c-plus-plus/c11-tutorial-introducing-the-move-constructor-and-the-move-assignment-operator/

Use of Lambdas:
http://stackoverflow.com/questions/7627098/what-is-a-lambda-expression-in-c11

C++/STL Containers:
http://www.cplusplus.com/reference/stl/

C++ 11 Features:
http://www.codeproject.com/Articles/570638/Ten-Cplusplus-Features-Every-Cplusplus-Developer
http://blog.smartbear.com/c-plus-plus/the-biggest-changes-in-c11-and-why-you-should-care/

Tuesday, July 26, 2016

Print All Diagonals of a given matrix

Given two dimen­sional matrix, write an algo­rithm to print all the diag­o­nals of matrix.
Exam­ple:



Find number of Employees Under every Employee

Given a dictionary that contains mapping of employee and his manager as a number of (employee, manager) pairs like below.
{ "A", "C" },
{ "B", "C" },
{ "C", "F" },
{ "D", "E" },
{ "E", "F" },
{ "F", "F" } 

In this example C is manager of A, 
C is also manager of B, F is manager 
of C and so on.
http://www.geeksforgeeks.org/find-number-of-employees-under-every-manager/

Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example,
123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"

http://www.programcreek.com/2014/05/leetcode-integer-to-english-words-java/

Find a peak element in a Given Array

In this arti­cle we will dis­cuss an algo­rithm to Find a peak ele­ment in a Given Array. We will see the recur­sion tech­niques to solve this problem.
Peak Ele­ment: peak ele­ment is the ele­ment which is greater than or equal to both of its neighbors.
http://www.programcreek.com/2014/02/leetcode-find-peak-element/
http://algorithms.tutorialhorizon.com/find-a-peak-element-in-a-given-array/

http://www.geeksforgeeks.org/find-a-peak-in-a-given-array/

Finding minimum vertex cover size of a graph using binary search

Find the size of the minimum size vertex cover, that is, cardinality of a vertex cover with minimum cardinality, for an undirected connected graph with V vertices and m edges.
Examples:
Input: V = 6, E = 6
       6
             /
     /
    1 -----5
   /|\
  3 | \
  \ |  \
    2   4
Output: Minimum vertex cover size = 2
Consider subset of vertices {1, 2}, every edge 
in above graph is either incident on vertex 1 
or 2. Hence the minimum vertex cover = {1, 2}, 
the size of which is 2.

Input: V = 6, E = 7
     2 ---- 4 ---- 6
    /|      |
  1  |      |
    \|      |
     3 ---- 5
Output: Minimum vertex cover size = 3
Consider subset of vertices {2, 3, 4}, every
edge in above graph is either incident on 
vertex 2, 3 or 4. Hence the minimum size of
a vertex cover can be 3.
http://www.geeksforgeeks.org/finding-minimum-vertex-cover-graph-using-binary-search/

Sunday, July 24, 2016

Efficient Data Stricure for findMin(), findMax(), deleteMin(), deleteMax(), insert, delete

Design a Data Structure for the following operations. The data structure should be efficient enough to accommodate the operations according to their frequency.
1) findMin() : Returns the minimum item.
   Frequency: Most frequent

2) findMax() : Returns the maximum item.
    Frequency: Most frequent

3) deleteMin() : Delete the minimum item.
    Frequency: Moderate frequent 

4) deleteMax() : Delete the maximum item.
    Frequency: Moderate frequent 

5) Insert() : Inserts an item.
    Frequency: Least frequent

6) Delete() : Deletes an item.
    Frequency: Least frequent
http://www.geeksforgeeks.org/a-data-structure-question/

Sort numbers stored on different machines

Given N machines. Each machine contains some numbers in sorted form. But the amount of numbers, each machine has is not fixed. Output the numbers from all the machine in sorted non-decreasing form.
Example:
       Machine M1 contains 3 numbers: {30, 40, 50}
       Machine M2 contains 2 numbers: {35, 45} 
       Machine M3 contains 5 numbers: {10, 60, 70, 80, 100}
       
       Output: {10, 30, 35, 40, 45, 50, 60, 70, 80, 100}
Representation of stream of numbers on each machine is considered as linked list. A Min Heap can be used to print all numbers in sorted order.


10 maximum integers from 1 million integers

You Have File of Containing 1 Million Integers You need To Find 10
Maximum Integer Out of Them.How You Will Do That. What is Time &
space Complexity of Algorithm that you will use then optimize the
solution..

Constraints- U can't Store Whole File in memory at one time.

Strategy:
Using Min Heap:

Use a min-heap of 10 elements.Initialize the heap with first 10 elements in O(10) [constant] time.For each of the next element,check whether it is greater than root of min heap,if it is,replace that element by the next element and heapify the heap again in O(log10) [constant] time.At last extract all the 10 elements one by one in O(log10) constant time each.so space complexity O(1) time complexity O(N).

Using Max Heap:

A solution for this problem may be to divide the data in some sets of 1000 elements (let’s say 1000), make a heap of them, and take 10 elements from each heap one by one. Finally heap sort all the sets of 10 elements and take top 10 among those. But the problem in this approach is where to store 10 elements from each heap. That may require a large amount of memory as we have billions of numbers.
Reuse top 20 elements from earlier heap in subsequent elements can solve this problem. I meant to take first block of 1000 elements and subsequent blocks of 990 elements each. Initially heapsort first set of 1000 numbers, took max 10 elements and mix them with 990 elements of 2ndset. Again heapsort these 1000 numbers (10 from first set and 990 from 2nd set), take 10 max element and mix those with 980 elements of 3rd set. Repeat the same exercise till last set of 990 (or less) elements and take max 20 elements from final heap. Those 10 elements will be your answer.
Complexity: O(n) = n/1000*(complexity of heapsort 1000 elements)
Since complexity of heap sorting 1000 elements will be a constant so the O(n) = N i.e. linear complexity 

Connect n ropes with minimum cost

There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.
For example if we are given 4 ropes of lengths 4, 3, 2 and 6. We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6 and 5.
2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.
3) Finally connect the two ropes and all ropes have connected.
Total cost for connecting all ropes is 5 + 9 + 15 = 29. This is the optimized cost for connecting ropes. Other ways of connecting ropes would always have same or more cost. For example, if we connect 4 and 6 first (we get three strings of 3, 2 and 10), then connect 10 and 3 (we get two strings of 13 and 2). Finally we connect 13 and 2. Total cost in this way is 10 + 13 + 15 = 38.


Pending

Pending

Count zeros in a row wise and column wise sorted matrix

Given a N x N binary matrix (elements in matrix can be either 1 or 0) where each row and column of the matrix is sorted in ascending order, count number of 0s present in it.
Expected time complexity is O(N).
Examples:
Input: 
[0, 0, 0, 0, 1]
[0, 0, 0, 1, 1]
[0, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
Output: 8
Input: 
[0, 0]
[0, 0]
Output: 4
Input: 
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
Output: 0
http://www.geeksforgeeks.org/count-zeros-in-a-row-wise-and-column-wise-sorted-matrix/


Range Addition

Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

http://www.programcreek.com/2014/07/leetcode-range-addition-java/

Advanced misc data structure

K Dimensional Tree

Segment Tree

B Tree

Splay Tree

Meeting Rooms

Saturday, July 23, 2016

Clone a Binary Tree with Random Pointers

Given a Binary Tree where every node has following structure.
struct node {  
    int key; 
    struct node *left,*right,*random;
} 
The random pointer points to any random node of the binary tree and can even point to NULL, clone the given binary tree.


Length of the largest subarray with contiguous elements

Largest subarray with contiguous elements
http://www.geeksforgeeks.org/length-largest-subarray-contiguous-elements-set-1/
http://www.geeksforgeeks.org/length-largest-subarray-contiguous-elements-set-2/

Longest Consecutive Sequence:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, given [100, 4, 200, 1, 3, 2], the longest consecutive elements sequence should be [1, 2, 3, 4]. Its length is 4.
http://www.programcreek.com/2013/01/leetcode-longest-consecutive-sequence-java/

How to check if two given sets are disjoint?

Given two sets represented by two arrays, how to check if the given two sets are disjoint or not? It may be assumed that the given arrays have no duplicates.
Difficulty Level: Rookie
Input: set1[] = {12, 34, 11, 9, 3}
       set2[] = {2, 1, 3, 5}
Output: Not Disjoint
3 is common in two sets.

Input: set1[] = {12, 34, 11, 9, 3}
       set2[] = {7, 2, 1, 5}
Output: Yes, Disjoint
There is no common element in two sets.

http://www.geeksforgeeks.org/check-two-given-sets-disjoint/

An array contains duplicate elements within k distance from each other or not

Pending


Misc System Design Questions

Question 1:
Given a hard drive with one terabyte of data, arranged in 2^32 key/value pairs, where the keys and values each have lengths of 128 bytes, you need to design, build, and deploy (by yourself) a system that lets you look up the value for a given key, over the internet, at a peak rate of 5000 lookups per second. The data never changes. Let’s design that system.
Question 2:
Given a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls. 
(i.e. have many large <string (url) -> int (visits)> maps, calculate implicitly <string (url) -> int (sum of visits among all distributed maps), and get the top ten in the combined map) The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed)
Question 3:



Design a workflow system

Tuesday, July 19, 2016

Design a Text Editor

Design limit-request-per-second

Design a function to return the top k requests during past time interval

Storage of Strings in C

How readonly & dynamically allocated strings are stored in C
In C, a string can be referred either using a character pointer or as a character array.
Strings as character arrays
char str[4] = "GfG"; /*One extra for string terminator*/
/*    OR    */
char str[4] = {‘G’, ‘f’, ‘G’, '\0'}; /* '\0' is string terminator */
When strings are declared as character arrays, they are stored like other types of arrays in C. For example, if str[] is an auto variable then string is stored in stack segment, if it’s a global or static variable then stored in data segment, etc.
Strings using character pointers
Using character pointer strings can be stored in two ways:
1) Read only string in a shared segment.
When string value is directly assigned to a pointer, it’s stored in a read only block(generally in data segment) that is shared among functions
char *str  =  "GfG";
In the above line “GfG” is stored in a shared read only location, but pointer str is stored in a read-write memory. You can change str to point something else but cannot change value at present str. So this kind of string should only be used when we don’t want to modify string at a later stage in program.
And also the above should be declared as
const char *p = "Hello";So the compiler will throw an error if you try to modify it.
2) Dynamically allocated in heap segment.
Strings are stored like other dynamically allocated things in C and can be shared among functions.
char *str;
int size = 4; /*one extra for ‘\0’*/
str = (char *)malloc(sizeof(char)*size);
*(str+0) = 'G';
*(str+1) = 'f';
*(str+2) = 'G';
*(str+3) = '\0';
Example 1 (Try to modify string) 
The below program may crash (gives segmentation fault error) because the line *(str+1) = ‘n’ tries to write a read only memory.
int main()
{
 char *str;
 str = "GfG";     /* Stored in read only part of data segment */
 *(str+1) = 'n'; /* Problem:  trying to modify read only memory */
 getchar();
 return 0;
}
str is a pointer stored on the stack. It gets initialized to point to the literal string "abc". That literal string is going to be stored in the data section of your compiled executable and gets loaded into memory when your program is loaded. That section of memory is read-only, so when you try and modify the data pointed to by str, you get an access violation.
char* str = malloc(sizeof(char) * 4);
strcpy(str, "abc");
Here, str is the same stack pointer.This time, it is initialized to point to a 4-character block of memory on the heap that you can both read and write. At first that block of memory is uninitialized and can contain anything. strcpy reads the block of read-only memory where "abc" is stored, and copies it into the block of read-write memory that str points to. Note that setting str[3] = '\0' is redundant, since strcpy does that already.
As an aside, if you are working in visual studio, use strcpy_s instead to make sure you don't overwrite your buffer if the string being copied is longer than you expected.
Here str is now an array allocated on the stack. The compiler will sized it exactly fit the string literal used to initialize it (including the NULL terminator). The stack memory is read-write so you can modify the values in the array however you want.
Below program works perfectly fine as str[] is stored in writable stack segment.
int main()
{
 char str[] = "GfG"/* Stored in stack segment like other auto variables */
 *(str+1) = 'n';   /* No problem: String is now GnG */
 getchar();
 return 0;
}
Below program also works perfectly fine as data at str is stored in writable heap segment.
int main()
{
  int size = 4;
  /* Stored in heap segment like other dynamically allocated things */
  char *str = (char *)malloc(sizeof(char)*size);
  *(str+0) = 'G';
  *(str+1) = 'f';
  *(str+2) = 'G';
  *(str+3) = '\0';
  *(str+1) = 'n'/* No problem: String is now GnG */
   getchar();
   return 0;
}
Example 2 (Try to return string from a function) The below program works perfectly fine as the string is stored in a shared segment and data stored remains there even after return of getString()
char *getString()
{
  char *str = "GfG"; /* Stored in read only part of shared segment */
  /* No problem: remains at address str after getString() returns*/
  return str;
}    
int main()
{
  printf("%s", getString());
  getchar();
  return 0;
}
The below program alse works perfectly fine as the string is stored in heap segment and data stored in heap segment persists even after return of getString()
char *getString()
{
  int size = 4;
  char *str = (char *)malloc(sizeof(char)*size); /*Stored in heap segment*/
  *(str+0) = 'G';
  *(str+1) = 'f';
  *(str+2) = 'G';
  *(str+3) = '\0'
  /* No problem: string remains at str after getString() returns */
  return str;
}
int main()
{
  printf("%s", getString());
  getchar();
  return 0;
}
But, the below program may print some garbage data as string is stored in stack frame of function getString() and data may not be there after getString() returns.
char *getString()
{
  char str[] = "GfG"; /* Stored in stack segment */
  /* Problem: string may not be present after getSting() returns */
  return str;
}
int main()
{
  printf("%s", getString());
  getchar();
  return 0;
}