## Arrays Interview Questions

- 0of 2 votes
A string contains a-z, A-Z and spaces. Sort the string so that all lower cases are at the beginning, spaces in the middle and upper cases at the end. Original order among lower and upper cases needs to remain the same. For example: a cBd LkmY becomes ackm BLY. Is there a way in O(n) without extra space?

- 0of 0 votes
Sheldon Cooper, Leonard Hofstadter and Penny decide to go for drinks at Cheese cake factory. Sheldon proposes to make a game out of this. Sheldon proposes as follows,

• To decide the amount of beverage they plan to consume, say X.

• Then order for a random number of different drinks, say {A, B, C, D, E, F} of quantities {a, b, c, d, e, f} respectively.

• If quantity of any three drinks add up to X then we'll have it else we'll return the order.

E.g. If a + d + f = X then True else False

Input Format:

1. First line contains number of bottles ordered denoted by N

2. Next N lines, contains a positive integer Ai, the size of the ith bottle

3. Last line contains the quantity they intend to consume denoted by X in text above

Output Format:

True, if combination is possible

False, if combination is not possible

Input:

6

1

4

45

6

10

8

22

Output:

True

Input:

4

1

3

12

output:

false

- 0of 0 votes
Given three arrays A,B,C with n elements each and a number 'K'. find whether there exists a,b,c where a belongs to A, b to B and c to C such that a+b+c = K. It should be done in NlogN time

- 1of 1 vote
Write program for the following scenario

Input Array :- {1,2,3,4,5,5,5,6,7,7}

Output:- 5 is repeated 3 times

7 is repeated 2 times

- 0of 0 votes
Round 6

Question 3 : You are given a word document, you have to print the words with frequencies. Now print the kth rank word in terms of frequency. Print top k words as well by frequencies

- 0of 0 votes
Round 5

Question 5 : Now lets say you are given k number of input streams, each stream have two method implemented, one is ReadNextNumber() and another is WriteToStream(), lets say each of the streams are sorted. How will you return a single sorted stream which contains all the streams data.

- -1of 1 vote
Round 5

Question 4 : Now lets say you have 1 PB(1000 TB) of numbers, what kind of system you would prefer, not that you can't store this data in one box. How will you sort these many numbers, what is the time complexity in seconds ?. does increasing core per machine help here ?

- -1of 1 vote
Round 4

Question 3 : this question was similar to Round 2 Question No 3, which is basically convert row type of data to column type of data

- -1of 1 vote
Round 3

Question 2 : You are given a array of integers, array may have duplicates, you have to find out the rank k number, and then print out the k highest numbers ?

Required complexity is O(N) + O(1) space, duplicates may be an issue, on which she wanted me to put more focus.

- 1of 1 vote
Tech Screening

Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry.

Interviewer was expecting O(N) solution for N asks.

Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks.

and integers are not given in a array, every time only one integer will be passed as input to your method.

- 0of 0 votes
Tech Screening round

Q.1 : a non decreasing sorted array is rotated by some random amount, write a routine to figure out this random amount.you can consider the clockwise rotation.

Write the test cases for it.

Interviewer wanted to see prod ready code.

- 0of 0 votes
Given an array of integers (+ve & -ve) find two equal sized contiguous non-overlapping sub-arrays with maximum dot-product

- 0of 0 votes
given an array with elements check if just by exchanging two elements of the array we get a sorted array.

- 1of 1 vote
Rotate a array by N. N can be smaller of greater than the array length.

e.g {0,1,2,4,5,6,7} N =4 should return {5,6,7,4,0,1,2}.

1) I did this using extra array but next I was asked to do without extra array and in o(n) time.

- 0of 0 votes
Given an unsorted array of integers find a minimum number which is not present in array.

e.g -1 ,4, 5, -23,24 is array then answer should be -22.

- 0of 4 votes
i18n (where 18 stands for the number of letters between the first i and the last n in the word “internationalization,”) Wiki it.

Generate all such possible i18n strings for any given string. for eg. "careercup"=>"c7p","ca6p","c6up","car5p","ca5up","care4p","car4up","caree3p","care3up"..till the count is 0 which means its the complete string again.

- 1of 1 vote
Given an array of integers and a number. WAP to find the pairs which sum of upto given number.

I solved it. Then he asked about writing test cases for this function.

I wrote below test cases

1.) All the elements should be number.

2.) Length of array should not be 0.

3.) Array itself should not be null.

4.) Given number, arrayLength can be represented by 32bits or 64 bits.

5.) number should not be negative.

6.) Input does not has pair, It should return false

7.) Input has pair, It should return true

8.) Input has all negative values and pair exists, then function should return true

9.) Input has all negative values and pair does not exists, function should return false

He told that he is looking for more test cases. Can you guys think of some more complex test cases.

