Launch of 5G chipsets by Qualcomm for AR/VR Headsets

Virtual reality (VR) and augmented reality (AR) is all set to transform the way users used to access technology. The headsets can take you to places and show things that don't even exist in the real world. Qualcomm's all-new AR/VR tech brings 5G support and caters to the needs of standalone VR, AR headsets.

Qualcomm claims that the XR2 chip is in line with the company's new mobile chips, including the most awaited Snapdragon 865, 765, and 765G. These chipsets support 5G mobile network connectivity. Qualcomm believes that the future of mobile devices is an aggregate of different display technologies. The VR headsets can be used for various uses cases, right from web browsing, to recipe tutorials and even GPS navigation.

In an official statement, Qualcomm said, "Multiple OEMs are committed to commercializing devices with the Snapdragon XR2 Platform, and other customers are in various stages of prototyping and evaluation."

The XR2 5G platform is designed to support 3K x 3K displays at 90Hz. It will offer accelerated AI processing, and work with up to seven simultaneous camera feeds. The XR2 is a successor to the Snapdragon XR1 which was made especially for the low-end AR and VR headsets.

The latest iteration of the chipset targets high-end standalone headsets including Oculus Quest 2, Magic Leap 2, and similar next-generation devices. The new platform offers notable improvements. Qualcomm claims that the CPU and GPU performance by 2x, pixel throughput for video playback by 4x, and up to 6x resolution per-eye compared to Snapdragon 835.

The simultaneous camera will support advanced tracking, both for the environment and the user. Oculus Quest features four cameras that can track the position of headset and controllers. XR2 offers low-latency pass-through, which improves the pass-through video experience on high-end headsets.

C++ program to convert Sorted Array to binary search tree

Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node%u2019s key.
• The right subtree of a node contains only nodes with keys greater than the node%u2019s key.
• The left and right subtree each must also be a binary search tree.

Algorithm

The mid-value of the given sorted array would represent the root of one possible BST that can be constructed from the given array elements.

1. Find the middle element of the array and make it root(Now the array is divided into two halves left and right, where the left half is our left subtree and right half, is our right subtree)

2. Recursively do the same for the left half and right half.

       (a) Get the middle of left half and make it left child of the root created into Step 1.

       (b) Get the middle of right half and make it right child of the root created into Step 1.

3. The base condition that would terminate the recursion would then be if low boundary index            exceeds high boundary index, in which case return null.

#include<iostream> using namespace std; struct Node { int data; Node *left; //pointer points to left node Node *right; //pointer points to right node }; /*function that returns new node*/ Node *newNode(int x) { Node *temp = new Node(); //temp points to the dyanamically formed node temp->data = x; temp->left = NULL; temp->right = NULL; return temp; //return the address of the node temp is pointing } Node *arrayToBST(int *arr, int start, int end) { /* Base Case*/ if(start > end) { return NULL; } /*Get the middle element and make it root*/ int mid = (start + end)/2; Node *root = newNode(arr[mid]); /* Recursively construct the left subtree and make it left child of root */ root->left = arrayToBST(arr,start,mid-1); /* Recursively construct the right subtree and make it right child of root */ root->right = arrayToBST(arr,mid+1,end); return root; } /*Function inOrder prints inorder traversal of the tree inorder traversal prints element in sorted order

*/ void inOrder(Node *node) { if(node == NULL) return; inOrder(node->left); cout<<node->data<<" "; inOrder(node->right); } int main() { int arr[] = {2, 4, 5, 6, 7, 10, 11, 15}; /*Number of elements in the array (total size of the array / size of one element ) In this case elements are integer */ int n = sizeof(arr)/sizeof(arr[0]); Node *root = arrayToBST(arr,0,n-1); inOrder(root); return 0; }

OUTPUT:

2 4 5 6 7 10 11 15

Our inorder traversal prints elements in sorted order, so our binary search tree is correct.

Time Complexity

