CareerCup

Find min number of jumps it will take to reach to the top in snake and ladder game using recursive function

I was asked the following question in an interview recently, which was a lot more vague and after asking clarification questions came down to this:
```
We have to perform N tests [1, 2, ... N] but in randomized order.
We have access to two functions test(x) and rand(x) which both take an integer.
test(x) returns if the current test was succesful or not and rand(x) returns a random integer
from 1<= rand(x) <= x.
The tests fail because of the sequeunce of tests carried out and we want to figure out which
sequences are bad and which sequences are good.
Basically our task is to generate a sequence of test while carrying them out and return the
sequence either when the test failed or when all tests are done.
```
I understand that the problem could be simplified by calling rand(N) just once, say x = rand(N) then we get the xth permuation of the seuence (1...N) and then call the test() function on this sequence reutrning only the part of sequence that finished successfully, this is deterministic and can be done in O(N) time.
Is there a better approach / solution in Python?

I was asked to sort extra large file 10GB which contains single word in each line, within 4GB RAM. I told External sort and optimised it with min-heap but interviewer was asking to optimise disk I/O. As last he told that use CS fundamentals. Don't know what was he expecting. Please help.

Write a binary calculator for summing two strings. Could not use standard {{ bin }} method.

Was asked at GHCI Bangalore at their booth for a prize and perhaps hiring interns or experienced software developers.

Find the return value for N=100

int returnAns(int N){
int ans=0;
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
ans +=((i & -i) == (j & -j)?1:0); //the question missed the condition and was returning a boolean, so I added it myself
}
}
return ans;
}

My answer: 0 ; their answer: 1610, hence got it wrong.
My explanation: I assumed negative of i in binary to be
simply represented by setting the MSB to 1 e.g. for 8 bit representation of 3: +3 is 0000 0011 and -3 is 1000 0011. In the inner loop the value of ans will always evaluate to 0 since Bitwise & of these i and -i or j and -j will always result into i and j respectively. (undergrad computer organization concept.)
Negative numbers can also be represented as 1s and 2's complement and in all modern machines by architecture its 2s complement.
Now if we assume 1's complement, +3: 0000 0011 and -3: 1111 1100. so bitwise & of these two is 0 and so the value of ans will always be incremented by 1. By two loops 100+99+98+97+...+1 = 100*101/2 (i.e. n*(n+1)/2)
Then 2's complement, which is the most relevant representation of signed binary numbers.
Odd numbers:
+3: 0000 0011 -3: 1111 1101 Binary & is 0000 0001.
For all even numbers:
+4: 0000 0100 and -4: 1111 1011+0000 0001 = 1111 1100 and Bitwise & of 4 and -4 is 0000 0100 which is 4.
So, in the innermost loop ans is incremented by 1 when i is odd and j is also odd. ie. when i is 1, 3, 5, 7... 97 and j is 3, 5, 7, 9,...,99 ans is added 1(return value of true ==) when calculated it comes to 1610.

Amazon has N buildings on the site, building ID ranged from 0 to N-1
Every employee has an office space in one of the buildings.

Now employee may make a request to move from current building X to
another building Y. A moving request is noted by

Class Request{
String employee names;
int from building;
int to building;
}

Initially all buildings are full. A request from building X to building Y is
achievable only if someone in building Y made an achievable requests to
move away and therefore creates a vacancy

Given a wishlist of requests, help us plan for the best way of building
swaps. A plan that fulfill the maximum number requests is considered
the best
Output is a list of employee names on cyclic swaps.

For Ex:
Input :

List<Request requests{
<"Alex" 1, 2>,
<"Ben", 2, 1>,
<"Chris", 1, 2>,
<"David", 2, 3>,
<"Ellen", 3, 1>,
<"Frank", 4, 5>
}

Expected Output:

List<List>
[ ["Alex","Ben"],["Chris","David","Ellen"] ]

Can someone please help me how to solve this one?

Suppose two arrays are given A and B. A consists of integers and the second one consists of 0 and 1.
Now a operation is given - You can choose any adjacent bits in array B and you can toggle these two bits ( for example - 00->11, 01->10, 10->01, 11->00) and you can perform this operation any number of times.
The output should be the sum of A[0]*B[0]+A[1]*B[1]+....+A[N-1]*B[N-1] such that the sum is maximum

During the interview, my approach to this problem was to get the maximum number of 1's in array B in order to maximize the sum.
So to do that , I first calculated the total number of 1's in O(n) time in B. Let count = No. Of 1's=x
Then I started traversing the array and toggle only if count becomes greater than x or based on the elements of array A(for example : Let B[i]=0 and B[i+1]=1 & A[i]=51 and A[i+1]=50
So I will toggle B[i] B[i+1] because A[i]>A[i+1])

But the interviewer was not quite satisfied with my approach and was asking me further to develop a less time complex algorithm.

Can anyone suggest a better approach with lesser time complexity??

find nearest word from the given non-english dictionary which is one off character. (could be non ascii characters)
for eg. dictionary contains { apple, pineapple, banana, orange }

if given word "applx" then return true, as applx matches with apple and only one character is off.
aplpe returns false

A stream of data representing the price of a commodity is being read. The data is of the format (price:Int, timestamp:Option[Long]).
If the timestamp is missing, it means the price has to be deleted.
If timestamp is old, it means the previous data with same timestamp has to be updated with this new price.
Else it's the new price of the commodity.
At any point of time the latest, max and min of the price has to be printed.
If the delete instruction is received through the stream, the min/max should be updated accordingly.

