Forum Posts
- 0 Answers Increasing Digital Subsequence Problem
Hi,
- abhi1988srivastava October 30, 2013
I was going through the Jeff Erikson notes on Dynamic programming and got stuck with one of the questions in the exercise. Here my pasting the complete question :
Let D[1.. n] be an array of digits, each an integer between 0 and 9. An digital subsequence of
D is an sequence of positive integers composed in the usual way from disjoint substrings of D.
For example, 3,4,5,6,8,9,32,38,46,64,83,279 is an increasing digital subsequence of the first
several digits of :
3 , 1, 4 , 1, 5 , 9, 2, 6 , 5, 3, 5, 8 , 9 , 7, 9, 3, 2 , 3, 8 , 4, 6, 2, 6, 4 , 3, 3, 8, 3 , 2, 7, 9
The length of a digital subsequence is the number of integers it contains, not the number of digits;the preceding example has length 12.
Describe and analyze an efficient algorithm to compute the longest increasing digital subsequence of D.
I thought of starting it with LIS restrircing to single digit number and adding 1 to it but how to compare for range of values like comparing for two k digits.
(restricting to single digit):
DS(i) = 1+ max{DS(j)} where j<=9 and A[i]>A[j]
Please help.
Regards
Abhinav| Flag | PURGE - 1 Answer Can you help me with some C code.
PROBLEM STATEMENT:
- Feurer October 28, 2013
Calculator Language (CL) supports assignment, positive and negative integers and simple
arithmetic. The allowable characters in a CL statement are thus:
A..Z : Variables
0..9 : Digits
+ : Addition operator
- : Subtraction operator
* : multiplication operator
/ : integer division operator
= : assignment operator
() : brackets
- : negative sign
All operators have the same precedence and are right associative, thus 15 - 8 - 3 = 15 - (8 - 3) = 10.
As one would expect, brackets will force the expression within them to be evaluated first. Brackets
may be nested arbitrarily deeply. An expression never has two operators next to each other (even
if separated by a bracket), an assignment operator is always immediately preceded by a variable
and the leftmost operator on a line is always an assignment. For readability, spaces may be freely
inserted into an expression, except between a negative sign and a number. A negative sign will not
appear before a variable. All variables are initialised to zero (0) and retain their values until changed
explicitly.
Write a program that will accept and evaluate expressions written in this language. Each expression
occupies one line and contains at least one assignment operator, and maybe more.
Input
Input will consist of a series of lines, each line containing a correct CL expression. No line will be
longer than 100 characters. The file will be terminated by a line consisting of a single #.
Output
Output will consist of a series of lines, one for each line of the input. Each line will consist of a
list of the final values of all variables whose value changes as a result of the evaluation of that
expression. If more than one variable changes value, they should be listed in alphabetical order,
separated by commas. If a variable changes value more than once in an expression, only the
final value is output. A variable is said to change value if its value after the expression has been
evaluated is different from its value before the expression was evaluated. If no variables change
value, then print the message `No Change'. Follow the format shown below exactly.
Sample input
A = B = 4
C = (D = 2)*_2
C = D = 2 * _2
F = C - D
E = D * _10
Z = 10 / 3
#
Sample output
A = 4, B = 4
C = -4, D = 2
D = -4
No Change
E = 40
Z = 3| Flag | PURGE - 0 Answers Vertex removal graph problem with minimization constraint
There is a graph in which each vertex has an associated cost and a label that is binary (0 or 1). You need to remove vertices from the graph such that none of the remaining edges in the graph connect vertices with the same label.
- Xi Qu October 25, 2013
Constraint: minimize the total cost of vertices removed.| Flag | PURGE - 1 Answer Interview Question at Amazon
: I am software services company. I have a bunch of engineers on bench. I want to create a new team out of this bench strength. I know the experience of each engineer as well as his CTC. I have to pick N engineers and my total budget for salary is D$ and get maximum possible experience.
- pshagl007 October 25, 2013| Flag | PURGE - 0 Answers JAVA
how do we compare two objects in java.
- gautam October 25, 2013| Flag | PURGE - 0 Answers What does offer roll out process mean
Hey guys I interviewed for Amazon one month back, I cleared all four rounds but was not selected. Two days ago the HR got back to me asking me to send my resume as they need to proceed with my OFFER ROLL OUT PROCESS any idea what this means
- revathi.srirangam93 October 20, 2013| Flag | PURGE - 0 Answers algo
Submit
- talukdarraktim92 October 20, 2013
All Submissions
Read problems statements in Russian here
Polo, the Penguin, has a lot of tests tomorrow at the university.
He knows that there are N different questions that will be on the tests. For each question i (i = 1..N), he knows C[i] - the number of tests that will contain this question, P[i] - the number of points that he will get for correctly answering this question on each of tests and T[i] - the amount of time (in minutes) that he needs to spend to learn this question.
Unfortunately, the amount of free time that Polo has is limited to W minutes. Help him to find the maximal possible total number of points he can get for all tests if he studies for no more than W minutes.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains the pair of integers N and W, separated by a space. The following N lines contain three space-separated integers C[i], P[i] and T[i] (i = 1..N).
Output
For each test case, output a single line containing the answer to the corresponding test case.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ C[i], P[i], T[i] ≤ 100
1 ≤ W ≤ 100
Example
Input:
1
3 7
1 2 3
2 3 5
3 3 3
Output:
11
Explanation
Example case 1. The best choice is to learn the first and the third questions and get 1*2 + 3*3 = 11 points.| Flag | PURGE - 4 Answers How to get into top product based companies with 2 years exp
Hi,
- Ravi Kumar October 20, 2013
I did my graduation from one of the top IIIT's in comp science. And I have 2 years of experience in Java in a top product based company. I have a CGPA >9 and I have very good algorithmic skills.
Now I want to get into companies like Google, Microsoft, Facebook .. or companies like that. I have applied in the career portals of those companies, but no use. I hardly get any calls.
What should be my approach to apply in such companies? How to apply, so that I get an Interview call at least?
Your replies will be very helpful for my career!.
Thanks in Advance :)| Flag | PURGE - 0 Answers Discord is in trouble for caus...
Discord is in trouble for causing discord, so he is trying to escape from Equestria. He's arrived at the port, and he doesn't care what boat he gets on, he just wants to get out. He can see the boat schedule, where he sees that N boats are arriving today,
- deepak.dpkgpt October 15, 2013
boat 1 arrives any time within a_1 minutes
boat 2 arrives any time within a_2 minutes
...
boat N arrives any time within a_N minutes (uniform distribution)
Tell discord the expected number of minutes he needs to wait for a boat to arrive.
For example If n=3 , and there arriving times are 49,50,51 respectively then expected number of minutes would be 12.495000 . Thats all I know .| Flag | PURGE - 3 Answers Being rejected though I correctly solving the problems
Hi guys ,
- Arian October 13, 2013
Recently I've had 3 in-person interviews (2 of them small companies and 1 a bigger one) , I was rejected in the two small ones and got accepted by the larger one.
I have a visa issue which I need to wait for 1 year to start my job (in the states) and I do the coding in Java. The two smaller companies did know that I do programming in Java but they used C# and Microsoft stack generally.
One of the smaller companies was not sure that I have visa issue but at the end of the interview day they told me that they can provide visa sponsorship.
I answered all the questions correctly as they all told me that I did a nice job ! but some days after I got rejected. I had a very nice attitude and we got friends at the interview but I can't understand why they rejected me ! It was really disappointing as you think you will be definitely offered a job but it doesn't happen !
Any idea ? How do they decide ? may it be because of visa problem ? may it be because I do the coding in Java and they use Microsoft stack ?
I'm confused :(| Flag | PURGE - 2 Answers Amazon Group Interview Process and Tips
Hi,
- krackCode October 06, 2013
I have a Group Interview at Amazon next week and I wanted to know if anyone has previously attended and what kinds of questions can be expected.
In this a total of N candidates attend this process
and are divided into group of 3 randomly
and every team is given a project to implement in 5 hrs and in between there will be 1 hr interview with amazon guys
Anyone have any idea about this ?| Flag | PURGE - 0 Answers solutions welcome..:)
City Tour of Paris is awesome !
- shailendra October 06, 2013
It seems like all the tourists who visits Paris wants to go for a city tour in bus. Some people go alone, other people go in groups and don't want to board the bus unless they can all go together. And Paris is so good that everyone who has a tour wants to tour again and again. A bus ticket costs 1 Euro per person. Your job is to figure out how much money the tour bus will make today.
The tour bus can hold k people at once. People queue for it in groups. Groups board the tour bus, one at a time, until there are no more groups left or there is no room for the next group; then the tour bus goes, whether it's full or not. Once the city tour is over, all of its passengers re-queue in the same order. The bus will run R times in a day.
For example, suppose R=4, k=6, and there are four groups of people with sizes: 1, 4, 2, 1. The first time the tour bus goes, the first two groups [1, 4] will ride, leaving an empty seat (the group of 2 won't fit, and the group of 1 can't go ahead of them). Then they'll go to the back of the queue, which now looks like 2, 1, 1, 4. The second time, the bus will hold 4 people: [2, 1, 1]. Now the queue looks like 4, 2, 1, 1. The third time, it will hold 6 people: [4, 2]. Now the queue looks like [1, 1, 4, 2]. Finally, it will hold 6 people: [1, 1, 4]. The tour bus has made a total of 21 Euros.
Input format:
The first line contains three space-separated integers: R, k and N.
The second line contains N space-separated integers gi, each of which is the size of a group that wants to ride. g0 is the size of the first group, g1 is the size of the second group, etc.
Output format:
For each test case, output one line containing the number of Euros made by the tour bus.
Also,
1 <= R <= 10^8
1 <= k <= 10^9
1 <= N <= 1000
1 <= gi <= 10^7
gi <= k
Sample Input:
4 6 4
1 4 2 1
Sample Output:
21| Flag | PURGE - 0 Answers Linux C programming for telecom equipments
Hello everyone,
- freak88delhi October 05, 2013
I want to understand the things regarding linux system programming from a practical/production system point of view. If anyone is working(or knows about) in telecom domain on network equipments like DSLAM/ONT/OLT etc, can that person please tell me below things to detail:
1. What is the scope/uses of Linux C programming in relation to these devices. (apart from device firmware and device drivers). i.e. what various applications are programmed so that device is accesed or interacted with.
2. How is that achieved? i.e. a C application can directly interact with device or some other applications lie midway? any code examples would be great.
3. What are the data formats and data structures that are used ,and flow through these devices.
4. What are the developments approach or practices followed for such applications i.e. Multithreading/signalling/client-server etc.
5. Which OS are commercially used as platform for developing such application/system programs?
To conlude, assuming that I am a user space Linux C programmer, what I'd be doing?
I have tried my best to frame this question. I can try clarifying further if someone wants.
Any guidance will be greatly appreciated on this.| Flag | PURGE - 1 Answer front-end infrastructure position in Google
I have an interview for this position in 2 weeks and I have no idea what kind of questions to expect. Will they be css/html/php related? Or same old data structure kind of questions for all technical positions?
- anon October 03, 2013
They asked me to point out the subjects that interest me and of course I choose front-end and UI but I have no idea if they make a difference in the kind of interview questions. i would really appreciate any insight on the matter.
thank you| Flag | PURGE