Upper triangular matrix | Inverse of a matrix | Solution of X's in Ax=B

This blog explores the ways to solve Ax=B, where A is nxn matrix, x is nx1 matrix and B is nx1 matrix. On the way, I will take a detour, where I will write a code to convert A into an upper triangular matrix, also I will validate it whether A is a singular matrix.

The code is written in C++.  When we have a system of linear equations, we can write it as
sum(Aij*Xj=Bi). In another blog, I will write code to find the inverse of non-singular n*n matrix. For now, We will focus on X's solution and way to convert A into upper triangular matrix.

The main utility function is upT(A, row, col, b), it takes A , its row length, column length and B matrix.
Validate(A, m, n) checks whether A has zero at pivot position. If pivot is found, then it exchanges zero pivot row with non-zero row. First for loop in upT function converts A into upper triangular matrix and then singular(A, m, n-1) checks whether A is a singular matrix. Second for loop converts upper triangular matrix into Identity matrix to find solution X's , where Xj=Ai/Bi (A being diagonal matrix)

Time complexity: O(n^3). (If you can improve it, please let me know)

#include <iostream>
using namespace std;

bool singular(float** A, int m, int n){

for(int i=0;i<m;i++){
int non_zero=0;
for(int j=0;j<n;j++){
if(A[i][j]!=0){
non_zero++;
}
}
if(non_zero<1){
return true;
}
}
return false;
}
void validate(float** a, int m, int n){
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==j and a[i][j]==0){
int found=0;
for(int k=i+1;k<m;k++){
if(a[k][j]!=0){
found=1;
for(int u=0;u<n;u++){
swap(a[i][u], a[k][u]);
}
}
if(found==1){
break;
}
}
}
}
}
}
void upT(float** A, int m, int n, float* b){
validate(A, m, n);
for(int i=0;i<m-1;i++){
int j=m-1;
while(j>i){
int k=i;
float r=A[j][i]/A[i][i];
int start=1;
while(k<n){
if(start==1){
A[j][k]=A[j][k]-(A[j][i]/A[i][i])*A[i][k];

start=0;
}else{

A[j][k]=A[j][k]-r*A[i][k];
}
k++;
}
j--;
}
}
if(singular(A, m, n-1)){
cout << "A is a singular matrix." << endl;
return;
}
cout << "Upper triangular matrix: " << endl;
for(int i=0;i<m;i++){
for(int j=0;j<n-1;j++){
cout << A[i][j] << " ";
}
cout << endl;
}
for(int i=0;i<m-1;i++){
int j=i;
while(j<m-1){
int k=j+1;
int start=1;
int r=A[i][j+1]/A[j+1][j+1];
while(k<n){
if(start==1){

A[i][k]=A[i][k]-A[i][j+1]/A[j+1][j+1]*A[j+1][k];
start=0;
}else{

A[i][k]=A[i][k]-r*A[j+1][k];
}
k++;
}

j++;
}
}
cout << "diagonal matrix A: " << endl;
for(int i=0;i<m;i++){
for(int j=0;j<n-1;j++){
cout << A[i][j] << " ";
}
cout << endl;
}
cout << "solution for X's: " << endl;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==j){
cout << b[i]/A[i][i] << endl;
}
}
}
}
int main(){
int m, n;
cout << "row & col of matrix: " << endl;
cin >> m >> n;
float** a;
a=new float*[m];
for(int i=0;i<n;i++){
a[i]=new float[n];
}
cout << "enter matrix elements: " << endl;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin >> a[i][j];
}
}
cout << "enter b elements: " << endl;
float b[m];
for(int i=0;i<m;i++){
cin >> b[i];
}

float** A;
int col=n+1;
A=new float*[m];
for(int i=0;i<col;i++){
A[i]=new float[col];
}
for(int i=0;i<m;i++){
for(int j=0;j<col;j++){
A[i][j]=(j==n)?(b[i]):a[i][j];
}
}
upT(A, m, col, b);
return 0;
}

