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/

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:

http://algorithms.tutorialhorizon.com/print-all-diagonals-of-a-given-matrix/

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/

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.

http://www.geeksforgeeks.org/sort-numbers-stored-on-different-machines/

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 2^ndset. Again heapsort these 1000 numbers (10 from first set and 990 from 2^nd set), take 10 max element and mix those with 980 elements of 3^rd 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.

http://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

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/