Associate Engineer

You are given a square matrix of non-negative integers of size 'N x N'. Your task is to rotate that array by 90 degrees in an anti-clockwise direction without using any extra space.

For example:

For given 2D array :

    [    [ 1,  2,  3 ],
         [ 4,  5,  6 ],
         [ 7,  8,  9 ]  ]

After 90 degree rotation in anti clockwise direction, it will become:

    [   [ 3,  6,  9 ],
        [ 2,  5,  8 ],
        [ 1,  4,  7 ]   ]

You have been given two strings “str1” and “str2”. You have to find the length of the longest common substring.

A string “s1” is a substring of another string “s2” if “s2” contains the same characters as in “s1”, in the same order and in continuous fashion also.

For example :

If “str1” = “abcjklp” and “str2” = “acjkp”  then the output will be 3.

Explanation : The longest common substring is “cjk” which is of length 3.

Given a binary tree and two node values, the first one is ‘source’ node value and the second one is ‘destination’ node value. Your task is to find a number of turns to reach from ‘source’ node to the ‘destination’ node.

A turn is defined as rotation in the path from ‘source’ to ‘destination’

For example -

The path from node 1( ‘source’ as blue) to -9 ( ‘destination’ as blue) is shown in the diagram.

All the nodes that come in the path are represented by orange colour.

According to the above path, we take a turn at node 4, node 10 and at node 3 to reach the destination node i.e. -9.

Hence the total number of turns required to reach at ‘1’ to ‘-9’ is ‘3’, return the total number of turns 3.

Note:

1. You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the number of turns required to reach from one ‘source’ node to ‘destination’ node.
2. It is sure that every node value will present exactly once in the binary tree.

Design and develop Virtual memory with the following specificationsThe VM should contain virtual RAM, SWAP RAM.Each process’s pages are stored in the RAM.If the pages do not fit into RAM, insert it to SWAP RAM(Assume SWAP RAM has more memory than RAM and it will never RUN out).The processes here are in the form of strings(not the actual OS process).Show the address translation from the virtual address(logical address) to the physical address.If the RAM is full and a new process comes in, implement an eviction strategy to swap pages from RAM to SWAP memory.I was able to solve the question with the required functionality. Also, note that to clear the 7hour coding round of interviews your grasp on operating system concepts should be good if not expert.Mentors were there to solve all our doubts, they were very helpful. They were evaluating us every 45minutes and based on the progress we were making they were asking us to leave. They gave us initial 45minutes to design the system, data structures, algorithms, block diagrams that we were going to use to develop the system.

Implement a file system structure containing directories and files with optimal file explorer operations(implemented using n-ary tree and hashing concepts)

Design and implement a Least Frequently Used(LFU) Cache, to implement the following functions:

1. put(U__ID, value): Insert the value in the cache if the key(‘U__ID’) is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting the new item.

2. get(U__ID): Return the value of the key(‘U__ID’),  present in the cache, if it’s present otherwise return -1.

Note:

  1) The frequency of use of an element is calculated by a number of operations with its ‘U_ID’ performed after it is inserted in the cache.

  2) If multiple elements have the least frequency then we remove the element which was least recently used. 

You have been given ‘M’ operations which you need to perform in the cache. Your task is to implement all the functions of the LFU cache.

Type 1: for put(key, value) operation.
Type 2: for get(key) operation.

Example:

We perform the following operations on an empty cache which has capacity 2:

When operation 1 2 3 is performed, the element with 'U_ID' 2 and value 3 is inserted in the cache.

When operation 1 2 1 is performed, the element with 'U_ID' 2’s value is updated to 1.  

When operation 2 2 is performed then the value of 'U_ID' 2 is returned i.e. 1.

When operation 2 1 is performed then the value of 'U_ID' 1 is to be returned but it is not present in cache therefore -1 is returned.

When operation 1 1 5 is performed, the element with 'U_ID' 1 and value 5 is inserted in the cache. 

When operation 1 6 4 is performed, the cache is full so we need to delete an element. First, we check the number of times each element is used. Element with 'U_ID' 2 is used 3 times (2 times operation of type 1 and 1-time operation of type 1). Element with 'U_ID' 1 is used 1 time (1-time operation of type 1). So element with 'U_ID' 1 is deleted. The element with 'U_ID' 6 and value 4 is inserted in the cache. 

“If I have 10 bags, where 9 of them weigh 10 gms, and one of them weighs 9 gms. What is the minimum number of comparisons I would need to find the bag with the least weight?”