rayasamharish
BAN USER- 0of 0 votes
AnswerWe need a functionality to block an user who makes more than 10 requests in last 5 minutes. You need to implement the following function.
- rayasamharish in United States
{{
boolean block_user(int user_id)
{
//TODO: return true in case u want to block user
}
}}| Report Duplicate | Flag | PURGE
anonymous SDE-2 Algorithm - 0of 0 votes
AnswersWedding Planner
- rayasamharish in India
Julia is a wedding planner who puts together phantasmagorical
extravaganza packages for new couples and their guests from 2 to
2,000. Hundreds of items are needed for each event, and Julia has a list
of supplier offers for all these items in various quantities. The price per
unit of every item is highly variable, depending on the supplier, the
number ordered, and the client/buyer who places the order. With her
years of record-keeping, Julia knows the best unit price she can get for
any item in any of a limited number of order sizes. Some items cost less
per unit when the number ordered goes up, some cost less per unit
when the number ordered goes down, and others have no rhyme or
reason for the unit prices available.
To price a new event, Julia consults her database of past offers.
If the amount needed for the new event is exactly the same as the
amount in a past offer, the unit price is also the same.
If she has a price for a higher amount and a price for a smaller
amount, her best guess will be that the unit cost will be linearly
interpolated from the unit costs for the closest lower amount and
the closest higher amount.
If the database only has one amount, then her best guess is that this
will be her unit cost.
And, if the amounts for which she has offers are all smaller or all
larger than the amount she needs, then she finds it most accurate to
linearly extrapolate from the closest two points to the amount
needed.
Finally, sometimes price offers lapse. When this happens, Julia, who
is not very database savvy, just overwrites the old unit price with a
zero or negative number. The amounts associated with zero or
negative unit price need to be disregarded.
automated so she can do it for hundreds of items with thousands of
individual prices.
Complete the function extrapolate , which takes a new amount n, an
array amount of old offer amounts in increasing order, and an array
ucost of corresponding unit prices. Your completed function should give
the expected unit price p for the new amount. The unit prices may
increase, decrease or oscillate, and may also contain invalid values like
0 or negative numbers. Your answer, as well as the unit prices in the
second array, should all be real numbers with exactly two decimal
places, representing dollars and cents. Use standard rounding to arrive
at two decimal places.
Input
A positive integer n, denoting the number if items for which a unit
price is needed.
1.
An array amount of l positive integers denoting the different order
amounts for which historical unit costs exist.
2.
An array ucost of l strings of real numbers denoting the different
unit costs for the corresponding amounts in array a.
3.
Output
A single positive number p with exactly two decimal places.
Note that the code for processing input and output is already present in
the system and designed to be compatible with the test case files used
to score your solution. There is no need to change only of the code other
than the body of the function extrapolate.
Constraints
1 ≤ l ≤ 100
2 ≤ n <= 2000
size(a) = l = size(u)
a(i) < a(j) ⇔ i < j
1
2
3
4
5
n = 25
a = {10, 25, 50, 100, 500 }
u = {"2.46","2.58", "2", "2.25", "3" }
Sample Output #1:
p = 2.58
Explanation #1:
The amount 25 is one of the values in the database. Its corresponding
unit price is 2.58.
Sample Input #2:
n = 2000
a = {10, 25, 50, 100, 500 }
u = {"27.32", "23.13", "21.25", "18.00", "15.50"}
Sample Output #2:
6.13
Explanation #2:
The item count 2,000 is not in the database. It is larger than any amount
in the database. The closest two price points to it are 15.5 for 500 and
18.00 for 100. Linear extrapolation from these two points means
reducing the price by 2.5 for every increase in amount of 400. There 3.75
jumps of 400 from 500 to 2,000, or 4.75 jumps of 400 from 100 to
2,000. The unit price for 2,000 is therefore 15.5 - 2.5 × 3.75 or 18 - 2.5 ×
4.75. Both expressions evaluate to 6.125. This rounds up to 6.13.| Report Duplicate | Flag | PURGE
Practo SDE1 - 0of 0 votes
AnswersStrong relation group
- rayasamharish in India
A group of social network experts are searching for an algorithm to find
"Strong relation groups" among people. A group of people form a strong
relation group if each of them know everyone else in the group. The
problem seemed very tough to them, so they want to attack a smaller
problem. If there are n people in a network and there are m pairs of
relationship among them, what will be the minimum size of the largest
"Strong relation group" in the network? If you know about graphs, you
can think of people as nodes and their relationship as edges.
Parameters:
Complete a function strongRelation which takes two integers n and m
as parameters.
Input Format:
First line contains a single integer denoting N.
Second line contains a single integer denoting M.
Return value:
Return the answer to the problem.
Constraints
1 <= T <= 100000
2 <= N <= 10000
1 <= M <= N*(N-1)/2
Sample Input:
3
2
Sample Output 1:
2
Sample input 2:
4
6
Sample Output 2:
4
Sample input 3:
5
7
Sample Output 3:
3
Explanation
1
2
3
4
5
"Strong relation group" cannot be smaller than 4.
For the third sample, it is easy to verify that any graph with 5 nodes and
7 edges will surely have a "Strong relation groups" of size 3 or more| Report Duplicate | Flag | PURGE
Practo SDE1 - 0of 0 votes
AnswersCan you predict the missing
- rayasamharish in India
grade?
Problem Statement
Introduction
The CBSE Class 12 examination, is taken by Indian high school students
at the end of K-12 school education. The scores or grades in this
examination form the basis of their entry to the College or University
system, for an undergraduate program. At the K-12 level, students
appear for examination in five subjects. These five subjects generally
include one language; three elective subjects oriented towards Science,
Commerce or Humanities; and any elective of their choice as a fifth
subject.
The Challenge
This challenge is based on real school data of the CBSE Class 12
examination conducted in the year 2013. You are given the grades
obtained by students with specific but popular combinations of subjects
(and all these students had opted for Mathematics). Their grades in four
subjects are known to you. However their grade in Mathematics (i.e, the
fifth subject) is hidden.
The records provided to you are the grades obtained by students who
had opted for the following combinations of subjects or courses and
obtained a passing grade in each subject. The individual subjects in the
data are:
English, Physics, Chemistry, Mathematics, Computer Science, Biology,
Physical Education, Economics, Accountancy and Business Studies.
The most dominant subject combinations, account for approximately
99% of the data are:
English, Physics, Chemistry, Mathematics, Physical Education
English, Physics, Chemistry, Mathematics, Economics
English, Physics, Chemistry, Mathematics, Biology
English, Economics, Accountancy, Mathematics, Business Studie
s
The grades of students in four subjects (other than Mathematics) are
provided to you. Can you predict what grade they had obtained in
Mathematics?
To help you build a prediction engine, we will provide you with a training
file, containing the grade points obtained by students with the above
subject combinations, in all five subjects.
Notes about the Grading System
The student is first assessed on a scale of 100. (S)He needs a score of at
least 33% to pass in the subject. Among those who pass:
Grade 1 is assigned to the top one-eighth of students who pas
s the course.
Grade 2 is assigned to the next one-eighth of students who pa
ss the course.
.....
Grade 8 is assigned to the last one-eighth of students who pa
ss the course.
If more than 1 student share the same score and lie in the margin, they
share the higher grade.
Input Format
The first line will be an integer N. N lines follow each line being a valid
JSON object. The following fields of raw data are given in json.
SerialNumber (Numeric): The identifier of the student record.
This is provided just for identification purposes and does n
ot have any direct use.
English (numeric) : The grade (between 1 and 8) obtained in E
nglish. This will always be present.
Three more numeric fields from among: Physics, Chemistry, Com
puterScience, Hindi, Biology, PhysicalEducation, Economics, A
1
2
3
4
5
The input for each record has the grade for all subjects opted by a
student, other than Mathematics which you have to predict as the
answer.
Constraints
1 <= N <= 10
The SerialNumber field will contain a unique numeric identifier such
that 1 <= SerialNumber <= 5 * 10 .
All other fields in the JSON fragment will represent the grades obtained
in four subjects and will be populated by numeric values between 1 and
8, both inclusive.
Output Format
For each student record that is given as a JSON object, containing the
grade obtained in four subjects, output the predicted grade in
Mathematics (this will be a numeral between 1 and 8, both inclusive) in
a newline.
Training File and Sample Tests
The training file with sample test data is available here.
The three files in this package are:
training.json
sample-test.in.json
sample-test.out.json
Training data as well as sample testcases have been provided in the
above file for offline training and to help you build your prediction
model. Feel free to include file data inside your code.
Sample Input
12345
{"SerialNumber":1,"English":1,"Physics":2,"Chemistry":3,"Comp
uterScience":2}
json_object
json_object
json_object
.
.
.
5
5
1
2
3
4
5
Sample Output
1
3
4
7
8
....
....
....
Explanation
It is predicted that first candidate obtained grade 1 in Mathematics, the
second candidate achieved grade 3 in Mathematics, the third candidate
achieved grade 4 in Mathematics and so on.
Scoring
For each of the N records in the input file, we will compute:
p = abs(Predicted Grade Point in Mathematics - Actual Grade Point in
Mathematics)
Where 'abs' indicates the Absolute Value or Magnitude. If p = 0 or 1 your
answer for that particular student record will be considered correct. i.e,
we allow a tolerance of one grade point away from the correct answer,
to take into consideration the marginal errors which might occur during
the testing or grading process.
Score = 100 * ((C-W)/N)
Where C = Number of Correct predictions, not more than one grade
point away from the actual grade point assigned.
W = Number of wrong (incorrect) predictions and
N = Total number of records in the input.
While the contest is in progress, only the score based on the sample
test case will be displayed to you. After the contest is completed, we
will revise the scores based on performance on a hidden test set only.
However, when you make submissions, you will be able to see whether
your program attains a positive score on both the sample and the
hidden test cases (to avoid a situation where unexpected errors occur
on the hidden test set at the end).| Report Duplicate | Flag | PURGE
Practo SDE1 - 0of 0 votes
AnswersNuclear Rods
- rayasamharish in India
A core meltdown has occurred at the Fubaru nuclear plant. There are
n nuclear fuel rods that are damaged and need to be removed using
specialized radiation-hardened robotic equipment
with solid-lead isolation chambers. Remote imaging has already
uniquely identified every damaged fuel rod and assigned it a number
between 1 and n. The imaging data also records which fuel rods were
fused to each other during the meltdown. Every recovery sortie by the
robot can pick up one set of nuclear fuel rods that are directly or
indirectly fused to each other.
The recovery costs per sortie are proportional to the square root of the
number of fused rods recovered. So the cost is K to recover K rods.
Isolation chambers are available for all positive integer costs (1, 2, 3, …).
An isolation chamber can be used multiple times, and each use will
incur the same cost. The robot can also recover a lower number of rods
than a chamber's capacity on a sortie.
Find the minimal cost to recover all the radioactive rods by completing
the given function.
Input
The first parameter integer n specifies the number of rods. The second
parameter pairs is an array of pairs of rods that are fused together. Each
item in the array contains exactly two integers, P and Q separated by a
space (" "), which means that the rod numbered P is fused to the rod
numbered Q. *Note - Each item in the array is a string which needs to be
parsed to P and Q
Output
2
Constraints
2 ≤ N ≤ 100,000
1 ≤ P, Q ≤ N
P ≠ Q
Sample Input
4
2
1 2
1 4
Sample Output
3
Explanation
Rods #1, #2, #4 are connected to each other (2-1-4) so they are in a
single group of 3. The sortie to recover them will cost 2 (with isolation
chamber capacity 2 = 4). Rod #3 is not fused to any other, so it can be
recovered at a cost of 1 (with isolation chamber capacity 1 = 1).| Report Duplicate | Flag | PURGE
Practo SDE1 - 0of 0 votes
AnswersStringChain
- rayasamharish in India
You are given a library with n words (w[0], w[1], ..., w[n - 1]). You
choose a word from it, and in each step, remove one letter from this
word only if doing so yields a another word in the library. What is the
longest possible chain of these removal steps?
Constraints:
1 ≤ n ≤ 50000
1 ≤ the length of each string in w ≤ 50
Each string composed of lowercase ascii letters only.
Input Format:
Complete the function "longest_chain" which contains an array of
strings "w" as its argument.
Output Format:
Return a single integer that represents the length of the longest chain of
character removals possible.
Sample Input #00:
6
a
b
ba
bca
bda
bdca
Sample Output #00:
4| Report Duplicate | Flag | PURGE
Practo SDE1 - 0of 0 votes
AnswersGiven encoded version of string like 'a2b2cd3' - It means string preceeding number is repeated digit number of times.'a2b2cd2' = 'aabbcdcd'
- rayasamharish in India
Input
You are provided a template in which you have to implement one function exploreString. The declaration of exploreString looks like
int exploreString ( string A, int k )
A is the compressed string.
k is an integer. find character at kth position.| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm
You cannot take as char array and iterate because 12 will be considered as 1 and 2 and you will push 1 and 2 into the stack instead of pushing 12 :)
- rayasamharish October 09, 2015Assuming that each edge has weight of 6
- rayasamharish October 04, 2015import java.util.*;
public class Graph {
int V;
int E;
int directed = 0; //undirected
ArrayList<NavigableSet<Integer>> adj;
public void init(int V)
{
this.V = V;
adj = new ArrayList<NavigableSet<Integer>>();
for(int i = 0; i < V; i++)
adj.add(i, new TreeSet<Integer>());
}
public void addEdge(int u, int v)
{
adj.get(u).add(v);
if(directed == 0)
adj.get(v).add(u);
}
public Set<Integer> adj(int u)
{
return adj.get(u);
}
}
public class BreadthFirstSearch {
static Graph g;
static int[] dist;
public static void bfs(int s)
{
Queue<Integer> q = new LinkedList<>();
q.add(s);
dist[s] = 0;
while(q.size() > 0)
{
int t = q.poll();
// System.out.println("polled " + t);
for(int v : g.adj(t))
{
if(dist[v] == -1)
{
q.add(v);
dist[v] = dist[t] + 1;
// System.out.println("setting dist of " + v + " as " + dist[v]);
}
}
}
}
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0)
{
g = new Graph();
int n = sc.nextInt();
int m = sc.nextInt();
g.init(n);
dist = new int[n];
Arrays.fill(dist, -1);
for(int i= 0; i < m; i++)
g.addEdge(sc.nextInt()-1, sc.nextInt()-1);
int s = sc.nextInt();
bfs(s-1);
for(int i = 0; i < n; i++)
{
if(i != s-1)
{
System.out.print((dist[i] == -1 ? -1 : (dist[i] * 6)) + " ");
}
}
System.out.println();
}
}
}
int a = 1;
char *c;
c = &a;
if(*c == 1)
{
printf("LITTLE ENDIAN");
}
else
{
printf("BIG ENDIAN");
}
It returns number of set bits in a number. While counting you are also erasing that set bit.
- rayasamharish September 24, 2015Hey,
what is the complexity of the solution. Because you are doing x & (x-1) it needs to do a bitwise AND on n bits so you are performing that operation k times so the total complexity is O(k*n) where k = No of set bits
Isn't that worst than plain one time scan of bits and counting number of 1's
public static int[] MergeSort(int[] A)
{
int[] temp = A.clone();
auxMergeSort(A,temp,0,A.length-1);
return temp;
}
public static void auxMergeSort(int[] A,int[] temp,int l,int h)
{
if(h -l == 0)
return;
if(h-l == 1)
{
if(A[h] < A[l])
{
int t = temp[h];
temp[h] = temp[l];
temp[l] = t;
A[h] = temp[h];
A[l] = temp[l];
return;
}
return;
}
if(l < h)
{
int m = (l + ((h - l) >> 1));
auxMergeSort(A, temp, l, m);
auxMergeSort(A, temp, m+1, h);
merge(A, temp,l,m,h);
}
}
public static void merge(int[] A, int[] temp,int l,int m,int h)
{
//A[l..m] is sorted and A[m+1..h] is sorted
int k = l;
int i = l, j = m +1;
while(i <= m && j <= h)
{
if(A[i] < A[j])
{
temp[k++] = A[i++];
}
else
{
temp[k++] = A[j++];
}
}
//Copy remaining elements
while(i <= m)
{
temp[k++] = A[i++];
}
System.out.println(" " + l + " , " + m + ", " + h);
System.out.println(Arrays.toString(temp));
//Dont need to copy second half
//Copy back the original array to reflect sorted order
for(int q = l ; q <= h; q++)
A[q] = temp[q];
}
It takes 60 mins to fill the jar since bacteria doubles it's volume every 1min so to fill half the jar it takes 59 minutes
- rayasamharish January 19, 2015Solution complexity is O(n)
{{
package hashtable;
import java.lang.*;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;
public class HashTableDemo {
public static void main(String[] args) {
Hashtable<Integer,Integer> ht = new Hashtable<Integer,Integer>();
int arr[] = {6,10,6,21,2,33,12,7,7,8,9,0};
int max_len = 0;
for(int i =0; i < arr.length; ++i)
{
if(!ht.containsKey(arr[i]))
{
ht.put(arr[i], i);
}
if(ht.containsKey(arr[i] - 1))
{
int start_index = ht.get(arr[i] - 1);
if(Math.abs(start_index - i) > max_len)
max_len = Math.abs(start_index - i);
System.out.println("Start : " + start_index + "End :" + i);
System.out.println("Max length : " + max_len);
continue;
}
if(ht.containsKey(arr[i] + 1))
{
int start_index = ht.get(arr[i] + 1);
if(Math.abs(start_index - i) > max_len)
max_len = Math.abs(start_index - i);
System.out.println("Start : " + start_index + "End :" + i);
System.out.println("Max length : " + max_len);
continue;
}
else
{
}
}
System.out.println("Max length : " + max_len);
}
}
}}
{{
This solution complexity is O(n).
package arrays;
public class arrangement {
public static void main(String[] args) {
int a_arr[] = {30,40,10,20,70,50,60,100,80,90};
int b_arr[] = {3,4,1,2,7,5,6,10,8,9};
int n = 0;
int curr = a_arr[0];
int loc = b_arr[0];
int temp_curr,temp_loc;
while(n < a_arr.length)
{ n++;
System.out.println("Iteration :" + n);
System.out.println("Curr :" + curr);
System.out.println("Location :" + loc);
temp_curr = a_arr[loc-1];
temp_loc = b_arr[loc-1];
if(temp_curr == curr && temp_loc == loc)
{
n--;
curr = a_arr[loc];
loc = b_arr[loc];
continue;
}
a_arr[loc-1] = curr;
b_arr[loc-1] = loc;
curr = temp_curr;
loc = temp_loc;
}
System.out.println("After completion");
for(int i = 0; i < a_arr.length;i++)
{
System.out.println("i : " + i);
System.out.println("a[i] : " + a_arr[i]);
System.out.println("b[i] : " + b_arr[i]);
}
}
}
}}
While doing infix to postfix conversion. If we get a ")" we pop the stack until we get a "(" . Now we see that we immediately encounter a "(" for a right parenthesis it indicates that it is a duplicate parenthesis.
- rayasamharish October 10, 2015