CareerCup

The idea is to use Merge function of Merge sort.

Create an array arr3[] of size n1 + n2.
Simultaneously traverse arr1[] and arr2[].
Pick smaller of current elements in arr1[] and arr2[], copy this smaller element to next position in arr3[] and move ahead in arr3[] and the array whose element is picked.
If there are remaining elements in arr1[] or arr2[], copy them also in arr3[].

1. Get the sum of numbers which is total = n*(n+1)/2
2. Subtract all the numbers from sum and
you will get the missing number

Initialize:
max_so_far = 0
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

There exist four cases:

All three numbers are equal to 0. The number of ways = f(0)C3 (where pCq is the number of ways of choosing q numbers from p numbers).
One number is equal to 0, the other two are equal to some x > 0: f(0) * f(x)C2.
Two numbers are equal to some x>0, the third is 2*x: f(x)C2 * f(2 * x).
The three numbers are x, y and x + y, 0 < x, y: f(x) * f(y) * f(x + y).

Watch Redis system design | Distributed cache System design by Narendra L

Easiest solution would be to populate a min-heap of size k.

First, populate the heap with the first k elements.

Next, for each element in the stream - check if it is larger than the heap's head, and if it is - pop the current head, and insert the new element instead.

At any point during the stream - the heap contains the largest k elements.

This algorithm is O(nlogk), where n is the number of elements encountered so far in the stream.

Token bucket algorithm

1. In regular intervals tokens are thrown into the bucket. ƒ
2. The bucket has a maximum capacity. ƒ
3. If there is a ready packet, a token is removed from the bucket, and the packet is sent.
4. If there is no token in the bucket, the packet cannot be sent.

You can min heap, max heap for this.

Use TRIE
If the Trie store {“abc”, “abcd”, “aa”, “abbbaba”} and the User types in “ab” then he must be shown {“abc”, “abcd”, “abbbaba”}.

Interviewbit dot com
design-search-typeahead

1. Show Original content
2. Live Streaming

// Utility method to return sum of square of 
// digit of n 
int numSquareSum(int n) 
{ 
    int squareSum = 0; 
    while (n) 
    { 
        squareSum += (n % 10) * (n % 10); 
        n /= 10; 
    } 
    return squareSum; 
}


//    method return true if n is Happy number 
bool isHappynumber(int n) 
{ 
    int slow, fast; 
  
    //    initialize slow and fast by n 
    slow = fast = n; 
    do
    { 
        //    move slow number by one iteration 
        slow = numSquareSum(slow); 
  
        //    move fast number by two iteration 
        fast = numSquareSum(numSquareSum(fast)); 
  
    } 
    while (slow != fast); 
  
    //    if both number meet at 1, then return true 
    return (slow == 1); 
}

We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value. In the following code, findMissingPositive() function does this part. Note that in findMissingPositive, we have subtracted 1 from the values as indexes start from 0 in C.

/* Find the smallest positive missing number  
in an array that contains all positive integers */
int findMissingPositive(int arr[], int size)  
{  
    int i;  
      
    // Mark arr[i] as visited by making arr[arr[i] - 1] negative.  
    // Note that 1 is subtracted because index start  
    // from 0 and positive numbers start from 1  
    for(i = 0; i < size; i++)  
    {  
        if(abs(arr[i]) - 1 < size && arr[ abs(arr[i]) - 1] > 0)  
        arr[ abs(arr[i]) - 1] = -arr[ abs(arr[i]) - 1];  
    }  
      
    // Return the first index value at which is positive  
    for(i = 0; i < size; i++)  
        if (arr[i] > 0)  
            // 1 is added because indexes start from 0  
            return i+1;  
      
    return size+1;  
}

/* Function to find LCA of n1 and n2. The function assumes that both 
   n1 and n2 are present in BST */
struct node *lca(struct node* root, int n1, int n2) 
{ 
    if (root == NULL) return NULL; 
  
    // If both n1 and n2 are smaller than root, then LCA lies in left 
    if (root->data > n1 && root->data > n2) 
        return lca(root->left, n1, n2); 
  
    // If both n1 and n2 are greater than root, then LCA lies in right 
    if (root->data < n1 && root->data < n2) 
        return lca(root->right, n1, n2); 
  
    return root; 
}

Delta encoding

vector<int> times, hits; 

times.resize(300); 
hits.resize(300); 

/** Record a hit. 
@param timestamp - The current timestamp 
(in seconds granularity). */
void hit(int timestamp) 
{ 
	int idx = timestamp % 300; 
	if (times[idx] != timestamp) { 
		times[idx] = timestamp; 
		hits[idx] = 1; 
	} 
	else { 
		++hits[idx]; 
	} 
} 

