Array Creation

Assume the datatype is int32 for the given problem

An input array A of size n is given.
An output array B needs to be created of size k which is defined as

Arr_B= Arr_A + Arr_A[i+1] +... +Arr_A[n-k+i];

Well few Constraints is given:

1) addition of any two elements arr_A[m] and arr_A[n] is expensive.
2) Subtract operation on any two elements sat Arr_A[m] and Arr_A[n] is not supported.

Find the time complexity to create array B and the number of additions in order of n for the creation ?

Hints:

Sliding Window...
This problem seems like you create a window of size n-k and then slide it over the elements of Arr_A to to produce Arr_B.

Decode

Problem:

You are given a mapping of alphabets to a particular code. The code is in 1s and 0s. For example

a - 1101
b - 01
c - 1000

The minimum size of this code is 1 and the maximum is 4.

You are now given a string to encode using the mapping above. For example abc is the input string. The encoded form should be 1101011000. This form can however be decoded to a variety of output strings. With the mapping in place, perhaps this encoded word can be interpreted as xrt instead of abc where x=110 r=1011 and t=000.

Given these requirements how do you write a function that returns the maximum possible number of strings that can be interpreted from the encoded string ? The output string must be of the same length as the input string.

Test case:

Let us say 1101011000 can be decoded to abc , xrt and repp. The program should output '2' since there are 2, 3 letter strings that can be found from the encoded string. Any string whose length is greater or lesser than the original string is not counted.

Hint: -> You can recursively backtrace when you dont have a match.

Hint: -> Look at the test cases carefully when programming the solution. Brute force will work.

Visualization of the solution:



You can traverse through each solution by branching from one alphabet to the next.





What changes must be made to the program in case duplicate letters are not allowed ?

How can the solution be optimized and when does the program know which branch to stop looking in ?

Horses on Induction

Theorem. All horses are the same color.

Proof. Induct on the number of horses. Base case: 1 horse. Clearly with just 1 horse, all horses have the same color.

Now, for the inductive step: let's show that if it is true for any group of N horses, that all have the same color, then it is true for any group of N+1 horses.

Well, given any set of N+1 horses, if you exclude the last horse, you get a set of N horses. By the inductive step these N horses all have the same color. But by excluding the first horse in the pack of N+1 horses, you can conclude that the last N horses also have the same color. Therefore all N+1 horses have the same color. QED.

Q. Where is the flaw in the induction argument ?

Clue: Double - check the induction argument at a specific case, P(2) => P(3). Strong induction ?

More questions:

Is there anything else besides the above mentioned problem in the induction argument ?

Ant Problem

The noted gourmet Pangolini Aardvark is preparing a late night snack of "Ant au Chocolat" and "Ant au Fromage". This requires the use of a five foot pole. One end of the pole is over a bucket of melted chocolate and the other is over a bucket of melted cheese.

Pangolini sprinkles some ants onto the pole. They immediately start scampering along the pole in random directions. If two ants run into each other then they both instantaneously reverse their directions and are now moving away from each other. An ant can change direction many times. Eventually, all of the ants will fall off one or other end of the pole. If each ant travels at a speed of one inch per second, what is the maximum time until all ants have fallen off?

Suppose now that n ants are placed on a circle of five foot circumference and randomly choose their direction of travel and again reverse direction when they bump into each other. One of the ants is named Alice. What is the probability that Alice is back where she started, one minute after the ants start their scampering.

Back to the pole. Alice starts in the middle of the pole. There are n other ants placed randomly on the pole and they start scampering in random directions. Alice has a cold. When an ant with a cold bumps into another ant, the uninfected ant catches a cold too. What is the expected number of ants who catch cold before they all fall off the pole?

Clue:

This one is vague but very much relevant - What happens in an elastic collision of identical balls ?

level order tree traversal

How would you print out the data in a binary tree, level by level, starting at the top?

Clue:

How about using a Queue. Relate to Dijkstra's SP algorithm.

typrewriter Gib

