peter tang
BAN USERIf the varying grouping of list in the input does not affect the output single list, then this should be fairly easy.
(1, (2, 3), (4, (5, 6), 7)) output (1, 2, 3, 4, 5, 6, 7)
(1, (2, 3), (4, 5), (6, 7)) output (1, 2, 3, 4, 5, 6, 7)
......
1. Keep the leftest "(" and rightest ")"
2. Remove any "(" and ")" between
3. Detect delimiter "," and found the number.
Code wise is easy. Sometimes this kind of interview is quick tricky. Throw you piles of information. Sometimes need to peel off the distraction and simplify the problem.
PushQueue, PopQueue.
1. starting, both empty.
2. push operation done by "PushQueue.push()"
3. pop operation done by
int t = 0;
while (t < (PushQueue.size() - 1)) {
PopQueue.push(PushQueue.pop());
}
return PushQueue.pop();
4. swap PushQueue and PopQueue.
- peter tang October 31, 2012Two pointer, one pointing to the top and one pointing the bottom. TopPtr moving downwards and BottomPtr moving upwards. Each time swap the char until TopPtr and BottomPtr meets. O(n/2)
- peter tang October 31, 2012I doubt if HASH table will work or not. It works only if the hash function is so good that there will be no collision for any number.
The safe way is to sort first then count the frequency. If use quicksort, average O(nlog(n)) + O(n), sorting plus traverse.
It won't work. Try a[5] = {0, 100, 10000, 1000000000000}, how could you define an array of 1000000000000000?????
- peter tang October 31, 2012HASH table is better than SET. STL SET is implemented Balance Binary Tree. It it takes O(logN) to find the duplicate. HASH table only takes O(1).
Use data structure to determine if nodes are duplicates as the key. If more than one data, use the joint. Think about boos hash table.
merge sort
- peter tang October 31, 2012It seems that there is duplicate question. Some someone has given a very good simplification about this problem. Can't remember whom it is. Basically it can be taken as two link lists. A --> TOP and B --> TOP, then this problem can be regards as if these two link list merge at some node.
- peter tang October 31, 2012Use pointer to pointing to the start of two string. Compare if match. If yes, move the pointer to PATTERN together with pointer to INPUT. If match not found, reset pointer to PATTERN to the begin.
- peter tang October 31, 2012Garbage value.
This is because post-fix ++ operator is return-by-value.
int operator++();// post-fix ++ operator
int& operator++();// pre-fix ++ operator
In a[indx] = indx ++, indx is loaded to a register then done the part a[0] = 0; then calling indx.++(). And it is return-by-value, so literally indx may have different address in stack before executing this assginment.
As long as you are going to allocate more meory, then you may have to move the memory from one place to another. Then it may invlove a lot of invocations of copy cstr and deletion. Then the cost of resizing rising.
- peter tang October 20, 2012A large arrary? How large is enough? Have you considered the cost of resizing?
- peter tang October 20, 2012a, b, c has N bits, so the maximal number is 2^N -1
a * b + c maximally can be
(2^N - 1) * (2^N - 1) + (2^N - 1)
= 2^(2N) - 2*2^N + 1 + 2^N - 1
= 2^(2N) - 2^(N+ 1)
< 2^(2N) - 1 // which is the maximal number that 2N bit can be
So a*b + c definitely can be represented in 2N bits
Now let's see if 2N-1 bits is enough to represet it.
The maximal number it can present 2^(2N-1) -1
2^(2N) - 2^N - (2^(2N-1) - 1)
= 2*2^(2N-1) - 2^N - 2^(2N-1) + 1
= 2^(2N-1) - 2^N + 1
= 2^N*(2^(N-1) -1) + 1 > 0 // as long as N >=1
So 2N-1 bit is not engouth to represet a*b + c
So the conclusion is '''2N'' bits
There are quite a few methods to judge the balance of tree structure. Like AVL, red-black and so on.
- peter tang October 15, 2012This is a typical question between memory and speed balance. In this case this space is precious.
- allocate 3 words with hits in the moemory
IF word IN top3words list
update the hit in top3words
ELSE IF top3words list HAS EMPTY SEAT
put this word into top3words and set hit as 1
ELSE
count the hit of this word from the beginning of the file
IF (hit > the lowest hit in top3words)
replace with this word and its hit
It requires constant memory but with O(n*n) computation.
Is Longest Increasing sub-sequence different from this quesiton?
- peter tang October 15, 2012It should not matter as long as the string comparison is implemented as if '4' < '5', and atio() does the same thing. Remember that we are not doing assembler.
- peter tang October 15, 2012Your comment is correct if this string is really long.(out of 64-bit can take) But if it is down to that road, the first question to answer to how to store the really large number (data structure) in computer. For instance a number is composed of 1 billion digits. For some meaningful computing some sanity checking is necessary beforehand.
- peter tang October 15, 20121) input name and find phone number
-- Trie structure for name (string), phone number as assocaited value.
-- Or hashtable (name as hash key), and link list as chaining (for name duplicatiion)
2) input phone number and find name
-- hash table
(phone number is unique, so use is as hash key)
4th approach
Count the hits of each character of two strings. Matches then yes.
There is even a more cunning method. Since the comparison of number is the same as the string/ASCII. For instance 46465 < 46546, for string it is also very true that "46465" < "46545" because the ASCII of "5" is more than "4".
So we can append these two string in difference order, the one winning on string comparison wins in integer-conversion.
// StringA and StingB input
std::string combAB = StringA + StringB;
std::string combBA = StringB + StirngA;
return combAB.compare(combBA) > 0? atio(combAB) : atio(combBA);
1) Rear.
As the rear pointer is the pointer can access the top and the bottom of this list in constant time of 1. All other node is depending on the length of this list and its position. The worst case is the front because it needs to go through the whole list to reach the last node.
And enqueue/dequeue is an operation on top/bottom node.
It's a fair comment. But the algorithm still applies because it doesn't use any future information. for loop can be replace with "while (next = file.getNextNumber())"
and the comparison (ARRAY[i] < ARRAY[i + 1])replaced by (cur < next). And late on update "cur" with (cur = next).
As they are not overlapped, so they are stored in the order. A structure having random access will boost the find() algorithm. Depending on how much operations of deleting and inserting a list may/may not used.
- peter tang October 14, 2012For those intersections having overlap they can be split into sub-sections.
For instance, two sections like [1, 5], [2, 4].
Then [1, 5] can be split into [1, 2 - delta), [2, 4], (4 + delta, 5] and apply the same method in my last comment. And the occurrence of [1, 5] is sum of 3 sub-sections.
I guess the intersections should meet ai-1 < bi-1 < ai < bi < ai+1 < bi+1.(i-1, i and i+1 are indices)
So here is an array a0, b0, a1, b1, ......, an-1, bn-1;
For each number x, find the least number that is greater/equal to x. And found and the index (M) is an ODD number (in C/C++ index) then x is located in [a(M-1)/2, b(M-1)/2]. Record the occurrence and find the largest
1. detect delimiter "e" and split to left and right parts
2. then two parts are parsed as
* detect the starting character with "+"/"-"
* call atoi() on the right part
* detect delimiter "." on the left part and split into two sections
* use atoi() on two sections
* the 2nd section times power(10, - 2ndSection.size());
* Then combine them together including the sign.
int ARRAY, ARRAYLEN; // input
int subArrStartInex = 0, subArrLen = 0; // ouput
int tempStartIndex = 0; tempArrLen = 1;
for (int i = 0; i < ARRAYLEN - 1; ++i) {
if (ARRAY[i] < ARRAY[i + 1]){
tempArrLen ++;
}
else {
// a descend detected
if (tempArrLen > subArrLen){
subArrStartIndex = tempStartIndex;
subArrLen = tempArrLen;
tempStartIndex = i + 1;
tempArrLen = 1;
}
}
}
if (tempArrLen > subArrLen){
subArrStartIndex = tempStartIndex;
subArrLen = tempArrLen;
}
It's O(n).
- peter tang October 14, 2012how about hashtable with link-list chaining.
For instance use first 1-3 characters as KEY. And in each entry link-list is used to chaining the words.
Christ, chrome, Christian, ......
use "Chr" as the hash key, and all the word in linked by a list.
Typo checking: not entry found in list, then it's a typo
auto typing: show some of words in this list. (depending on the rules)
int ARRAY, ARR_LEN, KEY; // passed in
int subArrStartIndex = 0, subArrLen = 0, sum = 0;
for (int i = 0; i < ARR_LEN; ++ i){
sum += ARRAY[i];
if (sum < key){
subArrLen ++;
} else {
sum -= ARRAY[subArrStartIndex];
subArrStartIndex ++;
}
}
This is to find one of the longest sub-arrays whose sum is just no less than KEY. And it's O(n).
- peter tang October 14, 2012Suppose two string, stringA and stringB, are integer-convertible.
a = atoi(stringA.c_str());
b = atoi(stringB.c_str());
valA = a * power(10, stringB.size()) + b;
valB = b * power(10, stringA.size()) + a;
return valA > valB? valA : valB;
type conversion operator is especially useful if some mathematics operations are to achieve.
class Foo; //wrapper of double
Foo a;
float b;
Foo c = a + b;
Exactly. C++ does not allow to change the return type of virtual function, which is to keep the line of polymorphisim.
- peter tang October 09, 2012They are based on different memory structure. Hence vector has random-access iterator however list has (bi)directional iterator. For most C++ algorithms they cannot apply to list.
- peter tang October 09, 2012Fundamentally reference can be taken as const pointer. And it is auto de-referenced.
- peter tang October 09, 2012
I started with some really complex node structure and thinking of using tree structure (with pointer to the next and sibling). And think of using recursive implementation to find out a algorithm.
- peter tang November 01, 2012Later it turns out if the output is always the sequence of the order of each number appearing in the list, then the data structure is not really matter.
So come up this solution. The only thing that bothering me is that do some sanity checking of the string. Basically check the brackets appearing in pair. But this is not very difficult.