- 0of 0 votes
In a Formula-1 challenge, there are n teams numbered 1 to n. Each team has a car and a driver. Car’s specification are as follows:

– Top speed: (150 + 10 * i) km per hour

– Acceleration: (2 * i) meter per second square.

– Handling factor (hf) = 0.8

– Nitro : Increases the speed to double or top speed, whichever is less. Can be used only once.

Here i is the team number.

The cars line up for the race. The start line for (i + 1)th car is 200 * i meters behind the ith car.

All of them start at the same time and try to attain their top speed. A re-assessment of the positions is done every 2 seconds(So even if the car has crossed the finish line in between, you’ll get to know after 2 seconds). During this assessment, each driver checks if there is any car within 10 meters of his car, his speed reduces to: hf * (speed at that moment). Also, if the driver notices that he is the last one on the race, he uses ‘nitro’.

Taking the number of teams and length of track as the input, Calculate the final speeds and the corresponding completion times.

- 0of 0 votes
This was a question asked to my cousin in a recent phone interview with Cisco.

You're given an array of integers (unsorted) and the length is really large (perhaps a million integers). Now you are required to write an efficient code to retrieve topN integers. If N is 10, return the top 10 integers from the array. You result may or may not be sorted, that's your call. For e.g. if given array is arr = { 2, 1, 20, 3, 6, 5, 4, 8, 11, 12 }; and given N value is 3, then your result should be either {20, 11, 12} (unsorted) or {11,12, 20} (sorted).

- 0of 0 votes
given an array with elements check if just by exchanging two elements of the array we get a sorted array.

time restriction:

O(NlogN)

space restriction: 2N

- 0of 0 votes
Find the longest running positive sequence in an array -

Eg - [1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6]

It should return 5, with start index : 8

- 0of 0 votes
I have an two arrays int[] 1 = {2,5,8,9}; and int[] 2={6,3,4,7,1};

I need to merge this two array in third array int[] 3 = new int[1.Length + 2.Length]; and give the output in sorted form.

Also I need to provide and optimized code with minimal complexity...

Output: {1,2,3,4,5,6,7,8,9}

Plz Help...

- 0of 0 votes
A mechanical engineer is writing a design specification for two gears to transmit motion between two parts, A and B, in a machine she is designing.

the distance between A and B is equal to D.

There are n types of gears, Agear type of i has a radius Rj and cost Cj.

The two gears specified, i and j , must have Ri+Rj >= D, inorder for there to be a way of placing them so that they touch and work togeather. The objective is

to find the pair which costs the least.

You need to produce a design table that gives the most suitable match for every gear type in the list. For every gear type 'i', you need to consider its description (Ri,Ci)

and list the gear type 'j' to pair with 'i' in table position T[i]. The best map might be the same type(Ti=i). if there are multiple solutions with the same cost,

choose the gear with the largest radius.If both the cost and radius you need are found in more than one gear type, choose the type with the smallest index j.

If no radius can be found that allow the distance D to be covered, table should contain 0.

Input

n D

R1 R2 ... Rn

C1 C2 ... Cn

Output

T1 T2 ... Tn

- 0of 0 votes
You are given an N*N matrix. The matrix contains characters. Write a program to find a word in the matrix.The word can be found in either the rows or columns or the diagonals. The program should return true if the word is found and false if the word is not found.

- 2of 2 votes
You have a function rand5(). This function returns numbers between 1 and 5 randomly with equal probability. Implement a function rand7() which makes use of rand5 to return a number between 1 and 7 randomly with equal probability.

- 1of 1 vote
Consider the 52 cards of a deck. You generated a random sequence for these cards and want to send that sequence to a receiver. You want to minimize the communication between you and the receiver, i.e., minimize the number of bits required to send the sequence.

What is the minimum number of bits required to send the sequence?

Hint: It is not 6 x 52

- 2of 2 votes
Find a given element in sorted array.

arr= [1, 2, 3, 4, 5, 6]

follow up: If the sorted array is shifted left by unknown number, modify existing binary search to find a element in modified array

arr = [4, 5, 6, 1, 2, 3]

- 0of 0 votes
Given a number A, find the smallest number which has only 1s and 0s as its digits which divisible by the number A. For example: if the given number A is 4, the smallest number with 1s and 0s is which is divisible by 4 is 100.

- 0of 0 votes
Completely blew it on this question today.

1.) Given an array, find the maximum difference between two array elements given the second element comes after the first.

For example.

array = [1,2,3,4,5,6,7]

We can take the difference between 2 and 1 (2-1), but not the different between 1 and 2 (1-2).

This question is super easy, I solved it within minutes of getting of the phone. I came up with an O(n^2) solution over the phone. My improved solution was O(n).

- 0of 0 votes
Implement 2 stacks in a single array