On April 1st a typist found the hammers of the typewriter resoldered in an arbitrary order, so typing a text resulted in gibberish. The typist decided to type a document in its entirety using this typewriter. Afterwards, if the result does not represent the original text, he will type the result, and so on. Prove that the clear text will emerge sooner or later. How many iterations are enough to guarantee that the clear text will appear, if the typewriter has, say, 46 keys? N keys?

Clue:

Why does it say April 1 ? Is the question poser trying to trick you in deep stuff ? May be. But you can take it to a suitable point and then leave to the crazy math guys.

To take it to the suitable pt:

Decompose a number into such constituents such that the LCM of the constituents is maximized। Think prime! Pray Riemann !

Find the previous alphabet.

khanji has a LOT of characters in their alphabet and are using a way of compressing it so that the most common characters are 1 byte and the less common are 2 bytes. If it's a '1 byte' character, it starts with a 0, If it's a 2 byte character, it starts with a 1. If you're at a particular character (at the beginning), how do you find where the previous character begins?

Now this is an interesting question.
Let the currect char be c (irrelevant), and the first bit of every previous byte be denoted by 1s, 2s....etc.

Some hints:
1. If 1s = 1, then previous char is 2 byte long.
2. If 1s = 2s = 0 then ??
3. If 1s = 0 then all (2...n)s = 1 then the problem is undecidable until you hit
a 0, in which case the answer is ??

DP - max subset of dominating pts.

A DP one.

Q. Consider that you have n 2D pts. Find the largest set of pts such that when sorted (by either axis) produce the same sequence.
Okay, the exact wordings of the original problem -
A circus is designing an act consisting of a tower of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower?

My thoughts -
Sort the pts by say x axis co-ordinates. Then the problem reduces to finding the longest increasing subsequence ( or longest decreasing subsequence Note: we hae to consider both ) in y axis co-ordinates. this is a std DP problem.

More questions :
1. Will it produce the same answer when first sorted in y axis co-ordinates. Or we have to do the both and then take the one of max-length ?

2. How would you generalize the problem to pts coming from dimension d > 2. Need to think over that.