T(n) = 2T(n/2) + C

By Master Theorem

T(n) = O(n)

Dynamic Programming - Rod Cutting Problem

This is one of the famous interview questions and most of you faced this question in the interview.

Question: Given a rod of length n and list of prices of rod of length i where 1 <= i <= n, find the optimal way to cut rod into smaller rods in order to maximize profit.

Program:

#include<iostream>
#include<algorithm>

using namespace std;

#define ROD_CUTS 4
#define LEN      5

int rodSize[ROD_CUTS] = {1, 2, 3, 4};
int rodSizeCost[ROD_CUTS] = {2, 5, 7, 8};
int costMatrix[ROD_CUTS][LEN+1] = {0};

int findCost(int i, int j)
{
   if(i < 1)
      return costMatrix[i][j-rodSize[i]]+rodSizeCost[i];
   else
   {
      if(j < rodSize[i])
         return costMatrix[i-1][j];
      else
         return std::max(costMatrix[i][j-rodSize[i]]+rodSizeCost[i], costMatrix[i-1][j]);
   }
}

int main()
{
   for(int i=0; i<ROD_CUTS; ++i)
   {
      for(int j=1; j<=LEN; ++j)
      {
         costMatrix[i][j] = findCost(i, j);
      }
   }
   cout << "Maximum Profit = " << costMatrix[ROD_CUTS-1][LEN] << endl;
   return 0;
}

Output:

Maximum Profit = 12

Implementing Stack using Linked List

QUESTION-

You need to implement a Stack class using linked list. The data members should be private. Implement the following public functions :

1. Constructor -

Initialises the data member (i.e. head to null).

2. push :

This function should take one argument of type int and has return type void. This function should insert an element in the stack. Time complexity should be O(1).

3. pop :

This function takes no input arguments and has return type int. This should removes the last element which is entered and return that element as an answer. Return 0 if stack is empty.

Time complexity should be O(1).

4. top :

This function takes no input arguments and has return type int. This should return the last element which is entered and return that element as an answer. Return 0 if stack is empty.

Time complexity should be O(1).

5. size :

Return the size of stack i.e. count of elements which are present ins stack right now. Time complexity should be O(1).

6. isEmpty :

Checks if the stack is empty or not. Return true or false.

SOURCE CODE-

#include<iostream>

using namespace std;

class Node {

    public :

    int data;

    Node *next;

    

    Node(int data) {

        this -> data = data;

        next = NULL;

    }

};

class Stack {

    Node *head;

    int size; // number of elements present in stack

    

    public :

    

    Stack() {

      size=0;

      head=NULL;

    }

    

    int getSize() {

        return size;

    }

    

    bool isEmpty() {

        return size==-1;

    }

    

    void push(int element) {

        Node* current=new Node(element);

      size++;

      current->next=head;

      head=current;

    }

    

    int pop() {

        // Return 0 if stack is empty. Don't display any other message

      if(head==NULL)

        return 0;

      size--;

      int data=head->data;

        head=head->next;

      return data;

    }

    

    int top() {

        // Return 0 if stack is empty. Don't display any other message

      if(head==NULL)

        return 0;

        return head->data;

    } 

};

#include "Stack.h"

int main() {

    

    Stack st;

    

    int choice;

    cin >> choice;

    int input;

    

    while (choice !=-1) {

        if(choice == 1) {

            cin >> input;

            st.push(input);

        }

        else if(choice == 2) {

            int ans = st.pop();

            if(ans != 0) {

                cout << ans << endl;

            }

            else {

                cout << "-1" << endl;

            }

        }

        else if(choice == 3) {

            int ans = st.top();

            if(ans != 0) {

                cout << ans << endl;

            }

            else {

                cout << "-1" << endl;

            }

        }

        else if(choice == 4) {

            cout << st.getSize() << endl;

        }

        else if(choice == 5) {

            cout << st.isEmpty() << endl;

        }

        cin >> choice;

    }

    

}