// Time Complexity : O(1) 

/** Return the number of hits in the past 5 minutes. 
	@param timestamp - The current timestamp (in 
	seconds granularity). */
int getHits(int timestamp) 
{ 
	int res = 0; 
	for (int i = 0; i < 300; ++i) { 
		if (timestamp - times[i] < 300) { 
			res += hits[i]; 
		} 
	} 
	return res; 
} 
// Time Complexity : O(300) == O(1)

// C++ program to implement your own tail 
#include <bits/stdc++.h> 
using namespace std; 
  
#define SIZE 100 
  
// Utility function to sleep for n seconds 
void sleep(unsigned int n) 
{ 
    clock_t goal = n * 1000 + clock(); 
    while (goal > clock()); 
} 
  
// function to read last n lines from the file 
// at any point without reading the entire file 
void tail(FILE* in, int n) 
{ 
    int count = 0;  // To count '\n' characters 
  
    // unsigned long long pos (stores upto 2^64 – 1 
    // chars) assuming that long long int takes 8  
    // bytes 
    unsigned long long pos; 
    char str[2*SIZE]; 
  
    // Go to End of file 
    if (fseek(in, 0, SEEK_END)) 
        perror("fseek() failed"); 
    else
    { 
        // pos will contain no. of chars in 
        // input file. 
        pos = ftell(in); 
  
        // search for '\n' characters 
        while (pos) 
        { 
            // Move 'pos' away from end of file. 
            if (!fseek(in, --pos, SEEK_SET)) 
            { 
                if (fgetc(in) == '\n') 
  
                    // stop reading when n newlines 
                    // is found 
                    if (count++ == n) 
                        break; 
            } 
            else
                perror("fseek() failed"); 
        } 
  
        // print last n lines 
        printf("Printing last %d lines -\n", n); 
        while (fgets(str, sizeof(str), in)) 
            printf("%s", str); 
    } 
    printf("\n\n"); 
}

#include <iostream>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

// M x N matrix
#define M 10
#define N 10

// queue node used in BFS
struct Node
{
	// (x, y) represents matrix cell coordinates
	// dist represent its minimum distance from the source
	int x, y, dist;
};

// Below arrays details all 4 possible movements from a cell
int row[] = { -1, 0, 0, 1 };
int col[] = { 0, -1, 1, 0 };

// Function to check if it is possible to go to position (row, col)
// from current position. The function returns false if (row, col)
// is not a valid position or has value 0 or it is already visited
bool isValid(int mat[][N], bool visited[][N], int row, int col)
{
	return (row >= 0) && (row < M) && (col >= 0) && (col < N)
		&& mat[row][col] && !visited[row][col];
}

// Find Shortest Possible Route in a matrix mat from source
// cell (i, j) to destination cell (x, y)
void BFS(int mat[][N], int i, int j, int x, int y)
{
	// construct a matrix to keep track of visited cells
	bool visited[M][N];
	
	// initially all cells are unvisited
	memset(visited, false, sizeof visited);
	
	// create an empty queue
	queue<Node> q;

	// mark source cell as visited and enqueue the source node
	visited[i][j] = true;
	q.push({i, j, 0});

	// stores length of longest path from source to destination
	int min_dist = INT_MAX;

	// run till queue is not empty	
	while (!q.empty())
	{
		// pop front node from queue and process it
		Node node = q.front();
		q.pop();
		
		// (i, j) represents current cell and dist stores its
		// minimum distance from the source
		int i = node.x, j = node.y, dist = node.dist;

		// if destination is found, update min_dist and stop
		if (i == x && j == y)
		{
			min_dist = dist;
			break;
		}

		// check for all 4 possible movements from current cell
		// and enqueue each valid movement
		for (int k = 0; k < 4; k++)
		{
			// check if it is possible to go to position
			// (i + row[k], j + col[k]) from current position
			if (isValid(mat, visited, i + row[k], j + col[k]))
			{
				// mark next cell as visited and enqueue it
				visited[i + row[k]][j + col[k]] = true;
				q.push({ i + row[k], j + col[k], dist + 1 });
			}
		}
	}

	if (min_dist != INT_MAX)
		cout << "The shortest path from source to destination "
				"has length " << min_dist;
	else
		cout << "Destination can't be reached from given source";
}

// Shortest path in a Maze
int main()
{
	// input maze
	int mat[M][N] =
	{
		{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
		{ 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 },
		{ 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 },
		{ 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
		{ 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
		{ 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 },
		{ 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
		{ 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
		{ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
		{ 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 },
	};

	// Find shortest path from source (0, 0) to
	// destination (7, 5)
	BFS(mat, 0, 0, 7, 5);

	return 0;
}