How to achieve this permalink -> category-name/custom-post-type-name/post-name

You have to filter 'post_type_link' to create the appropriate permalink. See this answer for a similar example.

The following code works:

add_action( 'init', array ( 'WPSE_63343', 'init' ) );

class WPSE_63343
{
    protected $post_type="video";

    public static function init()
    {
        new self;
    }

    public function __construct()
    {
        $args = array (
            'public' => TRUE,
            'rewrite' => array(
                'slug' => '[^/]+/' . $this->post_type .'/([^/]+)/?$'
            ),
            'has_archive' => TRUE,
            'supports' => array( 'title', 'editor' ),
            'taxonomies' => array( 'category' ),
            'labels' => array (
                'name' => 'Video',
                'singular_name' => 'Video'
            )
        );
        register_post_type( $this->post_type, $args );

        add_rewrite_rule(
            '[^/]+/' . $this->post_type .'/([^/]+)/?$',
            'index.php?post_type=" . $this->post_type . "&pagename=$matches[1]',
            'top'
        );

        // Inject our custom structure.
        add_filter( 'post_type_link', array ( $this, 'fix_permalink' ), 1, 2 );

        # uncomment for debugging
        # add_action( 'wp_footer', array ( $this, 'debug' ) );
    }

    /**
     * Print debug data into the 404 footer.
     *
     * @wp-hook wp_footer
     * @since   2012.09.04
     * @return  void
     */
    public function debug()
    {
        if ( ! is_404() )
        {
            return;
        }

        global $wp_rewrite, $wp_query;

        print '<pre>' . htmlspecialchars( print_r( $wp_rewrite, TRUE ) ) . '</pre>';
        print '<pre>' . htmlspecialchars( print_r( $wp_query, TRUE ) ) . '</pre>';
    }

    /**
     * Filter permalink construction.
     *
     * @wp-hook post_type_link
     * @param  string $post_link default link.
     * @param  int    $id Post ID
     * @return string
     */
    public function fix_permalink( $post_link, $id = 0 )
    {
        $post = &get_post( $id );
        if ( is_wp_error($post) || $post->post_type != $this->post_type )
        {
            return $post_link;
        }
        // preview
        empty ( $post->slug )
        and ! empty ( $post->post_title )
        and $post->slug = sanitize_title_with_dashes( $post->post_title );

        $cats = get_the_category( $post->ID );

        if ( ! is_array( $cats ) or ! isset ( $cats[0]->slug ) )
        {
            return $post_link;
        }

        return home_url(
            user_trailingslashit( $cats[0]->slug . "https://wordpress.stackexchange.com/" . $this->post_type . "https://wordpress.stackexchange.com/" . $post->slug )
        );
    }
}

Don’t forget to visit the permalink settings once to refresh the stored rewrite rules.