Meta Interview Questions

Meta Interview Questions for Intermediate

 Q11. You are given a root of a Binary tree. Now, convert the binary tree to a doubly linked list so that the provided order of the doubly-linked list is the same as an inorder traversal of the provided binary tree.

More Explanations from the interviewer  After conversion, the node's left pointer should point to the Doubly Linked List previous node, and its right pointer should point to the list's subsequent node. Before reading the answer and Algorithm, try it yourself.

Suppose the Binary Tree is given like as shown. 

According to the question, the final doubly linked list will look like this. 

An in-order traversal involves visiting the left subtree first, then the root, and finally the right sub-tree.

Creating an empty, doubly linked list at the beginning is one quick solution to this problem. Continue adding each element output into the doubly linked list as you traverse the binary tree in order.

But, the interviewer wants us to transform the binary tree to a doubly linked list in place, which means we shouldn't add any new nodes to the doubly linked list. If we carefully read the question, though.

This is one of the most asked Meta Interview questions.

So here comes the divide and conquer approach using recursion 

Algorithm 

• Recursively solve left and right subtrees by starting with the root node.
• Once the left and right subtrees at each step have been processed 
• Merge the left subtree's output with the root to create the intermediate outcome.
• To create the final result of the current recursive call, combine the intermediate result (created in the preceding step) with the output from the right subtree.

Time Complexity- Linear, O(n)

Space Complexity-  Linear, O(h)
 

Q12. Converting all the Decimal Numbers lying between 1 to 3999 to Roman Numerals.

This question is considered to be a below medium-level question. Given a number, find its corresponding Roman numeral. 

Example 

Input  

10

Output  

X

Input  

40

Output  

XL

Below is the list of some known roman numerals conversions. We shall use these values for conversion.

The logic is to separately convert the number's units, tens, hundreds, and thousandth places. If the digit is 0, no Roman numeral symbol is used to represent it. Numbers 4 and 9 convert slightly differently than other digits because they follow subtractive notation.

Algorithm 

The given number should be compared to the following base values  1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, and 1 provided in the above image. 

• The initial base value (biggest base value) will be the base value that is just smaller than or equal to the specified number. The remainder becomes the number for further division and repetitions once the number has been divided by its largest base value. 
• The corresponding base symbol will then be repeated a quotient of times. Up until the number reaches zero, the operation will be repeated.

3261 divided by 1000, the quotient is 3, with 261 as the remainder. Three times the corresponding symbol M for quotient will be used.

Now that Remainder is greater than 0. We call the function once again.

261 divided by 100, the quotient is 2, with 61 as the remainder. Two times the corresponding symbol C for quotient will be used.

Now that Remainder is greater than 0. We call the function once again.

61 divided by 50, the quotient is 1, with 11 as the remainder. One time the corresponding symbol L for quotient will be used.

Now that Remainder is greater than 0. We call the function once again.

Since 11 is greater than 10, 11 divided by 10, the quotient is 1, with one as the remainder. One time the corresponding symbol X for quotient will be used.

Now that Remainder is greater than 0. We call the function once again.

But the remainder is one, and one is present in the list of value-symbol. Hence we add Ɪ for it.

Now the roman conversion for 3261 is  MMMCCLXꞮ.
 

Q13. Given an array of daily stock prices consisting of integers, return the buy and sell prices for making the maximum profit out of given conditions.

The profit from a single buy and sale must be maximized. If we cannot turn a profit, we will work to limit the damage. The buy (green) and sell (red) prices for the instances below are emphasized to maximize profit. This is one of the most asked Meta Interview questions.

• The values in the array represent the cost of stock each day. We must determine the ideal purchase and sell prices at which our profit (or loss) is maximized (or reduced) over a specific period of time because we can only buy and sell the stock once.
• Finding the most significant gain between each element and its consecutive elements is a naive solution with a runtime complexity of an O(n^2).
• This problem has a complex linear solution, where we cycle through the full array of stock prices while keeping the current buy price (which is the smallest value observed so far), current profit, and global profit.

Algorithm  

// Algorithm
current_buy = stock_list[0]
global_selling = stock_list[1]
global_profit = global_selling - current_buy

for i = 1 to stock_list.length
 current profit =stock_list[i] - current_buy
 if current_profit is found to be greater than global_profit
   then update the global_profit to current_profit and update global_selling to stock_list[i]
 if stock_list[i] is less than current_buy
   then update current_buy to stock_list[i]

return global_profit and global_selling

Time Complexity- Linear, O(n)

Space Complexity- Constant, O(1)
 

Q14. What happens when you enter "www.google.com" in the web browser?

The steps being taken are listed below. 

• Whether the content is new or already cached, it will check your browser's cache first to see if it is present, and then it will still display.
• If not, the browser checks to see if the IP address of the URL is already cached (by the browser and OS); if not, the browser asks the OS to do a DNS search using UDP to obtain the URL's matching IP address from the DNS server and create a new TCP connection.
• The browser and server establish a new TCP connection through three-way handshaking.
• TCP is used to establish a connection and send an HTTP request to the server.
• Incoming HTTP requests are handled by the web servers running on the servers, which then send out the HTTP response.
• The web servers installed on the servers respond to incoming HTTP requests.
• When the server's HTTP answer is processed by the browser, the TCP connection may be closed or used again for further requests.
• Browsers cache the response data if it is cacheable.
• The browser renders the content after decoding the response.
  You can also read about Azure Data Engineer Interview Questions here.

