xiaoc10
BAN USER- 5of 5 votes
AnswersI came across this problem online.
- xiaoc10 in United States
> Given an integer:N and an array int arr[], you have to add some
> elements to the array so that you can generate from 1 to N by using
> (add) the elements in the array.
Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the count of the least adding numbers.
For example:
N=6, arr = [1, 3]
1 is already in arr.
add 2 to the arr.
3 is already in arr
4 = 1 + 3
5 = 2 + 3
6 = 1 + 2 + 3
So we return 1 since we only need to add one element which is 2.
Can anyone give some hints?| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
Answers>Compute the number of connected component in a matrix, saying M. Given two items with coordinates [x1, y1] and [x2, y2] in M, M(x1, y1) == -1 && M(x2, y2) == -1 && |x1-x2|+|y1-y2|=1 <=> they are connected
- xiaoc10 in United States
Example:
-1 0 -1 0 0
-1 -1 0 -1 -1
0 0 0 0 -1
0 0 0 -1 -1
0 0 0 -1 0
0 -1 0 0 0
0 -1 0 0 0
Output: 4. And they are:
-1
-1 -1
-1
-1 -1
-1
-1 -1
-1
-1
-1
My idea is to scan the matrix.
Initialization:
count = 0.
For every item in the matrix, do the following three tests.
(1) If it's 0, skip
> (2) If it's -1, check its four neighbors. If there is a neighbor whose
value is not 0 and -1, assign the value of this neighbor to the current item. Otherwise, `count++`, ant then assign `count` to the current item.
>
> (3) If it's not 0 and -1, assign the value of current item to its four
neighbors whose value is -1.
Can anyone help me verify this solution?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite an algorithm to find F(n) the number of bits set to 1, in all numbers from 1 to n for any given value of n.
- xiaoc10 in United States
Complexity should be O(log n)
For example:
1: 001
2: 010
3: 011
4: 100
5: 101
6: 110
So
F(1) = 1,
F(2) = F(1) + 1 = 2,
F(3) = F(2) + 2 = 4,
F(4) = F(3) + 1 = 5,
etc.
I can only design an O(n) algorithm.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 1of 1 vote
AnswersThere is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum. As for how to compute the cost of moving one group to another point, please see the following example.
- xiaoc10 in United States
Group1: (0, 1), 4
Group2: (1, 3), 3
Group3: (2, 0), 5
. 4 . .
. . . 3
5 . . .
If all of these three groups moving to (1, 1), the cost is: 4*((1-0)+(1-1)) + 5*((2-1)+(1-0))+3*((1-1)+(3-1))
My idea is :
Firstly, this two dimensional problem can be reduced to two one dimensional problem. In the one dimensional problem, I can prove that the best spot must be one of these groups. In this way, I can give a O(G^2) algorithm.(G is the number of group).
Use iterator's example for illustration:
{(-100,0,100),(100,0,100),(0,1,1)},(x,y,population)
for x, {(-100,100),(100,100),(0,1)}, 0 is the best.
for y, {(0,100),(0,100),(1,1)}, 0 is the best.
So it's (0, 0)
Is there any better solution for this problem.
Thanks,| Report Duplicate | Flag | PURGE
Google Algorithm
Inspired by abhishek's idea. It seems that there is a O(G) solution for this problem. Since everyone agree with the two dimensional problem can be reduced to two one dimensional problem. I will not repeat it again. I just focus on how to solve the one dimensional problem with O(G).
Suppose, people are standing like this, a[0], a[1], ... a[n-1]. There is a[i] people standing at spot i. There are G spots having people(G <= n). Assuming these G spots are g[1], g[2], ..., g[G], where gi is in [0,...,n-1]. Without losing generality, we can also assume that g[1] < g[2] < ... < g[G].
It's not hard to prove that the optimal spot must come from these G spots. I will pass the prove here and left it as an exercise if you guys have interest.
Since the above observation, we can just compute the cost of moving to the spot of every group and then chose the minimal one. There is an obvious O(G^2) algorithm to do this.
But using kilotaras's idea, we can do it in O(G)(no sorting).
cost[1] = sum((g[i]-g[1])*a[g[i]], i = 2,...,G) // the cost of moving to the
spot of first group. This step is O(G).
cur_r = sum(a[g[i]], i = 2,...,G) //How many people is on the right side of the
second group including the second group. This step is O(G).
cur_l = a[g[1]] //How many people is on the left side of the second group not
including the second group.
for i = 2:G
gap = g[i] - g[i-1];
cost[i] = cost[i-1] - cur_r*gap + cur_l*gap;
if i != G
cur_r = cur_r - a[g[i]];
cur_l = cur_l + a[g[i]];
end
end
The minimal of cost[i] is the answer.
Using the example 5 1 0 3 to illustrate the algorithm. In this example,
n = 4, G = 3.
g[1] = 0, g[2] = 1, g[3] = 3.
a[0] = 5, a[1] = 1, a[2] = 0, a[3] = 3.
(1) cost[1] = 1*1+3*3 = 10, cur_r = 4, cur_l = 5.
(2) cost[2] = 10 - 4*1 + 5*1 = 11, gap = g[2] - g[1] = 1, cur_r = 4 - a[g[2]] = 3, cur_l = 6.
(3) cost[3] = 11 - 3*2 + 6*2 = 17, gap = g[3] - g[2] = 2.
Nice code. But time complexity is O(mG+nG). Actually, it can be O(G^2) at least. Since we can prove that the best point must be one of the G groups, we just need to loop through every point having people.
In your code :
for (int x = 0; x < m; x++) ==> for (MeetingLocation location : meetingLocations)
Repameliahill344, abc at Detail Oriented
Professionally licensed Architect with a Master’s degree in Architecture and more than 4 years experience designing commercial buildings, offices ...
Repbungayasorya, Accountant at BrowserStack
An archeologist is an expert on history who gains expertise through experience with historical documents and artifacts. The archaeological record ...
RepNoraMiller, abc at A9
Confident and dedicated photographer with experience in both professional and freelance photography.. Prioritizes communication on the job to avoid errors ...
This is a correct answer!!! I've figured it out by myself these days!
- xiaoc10 August 15, 2015