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 ??