gokayhuz
BAN USERThis would give us O(n log n) in the worst case. Say the numbers are in decreasing order. You keep on putting the next element into the min-heap (O(log n)for all elements (O(n))
You might just as well sort the numbers in O(n log(n)) time and return the largest 1000 numbers.
The answer to this question is quick find with an initial shuffle
Assuming having a village with 64 families.
After they all have their babies, the village will have 32 baby boys and 32 baby girls. The number of boys = number of girls. Now, 32 families who had boys will stop having babies.
Of the remaining 32 families... 16 will have boys and 16 will have girls. The "total" number of baby boys = total number of baby girls = 32+16=48
Now, we have 16 families still going at it... of these, 8 boys and 8 girls will come out. Total number of boys = total number of girls = 32+16+8 = 56
Now, 8 couples will produce 4 boys and 4 girls. We have 60 boys and 60 girls total.
Next, 4 couples will have 2 boys and 2 girls. 62 boys and 62 girls
2 couples left... 63 boys and 63 girls
And finally we have only 1 couple left... Ignoring this pop couple who have had 8 babies in a row... As counter-intuitive as it looks, we can see that the ratio of baby boys/baby girls remains constant.
Here is an example with a unit test included. Basically, if the input is n, we check if (n+1) satisfies the three conditions.
If it does, we return it. If it does not we increment it again and check. We keep incrementing till the result meets all requirements.
And, I assume the OP's example is incorrect. 987's output should be 1234 according to the requirements.
#include <cstdio>
// returns truw if the digits are not in incremental order
bool checkIncremental(int input) {
bool check = true;
while (input) {
// next line checks if the inputs least significant
// digit is bigger than the second least significant
// digit or not
check = input % 10 > (input/10) % 10;
if (!check) return true;
input /= 10;
}
return false;
}
// returns true if there are repeating digits
bool checkRepeat(int input) {
int copy = input; // make a copy of the input
if (input < 10)
return false; // pigeonhole principle
if (input > 10000000000) // not necessary if working with 16-bit ints
return true; //pigeonhole principle again
int lastDigit = copy % 10;
copy /= 10;
while (copy){
if (copy % 10 == lastDigit)
return true;
else
copy = copy / 10;
}
return checkRepeat(input/10);
}
int nextInteger(int input) {
if (input < 0)
return 1;
input++;
while (checkRepeat(input) || checkIncremental(input) )
input++;
return input;
}
int main() {
int i = 1;
while (i) {
scanf("%d", &i);
printf("result %d\n", nextInteger(i));
}
return 0;
}
And my function accepts and returns an integer, as opposed to a string. But it is trivial to convert back and forth between them
- gokayhuz March 11, 2014Here is the C++ code.
Basically, you need the print the maximum of the x-distance or y-distance to the center position
#include <iostream>
using namespace std;
int abs(int i) {
return (i < 0 ? -i : i);
}
void print(int n) {
for (int i = 0; i<2*n-1; ++i) {
for (int j = 0; j < 2*n-1; ++j)
printf("%d", (abs(i-n+1) > abs(j-n+1) ? abs(i-n+1) : abs(j-n+1))+1);
printf("\n");
}
}
int main() {
print(7);
return 0;
}
"next least", as I understand, is the node that is the smallest that comes after the current node. So, it is asking for the successor.
But you are right, there is some ambiguity about the wording and this needs to be clarified at a interview. But, the given solutions are easy to implement correctly if the question is clarified.
Thanx aj. I fixed the "little" bug. It should be working now :)
However, your code also has one bug. More importantly, the little bug, I do not think it works.
The bug is when you call
successor(flag, root->left);
The function should take 3 parameters, not one.
And about the "real" problem...
Imagine a tree, where root has the value 10. To the left of the node, we have a child with data of 7. And 7 has a right child with data 9. Now, the successor of 9 is the root node, 10. However your code only prints 9 and not the successor
I tried to define what the "next least node" is in my solution. in this question, the "next least node" is the node that comes after a specific node in an "in-order traversal of the tree". It is usually called the "successor" of the node.
In layman's terms, if a tree contains nodes with the key values {3, 7, 19 ,23, 26, 31, 40}, the next least node for node{23} is node{26}. For node{3}, the successor is node {7} and naturally node{40} does not have a successor
All answers so far are incorrect. What you are looking for here is the "successor" of the current node. For the given question, I assume all nodes have a pointer two its parent. Otherwise, we need a O(N^2) solution.
There are two cases:
(1) the current node has a right subtree
(2) the right subtree of the current node is NULL.
For (1), the successor is the leftmost child of the right subtree
For (2), we have to go up towards the root till we find a parent node, whose left subtree contains the current node.
Also, note that the node might be the largest element in the tree, and hence there is no successor. In this case, the code returns NULL.
here is the pseudo code:
successor(x) {
if (x -> right != NULL) // current node DOES have a right node
y = x -> right;
while (y.left != NULL) // return the minimum element of the right sub-tree
y = y -> left;
return y;
}
else { // current node does NOT have a right subtree
y = x -> parent;
while (y != NULL && x ==y -> right) { // go up the tree
x = y;
y = y -> parent;
}
return y;
}
another difference is that processes are "fork"ed and threads are "spawn"ed.
A fork (creating a process) is usually more time-consuming. This is a system call.
A spawn (creating a new thread) can be faster than forking a new process.
The first time you run a program, you create a new process (never a new thread). A process can have multiple threads, but not the other way around. (edited and corrected)
(1) We know all the labels are wrong,
Because of (1), the "mixed" basket has to be either all apples or oranges, it cannot be mixed. You pick from the basket labeled "mix". There are two cases:
1. You picked an apple. We now know the basket labeled "mixed" is all apples. Then (again due to (1)) the basket labeled "orange" can either be all apples or mixed. But we already know it is not all apples. Thus, the basket labeled "orange" is mixed. And the remaining basket is all apples.
2. Similar to the case above. If you get an orange from the basket labeled "mixed", we know that the basket is all oranges. Then the one labeled "orange" has to be apples and the remaining one is all mixed (EDIT: corrected the last basket label. Thanks to John Zhao).
Both answers calculate the "profit" as "selling_price - buying_price", which is missing a very important point, which the interviewer intended to ask probably
Say for example you had two cases:
case 1: you buy the stock at $1000/share and sell at $1500/share. You have just made $500/share in profit
case 2: you buy the stock at $100/share and sell at $200/share. You have just made $100/share in profit.
Which case is "more profitable" as the original question asks? The solutions provided will pick case 1 when in case the answer is case 2.
The profits should be "normalized" by dividing the difference between selling and buying prices with the buying price.
So profit = (selling_price - buying_price) / buying_price
Also, the question is not clear in whether selling short is allowed or not. If it is, then the problem becomes trivially simple as finding the min and max in an array of numbers
There are 2 minor typos in your solution, the corrected version is as follows:
for(int i=n-1; i>=0; i--) {
swap(arr+random(i), arr+i);
}
Also, we should state our assumption that random(N) generates uniformly distributed integers in the range 0 to i (0 inclusive, i exclusive). In C++, we can guarantee this by i*rand(i)/RAND_MAX
- gokayhuz September 09, 2013the question needs some clarification on the definition of an X. Do the lines have to cross at mid-points? For example, do two lines that are orthogonal to each other but form a "T" count as an X or not? According to your definition, it does, but logically it should not.
Either way, we need to start at one corner and iterate through all elements in the matrix in a sequential way. For each "1", assume it is the crossing point of the "X":
- check the length of the longest line that crosses that point
- do we have a line that is perpendicular to the initial line. If yes, calculate its length and return the minimum of the two, else return 1.
This will yield a O(n^3) solution. Sounds bad but in this case, I think this is the best available solution
@Erasmus: imagine the knight travelling on the diagonal (1,1 to n,n). The knight will have to travel from 1,1 to k,k (where 1 <= k <= n) first.
In the sum,
- M(n) = Min(M(i) + M(j))
M(i) represents the first part of the move and M(j) represents the second part.
For a 8x8 board, we have the knight move from (1,1) to (8,8). However, the answer we are trying to compute is M(8).
Because we are starting our indices at 1 (and not 0), we need to add 1 to n.
The rationale is easy to visualize or you can reverse-engineer the off-by-one from the numbers as well.
Erasmus is right for the most part, except there are two important bugs.
The base cases are correct. However, we don't really need that many base cases.
Also there is an off-by-one error. The sum of i and j should be n+1, not n.
And in the function, the Min(a)'s should be M(i)
Here is the complete solution:
M(1) 0
M(2) not defined
M(3) = 4
M(4) = 2
M(5) = 4
M(6) = 4
For n>6;
M(n) = Min{ M(i) + M(j)}, where i+j = n+1 & i>;2 & j>2
This produces:
M(7) = M(4) + M(4) = 4
M(8) = M(5) + M(4) = 6
M(9) = M(6) + M(4) = 6
...
for the people that are too concerned about the "infinite years"...
- gokayhuz March 25, 2014there will come a time, when the sun will turn into a black hole... in billions of billions of billions.... years... but definitely that will happen before "infinite years".
there will be no boys and no girls. the ratio of girls to boys will be undefined (divide by zero)
I think the intent of the interviewer was not to ask about "infinite years", but wanted the interviewee to take a limit as n goes to infinity in the expected value of the two numbers.