Q15. Explain Caching? Explain two cache update strategies available in caching?

Caching is a practice of keeping copies of files in a temporary storage space referred to as a cache, which facilitates faster data access and lowers site latency. Only a certain amount of data can be kept in the cache. Because of this, choosing cache update solutions most suited to the organization's needs is crucial. This is one of the most asked Meta Interview questions. The different caching techniques are as follows. 

Cache-aside

In this approach, it is up to our program to write to and read data from the storage. The store and the cache do not directly interact. In this case, the program searches the cache for an entry before retrieving it from the database and adding it to the cache for later usage. A program that uses this update method is Memcached.

The cache-aside approach, also known as lazy loading, merely caches the requested entry, preventing unwanted data caching. The following are a few drawbacks of this tactic. 

• When a cache miss occurs, there will be a significant delay since data must first be fetched from the database before caching.
• If data is updated in the database, it is more likely to become stale. This can be minimized by forcing an update of the cache entry with the time-to-live argument.
• The increased delay occurs when a cache node fails and is replaced by a new, empty node.

Refresh-ahead

Using this technique, we may set the cache to automatically renew the cache entry before it expires.

If this caching approach can correctly forecast the things that will be required in the future, latency is decreased drastically.

For more information, you can refer to this dedicated blog on caching.
 

Q16. What do you understand by (CDN) Content delivery network?

A network of globally dispersed proxy servers known as a "content delivery network," or CDN for short, serves content to users from places close to end-users. Static items, including HTML, CSS, JS files, pictures, and videos, are typically provided from CDNs in websites.

Using CDN in delivering content helps to improve performance 

Users don't have to wait long because data is delivered from nearby centers, as seen in the graphic above.

As some of the burdens are shared by CDNs, the load on the servers is decreased immensely.

There are two different kinds of CDNs.

Push CDNs

In this case, the content is delivered to the CDNs whenever the server makes updates. We are accountable for uploading the content to CDNs. Only when content is changed or added to the CDN is it updated, maximizing storage while minimizing traffic. Push CDNs generally perform effectively for websites with low traffic or material.

Pull CDNs

In this case, when the first user requests the content from the website, new content is retrieved from the server. As a result, initial requests take longer to complete until the content is stored or cached on the CDN. Although these CDNs use the least amount of space possible, when outdated files are pulled before being modified, it can result in redundant traffic. Websites with high traffic volumes perform well when pulled CDNs are used.
 

Q17. You have been given two singly Linked Lists, each representing a positive number without any leading zeros.

Now, Your task is to add these two numbers and print the sum in the form of a linked list.

Before understanding the solution, Try to solve this Question.

Algorithm

• If one linked list has fewer digits than the other, iterate across the two linked lists to add any preceding zeros.
• Call a recursive function to access the following nodes starting at the head node of both lists.
• Continue till the last item on the Linked list.
• Returns the carry after creating a node for the current digits' sum.

Read our dedicated blog on Adding to Linked List.
 

Q18. You are given the address of a node in a connected undirected graph containing M edges and N nodes. Now, you must return a clone of the provided graph, which is nothing but making a deep copy. Each graph node contains an integer "data" and an array of its neighbor nodes.

We must traverse a graph to copy it. We will take advantage of the BFS graph traversal. Each node in a graph must be copied in order to be duplicated. However, the same node should not be copied more than once. A mapping from an original node to its copy is therefore necessary.

This is one of the most asked Meta Interview questions. That’s why, Before moving on to the Algorithm, Try this question.

Algorithm

• To prevent repeating copies of the same node, we must maintain track of the visited/cloned nodes. As a result, a HashMap is needed to keep track of all the nodes that have already been constructed. Whereas in the HashMap, the original node's address is stored in the key, and the copy node's address is stored in the value.
• Now, a queue for BFS traversal and a hash map that maintains track of all the nodes that have already been built are being created to reach each node and its neighbors.
• Create a new node that corresponds to the reference node provided, insert it into the hash map, and that node will be marked as visited.
• Repeat the steps below until the queue isn't empty, then push the provided reference node into the queue.
• Pull the front node out of the queue, visit all of its neighbors, and then determine whether a new cloned node has already been generated for each neighboring node (check it in the HashMap).
• If it wasn't generated, make a new copy of the neighbor node that corresponds to it, add it to the hash map, and put it into the queue as well.
• Now add the cloned neighbors to the cloned node's list of "neighbors."
• Return the source node of the copied graph when the queue is empty.

For more, read our dedicated blog on this question.
 

Q19. What is MVC(Model view controller), and how does it work?

The Model-View-Controller (MVC) architectural pattern divides an application into three logical parts: model, view, and controller. These parts are all made to handle particular phases of application development.

