Walmart Written Paper 2013

Type : online

Platform : Interview Street

Hint : You will be allowed to use IDE's to code.

10 MCQ + 2 Coding Questions - 90 min

IIT D:

coding questions :

1. Chef has an array of N integers. He wants to play a special game. In this game he needs to make all the integers in the array greater or equal to 0.
Chef can use two types of operations. The first type is to increase all the integers of the given array by 1, but it costs X coins. The operation of the second type is to add 1 to only one integer of the given array and to use this operation you need to pay 1 coin. You need to calculate the minimal cost to win this game (to make all integers greater or equal to 0)
Chef has an array of N integers. He wants to play a special game. In this game he needs to make all the integers in the array greater than or equal to 0.
Chef can use two types of operations. The first type is to increase all the integers of the given array by 1, but it costs X coins. The operation of the second type is to add 1 to only one integer of the given array and to use this operation you need to pay 1 coin. You need to calculate the minimal cost to win this game (to make all integers greater than or equal to 0)

Input

The first line of the input contains an integer N denoting the number of elements in the given array. The second line contains N space-separated integers A₁, A₂, ..., A_N denoting the given array. The third line contains number X - cost of the first type operation.

Output

For each test case, output a single line containing minimal cost required to make all the integers greater than or equal to zero.

Constraints

• 1 ≤ N ≤ 10⁵
• -10⁹ ≤ A_i ≤ 10⁹
• 0 ≤ X ≤ 10⁹

Example

Input:
3
-1 -2 -3
2

Output:
5

2.Input is again array of integers(can be negative also), and two numbers L and R (L <= R). Output the number of subsets who have sum between L and R inclusive.

IIT R:

1. Sql Query is given over a small database and we need to find out natural join.

2. If two threads are incrementing a variable 100 times each without synchronization,what would be the possible min and maximum value.
Ans: min:2,Max:200...

3. a c program we need to find out complexity of code.

4. In dijkstra if use d­ary heap then complexity?

5. support and confidence for a transaction.support and confidence for a transaction

6. give Matrix M1:10x100 M2: 100x20 M3: 20x5 M4: 5x80 find minimum multiplication required:(gate 2011 question)
Ans : 19000

7. Expectation question R = l is what?(gate 2011 question)
ANs : R>=0

8. given f(x)=  1⁄6  for x = 0,1,..,5 and x is the number of cakes sold by a baker on one day. theprofit is $1.00 / cake and loss is ­$0.40/ cake then what is the number of cakes he shall bake ?
note: cakes can not be stored for next day

9. linklist having a loop than some constraint is given on it we need to find out which is true.(easy one)

10. Don’t Remember.

11. Walmart  coding question:
we have stream of palindrome in increasing order like:{1,2,3,4,5,6,7,8,9,11,22,33,....101,111,121,131...212,222,232,.....}and they are forming a
n­digit number like: number = 12345678911223344.....101111121131..(all palindrome in increasing order) then we have to find the kth digit of the number.


12. Engineers at @WalmartLabs have decided to call any integer(+ve, ­ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) as Walprimes. Thus ­21, ­30, 0, 5, 14 etc are Walprimes, while ­121, 1, 143 etc. are not Walprimes.
Now, consider a n­digit integer d1d2d3..dn. Between any 2 consecutive digits you can place either a (+) sign, a (­) sign or nothing. So, there are 3(n­1) different expressions that can be formed from it. Some of the expressions so formed may evaluate to a Walprime. For example, consider the 6 digit integer 123456: 1 + 234 ­ 5 + 6 = 236, which is a Walprime, but 123 + 4 ­ 56 = 71, which is not a Walprime.

Your task is to write a program to find the no. of expressions (out of the possible 3^(n­1) expressions) that evaluate to a Walprime, for a given input. Note that leading zeroes are valid. For example, if the input is 1202004, it can be split as 12 + 020 ­ 04 etc. Also, the input itself can contain leading zeroes.

Input format: (Read from stdin)The first line of input contains a single integer 'T' denoting the no. of test cases.
Each of the following 'T' lines contain a single string 's' (of length 'n') denoting an input for which you need to find the no. of valid expressions evaluating to a Walprime.
Output format: (Write to stdout)
Output exactly 'T' integers (one per line), where the ith line denotes the no. of valid expressions that evaluate to a Walprime for the ith input string. Since the output can be large, print all the quantities modulo 1000000007.

