airfang613
BAN USERLooking at this problem again, I agree with db and remi.carton's explanation
- airfang613 August 28, 2012we will need to keep an internal buffer as well as a pointer indicating up to which position the internal buffer is used:
Note that the following code most likely won't compile, especially considering I am not entirely sure if memcpy works that way, but the logic should be correct, and you should be able to see what I am trying to achieve with the memcpy calls
class GenericReader {
Reader4k reader4k_;
int buf_ptr_;
char* internal_buf_;
public:
int Read(int n, char* buf) {
int count = 0;
int remain = n;
int buf_ptr = 0;
while (remain > 0) {
if (buf_ptr_ == -1) {
int bytes_read = reader4k.Read(internal_buf_);
if (bytes_read == 0) // we have exhausted the buffer
break;
buf_ptr_ = 0;
if (bytes_read > remain) {
memcpy(buf + buf_ptr, internal_buf_, remain);
count += remain;
buf_ptr_ += remain;
return count;
} else {
remain -= bytes_read;
count += bytes_read;
buf_ptr_ = -1;
memcpy(buf + buf_ptr, internal_buf_, bytes_read);
buf_ptr += bytes_read;
}
} else { // we still have stuff in internal_buf_, read those first
if (4096 - buf_ptr_ > remain) {
memcpy(buf + buf_ptr, internal_buf_ + buf_ptr_, remain);
buf_ptr_ += remain;
count += remain;
return count;
} else {
remain -= (4096 - buf_ptr_);
count += (4096 - buf_ptr_);
memcpy(but + buf_ptr, internal_buf_ + buf_ptr_, 4096 - buf_ptr_);
buf_ptr += (4096 - buf_ptr_);
buf_ptr_ = -1;
}
}
}
return count;
}
};
I am using brute force, but maybe using DP to cache some previous computed result can help pruning. I think my solution is essentially the same to shondik's.
Runnable code here: ideone.com/NSuWj
void PrintEquation(const vector<int>& series, stack<char>* ops) {
assert(series.size() - 2 == ops->size());
int ub = series.size() - 1;
for (int i = 0; i < ub; ++i) {
cout << series[i] << " ";
if (!ops->empty()) {
cout << ops->top() << " ";
ops->pop();
}
}
cout << "= " << series[series.size() - 1] << endl;
}
bool FindOperators(const vector<int>& series, int last_idx, float result, stack<char>* ops) {
if (last_idx == 0) {
if (series[0] == result) {
PrintEquation(series, ops);
return true;
} else
return false;
}
ops->push('+');
if (FindOperators(series, last_idx - 1, result - series[last_idx], ops))
return true;
ops->pop();
ops->push('-');
if (FindOperators(series, last_idx - 1, result + series[last_idx], ops))
return true;
ops->pop();
ops->push('*');
if (FindOperators(series, last_idx - 1, result / series[last_idx], ops))
return true;
ops->pop();
ops->push('/');
if (FindOperators(series, last_idx - 1, result * series[last_idx], ops))
return true;
ops->pop();
return false;
}
int main(int argc, char** argv) {
vector<int> series;
int tmp;
while (cin >> tmp)
series.push_back(tmp);
// sanity check for series.size()
if (series.size() < 3) {
cout << "Not enough operands" << endl;
return 0;
}
stack<char> ops;
if (!FindOperators(series, series.size() - 2, series[series.size() - 1], &ops))
cout << "No equation" << endl;
return 0;
}
Well... cplusplus.com has it all
cplusplus.com/reference/algorithm/rotate/
It is basically anonymous' solution converted to an iterative version
Very nice solution!
- airfang613 August 18, 2012small deliverables, shorter sprints makes the project more agile toward changes
- airfang613 August 18, 2012The question itself is pretty vague, can there be spaces between chars in a word as well? Otherwise this seems trivial. Considering a line with a single word, since there should be no spaces before and after, how would that case work?
- airfang613 August 17, 2012That's a pretty good hint, but I don't understand is how you can handle one pass in (O(string length) time)
the order of the words in L is arbitrary and we definitely need to check every segment of S following the first match because we could face the following situation:
fooo barr wing ding mehh nota matc hyet fooo wing ding barr wing
Go through the input once, build a hash table with the keys being the band name, values being a list of colleagues
Now go through the input again, for each band mentioned by each colleague, create a new hash table with key being other colleagues, value being the number of times they appear in the bands that the current colleague likes.
Now for each colleague, we just need to go through the new hash table and find the entry with the maximum value
Code can be tested here: ideone.com/4bgU7
One caveat is that the order of the compatibility list is not preserved (although it wasn't mentioned in the problem statement, but I can see that if there's a tie, output in the order same as the input colleague list).
import sys
def parseLine(line):
parts = line.split(':')
name = parts[0]
bands = parts[1].rstrip().split(',')
return name, bands
num_lines = int(sys.stdin.readline())
names = [] # to preserve the original order
colleague_likes = {}for line in sys.stdin:
name, bands = parseLine(line)
colleague_likes[name] = bands
names.append(name)
band_likes = {}
for item in colleague_likes.items():
name = item[0]
bands = item[1]
for band in bands:
if band_likes.has_key(band):
band_likes[band].append(name)
else:
band_likes[band] = [name]
for name in names:
bands = colleague_likes[name]
compatibility = {}
for band in bands:
for colleague in band_likes[band]:
if colleague == name:
continue
else:
if compatibility.has_key(colleague):
compatibility[colleague] = compatibility[colleague] + 1
else:
compatibility[colleague] = 1
max_compatibility = 0
compatibility_list = []
for item in compatibility.items():
if item[1] < 2:
continue
if item[1] > max_compatibility:
compatibility_list = [item[0]]
max_compatibility = item[1]
elif item[1] == max_compatibility:
compatibility_list.append(item[0])
print '%s: %s' % (name, ', '.join(compatibility_list))
Try it out at: ideone.com/eG3sQ
bool Matches(const string& str, const string& pattern) {
int pos = 0;
int str_len = str.size();
int pattern_len = pattern.size();
bool saw_wildcard = false;
for (int i = 0; i < pattern_len; ++i) {
if (pattern[i] == '*') {
saw_wildcard = true;
continue;
}
if (saw_wildcard) {
while (pos < str_len && str[pos] != pattern[i])
pos++;
if (pos == str_len)
return false;
else
pos++;
} else {
if (str[pos] != pattern[i])
return false;
else
pos++;
}
saw_wildcard = false;
}
// if last char in pattern is not a wildcard, then extra char in the input should not match
if (!saw_wildcard && pos < str_len)
return false;
return true;
}
I don't think the code is correct:
"This is the string " "is*is" should not be a match, but your program returned "yay"
Moreover, whether inputIndex can keep increasing definitely depends on whether the previous pattern character is a wildcard *
Also, I don't think you took care of the case when the pattern runs out but input still has characters left, which should not be a match, e.g., "xyzxyz" should not be a match for "*y*y"
reverse each individual rows, and then swap row 0 with row n - 1, row 1 with row n - 2, etc.
- airfang613 August 03, 2012While @student already gave a correct answer, I think there's another simple approach to this problem, it does require O(n) space though (so I wouldn't argue this is better than @student's solution)
The idea is to create an auxiliary array which contains the accumulative sum of the original array, then scan through the auxiliary array for element that is exactly half of the last element
int FindEquilibriumSimple(const vector<float >& input) {
int num_elem = input.size();
vector<float> sums(num_elem, 0);
sums[0] = input[0];
for (int i = 1; i < num_elem; ++i) {
sums[i] = sums[i-1] + input[i];
}
float target = sums[num_elem - 1] / 2;
for (int i = 0; i < num_elem - 1; ++i) {
if (sums[i] == target) // better to use abs diff < eps
return i;
}
return -1;
}
I have implemented both approach and from the test cases I provided so far they produce the same result, try it out here: ideone.com/bsc0f
- airfang613 July 29, 2012Perform a modified version of in-order traversal. When processing the node, update the current node's right pointer to point back to the head and the head's left pointer to point to the current node.
- airfang613 July 29, 2012Quoted from CareerCup 150, Question 1.6
The rotation can be performed in layers, where you perform a cyclic swap on the edges on
each layer In the first for loop, we rotate the first layer (outermost edges) We rotate the
edges by doing a four-way swap first on the corners, then on the element clockwise from the
edges, then on the element three steps away
Once the exterior elements are rotated, we then rotate the interior region's edges
1 public static void rotate(int[][] matrix, int n) {
2 for (int layer = 0; layer < n / 2; ++layer) {
3 int first = layer;
4 int last = n - 1 - layer;
5 for(int i = first; i < last; ++i) {
6 int offset = i - first;
7 int top = matrix[first][i]; // save top
8 // left -> top
9 matrix[first][i] = matrix[last-offset][first];
10
11 // bottom -> left
12 matrix[last-offset][first] = matrix[last][last - offset];
13
14 // right -> bottom
15 matrix[last][last - offset] = matrix[i][last];
16
17 // top -> right
18 matrix[i][last] = top; // right <- saved top
19 }
20 }
21 }
Because there's no sequence point: en.wikipedia.org/wiki/Sequence_point
Under section "Sequence points in C and C++", read Item 4
from wiki: "A balanced binary tree is commonly defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1"
- airfang613 July 27, 2012@Anonymous this tree is not balanced (min height = 2, max height = 4), but if Node 2 has a right child, this tree becomes balanced
- airfang613 July 26, 2012minheight for the tree you describe _is_ 1, not 4
- airfang613 July 20, 2012this tree is not balanced, since balance of a binary tree is recursively defined, according to my code, the minimum height at root will be 2 and the maximum height will be 4.
You can see the code run here: ideone.com/aSaoZ
The idea is very simple, the difference of minimum height and the maximum height should not exceed 1.
int MaxHeight(Node* root) {
if (root == NULL)
return 0;
return 1 + max(MaxHeight(root->left), MaxHeight(root->right));
}
int MinHeight(Node* root) {
if (root == NULL)
return 0;
return 1 + min(MinHeight(root->left), MinHeight(root->right));
}
bool IsBalanced(Node* root) {
if (root == NULL)
return true;
return (MaxHeight(root) - MinHeight(root)) <= 1;
}
this sounds like an interesting solution... but to be honest, I didn't quite understand OP's question, what does he mean by "at least one person knows other"?
- airfang613 July 20, 2012as I understand the question, the function just need to be able to take different types of input, unless there's some other interpretation?
- airfang613 July 11, 2012nerd's solution is almost correct, just need to take care of some offset
template<class T>
string Translate(T input) {
static const char kLookUp[26] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
string res = "";
while (input > 0) {
T idx = (input - 1) % 26;
res = kLookUp[idx] + res;
input = (input - 1) / 26;
}
return res;
}
That's correct, I don't know what I was thinking when I made the comment.
- airfang613 June 28, 2012Can somebody please explain the problem a little bit better? I got confused, what does "closest greatest" mean?
Say for an array: 1 100 1000, for A[0], 100 would be the closest element that is greater than itself, but 1000 would be the greatest element, I guess the question was referring to the first scenario?
It'd be great if you can post some examples. Thanks!
Good catch! Thanks!!
- airfang613 August 23, 2011I think if the question is just "whether" the strings can be chained not "how" they can be chained, there exists an easier solution than Euler tour/walk.
Idea: use 2 arrays to represent the char needs (in order for the strings to be chained), say, F and E.
For every string, if its 1st char's count in E is greater than 0, decrement its count in E, else increment its count in F. If its last char's count in F is greater than 0, decrement its count in F, else increment its count in E.
In the end, if the strings can be chained, we will ended up with either sum(F) == sum(E) == 0 or 1. In the case of 0, it just means that the final chained string would have its first char == last char.
Time complexity O(N), space O(1)
Working code here: ideone.com/3EquX
Please suggest if it solves the "whether" problem. If not please also suggest a counter example.
I actually don't understand how pushing to one of the stacks twice would work. Maybe you can elaborate a little bit?
- airfang613 August 22, 2011You are mixing up different problems. What you described works when all but one number appears odd times.
XOR in this case would just cancel out the number we want to find
+1
First scan the array to obtain unique elements, then XORing additionally these elements converts the problem of ODD-EVEN to EVEN-ODD problem again.
I think this solution works.
- airfang613 August 06, 2011What if what the index is out of range? E.g., some other number other than n is missing, this makes the index n-1. However, since the array only has n-1 elements, the largest index possible is n-2.
- airfang613 August 06, 2011I think main didn't return int because it is C not C++
- airfang613 August 06, 2011Agreed.
While searching for X, keep note of a value that is the smallest among the ones that are greater than X. If X is not found in the end, return this value. If it is, return X's successor.
This could also account for the case where X is greater than any element in the BST.
Hi Saumya, I don't think you understood kishore's solution. His algorithm will yield correct answer as 1324.
Note that he is not swapping digits[i] with digits[i+1], he's swapping digits[i] with the smallest digit after i that is greater than digits[i].
If level represents depth, then this computes horizontal sum :) but the idea is the same.
- airfang613 July 23, 2011Just keep track of current maximum sum, if the current element alone is bigger than the sum, then update the sum with current element.
See the code below in action: ideone.com/bPblj
int GetMaxSum(const vector<int>& array, int* max_lb, int* max_ub) {
int maxsum = std::numeric_limits<int>::min();
int sum = 0;
int lb = 0;
*max_lb = *max_ub = lb;
int len = array.size();
for (int i = 0; i < len; ++i) {
sum += array[i];
if (sum < array[i]) {
sum = array[i];
lb = i;
}
if (maxsum < sum) {
maxsum = sum;
*max_lb = lb;
*max_ub = i;
}
}
return maxsum;
}
This would be the naive solution to give first, but obviously too slow for the intention of this question.
- airfang613 July 23, 2011Actually, sometimes I was asked to give working code... (I mean here)
- airfang613 July 23, 2011It might be dependent on the compiler. I tried on ideone, it generates a warning, but still prints the output (16), and b has been updated to 5.
- airfang613 July 23, 2011Well, if STL can be used this is extremely easy, or does the interviewer wants to actually implement the string reverse and sorting functions?
- airfang613 July 22, 2011bingo
- airfang613 July 11, 2011Runnable code: ideone.com/QjGW2
The idea is to use a stack (I used a vector but a stack will do), start from right to left
I think the solution here works: sureinterview.com/shwqst/101005
Please suggest.
10-bit integers means integers in the range 0-1023, just create an array of 1024 entries and count the number of occurrence of each integer as you read.
The array values corresponds to the frequency of the integer. If it is 0, don't output, if it is 1, output once, and if it is N, output N times its index.
anon's solution works
so basically, generate the first string using as large fib number as possible
then for each 100 pattern, try replacing it with 011 (due to fib number property), generate all possible variations
Here is the code: ideone.com/rBFlC
Note if u input 1, it will output 01, since I pushed the first two fib number by default (trivial to fix)
I think that is a good solution
- airfang613 May 12, 2011Can you explain a little bit more in detail?
I can't quite follow your solution, what do you mean by n, m, and subarrays?
Thanks
Honestly, I think this is the answer they are looking for
- airfang613 August 29, 2012