Software Engineer

Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if the wildcard pattern is matched with the text. The matching should cover the entire text not partial text.

The wildcard pattern can include the characters ‘?’ and ‘*’

 ‘?’ – matches any single character 
 ‘*’ – Matches any sequence of characters(sequence can be of length 0 or more)

You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.

Note:

We cannot use the element at a given index twice.

Follow Up:

Try to do this problem in O(N) time complexity. 

There are 3 ants sitting on three corners of a triangle. All ants randomly pick a direction and start moving along edge of the triangle. What is the probability that any two ants collide?

Given an array ARR of N integers and an integer S. The task is to find whether there exists a subarray(positive length) of the given array such that the sum of elements of the subarray equals to S or not. If any subarray is found, return the start and end index (0 based index) of the subarray. Otherwise, consider both the START and END indexes as -1.

Note:

If two or more such subarrays exist, return any subarray.

For Example: If the given array is [1,2,3,4] and the value of S is equal to 7. Then there are two possible subarrays having sums equal to S are [1,2,3] and [3,4].

You will be given ‘Q’ queries. You need to implement a queue using two stacks according to those queries. Each query will belong to one of these three types:

1 ‘X’: Enqueue element ‘X’  into the end of the nth queue. Returns true after the element is enqueued.

2: Dequeue the element at the front of the nth queue. Returns -1 if the queue is empty, otherwise, returns the dequeued element.

Note:

Enqueue means adding an element to the end of the queue, while Dequeue means removing the element from the front of the queue.

Design a data structure that satisfies the constraints of a Least Recently Used (LRU).

1. Get(int num): If the key exists, it will return the value of the key stored. Else, return -1.    
2. Put(int key, int value): If the key already exists, update the value of the key. Else add the key-value pair to the cache. If the number of keys is more than the capacity for this operation, delete the least recently key used. 

Example:

For the following input: 

4 2
2 1 4
1 1
1 4

We will initialize an empty LRU cache for the first operation with a maximum capacity of 2.
For the first operation, we need to add a key-value pair (1,4) to the cache.
For the second operation, we need to return the value stored for key 1, i.e., 4
For the third operation, we need to return -1, as we don't have any key 4 in the cache.

So, the final output will be: 
4  -1

1. your strengths and weaknesses

2. where do you see yourself in 5 years?