Sample testcase:
Input:
2
011
12345
Output:
6
64

Explanation:
For the first test case, s = "011". There are 3^2 = 9 valid expressions that can be formed from this string, namely {0+11, 0­11, 0+1+1, 0+1­1, 0­1+1, 0­1­1, 01+1, 01­1, 011} . Out of these 9 expressions, only the following 6 of them evaluate to a Walprime: {0+1+1, 0+1­1, 0­1+1, 0­1­1, 01+1, 01­1}.
Constraints:
There are 3 data sets.
For the first data set (5 points) ­
1
For the second data set (10 points) ­
1
For the third data set (15 points) ­
1

IIT KGP:

1. Cube to be painted with 6 different colours on 6 faces..how many possible cubes?if on rotating 1 configuration, we get another, then that is not to be considered.

Ans :30 ?(5!/4)

2. (777^333 - 333^777) what is the digit at one’s place(LSB) in the resulting no.

Ans : 0 ?(7^333%10=3; 3^777%10 =3)

3. n elements unsorted array (their values are in range 0 to k-1)..minimum time to calculate median

4. linked list with last node pointing to one of the previous nodes(cycle)..how much time required to detect the cycle and make the last node point to NULL(i.e to remove the cycle)

5. O(n) complexity is required to calculate n/4 th sorted element of an unsorted array

quicksort pivot element is chosen to be that.what is worst time complexity of quicksort

6. Infinitely large no of elements in a b-ary tree. b is given. U need to search for an element at finite depth. possible methods BFS,DFS,iterative deepening depth 1st search (IDDFS). Dn some statements given about their complexities. This 1 was a multiple correct question.

7. n arrays to be sorted by merge sort. time?

8-

9-

10-

11. Piles of coins are given (ex. 5 piles : 9,0,5,1,5 ) total 20 coins.. The minimum no. of moves required so that all piles have equal no of coins (4,4,4,4,4) (ans for this is 9 moves) Rules: one coin can be moved to only adjacent piles..i.e. jth pile coin can be moved to j-1 or j+1 if they

exist

Level 1 : n < 10

Level 2 : n < 100/1000

Level 3 : n < 10^6

12. Tiles in the form of a string consisting of only B or W ex. “BWW” , “BBBWWBB” ..etc

given n tiles..find the largest possible chain of tiles by joining them..

Joining rules:

The last letter of a Tile should match the first letter of other tile.then they can be joined

ex. BW and W WB are joined as BWWWB but BW and BW cant be joined

Level 1 : n < 10

Level 2 : n < 100 or 1000 (don’t remember)

Level 3 : n < 10^5

IIT B:

10 MCQs

2 Coding Questions:

1. Given two numbers L and R, find the highest occurring digit in the prime numbers present between L and R (both inclusive). If multiple digits have the same highest frequency print the largest of them. If there are no prime no.s between L and R, print -1.

Testcases:

L=1, R=30, Ans=1

L=13, R=13, Ans=3

L=4, R=4, Ans= -1

2. Given a string s of ‘H’s and ‘T’s denoting heads and tails, there are 2 possible moves at every point:

a. Flipping a ‘T’ by ‘H’ or ‘H’ by ‘T’ is a valid move

b. Switching every character of a prefix of s, i.e., for any 1<=m<=n, replace all Hs with Ts and all Ts with Hs in s[1...m] is also valid.

Find the min. no. of moves to convert a given string into all ‘H’s.

eg: HHTH =>flip 3rd position => HHHH

HTTT =>(flip prefix) => THHH => HHHH

IIT M :

Coding:

1. Given a string ( with only ‘a’- ‘z’ characters and of length N), find the number of permutations that are palindromes.

2. There a N piles of coins. Array ‘A’ of length N contains the number of coins in each pile. Array ‘C’ of length N contains the cost to add/remove 1 coin to the corresponding pile. Goal is to make the array ‘A’ contain equal values. What is the minimum cost? Infinite supply of coins is allowed.