Amazon OA | SDE 1 | And Sort | July 2025 | Kumar K

Question

Answer 1

#include <iostream>

#include <vector>

#include <algorithm>

#include <unordered_set>

using namespace std;

void dfs(int node, const vector<vector<int>>& adj, vector<bool>& visited, vector<int>& component) {

    visited[node] = true;

    component.push_back(node);

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            dfs(neighbor, adj, visited, component);

        }

    }

}

int getSortingFactorK(const vector<int>& arr) {

    int n = arr.size();

    for (int k = n - 1; k >= 0; k--) {

        vector<vector<int>> adj(n);

        // Build the graph based on bitwise AND condition

        for (int i = 0; i < n; i++) {

            for (int j = i + 1; j < n; j++) {

                if ((arr[i] & arr[j]) == k) {

                    adj[i].push_back(j);

                    adj[j].push_back(i);

                }

            }

        }

        vector<bool> visited(n, false);

        bool canSort = true;

        for (int i = 0; i < n && canSort; i++) {

            if (!visited[i]) {

                vector<int> indices;

                dfs(i, adj, visited, indices);

                vector<int> values;

                for (int idx : indices) values.push_back(arr[idx]);

                sort(indices.begin(), indices.end());

                sort(values.begin(), values.end());

                for (int j = 0; j < indices.size(); j++) {

                    if (values[j] != indices[j]) {

                        canSort = false;

                        break;

                    }

                }

            }

        }

        if (canSort) return k;

    }

    return 0; // Default if nothing else works

}

int main() {

    vector<int> arr = {0, 3, 2, 1};

    cout << getSortingFactorK(arr) << endl;  // Output: 1

    return 0;

}

Answer 2

class Solution {

    public int sortPermutation(int[] nums) {

        int ans = Integer.MAX_VALUE;

        for(int i=0 ; i<nums.length; i++){

            if(i!= nums[i]){

                ans &= nums[i];

            }

        }

        return ans==Integer.MAX_VALUE? 0 : ans;

    }

}

Answer 3

def getSortingFactorK(arr):

    n = len(arr)

    sorted_arr = sorted(arr)

    

    def can_sort_with_k(k):

        # Build adjacency list

        adj = [[] for _ in range(n)]

        for i in range(n):

            for j in range(i + 1, n):

                if (arr[i] & arr[j]) >= k:

                    adj[i].append(j)

                    adj[j].append(i)

        

        # Find connected components using DFS

        visited = [False] * n

        for start in range(n):

            if not visited[start]:

                stack = [start]

                component_indices = []

                component_values = []

                while stack:

                    node = stack.pop()

                    if not visited[node]:

                        visited[node] = True

                        component_indices.append(node)

                        component_values.append(arr[node])

                        for neighbor in adj[node]:

                            if not visited[neighbor]:

                                stack.append(neighbor)

                

                # Check if component can be sorted internally

                if sorted(component_values) != [sorted_arr[i] for i in component_indices]:

                    return False

        return True

    

    # Try k from max possible bit (max(arr)) down to 0

    max_val = max(arr)

    for k in range(max_val, -1, -1):

        if can_sort_with_k(k):

            return k

    return 0

# Example usage

arr = [0, 3, 2, 1]

print(getSortingFactorK(arr))  # Output: 1

Answer 4

// leetcode problem link : https://leetcode.com/problems/maximum-k-to-sort-a-permutation/

int sortPermutation(vector<int>& nums) {

        int ans =-1;

        int n = nums.size();

        for(int i=0;i<n;i++){

            if(nums[i]!=i){

                if(ans == -1) ans = nums[i];

                else ans &= nums[i];

            }

        }

        return ans == -1 ? 0 : ans;

    }