Feel free to comment. If any error is found, please let me know
Reference : Matrix

MountBlue Technologies pvt ltd pre-screening coding test

This is a startup based in Bangalore, specializing in premium software development services. I have read a phase somewhere in a tech blog : Your first job is for you to learn not to earn. This is true for any kind of domain if this is your first job. Startup is best place if you believe on this although learning curve in big companies may be good too specially in product based companies. So anyway, few days ago, I gave a coding test for this startup : MountBlue Technologies pvt ltd.
There were two questions.
Level: Easy
Problem 1.
You have two arrays nums and maxes. You need to find out : for each ith element of maxes, how many elements in nums are less than or equal to that ith element of maxes. Store them into an array and print them out.

Ans: I think this is straightforward. Go to each ith element of maxes, compare it with all elements of nums, check the condition(s), if it satisfies, then counter++ and finally store the counter into an array.

This will take O(m*n) time in worst case (same for average case too). You will be forced to traverse all elements of nums.
But there is another way which won't traverse all elements of nums. First you need to store all elements of nums into a binary tree and now traverse through each ith element of maxes and compare that ith element with binary tree elements. In worst case, it will take O(m*n) but in average case, it will perform better than first algorithm.

Here is the code: 
(Programming language I used: C++)
#include <iostream>
using namespace std;
int c=0;
class btree{
public:
int data;
btree* left;
btree* right;
btree* add(int d, btree* root){
if(root==NULL){
btree* b=new btree();
b->data=d;
b->left=NULL;
b->right=NULL;
root=b;
return root;
}
if(d<=root->data){
root->left=add(d, root->left);
}else{
root->right=add(d, root->right);
}
return root;
}
void print(btree* r){
if(r==NULL){
return;
}
cout << r->data << endl;
print(r->left);
print(r->right);

}
};
void getNum(btree* r, int x){
if(r==NULL){
return;
}
if(r->data>x){
getNum(r->left, x);
}else if(r->data<=x){
c++;
getNum(r->left, x);
getNum(r->right, x);
}
}
void ans(btree* root, int* maxes, int m){

vector<int> v;
for(int i=0;i<m;i++){
int x=maxes[i];
btree* r=root;
c=0;
getNum(r, x);
v.push_back(c);
}
cout << "ans: " << endl;
for(int i=0;i<v.size();i++){
cout << v[i] << " ";
}
}
int main(){
btree* b=new btree();
btree* root=NULL;
int n;
cout << "enter n: " << endl;
cin >> n;
int nums[n];
cout<< "enter nums: " << endl;
for(int i=0;i<n;i++){
cin >> nums[i];
root=b->add(nums[i], root);
}
//b->print(root);
int m;
cout << "enter m: " << endl;
cin >> m;
int maxes[m];
cout << "enter maxes: " << endl;
for(int i=0;i<m;i++){
cin >> maxes[i];
}
ans(root, maxes, m);
return 0;

}

Problem 2.
You have a list of original items and their respective original prices. You have a helper who sells your items(by decreasing/increasing or same original price). You need to find out how many items have been sold in different prices than original prices.
Ans: Again instead of looping through original items and sold items, which will take O(m*n) in average case, use hashing.
Hash each element of original items into a map and now traverse through each element of sold items and compare it with hashed original items, if found different prices, counter++, and finally print out counter.

Here is the code:
#include <iostream>
#include <map>
using namespace std;

int getFraud(string* items1, float* prices1, int n, string* items2, float* prices2, int m){
map<string, float> m1;
int c=0;
for(int i=0;i<n;i++){
m1[items1[i]]=prices1[i];
}
for(int i=0;i<m;i++){
string s2=items2[i];
float p2=prices2[i];
if(m1[s2]!=p2){
c++;
}
}
return c;
}
int main(){
int n;
cout << "enter n: " << endl;
cin >> n;

string origItems[n];
float origPrices[n];
cout << "enter original items and prices: " << endl;
for(int i=0;i<n;i++){
cin >> origItems[i] >> origPrices[i];
}

int m;
cout << "enter m: " << endl;
cin >> m;
string items[m];
float prices[m];
cout << "enter items and prices: " << endl;
for(int i=0;i<m;i++){
cin >> items[i] >> prices[i];
}
cout << "fraud found: " << getFraud(origItems, origPrices, n, items, prices, m) << endl;
return 0;

}

