saurabh
BAN USER- 0of 0 votes
AnswersGiven two strings Y and Z , return True if y beats z or z beats y .
- saurabh in India
Beating Criteria : for i in [1,N] y[i]>=z[i] , if this condition is true for any of permutations of y for any of the permutations of z .| Report Duplicate | Flag | PURGE
Directi Software Engineer Algorithm - 0of 0 votes
AnswerAmazon receives marketplace sellers (clients) requests in XML format. Sometimes, the clients software makes mistakes and omit certain nodes starting or ending tags (or both). Amazon, being the earth most customer friendly company, still wants to honor the client’s request by converting this malformed XML to well-formed XML. Given a malformed XML as string, you have to return the structure that the input XML follows .
- saurabh in India
Following are the assumptions you can make:
1. XML follows the structure below :-
a. Any parent node ( say with tag A ) can have multiple children but only of the same tag ( say B ).
b. A tag can occur only at the exactly one level in the XML Structure ( say tag B can only occur at the level 2)
c. There is single leaf node tag.
2. For a given XML input, it will honor only a unique XML structure.
3. All node tag names are unique.
4. There is a single root node which is always present in the input XML.
Input Format:
Only line in the input contains a malformed string.
Output Format:
Print in a single line, space separated list of tags in the structure. Tags that are more closer to root has to be printed before the ones that are farther.
Sample Input:
<A><B></B><D><C></C></D><B><D></D></B></A>
Sample Output:
A B D C
Explanation:
The actual XML structure is root with tag 'A' . Root has two children each having tag 'B'. Each of the node with tag 'B' has one child with tag 'D' and finally each of the node with tag 'D' has one children with tag 'C'. The well-formed string for this case is "<A><B><D><C></C></D></B><B><D><C></C></D></B><B><D><C></C></D></B></A>" and in the sample input some of the tags were missing.
Constraints: The number of nodes is not more than 10,000. Size of tag string is less than 20.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersAs a follow up to the Problem "XML Structure", given the input malformed XML String and the XML structure that it needs to follow, you need to find the well-formed XML String. You can assume that malformed XML string does follow the given structure and there is a unique well-formed XML String corresponding to it.
- saurabh in India
Input Format:
First line of input contains the structure of XML. Next line of input contains the malformed string.
Output Format:
Print in a single line the well-formed XML string.
Sample Input:
A B D C
<A><B></B><D><C></C></D><B><D></D></B></A>
Sample Output:
<A><B><D><C></C></D></B><B><D><C></C></D></B><B><D><C></C></D></B></A>
Note: You can attempt this problem without attempting XML Structure problem first, however you should read the problem XML Structure for proper background in order to solve this.
Constraints: There will be no more than 10,000 nodes.| Report Duplicate | Flag | PURGE
- 0of 0 votes
AnswersYou received a transmission containing an expression of single digit positive integers (say: 9 *(5 – 4) * 3). However, during transmission all operators and brackets were lost and you only received 9 5 4 3. Given the array of digits, you have to calculate the least positive integer value of the expression that could NOT have been received by you. The binary operators possible are *, +, -, / and brackets possible are ( and ). Note that / is an integer division i.e. 9/5 = 1.
- saurabh in India
Example: You have received 6,6,4,4. The minimum positive integer that could NOT have been formed is 18. This is because integers less than 18 are formed as below.
1 = 6 /6 + 4-4
2 = 6/6 + 4/4
3 = 6 +( 6/4) -4
4 = (6+6+4) / 4
……..
18 cannot be formed
Input Format:
FIrst line contains an integer N, the number of digits in the array.
Then follow N lines each containing a digit.
Output Format:
Print a single integer which is the required answer.
Sample Input:
4
6
6
4
4
Sample Output:
18
Constraints:
1 <= N <= 10
Note: You need not worry about the precedence of operators as you can impose necessary precedence using brackets at appropriate places.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answers3-way-mergesort : Suppose instead of dividing in half at each step of the mergesort, you divide into thirds, sort each third, and finally combine all of them using a three way merge. What is the overall running time of this algorithm ? (Hint - Note that the merge step can still be implemented in O(n) time.)
- saurabh in India
n
nlog(n)
n^2(log(n))
n((log(n))^2)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answersk-way-mergesort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine in which you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, and so on until you merge in the final (kth) input array. What is the time taken for this strategy, as a function of k and n ? (Optional: can you think of a faster way to do the k-way merge procedure ?)
- saurabh in India
θ(n^2(k))
θ(n(k^2))
θ(nk)
θ(nlog(k))| Report Duplicate | Flag | PURGE
- 0of 0 votes
AnswersAssume again two (positive) functions f and g such that f(n)=O(g(n)). Is 2f(n)=O(2g(n)) ? (Multiple answers may be correct.)
- saurabh in India
1.Never
2.Sometimes
3.Yes if f(n)≤g(n) for all sufficiently large n
4.Always| Report Duplicate | Flag | PURGE
Amazon Software Development Manager - 0of 0 votes
AnswersYou are given functions f and g such that f(n)=O(g(n)). Is f(n)*log2(f(n)c)=O(g(n)*log2(g(n))) ? (Here c is some constant >0. You can assume that f and g are always bigger than 1.
- saurabh in India
1.Depends on the choice of f and g
2.True
3.False
4.Depends on choice of c| Report Duplicate | Flag | PURGE
Software Engineer / Developer - 0of 0 votes
AnswersGiven a program on fork() system call.
- saurabh in India
#include <stdio.h>
#include <unistd.h>
int main()
{
fork();
fork() && fork() || fork();
fork();
printf("forked\n");
return 0;
}
How many processes will be spawned after executing the above program?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Unix - 0of 0 votes
AnswersThe file(Text file) contains all the 100,000 integers between 1 and 100,000 (including both) in some random order( no integer is repeated).
- saurabh in India
Your task is to find the number of inversions in the file given (every row has a single integer between 1 and 100,000). Assume your array is from 1 to 100,000 and ith row of the file gives you the ith entry of the array
as an example:
text file(test.txt):
2342
1233
8278
.
.
.
.
.
.
.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersWhich Data structure is used in window search...??
- saurabh in India| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
Answersx*y = a + b*lcm(x,y) + c*gcd(x,y)
- saurabh in India
It's easy: you are to write a program which for given a, b and c finds the number of pairs of positive integers (x, y) satisfying this equation.
Here * stands for multiplication, gcd(x,y) stands for the greatest common divisor of x and y, while lcm(x,y) stands for the least common multiple of x and y.
Input
The first line of the input file contains one integer T -- the number of test cases (no more than 10). Each of the next T lines contains exactly three space-separated integers a, b and c (0 ≤ a, b, c ≤ 106).
Output
For each test case output one line containing the sought number of solutions to the equation. If there is an infinite number of solutions, output -1 instead.
Example
Input:
3
2 1 1
160 0 90
300 7 5
Output:
2
8
4
Explanation:
In the first test case, the only pairs are (2,4) and (4,2).| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersHave you ever thought, when given an undirected graph in some problem, that it would be easier to solve it if the graph's edges were actually its vertices and the graph's vertices were its edges? This problem is right about this -- unfortunately, not about bears and bees (but if you want, you may think of vertices as of bears and of edges as of bees (or even vice versa)).
- saurabh in India
Suppose you're given an undirected graph G0 with N vertices and M edges. Let's perform a simple transformation on graph G0 to obtain graph G1 with M vertices so that each vertex of G1 corresponds to a unique edge of G0 and a pair of vertices in G1 is connected by a single edge if and only if the corresponding edges of G0 share a common vertex. Similarly, let's perform a simple transformation on graph G1 to obtain graph G2, and let's perform a simple transformation on graph G2 to obtain graph G3.
All you have to do is to output the number of vertices and edges in G3.
Input
The first line of the input file contains one integer T -- the number of test cases (no more than 10). Each test case is described by a line containing two integers N and M (1 ≤ N, M ≤ 1000) followed by M lines, each containing two integers between 1 and N, inclusive, separated by a single space and describing an edge of graph G0. It's guaranteed that each edge connects two distinct vertices and each pair of vertices is directly connected by at most one edge.
Output
For each test case output just one line containing two integers -- the number of vertices and edges in G3.
Example
Input:
2
3 3
1 2
1 3
2 3
4 4
1 2
1 3
2 3
3 4
Output:
3 3
8 18
Explanation:
In the first test case the given graph is a "triangle". It's easy to see that a simple transformation on a triangle results in the same triangle (as it contains three pairwise connected vertices and three pairwise "connected" edges).| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswerSeveral days ago Chef decided to register at one of the programming sites. For registering he was asked to choose a nickname and a password. There was no problem with choosing a nickname ("Chef" is his favorite nickname), but choosing a password in a secure way seemed to be a real problem for Chef. Therefore, he decided to write a program which would generate the password of length N consisting of small Latin letters a..z. Then Chef successfully registered at the site and saved the password in a file (as it was too hard to remember).
- saurabh in India
Today Chef decided to visit the site once again. He entered his nickname, copied the password from the file... "Authentication failed!" was the answer. Trying to understand the reason of this, he noticed that the password in his file had length N+K instead of N! Sure enough of the source of the problem, Chef went straight to his young brother.
And Chef was right, it was his brother who had inserted K random small Latin letters at some random positions (possibly at the beginning or at the end) of the password. Chef's brother didn't remember what exactly changes he had made at all, but he promised that he had done nothing besides inserting letters.
As there is no other way to recover the password, Chef is now starting to remove every possible combination of K letters from the password trying to enter (when Chef obtains the same password as one of the previously entered passwords, he doesn't try to enter using this password again). Now the question is: what is the number of times Chef will receive "Authentication failed!" as the answer before successful entering in the worst case? As the answer might be quite large, output its remainder of division by 1009419529.
Input
The first line of the input file contains one integer T -- the number of test cases (no more than 10). Each test case is described by a line containing two integers N and K (1 ≤ N ≤ 10000, 1 ≤ K ≤ 100) separated by a single space, followed by a line containing a string of length N+K consisting of small Latin letters a..z.
Output
For each test case output just one line containing the required number modulo 1009419529.
Example
Input:
3
2 1
aaa
3 1
abcd
4 2
ababab
Output:
0
3
10
Explanation:
In the first test case, the password is definitely "aa". In the second test case, it can be "abc", "abd", "acd" or "bcd", so in the worst case Chef will guess the correct option from the fourth attempt, thus making 3 unsuccessful attempts| Report Duplicate | Flag | PURGE
- 0of 0 votes
Answershow do you perform string compression:
- saurabh in India
i/p-->str="aabbbcdddd"
o/p-->str="a2b3cd4"| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answersmy prog is not working.....(compression of sring)
- saurabh in India
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cout<<"Enter String:";
cin>>s;
int count=0;
int i=0,j=-1;
if(s[i]!='\0')
{ if(s[i]!=s[i+1])
{
s[count++]=s[i];
s[count++]=i-j;
j=i;
}
i++;
}
s[count]='\0';
cout<<s;
getchar();
}| Report Duplicate | Flag | PURGE
Algorithm
- 1 Answer Run length encoding(any1 suggest me what is wrong in my code)
#include<stdio.h>
- saurabh February 13, 2012
#include<conio.h>
int c1=1;
void runlen(char *str)
{
int i=0,j=0;
while(str[i])
{ if(str[i]!=str[i+1])
{ str[j++]=str[i];
str[j++]=c1;
c1=1;
}
else
c1++;
}
str[j]='\0';
}
int main()
{
char str1[30];
printf("ENTER String:");
gets(str1);
runlen(str1);
printf("\n%s",str1);
getchar();
}| Flag | PURGE
def numSquares(n):
if n < 2:
return n
lst = []
i = 1
while i * i <= n:
lst.append( i * i )
i += 1
print(lst)
cnt = 0
toCheck = {n}
while toCheck:
cnt += 1
temp = set()
for x in toCheck:
for y in lst:
if x == y:
return cnt
if x < y:
break
temp.add(x-y)
toCheck = temp
print(toCheck)
return cnt
numSquares(12)
import re
import operator
class SortHotelsOnWordFrequency:
def compressValuesOfMap(self, hotel_map_with_count):
compressed_hotel_map = {}
for hotel_id, hotel_map in hotel_map_with_count.items():
total_freq = 0
for word, freq in hotel_map.items():
total_freq += freq
compressed_hotel_map[hotel_id] = total_freq
return compressed_hotel_map
def getHotelsWithCount(self, hotel_map, words):
hotel_map_with_count = {}
for hotel_id, reviews in hotel_map.items():
map_word_count = {}
for word in words:
for review in reviews:
for r in review:
if r.lower() == word:
if word in map_word_count:
map_word_count[word]+=1
else:
map_word_count[word]=1
hotel_map_with_count[hotel_id] = map_word_count
return hotel_map_with_count
def parseFile(self, input_file):
file = open(input_file, "r")
lines = file.readlines()
words = lines[0].strip("\n").split(" ")
m = int(lines[1])
hotel_map = {}
for i in range(2,m*2+2,2):
hotel_id = int(lines[i])
reviews = re.sub(r'[^\w\s]','',lines[i+1].strip("\n")).split(" ")
if hotel_id in hotel_map:
hotel_map[hotel_id].append(reviews)
else:
hotel_map[hotel_id] = []
hotel_map[hotel_id].append(reviews)
hotel_map_with_count = self.getHotelsWithCount(hotel_map, words)
compressed_hotel_map = self.compressValuesOfMap(hotel_map_with_count)
sorted_hotels_tuples = sorted(compressed_hotel_map.items(), key=operator.itemgetter(1), reverse=True)
sorted_hotels = []
for hotel_tuple in sorted_hotels_tuples:
sorted_hotels.append(hotel_tuple[0])
return sorted_hotels
sort_hotels = SortHotelsOnWordFrequency()
print(sort_hotels.parseFile("reviews.txt"))
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node *left;
struct node *right;
};
typedef struct node Tree;
Tree *new_node(int data)
{
Tree *node = (Tree *)malloc(sizeof(Tree));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
void make_tree(Tree **root,int data) // constructing tree
{
if(*root==NULL)
{
*root = new_node(data);
}
else
{
if(data>(*root)->data)
{
make_tree(&(*root)->right,data);
}
else
{
make_tree(&(*root)->left,data);
}
}
}
int arr[5]; // storing inorder traversal into global array so it can reflect in our main
void inorder(Tree *root)
{
static int i=0;
if(root==NULL)
return;
inorder(root->left);
arr[i++]=root->data;
cout<<root->data<<"\t";
inorder(root->right);
}
int main()
{
Tree *head=new_node(5); // making tree as per given condition
head->left=new_node(3);
head->right=new_node(4);
head->left->left=new_node(2);
head->left->right=new_node(6);
inorder(head);
cout<<endl;
int count=0,index1,index2;
for(int k=0;k<4;k++) // finding position of swap indexes in an array
{
if(arr[k]>arr[k+1] && count==0)
{ index1=k; count++;}
if(arr[k]>arr[k+1] && count==1)
index2=k;
}
int temp=arr[index1]; // swap those values
arr[index1]=arr[index2];
arr[index2]=temp;
head=NULL; // again reconstructing
for(int k=0;k<5;k++)
make_tree(&head,arr[k]);
inorder(head);
getchar();
return 0;
}
#include<iostream.h>
#include<conio.h>
int getmaxsum(int *a,int l)
{
int maxsum = 0;
int runningsum = 0;
int size = 2 *l;
for(int i=0; i < size-1; i++)
{
runningsum += a[i%l];
if(maxsum < runningsum)
maxsum = runningsum;
else if(runningsum < 0)
runningsum = 0;
}
return maxsum;
}
int main()
{
int b[20] = {8,-8,9,-9,10,-11,12};
cout<<"maxsum is :";
int s = getmaxsum(b,7);
cout<< s;
getch();
return 0;
}
An automatic face morphing algorithm is proposed. The algorithm automatically extracts feature points on the face, and based on these feature points images are partitioned and face morphing is performed. The algorithm has been used to generate morphing between images of faces of different people as well as between different images of the face of an individual. The results of both inter- and intra-personal morphing are subjectively satisfactory.
ref-->/
ccrma.stanford.edu/~jacobliu/368Report/index.html
test case on cup handle:
1.Not too thin Nor too thick
reason-->if is too thin then center of mass of cup should be far from finger(Unstable equilibrium) & Not to thick (since it should be handy);
2.Gap in the handle (optimum).
3.curvature of handle should be curve (no square....) --->easy to handle.
Test case on cup:
1.How much temp. it can withstand.
2.Interior color-->like if it is black(absorption of Heat energy so coffee will become cold readily).
3.Shape of cup-->if(circular) then (while drinking it will not spill out)...other shape like (square
may result in spilling)
4.weight of coffee cup-->(optimum(acc to its capacity))
Repmonicahbess, SDET at Adap.tv
Hi Everyone, I'm Monica H. Bess. I love to build props...everything from a casket to pneumatic monsters.My ...
Repbilliejeckley, SEO at Flipkart
Spent 2002-2008 testing the market for spit-takes in Los Angeles, CA. Spent 2001-2004 deploying how to get boyfriend back by ...
Repjaynebackus, Applications Developer at Achieve Internet
I am Jayne And I am working as a Record center clerk in a company. Also I'm doing a ...
- saurabh September 19, 2019