INPUT-

1 3 1 4 1 63 1 21 1 9 2 3 1 7 2 4 2 2 3 1 799 1 33 1 35 3 2 2 1 97 2 3 2 1 22 1 999 1 23 1 98 2 2 5 3 -1

OUTPUT-

9

21

7

4

21

63

4

35

35

33

97

799

799

98

23

false

999

find largest binary search tree in a Binary Tree

We have to write a program to find the largest binary search tree (BST) in a given binary tree.

A given tree is BST if the value of node is greater than the value of its left child and smaller than the value of its right child.

We will use top-down approach for solving this. We will traverse the whole tree. At every node we will check if the subtree is BST or not. If the current tree is BST then we found the largest BST. If not, then we  have to check the whether left or right subtree is BST or not. If only one tree is BST then we will return that subtree. If both left and right subtrees are BST, then we will return the larger of the two.

Example:

                                             60

                                         /         \

                                     50           90

                                  /      \        /      \

                               40     55    70     100

                                                /         /     \

                                             80      200  150

In the above binary tree, the whole tree is not BST because left child of 70 is 80 (>70) and also left child of 100 is 200 (>100). 

Largest BST in the above example is:

                             50

                           /     \

                         40     55

The code will return 3 as there are three nodes in the largest BST. 

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// C++ program to find largest binary search tree in a Binary Tree

#include<bits/stdc++.h>

using namespace std;

class node{ 

public: 

int data;

node* left;

node* right;

node(int data) // Constructor that makes a new node

{ 

this->data = data;

this->left = NULL;

this->right = NULL;

}

};

// This function finds the maximum size of the largest BST.

// If the tree is BST then this function returns the size of the tree

int findBST(node* node, int *minn, int *maxx, int *maxSize, bool *isBst){

// Base Case

if(node == NULL){

*isBst = 1;

return 0;

}

int lSize, rSize; // Stores the size of left and right subtree.

int mi = INT_MAX;

bool flag1 = 0; // Flag for left subtree. It stores 1 if left subtree is BST.

bool flag2 = 0; // Flag for right subtree. It stores 1 if right subtree is BST.

*maxx = INT_MIN; 

lSize = findBST(node->left, minn, maxx, maxSize, isBst); // recursive call for left subtree

// checking if left subtree is BST or not

if (*isBst == 1 and node->data > *maxx) 

flag1 = 1;

mi = *minn;

*minn = INT_MAX;

rSize = findBST(node->right, minn, maxx, maxSize, isBst); // recursive call right subtree

// checking if right subtree is BST or not

if (*isBst == 1 and node->data < *minn) 

flag2 = 1;

if (mi < *minn)

*minn = mi;

if (node->data < *minn)

*minn = node->data;

if (node->data > *maxx)

*maxx = node->data;

// If right and left subtrees are BST, then return the size of the tree.

if(flag1 and flag2){ 

if (lSize + rSize + 1 > *maxSize) 

*maxSize = lSize + rSize + 1; 

return lSize + rSize + 1; 

}

else{ 

// If tree is not BST

*isBst = 0;

return 0;

} 

}

int main()

{

node *root = new node(60);

root->left = new node(50);

root->right = new node(90);

root->left->left = new node(40);

root->left->right = new node(55);

root->right->left = new node(70);

root->right->left->left = new node(80);

root->right->right = new node(100);

root->right->right->left = new node(200);

root->right->right->right = new node(150);

int minn = INT_MAX, maxx = INT_MIN;

int maxSize = 0; // stores maximum size of the BST

bool isBst = 0; // If tree is BST then we store 1 in it, otherwise 0.

findBST(root, &minn, &maxx, &maxSize, &isBst); // values are passed by reference

cout<<"Size of the largest BST is: "<<maxSize;

return 0;

}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Output : 3

Time Complexity : O(n)

n is the number of nodes in  the given binary tree