If anything found wrong, please let know.

Cogoport Developer Hiring Challenge , January'18 | HackerEarth

Recently, I participated in programming contest : Cogoport Developer Hiring Challenge.
It has been months since I had participated in any kind of such programming contest (in HackerEarth or HackerRank or SPOJ). I needed to brush up my algorithmic concepts. My purpose was to solve all the questions so that I could get a chance to attend Cogoport interview. So with this in my mind, I logged in and started solving Cogoport developer hiring challenge on HackerEarth.

There were total 4 problems. Before, I jump into the the details, I must elaborate different tags associated with all these 4 problems. So here they are: string manipulation, palindrome, binary number.

To my embarrashment, I couldn't even solve one of them in the allotted time as I told you I had not brushed up my concepts. So, anyway, later, I solved them in my free time. I had tried two problems. So I am going to talk about those two. I will try to remember those two problems.

Problems:
1. You are given a binary number as a string, n. n has substrings. Find the number of all odd decimal representations of the substrings. Binary number will be assumed from left to right.

Input: First line contains integer, t, number of test cases. For each test case, string, n is given as               input.
Output: For each string n, print out number of all odd decimal representations of substrings.

[Note: There was a condition for len(n)]

Solution: Here is what I thought while solving this problem. If any odd number represented in binary,  then its binary number has 1 at its least significant position.
Example: binary(5)=101, binary(7)=1101. In 5, 7 cases, 1 is always at the end : least significant position. So using this simple knowledge, we are done.
Now let's take an example : n=1101
substrings of n: 1, 1, 0, 1, 11, 10, 01, 110, 101, 1101. Total=10 substrings.
Remember: binary number : from left to right as said in the problem statement.
1, 1, 1, 11, 10, 110, 101, 1101 are our solutions as they are odd decimal representation.
not 01 because left to right , that means , in 01 , least significant position has 0 and it makes it even decimal representation.

That's lot of things to digest. Anyway, think about this. Here is a C++ code for it.

#include <iostream>
using namespace std;
int utility(string b){
int n=b.length();
int s=0;
for(int i=0;i<n;i++){
if(b[i]=='1'){
int j=n-i;
s+=j;
}
}
return s;
}
int main(){
string b;
cin >> b;
cout << utility(b);
return 0;
}


2. Problem 2.

You are given two integer n and k. You need to find a special binary number of length n which satisfies palindrome condition. This binary number has to be created by concatenating binary string of length k.

Speical binary number has properties:
A. It must have at least 1 '0' and 1 '1'.
B. If there are more that one such special binary number, they you need to print the one which has highest number of zeros in it.

Input: First line contains an integer, t, number of test cases. Each test case line should have two input: n and k.

Output: print the special binary  number if found otherwise print "impossible".

example: n=8, k=5, special binary number=100101001
               n=10, k=6, special binary number=1001001001
               n=8, k=2, special binary number=impossible

Here is the code:

#include <iostream>
#include <map>
using namespace std;

map<string, int> repeat;
bool palindrome(string s){
int n=s.length();
int zero=0;
int found=1;
int j=0;
for(int i=0;i<n/2;i++){
if(s[i]!=s[n-j-1]){
found=0;
break;
}
if(s[i]=='0'){
zero=1;
}
j++;
}
if(found==0){
return false;
}else{
if(zero==1){
return true;
}else{
return false;
}
}
}