An aside :
See if you could relate some parts of the above problem to the following problem.
Given any sequence of mn+1 real numbers, some subsequence of (m + 1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.

ugly numbers

I lifted it from the career cup site
Design an algorithm to find the kth number divisible by only 3 or 5 or 7. That is, the only factors of these numbers should be 3,5 and 7.

What I have in mind -

Generating the numbers which have prime factors as only 3,5, 7 is not a big thing. but doing so in a sorted order is a little tricky.
Let's call the exponents of 3,5,7 as a,b and c repectively.
Claim: The order of numbers with a = b = c = n to a = b = c = n+1 would be unchanged for any n >= 0.
And that gives an idea to program it. We have to find an order between to successive exponents. Lets start with n = 0. Then we have to find all the numbers ordered ( with their exponents known ) less than 105 ( 3*5*7 ) and greater than 1.
Way 1 -
Write a program to generate all the numbers which are factors of 3 or 5 or 7 ( with their factors recorded. And then keep increasing these factors...
For exp if the factors have exponents (a1,b1,c1), (a2,b2,c2)....(am,bm,cm). then the next cycle of increasing numbers will have exp ( a1+1, b1+1, c1+1 )....(am+1, bm+1, cm+1).
Way 2 -
Generale the numbers thru' the exp. Its clear that they are upper bounded, for n = 0, as a < 5, b < 3, c < 3. So 3 for loops and get all numbers which fall below 105, get their corresponding exp and thats it.

Marble / Egg drop

Problem:

You have a staircase and 2 eggs. The staircase is N steps long. You can drop eggs on this staircase at any point between 0 to N. At a point X on the staircase where X >0 and X < N the eggs begin to break. Your mission, if you choose to accept it, it to find the point X in this staircase by making a minimum number of drops.

O O Step 0
|_
...|_
.......|_
..........|_ - The random point X where the egg breaks
..............|_
..................|_

Analysis:

Solution 1: Ugly

The easiest thing to do is to drop the egg at each step and check if it breaks. The worst case running time of such an algorithm is O(N). However there must be a reason we have 2 eggs to solve this problem. So obviously this is not the optimal solution. Lets think a little more.

Solution 2: A lil better

What can we do to use both the eggs ? Hmmm... Lets do this. Take egg 1 and drop it on odd steps. If it breaks then take the other egg and break it on the last even step before the step where egg1 broke. That is if egg 1 broke at step 5, drop egg 2 on step 4 (last even number before 5). If egg 2 breaks then you know that point is X (since the egg did not break at N=3). If it does not break then you know X is the number where egg 1 broke.

The efficiency of this solution is O(N/2) ~ O(N). But we can do better

Solution 3: I will leave it to you to figure this one out

Its possible to have an efficiency of something better than O(N) for this problem. With the last solution the egg can be dropped at odd intervals. What if we can drop the egg at an interval Z ? How will that help us determine the value of X ? Think about that. How should egg 2 be dropped so that for any interval Z, the value of X can be ascertained.

Performance:

To determine the performance for solution 3, consider making an equation F(Z). F(Z) is a function that determines the number of times (worst case) an egg must be dropped to determine the value of X.

Hint: F(Z) contains 2 component. One that is relevant before egg 1 breaks and one that is relevant after egg 1 breaks.

Once you have this equation in place you can determine the best running time for the worst scenario quite easily.

Hint: Differentiation. F(Z)' and F(Z)''.

This problem can be used to solve some practical difficulties. For example you know that you are to receive a 1024 bit number whose values you must calculate. You know that this number is formatted like so 0000000001111111... but you dont know where the 1s begin. This is like the staircase problem. Applying solution 3 can save time and allow you to quickly calculate the 2nd power of the 1024 bit number.

What sorting algorithm does Makefile use?

Most of us know what a makefile is.
It has instructions for creating the a.out file.

If you're new to makefiles, you might want to read this before proceeding further.
So, let me get to the point here.
We write rules on how to compile the programs of the form

target : dependencies
commands

If we see the whole story, the make file produces the target based on dependencies, IN ORDER.
Can you relate this to any algorithm?
Think... What algorithm relates events to happen in a definite sequence to produce the output?

Answer: Topological sort
Think about it. The dependencies are compiled in order.
Lets look at an example.
out : main.o sort.o
gcc -o out main.o sort.o

main.o : main.c
gcc -c main.c

sort.o : sort.h sort.c
gcc -c sort.c

the rule main.o has to be dealt with.
This in turn will compile main.c if:
1: main.o didn't exist.
2: main.c was modified after creation of the previous main.o

Similarly, sort.o will have to be dealt with to produce sort.o
Then, both the main.o and sort.o files will be combined to produce out which can be run using ./out

Rational Pirates (really ??)

k, somebody sent me this question and a quick googling gave me this wikipedia link to the question itself. The question

There are five rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them.

The Pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E.

The Pirate world's rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates should then vote on whether to accept this distribution; the proposer is able to vote, and has the casting vode in the event of a tie. If the proposed allocation is approved by vote, it happens. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again.

Pirates base their decisions on three factors. First of all, each pirate wants to survive. Secondly, each pirate wants to maximize the amount of gold coins he receives. Thirdly, each pirate would prefer to throw another overboard, if all other results would otherwise be equal.

Wiki link - http://en.wikipedia.org/wiki/Pirate_game

Assuming the reader has read just the question, let me proceed further by strengthening it. What strategy should A employ that he doesn't get thrown overboard ?
Clue: Why not try this with a smaller number of people and then increase to see if it proves to be any helpful.
If n = 2, (say D and E ) are there. Then D obviously splits it as 100:0. So E will always attempt to never reach this situation where only 2 people are left out.
Consider n = 3. C knows that E would not want to in a situation with n = 2, so he would vote for me with any bare min payoff. So he would splits it as 99:0:1.
Now consider n = 4. B clearly knows that D would not want n = 3 situation and by same reasoning would split it as 99:0:1:0 ( note : In this case the casting vote would rule as C and E will vote against the proposition ).

Do you see a pattern readers. Plz note the flipping payoffs. And this is how A would split 98:0:1:0:1.

Easily generalizable. Solved.

Better still, they should all be given swords to finish it off, say, in more pirately manner.