Nits
BAN USER 0of 0 votes
AnswersWhat data structure will you use to suggest friends in FB
 Nits in India Report Duplicate  Flag  PURGE
RazorPay Software Development Manager  0of 0 votes
AnswerDesign a hit counter which counts the number of hits received in the past 5 minutes.
 Nits in India Report Duplicate  Flag  PURGE
Adobe Computer Scientist  0of 0 votes
AnswersYou are given a list of n1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.
 Nits in India Report Duplicate  Flag  PURGE
Brocade Software Developer  0of 0 votes
AnswersFind a subarray with a give sum
 Nits in India Report Duplicate  Flag  PURGE
Amazon SDE3
Easiest solution would be to populate a minheap 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.
// 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);
}

Nits
August 17, 2019 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;
}

Nits
August 16, 2019 /* 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;
}

Nits
August 16, 2019 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)

Nits
August 16, 2019 // 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");
}

Nits
August 15, 2019 #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;
}

Nits
August 15, 2019 Open Chat in New Window
Watch Redis system design  Distributed cache System design by Narendra L
 Nits August 29, 2019