The controller receives the request first, chooses a suitable view, interacts with the model, who then communicates with your database and sends the controller the response. The controller then provides the output parameter to the view based on the response.

Read out Dedicated Blog on MVC Architecture
 

Q20. What is a Gateway in Computer networking?

A firewall, server, or router are examples of hardware devices that act as gateways between networks. It makes it possible for traffic or data to move between networks. A gateway is a node that guards the other nodes in the network by residing at the network's edge. Every piece of data that enters or leaves the network must transit through the gateway node. A gateway can also transform data from an external network into a format or protocol that all devices on the internal network can understand.

Click here to know about Html interview questions here. 

Meta Interview Questions for Experienced

Q21. Serialize a given Binary Tree to a file and then Deserialize it back to a normal tree so that the provided original and the later deserialized trees are identical.

Understand the terms here,

Serialize means writing of the tree in a file.

Deserialize means reading from a file and reconstructing the tree in memory.

You can serialize a stream in any effective format since there are no restrictions on the format of a serialized stream. However, the tree should resemble the original tree exactly after being deserialized from the stream. This is one of the most asked Meta Interview questions. Think of the tree below as the input tree.

The serialization and deserialization of the tree can be done in various ways. One method is to serialize individual nodes to the stream while performing a depth-first traversal. Here, we'll employ a pre-order traversal. To aid in deserializing the tree, we'll also serialize some markers to represent a null pointer.

As an illustration, think about the binary tree below. This tree now has markers (M*) to signify null nodes. The number associated with each marker, such as 1 in M1 or 2 in M2, denotes the marker's location within the stream.

Here is the serialized tree (pre-order traversal) from the above example 

While deserializing the tree, we'll again use the pre-order traversal, and at this time, we will create an entirely new node for every non-marker node(not marked with M*). And encountering a marker node indicates that it was a null node.

Time Complexity  Linear O(n)

Space Complexity  Logarithmic, O(log(n))
 

Q22. Design a URL shortener.

In order to create shorter aliases for lengthy URLs, URL shortening services like bit.ly and TinyURL are pretty popular. You must create a web service that, in response to a long URL entered by the user, returns a short URL; conversely, in response to a short URL entered by the user, the service returns the long URL entered by the user. We have a dedicated blog for the step-by-step guide to designing a URL shortener. Designing various products and scaling is considered to be a hot topic for Meta Interview questions.

Please read our blog for a step-by-step guide to learn Design a URL Shortner.
 

Q23. Design a Recommendation System.

The most recent system design interviews for major tech companies frequently include the subject of how to develop a recommendation system. It's easy to understand why. Over the past few years, recommendation systems have gained significant importance. Several businesses, like Amazon, Netflix, YouTube, Hulu, Instagram, and others, have systems for recommending various options to their users. To propose the most pertinent content to each user from a vast bank of content, various algorithms are employed to detect trends in the types of data users use on the application.

Here are some of the dedicated blogs for Recommendation system designing.

Recommendation system using ML

Recommendation Engine

System Design Essentials
 

Q24. Implement strStr() using an efficient method.

By asking this question, the interviewer just wants to know your understanding of strings and the KMP algorithm.

To understand the question in more depth, visit our dedicated section on Code Studio Question Link.

Algorithm 

• If the length of string 2 is less than that of string 1, then we simply return -1.
• Now let’s denote the length of string1 as M and the length of string2 as N.
• Now, we run a loop from 0 to N - M, and for each index i in the range of 0 to N - M, we run another loop from 0 to M. Let's denote this inner loop counter as j.
• Then match the characters at (i + j)th index of a string with (j)th index of string1. If characters mismatch at any point, we break the inner loop and increment i by 1. If all these characters match, and we are out of the inner loop, then we return i, as it is the index of the first occurrence of string1 in string2.
• If we reach the end of the outer loop, then we return -1, as string1 is not present in string2.

Q25. What are the different types of design patterns in Java?

There are three types of design patterns. They are:

Creational Patterns- By concealing the logic, these patterns offer the flexibility to choose how to create items. The created items are independent of the working system. Factory design pattern, Builder design, Prototype design, Singleton design, and Abstract Factory design are a few examples of creational patterns.

Structural patterns- These patterns aid in specifying how the composition of classes, interfaces, and objects should be defined by the structures of the classes and objects. The Adaptor Design, Facade Design, Decorator Design, Proxy Design, etc., are a few instances of structural patterns.

Behavioral Patterns- These patterns aid in outlining how the items should talk to one another and interact. Command pattern, Iterator pattern, Observer pattern, Strategy pattern, etc., are a few examples of behavioral patterns

Design-related questions are considered to be the most asked Meta Interview Questions.

We have a dedicated blog for Sofware Design patterns to learn more about design parameters.

Conclusion

In this article, we have extensively discussed the Interview questions that are being asked in Meta and found that the interview's primary focus is on Advanced-Data structures and System Design.

See Top Questions for PBC, Interview Bundle to learn about such interview questions.

You can also check out Facebook Interview Experience to learn about Facebook’s hiring process.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses, refer to the mock test and problems; look at the interview experiences and interview bundle for placement preparations.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!