interview question

general
1

1)
You need to prepare food, for that you have a set of ingredients available. Each ingredient has its own health value. You need to write a code which can determine all possible combinations of ingredients whose sum of total health is highest in the end. The number of ingredients in any combination can be 3 ingredients. Given below is the list with ingredient and their health value.

Salt -1

Sugar +1

Onion +2

Tomato +1

Spinach +3

Oreo -2

For example: Spinach (+3), Onion (+2), Sugar(+1) have a total health value of 6 and number of ingredients are 3. Like this your program should find best combinations (print the 3 best ingredients).

**2)**You need to find smallest positive integer which has certain digits on a condition that if this integer is multiplied by 2,3,4,5 or 6, the answers will still have same digits.

For example: 125874 when multiplied by 2 gives 251748. Both numbers have same digits, i.e. 1, 2, 4, 5, 7 and 8

3)
Given two arrays of length n and n-1, all elements of both the arrays are same except one. Find the odd element out, giving O (1) solution.

Given two binary trees (not any special tree like binary search tree or red black tree) with n and n-1 nodes respectively, find the odd node out.

Given two binary search trees with n and n-1 nodes respectively with all elements same except one, find the odd node.

Given an array where each element signifies the number of cells which can be skipped, find the minimum number of steps taken to reach the last cell of the array. One has to start at index 0 and always move forward either by skipping cells by number given or by one.

2

Question 1 is standard greedy wherein you sort the list in ascending order and pick the last 3 array elements(considering only 1 optimal solution is required). Question 2 looks interesting if it has a non-brute force solution!

1 Like
3

For the first one: many solution possible answer required.

for second yup no brute force:

I tried to reduce it to some extend like

if the number starts with 2: 5,7,8 will not occur

if the number starts with 3: 4,5,7,8 will not occur

if the number starts with 4: 3,4,5,7,8 will not occur

if the number starts with 5 and above: no answer possible

But the interviewer is not satisfied

4

Then the first one has cases:

Case 1: The highest element value occurs >2 times

Case 2: The highest element value occurs 2 times

Case 3: The highest element value occurs 1 time and 2nd highest occurs>=2 times

Case 4: The 2nd highest also occurs once only.

It becomes a tad complicated.

5

For first question

We can sort based on health values , then we can have cases based on the extracted top 3 values as

1) All 3 values are same.(e.g. - 5,5,5)

If all three values are same , look again in the array for number of times we have the top value suppose it turns out to be n and then the answer will nC3.(Here C is combinations).

2) 2 Max values are same and last one is different.(e.g. - 5,5,2)

We just need to look if we have the different values again in the array(e.g. we will look for 2) , if we have then the answer would be the total number of time the different value came.

3) 1 Max value and other two values are same.(e.g. - 5,2,2)

Again we will look for the number of times lowest value is there in the array(from e.g. we will look for 2) and suppose the total number of times it occurs is n , our answer will be nC2.(Here C is combinations).

4) 1 Max value , 2 different values.(e.g. - 5,3,1)

We will simply look for 1 in the rest of the array , and then the answer would be number of times it occurs.

More over based on the constraints we can optimize it further , if maximum value of health values lie under 10*5 , we can have a freq array , and hence store the frequencies of different food at the time we take input , so we dont have to traverse the array again and hence we just need to look for which case we have.

I hope much would be helpful.!

**

For second question , i suggest you to visit this sites

**

1

2

2 Likes
6

For the third question you can use set.
While taking the input of the first array add that element to the set.
Whereas while taking the input of the second array erase the element from the set.

Print *** *S.begin()**.

Even though the answer is returned in O(1), the preprocessing time complexity is O(nlogn).

P.S
if you have first array with certain elements whose frequency is more than that of second you might use unordered_set. In this case the preprocessing time would be O(n) since *** unordered_set has time complexity** of O(1) on average case.

See for Implementation

For the Second part of third question you can again use set or unordered_set to return the odd node in O(1).

Remember that even a binary tree can be represented as an array. Here the size of the array would be the total number of nodes in the binary tree. Thus part 1 and part 2 of the third questions is same.

7

For @techbuzz answer,
If we are allowed preprocessing then O(n) solution would be summation of both arrays and printing the difference between the two, hence providing the answer which is better than your O(nlogn).

O(1) solution for Question 3(a) would be just doing XOR for all elements and the answer would be the Xor of all elements.
For example :

x = [1,2,3,4,5]
y = [1,2,3,4]
XOR for all elements of both arrays = 5 which is your answer.

Note : you can perform this operation in just O(1) extra time if you consider the input
complexity as exclusive.

8

@nagpalkaran95 your first solution would not work if you allow just taking the difference, since the input between both the arrays would not be in the same order
Consider the case :

arr1 = [1,2,3,4,5]

arr2 = [5,4,1,2]

If you start taking the difference, I don’t think the preprocessing could be completed in O(n) .

Moreover if we use unoredered_set the complexity would be constant and preprocessing complexity would be O(1).

P.S if i understood you wrong, please point me out.

9

@techbuzz You understood me wrong.
I meant taking the summation of array1 as sum1 and sum2 for array2 and then the answer would be the difference of sum1 and sum2.
Talking about your example:

sum1 = 15
sum2 = 12
sum1 - sum2 = ans = 3

where sum1 and sum2 can be calculated while taking the input.

P.S. Point out mistakes if any.