Coding tasks for IT interview

Problem: Find the only element which appears once.

In an unsorted long array of integers (100 millions unique numbers),
every element appears twice except for one element that appears only once.
Return that element.

Example:
a=[1,4,2,4,1,3,2]
Output: 3

Function could be: public int solution( int[] array) {...}

Problem: Find a duplicate in an array

Given an array of n + 1 integers between 1 and n, find one of the duplicates.
If there are multiple possible answers, return one of the duplicates.
If there is no duplicate, return -1.

Example 1:
Input: [1, 2, 2, 3]
Output: 2

Example 2:
Input: [3, 4, 1, 4, 1]
Output: 4 or 1

Problem: Reverse an immutable list.

Task:
We have to implement the following interface to reverse an input list:

public interface Reverser {
    List reverseList(final List list);
}

The only constraint is that the input 'list' is immutable.

Example:
Input: 1, 2, 3
Output: 3, 2, 1

Note:
Take memory and processor consumption into the consideration.

Problem: Build biggest number from a list of numbers.

Given a list of non negative integers, arrange them such that they form the largest number.

Example:
Given [3, 30, 34, 5, 9],
the largest formed number is 9534330.

The result may be very large, so you need to return a string instead of an integer.

Problem: Compute the length of single-link list without a cycle.

A pointer is called a linked list if:

it is an empty pointer (it is then called a terminator or an empty list); or
it points to a structure (called a node or the head) that contains a value and a linked list (called the tail).

The length of a list is defined as the total number of nodes it contains. In particular, an empty list has length 0.

For example, consider the following linked list:

A -> B -> C -> D ->

This list contains four nodes: A, B, C and D. Node D is the last node and its tail is the terminator. The length of this list is 4.
Assume that the following declarations are given:

class IntList {
  public int value;
  public IntList next;
}

Write a function:

class Solution { public int solution(IntList L); }

that, given a non-empty linked list L consisting of N nodes, returns its length.

For example, given list L shown in the example above, the function should return 4.
Assume that:

N is an integer within the range [1..5,000];
list L does not have a cycle (each non-empty pointer points to a different structure).

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

class Solution {
    public int solution(IntList L) {
        // write your code in Java SE 8
    }
}

Poblem: Count the number of pairs (x, y) such that x * y >= x + y.

Zero-indexed arrays A and B consisting of N non-negative integers are given.
Together, they represent N real numbers, denoted as C[0], ..., C[N-1].
Elements of A represent the integer parts and the corresponding elements of B (divided by 1,000,000) represent the fractional parts of the elements of C.
More formally, A[I] and B[I] represent C[I] = A[I] + B[I] / 1,000,000.

For example, consider the following arrays A and B:

A[0] = 0	B[0] = 500,000
A[1] = 1	B[1] = 500,000
A[2] = 2	B[2] = 0
A[3] = 2        B[3] = 0
A[4] = 3	B[4] = 0
A[5] = 5	B[5] = 20,000

They represent the following real numbers:

C[0] = 0.5
C[1] = 1.5
C[2] = 2.0
C[3] = 2.0
C[4] = 3.0
C[5] = 5.02

A pair of indices (P, Q) is multiplicative if 0 <= P < Q < N and C[P] * C[Q] >= C[P] + C[Q].
The above arrays yield the following multiplicative pairs:

(1, 4), because 1.5 * 3.0 = 4.5 >= 4.5 = 1.5 + 3.0,
(1, 5), because 1.5 * 5.02 = 7.53 >= 6.52 = 1.5 + 5.02,
(2, 3), because 2.0 * 2.0 = 4.0 >= 4.0 = 2.0 + 2.0,
(2, 4) and (3, 4), because 2.0 * 3.0 = 6.0 >= 5.0 = 2.0 + 3.0.
(2, 5) and (3, 5), because 2.0 * 5.02 = 10.04 >= 7.02 = 2.0 + 5.02.
(4, 5), because 3.0 * 5.02 = 15.06 >= 8.02 = 3.0 + 5.02.

Write a function:

class Solution { public int solution(int[] A, int[] B); }

that, given zero-indexed arrays A and B, each containing N non-negative integers, returns the number of multiplicative pairs of indices.
If the number of multiplicative pairs is greater than 1,000,000,000, the function should return 1,000,000,000.
For example, given:

A[0] = 0	B[0] = 500,000
A[1] = 1	B[1] = 500,000
A[2] = 2	B[2] = 0
A[3] = 2	B[3] = 0
A[4] = 3	B[4] = 0
A[5] = 5	B[5] = 20,000

the function should return 8, as explained above.

Assume that:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [0..1,000];
each element of array B is an integer within the range [0..999,999];
real numbers created from arrays are sorted in non-decreasing order.

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

class Solution {
    public int solution(int[] A, int[] B) {
        // write your code in Java SE 8
    }
}

Problem: Check hotel reservations.

A hotel manager has to process N bookings of rooms for the next season.
His hotel has K rooms.
Bookings contain an arrival date and a departure date.
He wants to find out whether there are enough rooms in the hotel to satisfy the demand.

Inputs:

First list for arrival time of booking
Second list for departure time of booking
Third is K which denotes the count of rooms

Output:

A boolean which tells whether its possible to make a booking
false means there are not enough rooms for N booking
true means there are enough rooms for N booking

Example

Inputs:

arrivals = [1, 3, 5]
departures = [2, 6, 10]
K = 1

Output: false.

At day = 5, there are 2 guests in the hotel. But we have only one room.

Problem: Calculator

Write some code to calculate a result from a set of instructions.
Instructions comprise of a keyword and a number that are separated by a space per line.
Instructions are loaded from file and results are output to the screen.
Any number of Instructions can be specified.
Instructions can be any binary operators of your choice (e.g., add, divide, subtract, multiply etc).
The instructions will ignore mathematical precedence.
The last instruction should be “apply” and a number (e.g., “apply 3”).
The calculator is then initialised with that number and the previous instructions are applied to that number.

Examples of the calculator lifecycle might be:

Example 1

Input from file:

add 2
multiply 3
apply 3

Output to screen:

Explanation:

(3 + 2) * 3 = 15

Example 2

Input from file:

multiply 9
apply 5

Output to screen:

Explanation:

5 * 9 = 45

Example 3

Input from file:

apply 1

Output to screen: