Antonio Gulli's coding playground

A suggestion for facebook: Can I post my message in multiple languages and you route it according to the reader? Today everyone who is living in a non-English country has always English speaking friends and so you never know what language to adopt because you want to respect your multiple readers

In other words, a type of circles based on languages. This time useful

[フレーム]

a scientific and rigorous methodology adopted by the industry and academia

How to make it scalable?

What technologies would you adopt? how to make it scalable?

This is a typical problem of recursion.

The diameter of a tree is the number of nodes on the longest path between two leaves in the tree. So you can compute it as the max among the height for the left subtree, the height of the right subtree and the longest path between two leaves passing through the root.

This is certainly linear, but how can you minimize the #of comparison.

Hint: think about the way we build an heap.

You are the manager of an airport and have a collection of N airplanes arriving at time a(i), leaving at time l(i) and paying p(i) for occupying one of the available K runaways (where K is << N). Write a program for maximizing your gain in terms of money. Write a program for maximizing the usage of the K runaways.

Bing News is now in Germany, Spain and Italy too!.

How many different ways do you have for spelling Gaddafi? It's Gaddafi in English and German, but it is Gheddafi in Italian and Gadafi in Spanish.

You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once. Fastest way to find that single integer

Solution

First thing that I was considering is to use XOR, because x^x = 0 so all the numbers that are replicated 2 times will be deleted and the unique number that is not duplicated will stay there. But here the numbers are duplicated 3 times and x^x^x=x so this would not help. We can remove items that are duplicated a even number of times.

So we need an alternative way based on logic operations. For each element A[i]

1. get elements that appear 1 time -> ones =^x; (remove)
2. get elements that appear 2 times -> two |= ones & x; (needs to be before previous remove operation)
3. get elements that appear 3 times -> three = ones & two
4. get elements that not appear 3 times ~three
5. remove the one not appearing 3 times from one and two -> one &= ~three; two &= ~three

The problem requires to find the maximum area of a rectangle containing an histogram, given N histog

Solution

If we insert the histogram i, then the rectangle can have height h(i) or larger, because the rectangle must contain the histogram i with height h(i). If we insert the histogram i then we need to look to the left j \in [i-1 .. 0] for adjacent histograms with h(j) > h(i), say those are l(i). If we insert the histogram i then we need to look to the right j \in [i+1 .. n] for adjacent histograms with h(j) > h(i), say those are r(i). These two steps will give us the basis b(i) of rectangle R_i with height h(i) containing the histogram i. In particular b(i) = l(i) + r(i) + 1, and the area for rectangle i will be a(i) = b(i) * h(i). So the final answer would be A = max_i a(i) which can be computed in O(N)

So the main problem is how to compute l(i) and r(i). If we take O(N) then the final outcome would be quadratic. We need a solution in O(1). Can you make it?

Two problems;




2. Given a number, generate all the strings that can be obtained with that number on a telephone keypad

Solution

Trivial recursion, just pay attention to space allocation.

This is a classical problem, quite frequently asked in interviews. Given an array find the majority element. How about a stream?

Solution

There is a trivial O(nlogn) solution based on sorting and counting, but you are not using the majority propriety.

There is another solution based on hashing, but you are not using the majority propriety and this will not work on streams because you cannot bound the hash table.

The majority element will appear by definition on more than 50% of elements. So you can maintain a variable with the current element and another variable with the current counting. When you see the same element you increment, when you see another element you decrement, when you reach zero then you change the current element. In this way, if there is a majority element you will identify it in the current element variable.

What happen if there is no majority element? will you have a false positive?

How to adapt the above principle to a stream?

The cables are 10 KM in length and both ends of each wire are out in open. Label all the cables with minimum number of trips.

Solution.

The key intuition here is that you have 2 sources of information. Either the cables are connected or they are disconnected ;-). so you can connect all of them but leave two of disconnected or connect just two of them. if you leave 3 disconnected than you have an ambiguity and you need a round trip for solving this for just 3 cables. That's a lot

Let's try to leave just 2 connected. You need 1 round trip to identify the pair and so a total of 60 trips. That's a lot.

Let's try to connect all of them but leave 2 disconnected marking them red and blue. In one trip you find the disconnected pair and can name them #1 and #120 (any number works here provided that you remember it for the next step). All the other cables will be numbered from #2 to #119. Here you can encode another information just by leveraging the order. You assign to a cable #2 and to the one connected to it #3. Then you assign to another cable #4 and to the one connected to it #5, and so on and so forth (*).


Now Let's try to connect again all of them and leave 2 disconnected. This time we will split the disconnect pair and connect one cable of them. So assume we connect (#1, #2 ) (#3, #4) (#118, #119) and leave #120 disconnected (**)

Return to base. We have red and blue. But we know that one of them must be disconnected and we know that the disconnected one has number #120, while the other one must be #1. That' why we broke the pair because we wanted to solve the ambiguity a (disconnection is not ambiguous when there is just one disconnected). So now we know what is #1 and what is #120.

Surprisingly enough we are done! because we know that the other side has (#1, #2 ) so we know #2 is the one connected to #1 and we can test what is connected to #1. But when we know the #2 then we know the #3 because of the naming convention adopted here (*), and if we know the #3 then we know the #4 because of the choice taken here (**).

Talking about encoding information.

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

Solution:

this looks like a Dynamic Programming problem. Say M(i, j) is the maximum when there are the coins from i to j available. In this case I have 2 options.

Pick from A[i], so i get value A[i]. The other player takes either A[j] or A[i+1] leaving me the options either for M(i+1, j-1) or M(i+2, j). The other player will try to minimize my gains so he will chose min(M(i+1, j-1), M(i+2, j))

Pick from A[j], so i get value A[j]. The other player takes either A[i] or A[j-1] leaving me the options either for M(i+1, j-1) or M(i, j-2) and again the other player will try to minimize my choices min(M(i+1, j-1), M(i, j-2))

I select the two above trying to maximize my ROI, so the total formula would be

max (A[i]+min(M(i+1, j-1), M(i+2, j)), A[j]+min(M(i+1, j-1), M(i, j-2)))

Pretty cool isnt'it?

Standard memoization is suggested

A long array A[] is given to you. There is a sliding window of sizewwhich is moving from the very left of the array to the very right. You can only see thewnumbers in the window. Each time the sliding window moves rightwards by one position. Produce an array B[], B[i] is the maximum value of from A[i] to A[i+w-1]

Solution


- a naive solution is O(n w)
- an heap based solution could be O( n lg w), but we need to change the heap for maintaining n-w max positions and invalidate when the windows move. too complicated and not sure we can make it


- we can maintain a queue or better a dequeue while processing the array. The size of the queue Q is w and the key observation is that when we see an element A[j] we can remove each element in Q such that A[j] > Q[z] because we are looking for the max and those elements are not max given the esistence of A[j]. In doing so, we keep the current maximum at front and we remove the other elements from the back of the deque. Each element will enter 1 time in the queue and will exit at most 1 time, so the total complexity is O(n) which is pretty good. For keeping the sliding window we push current Array index so we need to remove from front when out of current window

You have n types of items, where the i^thitem type has an integer size s_iand a real value v_i. You need to fill a knapsack of total capacity C with a selection of items of maximum value.

[フレーム]

Pretty educative talk by the way of Google guys.

I like this question because it forces you to think about recursion, visit of a tree and how to change pointers

Find if any subtree of a binary tree has sum equal to given value. Subtree may or may not start from root.


Hint: solve the one with substree starting from root first.