Given an array of integers find the maximum value of a[i] - a[j] + a[k]
with constraints i < j < k and a[i] < a[j] < a[k]

Given a rectangle with width 'W' and height 'H', you have to fit a string 'S' in it with maximum possible font size
The font size ranges from 1 to 30
You are given two APIs getCharacterWidth(char c , int font_size) and getCharacterHeight(int font_size)
getCharacterWidth(char c , int font_size): returns the width of a character for a particular font size
getCharacterHeight(int font_size): returns the height of characters for a particular font size

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Count number of strings of length N with following properties:

A. Consists of char 'A' and 'B' only.
B. There is atleast one occurrence of 3 consecutive Bs.

Input: Only line having integer N.

Output: Number of string with given properties. As then number can be very large print it with modulo 10^9+7.

Sample Input 1:
3

Sample Input 2:
1

Explanation: Only possible string "BBB"

Its farewell day, there are total N students, every student has bought a gift to give. He/She will give this gift to some other student. After gifting process is over, you are given an array, representing number of gift student receive i.e. ith number denoting number of gift he/she got. Your task is to find, whether given gift count array is valid or not. If it is valid print any of possible way of gifting that lead given array.

PS: Student can't gift to himself. Student has exactly one gift with himself.

Input: First line will have one integer M, denoting number of students. Next line wil have N spaced integers denoting number of gift student gets.

Ouput: -1, if given gift received array is not valid else print N spaced integers denoting ith gifted to jth.

Sample Input 1:
3
1 1 1

Sample Output 1:
2 3 1

You have given a string which consists of four characters {a,c,t,g}, find minimum length of unique substring which occurs only once.

Eg:

Input :
#1 aacc
#2 actg

Output:
#1 2 3
#2 1 4

Explain:

aacc -> {aa, ac, cc} are the smallest unique string with single occurrence.

C program for the given two array as point of x and y
int x[] = { 2,3,2,4,2};
int y[] = {2, 2, 6,5,8}; count the pair
maximum area coverd in x y plane
Ouput:3
From the above input there are five coordinates possible (2,2)(3,2)(2,6()(4,5)and (2,8) in which (2,2)(2,6)(2,8)that is three coodinaters covers the maximum area in x y plane
Input: x[] ={1,2,3}
Y[] = {1,2,3}
Output: 1
there are three coordinates (1,1)(2,2)(3,3)in which only one coordinates covers maximum distancethat is (1,3)

Program to print last element of matrix by traversing a matrix by anticlockwise starting from cell(1,1) and skiping alternate.
Ex:
Input:1 2 3 4
2 4 5 1
7 9 6 2
3 5 2 7
Output: 5
Start traversing matrix from cell(1,1) skip next row element go to 3 row element again skip 4 element go to bottom of second column .....up to last element and print only last element.
If Input: 1 2
3 4
Output: 2
Input:1 2 3
4 5 6
7 8 9
Output: 5

Given a list of sorted lists each of size maximum size M, implement an iterator (maintain the order of items as in the original list of lists).

I had a solution requiring extra space using minHeap; However, the interviewer was looking for a constant space solution.

Given a directed graph and a node , find the shortest cycle in a graph with given node .

How to divide a circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array.

For e.g If the array is as follow. [6 13 2 10] and k=2 then o/p should be 16(6+10)-15(13+2)=1. As array is circular 6,10 are contiguous element of array.

For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29

l1=[1,2,3,4]
l2=[1,3,6,7,null,null,null,null]
output: l2=[1,1,2,3,3,4,6,7]

k=2, l=[1,2,3,4,5,6]
output: l=[5,6,1,2,3,4]
In place O(1) space complexity

You have two sorted arrays, where each element is an interval. Now, merge the two array, overlapping intervals can be merged as a single one.

I/P :
List 1 [1,2] , [3,9]
List 2 [4,5], [8, 10], [11,12]

O/P [1,2], [3,10], [11,12]

I/P [8, 3, 2, [5, 6, [9]], 6]

O/P 8+3+2+2*(5+6+3*(9))+6 => 95

You are given an array A of size N and Q queries. For each query, you are given two indices of the array L and R. The subarray generated from L to R is reversed. Your task is to determine the maximum sum of the subarrays.

Note: After each query is solved, the array comes to its initial states.

Input format

First line: Two space-separated integers N and Q
Next line: N space-separated integers denoting the array elements.
Next
Q lines: Two space-separated integers in every line denoting the values of Li and Ri
Output format

For each query, print the required answer in a new line.



5 2
3 -1 4 2 -1
3 4
1 2

//output
8
9

Given the root of a binary tree, print the nodes column wise and row wise.

..............6
............/....\
...........9......4
........../..\......\
.........5....1.....3
..........\........./
...........0.......7

The answer would be 5 9 0 6 1 4 7 3.

Explain the difference between ORM and JDBC.
Provide some examples and when to use one over the other.

given two strings s1 and s2 we have to convert s1 into palindrome such that s1 contain s2 as a substring. in a minimum number of operation. wherein a single operation we can replace any word of s1 with any character.
constraint : |s1| <= 1000
|s2| <= |s1|
ex: s1 = "abaa" , s2 = "bb"
output : 1

Given an array which represents columns, find the position of two columns which when removed will trap the maximum amount of water. This is related to trapping raining water problem.

Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.

For eg. 6, 9, 3, 2, 10, 2, 3