reci April 17, 2018 at 15:33

Issue # 18: IT training - current issues and challenges from leading companies

We have prepared for you a new issue with interesting tasks from interviews at Apple.

KDPV

At Apple, job seekers can ask questions not only about the technical plan, but also about treasures and pirates (I wonder if this is related to the company's position regarding illegal content?). Questions and tasks, as always, of different difficulty levels. In general, it should be noted that the share of logical tasks is supplanted by purely technical issues, but nevertheless, puzzles at the interviews still occur.

Questions

Gems and pirates
Seven pirates attacked the ship and looted some rare gems from them. They decided to rest for some time and then divide the gems later. While everyone was resting, two pirates wake up and planned to divide gems equally between the two. When they divided gems equally, one gem was left. So, they decided to wake up the third pirate and divide among three, but alas again one gem was left. They decide to wake up the fourth pirate to divide the gems and again one gem was left. The same happened again with the fifth and sixth. Finally, they woke up the 7th pirate and this time the gems were divided equally.
How many minimum gems did they stole in total?

Transfer
Seven pirates captured the ship and mined some gems. They decided to relax and share the booty later. While everyone was sleeping, 2 pirates woke up and decided to divide the stones among themselves equally. When they divided, one stone remained. Then they decided to wake up another pirate and divide the stones equally into three, but when they did so, one stone remained. They woke the 4th pirate and again tried to share the treasure, and again there was only one stone left. It was the same when they woke the fifth and sixth pirates. Only when they woke up the seventh pirate did they manage to separate all the stones without a trace.
How many (minimum) gems made pirate mining?
Faulty coin & perfect coin
I have two coins.
* One of the coin is a faulty coin having tail on both side of it.
* The other coin is a perfect coin (heads on side and tail on other).

I blind fold myself and pick a coin and put the coin on table. The face of coin towards the sky is tail.

What is the probability that other side is also tail?

Transfer
I have 2 coins:
* One of them is the wrong coin, with tails on both sides.
* The second coin is an ideal coin (an eagle on one side, and a tails on the back).

With blindfolds, I take a coin and toss it on the table. The visible part of the coin is tails.

What is the likelihood that the tails are also on the back?

Tasks

Print all nodes at distance k
Given a binary tree, a target node in the binary tree, and an integer value k, print all the nodes that are at distance k from the given target node. No parent pointers are available.

Consider the tree shown in diagram:
```
 
                              20
                             / \
                            8 22
                          / \
                        4 12
                              / \
                             10 14
```
Input: target = pointer to node with data 8; root = pointer to node with data 20; k = 2.
Output: 10 14 22

If target is 14 and k is 3, then output should be “4 20”
Transfer
Given a binary tree, the selected tree node and integer k. Print all tree nodes that are k away from the target node. Parent links are not available.

Consider the tree:
```
 
                              20
                             / \
                            8 22
                          / \
                        4 12
                              / \
                             10 14
```
Input: target = pointer to node 8; root = pointer to node 20; k = 2.
Output: 10 14 22

If target = 14 and k = 3, then the output should be “4 20”.
Car assembly task
A car factory has two assembly lines, each with n stations. A station is denoted by S _{i, j} where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by a _{i, j} . Each station is dedicated to some sort of work like engine fitting, body fitting, painting and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station S _{i, j} , it will continue to station S _{i, j + 1}unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j - 1 to station j on the other line takes time t _{i, j} . Each assembly line takes an entry time e _i and exit time x _i which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

Transfer
The machine factory has 2 assembly lines, each with N stations. The station is determined by S _{i, j} , where i, which can take the values 1 or 2, indicates the line on which the station is located, and j - indicates the number of the station. The time spent by the station is denoted as a _{i, j} . Each station is designed to perform a specific type of work - fitting the engine, adjusting the hull, painting, etc. So, the chassis of the machine must go through all n stations in a certain order before it is released from the factory. Parallel stations on both assembly lines perform the same task. After the part passes through the station S _{i, j} , it will continue to move through S _{i, j + 1}if it is not decided to transfer it to another line. The transition from station to station on one line does not require additional time, but the transfer from station ji to station j on another line requires time t _{i, j} . Each assembly line also has an input time e _i and an output time x _i , which may be different for both lines. Suggest an algorithm with minimal machine assembly time.
Search in sorted matrix
Given an nxn matrix, where every row and column is sorted in increasing order. Given a key, write a program finding whether this key is in the matrix.

Transfer
Given an NxN matrix, where each row and column are sorted in ascending order. The key meaning is given. Write a program to determine where this key value is located in the matrix.

Answers will be given within the next week - have time to decide. Good luck

Solutions

Question 1
The pirates had 301 gems, as correctly noted in the commentary .
Question 2
The probability is 2/3, why you can see in this comment .

Task 1

Solution Option:

// Java program to print all nodes at a distance k from given node
// A binary tree node
class Node 
{
    int data;
    Node left, right;
    Node(int item) 
    {
        data = item;
        left = right = null;
    }
}
class BinaryTree 
{
    Node root;
    /* Recursive function to print all the nodes at distance k in
       tree (or subtree) rooted with given root. */
    void printkdistanceNodeDown(Node node, int k) 
    {
        // Base Case
        if (node == null || k < 0)
            return;
        // If we reach a k distant node, print it
        if (k == 0) 
        {
            System.out.print(node.data);
            System.out.println("");
            return;
        }
        // Recur for left and right subtrees
        printkdistanceNodeDown(node.left, k - 1);
        printkdistanceNodeDown(node.right, k - 1);
    }
    // Prints all nodes at distance k from a given target node.
    // The k distant nodes may be upward or downward.This function
    // Returns distance of root from target node, it returns -1
    // if target node is not present in tree rooted with root.
    int printkdistanceNode(Node node, Node target, int k) 
    {
        // Base Case 1: If tree is empty, return -1
        if (node == null)
            return -1;
        // If target is same as root.  Use the downward function
        // to print all nodes at distance k in subtree rooted with
        // target or root
        if (node == target) 
        {
            printkdistanceNodeDown(node, k);
            return 0;
        }
        // Recur for left subtree
        int dl = printkdistanceNode(node.left, target, k);
        // Check if target node was found in left subtree
        if (dl != -1) 
        {
            // If root is at distance k from target, print root
            // Note that dl is Distance of root's left child from 
            // target
            if (dl + 1 == k) 
            {
                System.out.print(node.data);
                System.out.println("");
            }
            // Else go to right subtree and print all k-dl-2 distant nodes
            // Note that the right child is 2 edges away from left child
            else
                printkdistanceNodeDown(node.right, k - dl - 2);
            // Add 1 to the distance and return value for parent calls
            return 1 + dl;
        }
        // MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
        // Note that we reach here only when node was not found in left 
        // subtree
        int dr = printkdistanceNode(node.right, target, k);
        if (dr != -1) 
        {
            if (dr + 1 == k) 
            {
                System.out.print(node.data);
                System.out.println("");
            } 
            else
                printkdistanceNodeDown(node.left, k - dr - 2);
            return 1 + dr;
        }
        // If target was neither present in left nor in right subtree
        return -1;
    }
    // Driver program to test the above functions
    public static void main(String args[]) 
    {
        BinaryTree tree = new BinaryTree();
        /* Let us construct the tree shown in above diagram */
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.right = new Node(22);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);
        Node target = tree.root.left.right;
        tree.printkdistanceNode(tree.root, target, 2);
    }
}

