Amazon Interview Question SDE1s
Country: United States
Interview Type: Written Test
Thank you so much for the help. Could you please describe the logic with explanation for understanding. Thanks a lot.
Thank you so much for the help. Could you please describe the logic with explanation for understanding. Thanks a lot.
It is brute force, as SK says, but we can avoid exploring some options. It's a recursive solution. The strategy is to start from the pair that has the fewest options, when the gap is
n
and then proceed to
n-1
. If we can't find a fit for the current pair
gap
, we return false, which results in us unwinding the placement of
gap+1
, (setting back to zero). If we get to a
gap
of zero we have a solution. Since the array is passed by reference we don't need to return it from
explore()
. The approach is called 'backtracking'.
public static int[] findSolution(int n){
int[] sol = new int[2*n];
if (explore(sol, n)) return sol;
return null;
}
public static boolean explore(int[] sol, int gap){
if (gap == 0) return true;
for (int i = sol.length-1; i - gap > 0 ; i--) {
if (sol[i] == 0 && sol[i-gap-1] == 0) {
sol[i] = gap;
sol[i-gap-1] = gap;
if (explore(sol, gap-1)) return true;
else {
sol[i] = 0;
sol[i-gap-1] = 0;
}
}
}
return false;
}
To add to that (From Wiki page of Langford Sequence)
Langford pairings exist only when n is congruent to 0 or 3 modulo 4; for instance, there is no Langford pairing when n = 1, 2, or 5.
The numbers of different Langford pairings for n = 1, 2, …, counting any sequence as being the same as its reversal, ar
0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, …
Langford pairings exist only when n is congruent to 0 or 3 modulo 4; for instance, there is no Langford pairing when n = 1, 2, or 5.
The numbers of different Langford pairings for n = 1, 2, …, counting any sequence as being the same as its reversal, are
0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, … (sequence A014552 in OEIS).
Arrange copies of the n digits 1, ..., n such that there is one digit between the 1s, two digits between the 2s, etc. For example, the unique (modulo reversal) n=3 solution is 231213, and the unique (again modulo reversal) n=4 solution is 23421314. Solutions to Langford's problem exist only if n=0,3 (mod 4), so the next solutions occur for n=7. There are 26 of these, as exhibited by Lloyd (1971). In lexicographically smallest order (i.e., small digits come first), the first few Langford sequences are 231213, 23421314, 14156742352637, 14167345236275, 15146735423627, ...
Arrange copies of the n digits 1, ..., n such that there is one digit between the 1s, two digits between the 2s, etc. For example, the unique (modulo reversal) n=3 solution is 231213, and the unique (again modulo reversal) n=4 solution is 23421314.
Solutions to Langford's problem exist only if n=0,3 (mod 4), so the next solutions occur for n=7.
There are 26 of these, as exhibited by Lloyd (1971).
In lexicographically smallest order (i.e., small digits come first), the first few Langford sequences are 231213, 23421314, 14156742352637, 14167345236275, 15146735423627, ...
public static int[] GetSequence(int n)
{
var result = new int[n * 2];
var usage = new byte[n + 1];
for (int i = 1; i <= n; i++)
{
result[0] = i;
usage[i]++;
if (SetSequence(result, 1, n, usage))
{
return result;
}
else
{
usage[i]--;
}
}
return null;
}
private static bool SetSequence(int[] result, int startIndex, int n, byte[] usage)
{
if (startIndex == n * 2)
{
return true;
}
for (int i = 1; i <= n; i++)
{
if (usage[i] == 0)
{
result[startIndex] = i;
usage[i]++;
if (!SetSequence(result, startIndex + 1, n, usage))
{
usage[i]--;
}
else
{
return true;
}
}
else if (usage[i] == 1 &&
startIndex - i - 1 >= 0 &&
result[startIndex - i - 1] == i)
{
result[startIndex] = i;
usage[i]++;
if (!SetSequence(result, startIndex + 1, n, usage))
{
usage[i]--;
}
else
{
return true;
}
}
}
return false;
}
<?php
$input = 3;
$output = [];
for ($i = 0; $i < 2*$input; $i++) {
$output[$i] = 0;
}
function check_insert_pair($arr, $number, $index) {
if ($number + $index + 1 > count($arr))
return false;
else if (($arr[$index] != 0)|| ($arr[$index + $number + 1] != 0)){
return false;
}
return true;
}
function solve( &$arr, $number) {
//echo $number;
if ($number > count($arr) / 2)
return true;
for ($j = 0; $j < count($arr) - $number -1; $j++) {
if (check_insert_pair($arr, $number, $j)) {
$arr[$j] = $number;
$arr[$j + $number + 1] = $number;
if (solve($arr, $number + 1))
return true;
else {
$arr[$j] = 0;
$arr[$j + $number + 1] = 0;
}
}
}
return false;
}
solve($output, 1);
print_r($output);
?>
var sequence = function (n) {
var solution = new Array(n * 2);
function arrange(v) {
if (v === 0) {
return true;
}
for (var i = 0; i < solution.length - v - 1; i++) {
if (!solution[i] && !solution[i + v + 1]) {
solution[i] = v;
solution[i + v + 1] = v;
if (arrange(v - 1)) {
return true;
}
solution[i] = undefined;
solution[i + v + 1] = undefined;
}
}
return false;
};
if (arrange(n)) {
return solution;
}
else
{
return undefined;
}
};
def fact(n):
if n == 1:
return 1
return n*fact(n-1)
def sequenceutil(arr, length, n, index):
res = False
if index > n:
print arr
return True
for x in range(length-index-1):
if arr[x] == -1 and arr[x+index+1] == -1:
arr[x] = index
arr[x+index+1] = index
res = sequenceutil(arr, length, n, index+1)
if res == False:
arr[x] = -1
arr[x+index+1] = -1
else:
break
return res
def sequence(n):
arr = [-1 for x in range(fact(n))]
return sequenceutil(arr, fact(n), n, 1)
#main
n = 3
sequence(n)
def fact(n):
if n == 1:
return 1
return n*fact(n-1)
def sequenceutil(arr, length, n, index):
res = False
if index > n:
print arr
return True
for x in range(length-index-1):
if arr[x] == -1 and arr[x+index+1] == -1:
arr[x] = index
arr[x+index+1] = index
res = sequenceutil(arr, length, n, index+1)
if res == False:
arr[x] = -1
arr[x+index+1] = -1
else:
break
return res
def sequence(n):
arr = [-1 for x in range(fact(n))]
return sequenceutil(arr, fact(n), n, 1)
#main
n = 3
Langford pairings exist only when n is congruent to 0 or 3 modulo 4; for instance, there is no Langford pairing when n = 1, 2, or 5.
The numbers of different Langford pairings for n = 1, 2, …, counting any sequence as being the same as its reversal, are
0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, …
sequence A014552 in OEIS.
Langford pairings exist only when n is congruent to 0 or 3 modulo 4; for instance, there is no Langford pairing when n = 1, 2, or 5.
The numbers of different Langford pairings for n = 1, 2, …, counting any sequence as being the same as its reversal, ar
0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, … (sequence A014552 in OEIS)
- Anonymous August 12, 2015public static int[] findSolution(int n){ int[] sol = new int[2*n]; if (explore(sol, n)) return sol; return null; } public static boolean explore(int[] sol, int gap){ if (gap == 0) return true; for (int i = sol.length-1; i - gap > 0 ; i--) { if (sol[i] == 0 && sol[i-gap-1] == 0) { sol[i] = gap; sol[i-gap-1] = gap; if (explore(sol, gap-1)) return true; else { sol[i] = 0; sol[i-gap-1] = 0; } } } return false; }