11 weeks ago

Rohit • 610

Hyderabad

Avg CTC: 12lpa

Role: Software Engineer

Job Link: Software Engineer Role

Question 1

Given a string which is a random combination of a b and ? ; where ? can be either a or b

You need to return a string by replacing ? with either a or b such that no 3 consecutive letter would be same in the string. If there exist multiple answers return any one of them.

Example test:

'a?b?aa'

Output:

'aabbaa'

Question 2

Given two arrays numerator[i] and denominator[i].

Find the most frequent fraction where fraction = numerator[i]/denominator[i]

Question 3

You have a traditional 6-faced dice, and you rolled it M + N times. The numbers from rolls of M times are in A and the numbers from rolls of N times are in B. You want each array to have a common sum. You can modify the arrays so that their sums are equal but you should use the minimum number of turns. Through a turn, you can change a value from an array into any value between 1 and 6. You cannot delete a value or make it 0 or negative.

A's length and B's length can be different. If it is impossible to make both arrays sum to a common sum, return -1.

Example

(A = [1,4,3], B = [6,6,6]) => 2 (turns)

Question 4

Suppose you are given a set of exchange rates among certain currencies and you want to determine if an arbitrage is possible, i.e, if there is a way by which you can start with one unit of some currency C and perform a series of barters which results in having more than one unit of C.

Let's assume that

• transaction costs are zero
• exchange rates do not fluctuate
• fractional quantities of items can be sold

5

USD 1 0.741 0.657 1.061 1.005

EUR 1.349 1 0.888 1.433 1.366

GBP 1.521 1.126 1 1.614 1.538

CHE 0.942 0.698 0.619 1 0.953

CAD 0.995 0.732 0.650 1.049 1

The above picture shows such chart.

USD -> EUR -> CAD -> USD

Let's suppose we start with 10000 USD then exchange it for EUR. We get 7410 EUR. Now I want to exchange this with CAD.

7410 EUR = 7410 * 1.366 = 10122 CAD

Now let's exchange this for USD.

10122 CAD = 10122 * 0.995 = 10071

Therefore, started with 10000 USD and ended up having 10071 USD. A good 71 USD profit. Design an efficient algorithm to determine whether there exists an arbitrage - a way to start with a single unit of some currency and convert it back to more than one unit of that currency through a sequence of exchanges.

8 months ago

Shikhar Mehrotra 480

Chennai

Q1)
Analysis
First of all observe here that If we want to put a character at some position than we have to check it's validity with previous 2 characters also.
And if it's valid to put previous 2 characters than we could put a valid character at that position.
For example if we are currently having these kind of situations
1> ...ab[current_position](ignore the characters after current_position for now] and if we know that it is valid to make ...ab than it's also valid to make ...aba and ...abb
2>...aa[current_position](ignore the characters after current_position for now] and if we know that it is valid to make ...aa than it's also valid to make ...aab but not ...aaa
3>...bb[current_position](ignore the characters after current_position for now] and if we know that it is valid to make ...bb than it's also valid to make ...bba but not ...bbb
4>...ba[current_position](ignore the characters after current_position for now] and if we know that it is valid to make ...ba than it's also valid to make ...baa and ...bab

Solution
From above analysis it motivates us to define a function F(current_position,prev1,prev2) which represents is it possible to convert the prefix into valid string upto current_position such that previous 2 characters i.e current_position-2 and current_position-1 is prev1 and prev2. respectively and define the recursion as stated above and optimize it using memoization. For reconstructing the string store the parents(of valid transitions) and backtrack the parents just like you do if you had been asked to find the path from a source node to a target node in a graph.

Remember : (It could be changed also ) In amex OA your final results of all test cases are given at the end i.e when you end your test hence, you must be sure of your solution before ending the test because unlike other company's tests you run your tests and get the final verdict on the spot.

9 weeks ago

Akash 240

New Delhi

Question 3: Dice Sum

Overview

• Make the sum of two arrays equal in minimum number of turns.

Approach

• A greedy algorithm would work well for this:

• Determine which of the arrays has the larger sum and which the smaller

• Sort the arrays, and while the sum is not the same

1. Get the maximum element from the larger, and the minimum element from the smaller array.

2. Determine which has more "potential" to equalize the sum, e.g., a 5 in the "larger" array can be changed to 1, or a 3 in the smaller array can be changed to 6 pick the element that has more "potential" and change it (all the way to 1 or 6, or as needed)

Complexity

Time Complexity: O(N log N) N is size of the array.

4 months ago

Ujjwal Srivastava 320

Bengaluru

Question 2

Overview

• Given 2 arrays numerator[i] and denominator[i].
• We have to find most frequent fraction where fraction = numerator[i]/denominator[i]

Solution

• Iterate from index 1 to n.
• Let us say the current index is i and gcd(numerator[i],denominator[i]) = gc ,then do numerator[i]/gc,denominator[i]/gc to reduce the fraction to its lowest form where numerator and denominator are coprime.
• Now just take a map of pair and increment map_pair[{numerator[i],denominator[i]}] by 1.
• Now using the map_pair we can find the fraction which occurs most frequently.