Task 2

Initial solution:

// A C program to find minimum possible time by the car chassis to complete
#include 
#define NUM_LINE 2
#define NUM_STATION 4
// Utility function to find minimum of two numbers
int min(int a, int b) { return a < b ? a : b; }
int carAssembly(int a[][NUM_STATION], int t[][NUM_STATION], int *e, int *x)
{
    int T1[NUM_STATION], T2[NUM_STATION], i;
    T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 1
    T2[0] = e[1] + a[1][0]; // time taken to leave first station in line 2
    // Fill tables T1[] and T2[] using the above given recursive relations
    for (i = 1; i < NUM_STATION; ++i)
    {
        T1[i] = min(T1[i-1] + a[0][i], T2[i-1] + t[1][i] + a[0][i]);
        T2[i] = min(T2[i-1] + a[1][i], T1[i-1] + t[0][i] + a[1][i]);
    }
    // Consider exit times and retutn minimum
    return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]);
}
int main()
{
    int a[][NUM_STATION] = {{4, 5, 3, 2},
                {2, 10, 1, 4}};
    int t[][NUM_STATION] = {{0, 7, 4, 5},
                {0, 9, 2, 8}};
    int e[] = {10, 12}, x[] = {18, 7};
    printf("%d", carAssembly(a, t, e, x));
    return 0;
}

Task 3

An interesting graphical analysis of the task is proposed here. Initial option:

// Java program for implementation of divide and conquer algorithm 
// to find a given key in a row-wise and column-wise sorted 2D array
class SearchInMatrix
{
    public static void main(String[] args)
    {
        int[][] mat = new int[][] { {10, 20, 30, 40}, 
                                    {15, 25, 35, 45},
                                    {27, 29, 37, 48},
                                    {32, 33, 39, 50}};
        int rowcount = 4,colCount=4,key=50;
        for (int i=0; i=fromCol)
                  search(mat, fromRow, toRow, fromCol, j-1, key);
            }
        }
    }
}

Tags:

Issue # 18: IT training - current issues and challenges from leading companies

Questions

Tasks

Solutions

Also popular now: