11 weeks ago

John 910

Hyderabad

Question 1

The company WebTech is developing a system to analyze user purchasing behavior to provide a better shopping experience. User behavior sequences are encoded to strings of '0'and '1' where '0' represents the product purchased and '1' represents the product returned one of the steps is to find the largest substring containing an equal number of 0s and 1s, which would indicate that product purchase and return rate are the same. As one of team's software development engineers, you need to develop a method to process the encoded string and return the largest substring that contains an equal number of 0s and 1s.

Input

The first line of the input consists of a string inputString, representing the encoded string depicting the user behavior.

Output

Print a string representing the largest substring that contains an equal number of 0s and 1s.

Note

If more than one largest substring possible then output the string that appeared first.

Example

Input:

11101011100

Output:

01011100

Question 2

An automated grocery store operates with the help of robots. Robots are fed the database of products which are available in the store in the form of a string. Each character of the string denotes a product's category tag which is a letter from the English alphabet (a-z). Whenever a customer orders some products then this order is stored as a string of ordered products. In the string, each character denotes the category tag of the product. The products of the order are then collected by the robots in the store. The robots work on a fixed procedure. They will get the product from the customers onder which is present earli n the database list. Similarly, they will collect all the their products from the order.

The store manager wants to analyze the efficacy of the robot's procedure by analyzing the first product searched by the robot from the customer's order list string which is present earliest in the database. Write an algorithm for the procedure to find the product from the customer's order which is found earliest in the store's database.

Input

The first line of the input consists of a string - database, representing the sequence of product tags of the available products stored in the database.

The second line consists of a string - custOrder, representing the sequence of product tags of the products ordered by the customers.

Output

Print a string representing the product tag of the product present in the customer's order which is found earliest in the store's database. If none of the ordered products are found in the database then print "NA".

Note

A product tag can be repeated in the database and custOrder

The product tags are letters from the English alphabet (a-z)

Question 3

A data center transfers N data packets from the client server to the main server. Each data packet has a unique identification number. The N data packets are transferred in a sequential list according to the increasing order of their packet IDs. Each packet is assigned a unique acknowledgement ID that the main server sends to the client server to report the successful transfer. These acknowledgement IDs are assigned sequentially from 0 to N-1. To avoid any type of intrusion and to secure the transfer of the packages, the data center rotates the list rightward cyclically. Now the data center wishes to know the acknowledgement ID of the desired packet according to the original list.

Write an algorithm for the data center to find the acknowledgement ID of the desired packet (P) according to the original list of packets. If a packet is transferred more than once (i.e the list contains similar packet IDs) then return the acknowledgement ID of the first packet transferred. If no packet is transferred, then return -1.

Input

The first line of the input consists of two space separated integers - num and searchPkt representing the number of packets in the list(N) and the packet ID to be checked for acknowledgement (P), respectively.

The second line consists of N space-separated integers - listPkts1, listPkts2, ......, listPktsN representing the IDs of the packets that are transferred from the client server to the main server.

Output

Print an integer representing the acknowledgement ID of the packet with Id P in the original list.

Constraints

0 <= num < 10^5 0 < listPkts[i], listPkts < 10^6 0 <= i < num

Example

Input: 9 1 1 2 3 4 5 6 7 8 1

Output: 0

Question 4

The warehouse of e-commerce company "GoodsOnline" had a list of N available products. The list contains the quantity of each product that is available in the warehouse. The company wishes to move all the products with a quantity of zero to the end of the list while maintaining the relative order of the products with non-zero quantities in the list.

Write an algorithm to move all the products with a quantity of zero to the end of the list.

Input

The first line of the input consists of an integer - numProducts, representing the total number of products on the list (N).

The next line consists of N space separated integers - quantity[0], quantity[1],......., quantity[N-1], representing the quantities of the N products.

Output

Print N space-separated integers representing the quantity of the products while maintaining their relative order and moving all of the products with zero quantity to the end of the list.

Example

Input:

7
12 0 5  0 34 3 0

Output:

12 5 34 3 0 0 0

Explanation:

After moving all of the products with '0' quantity to the end of the list we get the list 12 5 34 3 0 0 0. Therefore, the output is 12 5 34 3 0 0 0.

11 months ago

Manas 330

Bānswāra

Question 1

The idea would be to calculate the longest subarray with 0 sum. Instead of 0's and 1's, assume the array has -1 instead of 0's. Now if we have equal number of 1's and -1, the sum of the subarray would be 0. Let us discuss an approach to see how we can find the longest subarray optimally. Let's assume we take the prefix sum of the array. S[i] -> prefix sum till ith element. It can be seen that if we consider any j > i and if S[i] equals S[j], this would imply that the sum of the elements from i to j is 0, as the prefix sum at both the positions is the same. \ S[i] = arr[0] + arr[1] + .... + arr[i] \ S[j] = arr[0] + arr[1] + ..... + arr[i] + arr[i+1] + ...arr[j] \ S[j] - S[i] = arr[i+1] + arr[i+2] + .... arr[j] \ Since we know that S[j] == S[i], we get from the above eq that : arr[i+1] + arr[i+2] + ... arr[j] = 0 We can store a hash map of all the prefix sum values which occur and then check if any value repeats. If any value repeats the we would know that there exists a subarray with 0 sum. Since we want to print the array, in the hashmap we can store the index of the first occurrence of every sum (as we want to print the longest subarray). We can now iterate over the array and find the longest 0 sum substring and then print the same.

11 months ago

Manas 330

Bānswāra

Question 4

The most optimal approach would be to use 2 pointers. The fast pointer does the job of processing new elements. If the newly found element is not a 0, we record it just after the last found non-0 element. The position of last found non-0 element is denoted by the slow pointer, let's call it "lastNonZeroFoundAt" . As we keep finding new non-0 elements, we just overwrite them at the "lastNonZeroFoundAt + 1" 'th index. This overwrite will not result in any loss of data because we already processed what was there(if it were non-0,it already is now written at it's corresponding index,or if it were 0 it will be handled later in time).

After the fast pointer index reaches the end of array, we now know that all the non-0 elements have been moved to beginning of array in their original order. Now comes the time to fulfil other requirement, "Move all 0's to the end". We now simply need to fill all the indexes after the "lastNonZeroFoundAt" index with 0.