Software Engineer

You are given an N-ary tree where every node has at most ‘N’ child nodes. You need to first serialize it and then deserialize the serialized tree.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

In simple words, serialization is a process to store a tree in a file so that it can be later restored to its original form. Deserialization is reading the tree back from the file.

Note:

Note that the structure of the tree must be maintained while serialization and deserialization. Also, you can use any method to serialize or deserialize the tree. You just need to see that the tree can be serialized into a string and further deserialized into the original tree.

Design a data structure that stores a mapping of a key to a given value and supports the following operations in constant time.

1. INSERT(key, value): Inserts an integer value to the data structure against a string type key if not already present. If already present, it updates the value of the key with the new one. This function will not return anything.

2. DELETE(key): Removes the key from the data structure if present. It doesn't return anything.

3. SEARCH(key): It searches for the key in the data structure. In case it is present, return true. Otherwise, return false.

4. GET(key): It returns the integer value stored against the given key. If the key is not present, return -1. 

5. GET_SIZE(): It returns an integer value denoting the size of the data structure. 

6. IS_EMPTY(): It returns a boolean value, denoting whether the data structure is empty or not. 

Note :

1. Key is always a string value.
2. Value can never be -1.

Operations Performed :

First(Denoted by integer value 1):  Insertion to the Data Structure. It is done in a pair of (key, value).

Second(Denoted by integer value 2):  Deletion of a key from the Data Structure.

Third(Denoted by integer value 3): Search a given key in the Data Structure.

Fourth(Denoted by integer value 4): Retrieve the value for a given key from the Data Structure.

Fifth(Denoted by integer value 5): Retrieve the size of the Data Structure.

Sixth(Denoted by integer value 6): Retrieve whether the Data Structure is empty or not.

On an Island, there is an airport that has an unlimited number of identical air-planes. Each air-plane has a fuel capacity to allow it to fly exactly 1/2 way around the world, along a great circle. The planes have the ability to refuel in flight without loss of speed or spillage of fuel. Though the fuel is unlimited, the island is the only source of fuel. You can ignore the time and fuel consumption of refuelling.
What is the minimum number of air-planes required to get one air plane all the way around the world assuming that all of the air planes must return safely to the airport?

You are given a path to a file/directory in Unix-style of length N, In a Unix-style file system, a dot(.) refers to the current directory. A double dot(..) refers to the previous directory in reference to the current directory. If there are multiple slashes between two directories you should consider it as a single slash.

Now, for a given directory path as a string, you are required to simplify the same and tell the final destination in the directory structure or the path.

The simplified path should always begin with a slash(/) and there must be a single slash between two directory names. There should not be a trailing slash.