先说店面
Finding all pairs of elements (say, a and b) from elements in an array such that a & b is 0.
input: {1, 2, 6, 9, 3}
output: [6,9],[1,2],[2,9],[1,6]
inuput {1, 2, 6, 9, 3, 0}
output: [2,9],[3,0],[2,0],[6,0],[1,6],[9,0],[1,0],[1,2],[6,9]
Solution: Brute force is obivious
Details
private List<int[]> pairs(int items[]) {
if (items == null || items.length == 0)
return Collections.EMPTY_LIST;
final Set<int[]> pairs = new HashSet<>();
for (int i = 0; i < items.length; i++) {
for (int j = i + 1; j < items.length; j++) {
int e1 = items[i];
int e2 = items[j];
if ((e1 & e2) == 0)
pairs.add(new int[]{e1, e2});
}
}
return new ArrayList<>(pairs);
}
Solution 2: I thought about one more solution but that also end up to O(n^2)
Algo:
Find all elements whose 1’s bit (right most) is set
Find all elements whose 1’s bit (right most) is NOT set
Iterate both list and do & and check
Example: {1, 2, 6, 9, 3}
1st bit set -> {1,9,3}
1st bit not set -> {2,6}
output: [6,9],[1,2],[2,9],[1,6]
3 will be discard with all of them as 3 & 2!=0 , 3&6!=0
In worst case, the array will be divied in two parts. Hence O(n^2)
上门我就说下Board Game这题，没做出来的
You are implementing a board game where you are given a size N x M for the board, where N is the number of rows and M is the number of columns.
In this board game you are playing with some fixed size lego pieces, where each player places 1 piece on the board every turn until no more piece can fit onto the board, and the last player to move wins.
The problem is to implement a method for making a move on this board, placing a piece wherever there is space available, and returns a boolean indicating whether or not the player that has just made the move has won.
Follow up question: The method should also find if there is any move that can be made that will make it so that the next player is unable to place a piece anywhere on the board in their next turn, and make that move.
You choose how to represent the board and lego pieces in the problem, during my interview I chose to use a 2D array of booleans for the board, where each boolean indicates whether that spot on the board is occupied, and for the lego piece I asked the interviewer if I could assume the lego piece would be rectangular, which he agreed to.
Simple example (small board for demonstration purposes, board length = 2 x 3, lego piece length = 1 x 2):
Empty Board:
O O O
O O O
Board after player 1 makes move, placing lego piece at top right corner:
O X X
O O O
At this point, player 2 can make a move that will prevent player 1 from placing another piece:
O X X
X X O
and so the method should be able to find and make that winning move, rather than an alternative move that would
miss an opportunity for a win:
O X X
O X X
I devised something like the following outline for my solution during the interview based on the requirements:
Piece = collections.namedTuple('Piece', ['x', 'y'])
class BoardGame:
def __init__(self, n, m, x_length, y_length):
self.board = [[False] * m for _ in range(n)]
self.pieceRows = x_length
self.pieceCols = y_length
# returns a boolean indicating whether a winning move was made
def makeMove(self):
...
In my code x and y are parameters for the size of the lego piece to be used in the game.
My solution used a brute force approach checking every possible spot in the board to make a move and check if this would be a winning move, but could not come up with an efficient implementation, even now after the interview. Can anyone come up with an efficient approach that would solve the problem more effectively than a brute force approach?
还有 Self-Descriptive Number 这题，类似 https://rosettacode.org/wiki/Self-describing_numbers
An integer is said to be self-descriptive if it has the property that, when digit positions are labeled 0 to N-1, the digit in each position is equal to the number of times that this digit appears in the number. Write a function that will check whether a given positive integer is self-descriptive.
Example 1:
Input: 2020
Output: true
Explanation:
Position 0 has value 2 and there are two 0s in the number
Position 1 has value 0 and there are no 1s in the number
Position 2 has value 2 and there are two 2s
Position 3 has value 0 and there are zero 3s
Example 2:
Input: 3211000
Output: true
Explanation:
Position 0 has value 3 and there are three 0s in the number
Position 1 has value 2 and there are two 1s in the number
Position 2 has value 1 and there is one 2 in the number
Position 3 has value 1 and there is one 3 in the number
Position 4 has value 0 and there are zero 4s
Position 5 has value 0 and there are zero 5s
Position 6 has value 0 and there are zero 6s
Follow-up:
Generate all self-descriptive numbers that will fit in a 32-bit integer. There are 5 such integers:
1210
2020
21200
3211000
42101000