Samsung Interview Questions asked in Samsung 3 Hour Test | Set 2

1. 

You’ll be given a grid as below: 

0 1 0 2 0 

0 2 2 2 1 

0 2 1 1 1 

1 0 1 0 0 

0 0 1 2 2 

1 1 0 0 1 

x x S x x 

In the grid above, 

1: This cell has a coin. 

2: This cell has an enemy. 

0: It contains nothing. 

The highlighted(yellow) zone is the control zone. S is a spaceship that we need to control so that we can get maximum coins. 

Now, S’s initial position will be at the center and we can only move it right or left by one cell or do not move. 

At each time, the non-highlighted part of the grid will move down by one unit. 

We can also use a bomb but only once. If we use that, all the enemies in the 5×5 region above the control zone will be killed. 

If we use a bomb at the very beginning, the grid will look like this: 

0 1 0 2 0 

0 0 0 0 1 

0 0 1 1 1 

1 0 1 0 0 

0 0 1 0 0 

1 1 0 0 1 

x x S x x 

As soon as, the spaceship encounters an enemy or the entire grid has come down, the game ends. 

For example, 

At the very first instance, if we want to collect a coin we should move left( coins=1). This is because when the grid comes down by 1 unit we have a coin on the second position and by moving left we can collect that coin. Next, we should move right to collect another coin( coins=2). 

After this, remain at the same position( coins=4). 

This is the current situation after collecting 4 coins. 

0 1 0 2 0 0 1 0 0 0 

0 2 2 2 1 -->after using 0 0 0 0 1 

x x S x x -->bomb x x S x x 

Now, we can use the bomb to get out of this situation. After this, we can collect at most 1 coin. So maximum coins=5.

2. 

Mr. Kim has to deliver refrigerators to N customers. From the office, he is going to visit all the customers and then return to his home. Each location of the office, his home, and the customers is given in the form of integer coordinates (x,y) (0≤x≤100, 0≤y≤100) . The distance between two arbitrary locations (x1, y1) and (x2, y2) is computed by |x1-x2| + |y1-y2|, where |x| denotes the absolute value of x; for instance, |3|=|-3|=3. The locations of the office, his home, and the customers are all distinct. You should plan an optimal way to visit all the N customers and return to his among all the possibilities. 

You are given the locations of the office, Mr. Kim’s home, and the customers; the number of the customers is in the range of 5 to 10. Write a program that, starting at the office, finds a (the) shortest path visiting all the customers and returning to his home. Your program only have to report the distance of a (the) shortest path. 

You don’t have to solve this problem efficiently. You could find an answer by looking up all the possible ways. If you can look up all the possibilities well, you will get a perfect score. 

[Constraints] 

5≤N≤10. Each location (x,y) is in a bounded grid, 0≤x≤100, 0≤y≤100, and x, y are integers. 

[Input] 

You are given 10 test cases. Each test case consists of two lines; the first line has N, the number of the customers, and the following line enumerates the locations of the office, Mr. Kim’s home, and the customers in sequence. Each location consists of the coordinates (x,y), which is reprensented by ‘x y’. 

[Output] 

Output the 10 answers in 10 lines. Each line outputs the distance of a (the) shortest path. Each line looks like ‘#x answer’ where x is the index of a test case. ‘#x’ and ‘answer’ are separated by a space. 

[I/O Example] 

Input (20 lines in total. In the first test case, the locations of the office and the home are (0, 0) and (100, 100) respectively, and the locations of the customers are (70, 40), (30, 10), (10, 5), (90, 70), (50, 20).) 

5 ← Starting test case #1 

0 0 100 100 70 40 30 10 10 5 90 70 50 20 

6 ← Starting test case #2 

88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14 

10 ← Starting test case #3 

39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36 

... 

Output (10 lines in total) 

#1 200 

#2 304 

#3 366