Combine 2 different custom post slugs into a single permalink?

Here’s the solution if anyone comes across such a ‘weird’ requirement 😉
Also, when the job CPT (or any CPT you want to associate) is published, you need to save the id of the company CPT (whose slug will be used for forming the other part of the permalink) as a post meta for the job.

<?php
add_filter('init', 'add_page_rewrite_rules');
function add_page_rewrite_rules(){
    global $wp_rewrite, $wp;

    add_rewrite_rule('^company/([^/]+)/job/([^/]+)', 'index.php?company=$matches[1]&job=$matches[2]', 'top');
    $job_structure="/job/%job%";
    $wp_rewrite->add_rewrite_tag("%job%", '([^/]+)', "job=");
    $wp_rewrite->add_permastruct('job', $job_structure, false);

}

add_filter('post_type_link', 'job_permalink', 10, 3);
function job_permalink($permalink, $post_id, $leavename) {
    $post = get_post($post_id);
    $rewritecode = array(
    '%job%',
    'job'
    );

    if ( '' != $permalink && !in_array($post->post_status, array('draft', 'pending', 'auto-draft')) ) {
        job_link = '';
        if ( strpos($permalink, 'job') !== false ) {
            $company_id = get_post_meta($post->ID, 'job_company_id', true);
            $company = basename(get_permalink($company_id));
            $job_link = 'company'."https://wordpress.stackexchange.com/".$company;
        }

        $rewritereplace = array(
                                    $post->post_name,
                                    $job_link.'/job'
                        );
        $permalink = str_replace($rewritecode, $rewritereplace, $permalink);
    } 
    else { 
        // if they're not using the fancy permalink option
    }
    return $permalink;
}
?>

Hope this helps someone! You can contact me if stuck while implementing this.