nahidcse05 / elements-of-programming-interviews Goto Github PK

What steps will reproduce the problem?
1. go to project home 
page@http://code.google.com/p/elements-of-programming-interviews/
2. click 'here' @http://imm.io/WliG
3. link is broken

Appreciate the book, plz fix the link.

What steps will reproduce the problem?
1. shared_ptr<node_t<T>> 
2. new node_t<int>{i, nullptr}
3.

What is the expected output? What do you see instead?
the program cannot compile.

What version of the product are you using? On what operating system?
g++ 4.6.3, with -std=c++0x

Please provide any additional information below.
1. add space between the >>
2. add constructor for class node_t, or doesn't use {i, nullptr}

Since all the elements in Q is distinct, we would go into this if statement 
only once, so there is no need and will never update a existed value res twice.

Problem 5.6 specifies that stringToInt should throw an exception if the input 
string does not encode an integer.  "-" does not seem to encode an integer, 
though the stringToInt in Interconverting_string_integer.cpp returns 0 in this 
case.  While a somewhat minor problem, I think it's good to be precise.

I think it might be better for this problem to define explicitly the set of 
strings that have integer representations (e.g. I would choose those matching 
regexp -?[0-9]+ , allowing leading zeros and prohibiting "-").

Patch tested by copying out stringToInt function and using in separate file, 
since main file does not compile with g++ version 4:4.6.3-1ubuntu5 using 
command line "g++ -o int_string Interconverting_string_integer.cpp".

Given the following lesson requests:

9 - 9:30
9:30 - 10
10 - 10:30
10:30- 11
11 - 11:30
11 - 11:30
-----------------
The proposed greedy algorithm will resolve with 3 tutors, but these requests 
can be resolved with 2 tutors only.

Another example that won't work: (need 3 instead of 4)
9 - 9:30
9 - 9:30
9:30 - 10
9:30 - 10
10 - 10:30
10 - 10:30
10:30- 11
10:30- 11
11 - 11:30
11 - 11:30
12 - 12:30
12:30 - 1

=============

One solution would be to greedily assign tutors to current most overlapping 
lesson requests and update all overlap counts after each assignment. 

What steps will reproduce the problem?
1. vector<int> F(A.size())
2.
3.

What is the expected output? What do you see instead?
A.size() is m, but F has n elements, they can be different

What version of the product are you using? On what operating system?


Please provide any additional information below.

1->3->5->7->9    suppose we need to delete  4th element from last i.e '3'  and 
num = 4 initially. after the first while loop, ahead will be at 9 and num will 
be -1 due to which it will enter the if condition and throw exception.

What steps will reproduce the problem?
1. let A = (-1, -1)
2.
3.

What is the expected output? What do you see instead?
0 0
1 3
What version of the product are you using? On what operating system?
newest version
ubuntu 12.0.4, g++ 4.6.3

Please provide any additional information below.
A[j]>=A[j+1] will be out of range, and vector<int> has default value of 0, so 
if A has negative values, it would generate additional increasing subarray.

Some links are broken, such as:

https://github.com/adnanaziz/EpiCode/tree/master/src/com/Intersect_sorted_arrays
3.java

What steps will reproduce the problem?
Try following code with the Queue class:

int main(int argc, char *argv[]) {
    Queue<int> q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);
    q.enqueue(6);
    q.enqueue(7);
    q.enqueue(8);
    // Now head = 0 and tail = 0

    cout<<q.dequeue()<<endl;
    cout<<q.dequeue()<<endl;
    cout<<q.dequeue()<<endl;
    // Now head = 3 and tail = 0

    q.enqueue(11);
    q.enqueue(12);
    q.enqueue(13);
    // Ok till here. Now head = 3 and tail = 3

    q.enqueue(14); // now the vector (data) is resized; but the head and tail (or elements) does not change accordingly. data[tail]=data[3]=14!
    q.enqueue(15);
    q.enqueue(16);
    q.enqueue(17);
    q.enqueue(18);    
    // The elements starting from head=3 are overwriten! 

    cout<<q.dequeue()<<endl;
    cout<<q.dequeue()<<endl;
    cout<<q.dequeue()<<endl;
    cout<<q.dequeue()<<endl;
    cout<<q.dequeue()<<endl;
    cout<<q.dequeue()<<endl;
    cout<<q.dequeue()<<endl;

    return 0;
}

What is the expected output? What do you see instead?

Expected output:
1
2
3
4
5
6
7
8
11
12

The actual output:
1
2
3
14
15
16
17
18
0
0


What version of the product are you using? On what operating system?
Book version 1.2.0
Test on Ubuntu 12.04 with gcc version 4.6.3

Please provide any additional information below.
The resize operation is not correct. The operation appends zeros to the data 
but the existing elements are not rearranged. Also see my comments in the 
testing code.

1, need to include <iterator> to use ostream_iterator
2, the test/explanation example provided in main() is problematic, since the 
integer range is 0-6, then F should be of size 7; Furthermore, the problem does 
not assume |A|=|B|=m=n=|S|, so it is better to use another parameter to let the 
function know "N-1";
3, from my personal viewpoint, the whole explanation is kind of confusing. 
Without working on an example, I do not quite understand what the problem wants 
and what the explanation means...I think, it is better to use input/output to 
clarify. For example, the inputs are simply S, A and B; the output should be an 
array F such that |F|=|S| and F[i] should be the smallest number that is 
equivalent to S[i]. You can also define this as the so-called "weakest" 
equivalence.

I would be interested in an Errata sheet. I just got the book today, and there 
seems to be an error in the introduction. Page 2-3 gives the following 
algorithm description for the introduction problem (stocks, maximize buy to 
sell profit):  "Iterate through 'S', keeping track of the minimum element 'm' 
seen thus far. If the difference of the current element and 'm' is greater than 
the maximum profit recorded so far, update the maximum profit. This algorithm 
performs a constant amount of work per array element, leading to an O(n) time 
complexity."

I believe there's a defect in this method, and that this problem cannot be 
simplified to O(n) time complexity. It is time-consuming to explain where I'm 
coming from, so instead of justifying my claim, I will just ask if you could 
reconsider the solution.

Also, the implementation is missing. For this problem, the book says "Working 
code is presented in Solution 3.3 on Page 181" -- which is not true. Solution 
3.3 on p181 exists, but is talking about 3-dimensional array and robot battery.

Didn't compile on my computer without including <iterator>

Hi 
I am using 1.3.0 version of the book. I recently bought it and have been 
studying the problems. Currently,I am studying Problem 6.4 (1.) "Compute 
Maximum Value of (A[j0]-A[i0]) + (A[j1]-A[i1]), subject to i0<j0<i1<j1".

I could see Problem 6.4(1.) description (book version 1.3.0), but could not 
figure out the algorithm from the description. Could you please provide the 
algorithm here?

Regards
Thameeem

Can you please check that the recurrence for S_i^j is correct? It looks to me 
that it should be 
S_i^j=A[i]+max_{i'<i}B_{i'}^j

building from postorder traversal, so need to judge each elements with root 
which is the last element, not the first element.

What steps will reproduce the problem?
1. Create a text file with string input of variable lengths
2. Run the book solution for 10.2 (pg 288) over the input file

What is the expected output? What do you see instead?
Expected to see sorted strings in output file, instead I see memory addresses.

What version of the product are you using? On what operating system?
1.1.5, Windows 7

Please provide any additional information below.

the lines
for (const T* p : P) {
     ofs << p << endl;
}

shouldn't it be the de-referenced pointer
" ofs << *p << endl; "

otherwise we write out the pointer addresses to file.