Linkedin | SRE | Coding OA and Solutions | Set-17 | 2022

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

Arranging Numbers
Jayme has a list of consecutive numbers beginning with 1. Her arrangement of those numbers is called a beautiful arrangement if at least one of the following is true:

 

• The number present at the ith position is divisible by i
• i is divisible by the number present at the ith position.

 

Determine how many beautiful arrangements of her integers is possible. For example, she has n =5 integers, [1,2,3,4,5]. Using 1-based indexing, there are the following arrangements satisfying the above:

 

[1,2,3,4,5]
[2,1,3,4,5]
[3,2,1,4,5]
[4,2,3,1,5]
[5,2,3,4,1]
[4,1,3,2,5]
[1,4,3,2,5]
[3,4,1,2,5]
[2,4,3,1,5]
[5,4,3,2,1]

 

In the first row, both conditions hold for all elements: each i equals the value at index i, so each i is divisible by the element and each element is divisible by its index i. In the next row, where the first two elements have been switched, where i = 1 and value is 2, 2 is divisible by i. In the next position, index i=2 is divisible by its element value of 1. Similar logic is applied to form each of the subsequent rows.

 

Constraints

 

• 1 < n < 20

Answer 2

Can use bruteforce via backtracking.

 

pub fn arranging_numbers(n: usize) -> usize {
    let mut visited = vec![false; n];
    let mut count = 0;
    backtrack_arrange(&mut visited, &mut count, 0);
    count
}

pub fn backtrack_arrange(visited: &mut Vec<bool>, count: &mut usize, position: usize) {
    if position == visited.len() {
        *count += 1;
    }

    for i in 0..visited.len() {
        if !visited[i] && ((position + 1) % (i + 1) == 0 || (i + 1) % (position + 1) == 0) {
            visited[i] = true;
            backtrack_arrange(visited, count, position + 1);
            visited[i] = false;
        }
    }
}

Answer 3

https://leetcode.com/problems/beautiful-arrangement/discuss/1423458/c-backtracking