bool getBinary(int n, int k, string k1, int x){
if(x<k){
k1[x]='1';
}
string k2=k1;
string s="";
string prefix="";
int f=0;
while(true){

if(k1.length()>=n){
int i=0;
k1=prefix+k1;
s="";
while(i<k1.length()){
s+=k1[i];
                                             if(s.length()==n and s[0]=='1' and palindrome(s)){
cout << "ans s: " << s << endl;
return true;
}
if(repeat[s]==1){
return false;
}
if((s.length()==n and !palindrome(s)) or (s.length()==n and s[0]=='0')){
repeat[s]=1;
s="";
}
i++;
}
prefix=s;
k1="";
}else{
k1+=k2;
}
if(prefix==k2){
return false;
}

}
}
void utility(int n, int k){
string k1="1";
bool ans=false;
for(int i=0;i<k-1;i++){
k1+="0";
}
int found=0;
if(n==k and k1[0]=='1' and palindrome(k1) ){
cout << k1 << endl;
}else{

int j=k;
while(j>=1){
ans=getBinary(n, k, k1, j);
if(ans){
found=1;
break;
}
j--;
}
}
if(found==0){
cout << "impossible" << endl;
}
}
int main(){
int n, k;
cin >> n >> k;
utility(n, k);
return 0;
}


Please let me know if You had participated in this challenge or If you find anything wrong in this thread.
Cogoport developer hiring challenge

Binary Tree Inversion

 This is a special article to show you how to invert a binary tree. A binary tree is a data structure where data types (integers, floats, strings) are stored in a tree. This tree as the name suggests has two children: Left child and Right child and a root node at the top of the tree. Normally, left child is stored at the left side of a node and the right child at the right side of the node.

Look at the image: 

Google image

To design an algorithm for a binary tree is easy. I am going to focus on how to get its mirror image once you have created a binary tree.

Algorithm to create mirror image of binary tree

Once you have created a binary tree, you get a root node of this tree.

What is the difference(s) between normal binary tree and its mirror image?

Ans: In a binary tree, for a parent node, its children have swapped their positions, i.e , left child became right child and vice-versa to become inverted binary tree. Root node stays at the same position.

Algorithm:

Step1. Start traversing the tree until you get the null node

           (Either start from left child or right child)

Step2. Once you get null node, return and swap your left and right child.

              And Voila, It's done!!!

Code:

---

Stack and Queue implementation in C++

Stack (also known as LIFO) and Queue(also known as FIFO) are two abstract data types in computer science that serve as collection of elements.

There are some specific operations associated with these two data types:

1. Push
2. Pop

Third operation is basically 'look up' (to see the top element in stack/queue).

All these three operations should take O(1) to process.

To know details of stack and queue, you can look up wikipedia[1][2]  to know more.

I am here to show you the implementation of these two in C++.

I am using linked list to implement it. Linked list has usual properties : node, head and link

---

Stack:

using namespace std;
class Stack{
public:
Stack* next;   // link between two nodes
Stack* head=NULL; // to gateway to enter the linked list (in this case our stack)
int data;
void push(int data){
Stack* s=new Stack();    // create a new node
s->data=data;
s->next=head;
head=s;
}
void pop(){
head=head->next;
}
int top(){
return head->data;
}
};

int main(){
Stack* s=new Stack();
s->push(12);
s->push(19);
s->push(23);
s->push(34);
s->pop();
cout << s->top() << endl;
return 0;
}

---

Queue:

#include <iostream>
using namespace std;
class Queue{
public:
Queue* next;
Queue* head=NULL;
Queue* tail=NULL;  // so that new element can be added to the queue in O(1) time.
int data;
void push(int data){
Queue* q=new Queue();
q->data=data;
q->next=NULL;
if(head==NULL){
head=q;
tail=q;
}else{
tail->next=q;
tail=q;
}
}
void pop(){
head=head->next;
}
int top(){
return head->data;
}
};

int main(){
Queue* q=new Queue();
q->push(12);
q->push(19);
q->push(23);
q->push(34);
q->pop();
q->pop();
cout << q->top() << endl;
return 0;
}

If I missed something, please let me know.
Happy coding !

---

Terms used in the blog:

LIFO: Last in first out

FIFO: First in first out

Reference:
Stack
Queue
Abstract data types