Sayef's Tech Blog

Articulation Point

art points

If a graph becomes disconnected after removal of any node (and its adjacent edges also) from the graph, then we call that node as an articulation point of the graph. In the picture, we can see that if the node d is removed, the graph is separated into two components. So it's an articulation point. In other words, node v is an articulation point, if there are two such nodes u and w, v node is present in every possible paths from u to v. And the graph that does not have any articulation point, we call that a biconnected graph.

bcntd

How to find these points? One naive approach could be like following-

  1. Remove a node

  2. Run DFS or BFS to check if the graph is connected or not, if not then it's an articulation point.

  3. Repeat 1 and 2 for all nodes.

Complexity is O(V(V+E)). There is an efficient solution to this problem which is of O(V+E) complexity.

To achieve this complexity we need to run a mandatory DFS. Let's say, we have connected graph G. For each node v ∈ V : we will declare two matrices i.e. discovery[v], back[v].

discovery[v] is nothing but DFS number. That means, we will assign a number (i.e 1, 2, 3) by increasing order to each node when DFS traverses the graph. First, we will initialize back[v] by discovery[v]. Later on, while the graph will be traversed and backtracked we will change the value of back[v].

Let's say v is a node while traversing the graph. There are two cases. If v is source from where we would like to start our traversal or v is any other node.

  • Now the source is an articulation point if it has more than one child.
  • For other nodes, v is an articulation point if it has child node w and back[w] >= discovery[v].
Read more >>

Creating Desktop App With Electron

  1. Assuming we have all set with nodejs and npm for creating a simple desktop project with electron. Now what we need, just to initiate a new project with the following command.
$ npm init
  1. Install electron with npm. All binary dependencies of electron will be preserved inside the node-modules directory.
$ npm install electron --save-dev --save-exact
  1. We want to create an entry point js file to write some server side codes which will render our desired HTML files to the user through chromium interface or any other modern browsers. Let’s create main.js file. Then we need electron APIs to make available in this js file. We will use this as a simple controller which will render an HTML page to show in the client side (in our case a desktop window).

main.js

const electron = require('electron');
  1. Since this electron variable is actually a complex object with lots of functionality inside, we will be using it for many purposes like creating window, load HTML files on that window etc. With the help of following line we can access app and BrowserWindow functionalities of electron.

main.js

const electron = require('electron');
const {app, BrowserWindow} = electron;
Read more >>

Hello World Project with NodeJS

Install Node.JS

  1. Download node.js from nodejs.org.

  2. Unpack anywhere you prefer.

  3. Export path variable.

    3.1 Open .bashrc file to export path variable (I prefer this way! :P)

$ gedit .bashrc

​ 3.2 Add the following lines to the .bashrc file.

    export NODE_HOME="/home/sayef/node-4.5.0"
    export PATH=${NODE_HOME}/bin:$PATH

​ 3.3 Save, exit and source the .bashrc file to come into effect the changes.

 $ source .bashrc

Install NPM (node package manager)

NPM is a command line interface program to manage node.js libraries. We can install some other fantastic and handy libraries to work with nodejs. We can initiate a server, see the changed effects in browser using those npm packages and making lot more funs with this package manager. Following command will install npm.

$ sudo apt-get install npm
937-666-9298

3D Object Detection From Mouse Click

We often use mouse event in computer graphics. I’m pretty sure that we can easily detect a 2D object using mouse event in OpenGL since a view-port or screen is of 2D. But problem arises whenever we have 3D space model having perspective projection and we are asked to detect an object using a mouse click. Ok! Let’s consider an example.

Suppose, we have an sphere shaped object locating at (0,0,0) and the radius is 100 unit in our model. After doing some work on perspective projection we are done with setting up camera position, object position, projection angle etc and now see the effect. What are we watching? Let’s assume the object is now located at right-top (640,480) corner of our view screen and our view screen is of 640×480. What actually we are seeing?

Sphere  at (0,0,0)

Figure: Sphere at (0,0,0) originally

Sphere at (640,480)

Figure Sphere at (640,480) from window screen

Now click on the sphere and use your mouse event. The co-ordinate you are getting is simply something close around (640,480) and how would I say this clicked object is actually situated at (0,0,0)? So, we would like to confirm that this clicked upon object is surely the object located at (0,0,0) of our main 3D space.

That means, we are going to find out the main object from this 2D point. See the following picture and try to feel what we are going to do now.

How projection works

Figure: Perspective projection and mouse click
Read more >>

A Short Tutorial on B+ Tree

We may get confused with the terms Binary Tree, Binary Search Tree, B Tree and B+ Tree. B Tree is also called Balanced Search Tree and B+ tree is something like B tree having some other features and conditions applied to it. We first remove our confusion learning the difference between these terms.

■ What is Balanced Tree?

A balanced tree means that all searches for individual values require the same number of nodes to be read from the disc. The B+-Tree is called a balanced tree because every path from the root node to a leaf node is the same length.

■ Difference between Binary Tree and Binary Search Tree

Binary tree is a generic version of binary search tree and its not ordered.

While constructing, binary tree we follow a rule that every node should have at most two children.

Whereas in case of BST, along with at most two children rule, we follow below rules

  1. All left descendants should possess smaller values than root value.

  2. All right descendants should possess larger values than root value.

BST are effective only when we are dealing with data which resides in main memory (RAM).

■ Differences between a B tree and a B+ tree

Read more >>

1080 TI: CUDA 9.0 and Graphics Driver Installation in Ubuntu 16.04

Download


  • I have installed both the graphics driver and cuda from a single installation file cuda_9.0.176_384.81_linux.run. It comes with compatible driver version 384. So you have not to worry about driver compatibility issue. Following link will show downloadable run file (1.6 GB) for ubuntu 16.04. /developer.nvidia.com/cuda-downloads?target_os=Linux&target_arch=x86_64&target_distro=Ubuntu&target_version=1604&target_type=runfilelocal

Installation


1) Pre-installation
  • Verify the system has a CUDA-capable GPU.
  • Verify the system is running a supported version of Linux.
  • Verify the system has gcc installed.
  • If there is any NVIDIA driver already installed, uninstall it for safety (not mandatory)
$ sudo apt-get purge nvidia* 
2) Disabling Nouveau
  • To install the Display Driver, the Nouveau drivers must first be disabled. The Nouveau drivers are loaded if the following command prints anything:
9788780786

Installing cuDNN on Linux

1. Downloading cuDNN

In order to download cuDNN, ensure you are registered for the NVIDIA Developer Program.

  • Go to: NVIDIA cuDNN home page. (/developer.nvidia.com/rdp/cudnn-download)
  • Join/Signup and complete the short survey and click Submit.
  • Accept the Terms and Conditions. A list of available download versions of cuDNN displays.
  • Select the cuDNN version you want to install. A list of available resources displays. (I prefer cuDNN v7.0 Library for Linux)

2. Before we begin, let's assume that -

  • your CUDA directory path is referred to as /usr/local/cuda/
  • your cuDNN download path is referred to as

3. Installing from a Tar File (In may case: cudnn-9.0-linux-x64-v7.tgz)

  • Navigate to your directory containing the cuDNN Tar file.
  • Unzip the cuDNN package.
$ tar -xzvf cudnn-9.0-linux-x64-v7.tgz
  • Copy the following files into the CUDA Toolkit directory.
$ sudo cp cuda/include/cudnn.h /usr/local/cuda/include
$ sudo cp cuda/lib64/libcudnn* /usr/local/cuda/lib64
$ sudo chmod a+r /usr/local/cuda/include/cudnn.h /usr/local/cuda/lib64/libcudnn*
Read more >>

Lowest Common Ancestor Node in a Tree: A Success Story

Interviewer: Are you ready for your interview?
Candidate: Yeah, I am ready.
Interviewer: Would you please introduce me to your most recent project?
Candidate: I finished a Multi-Target project in Civil 3D (software for civil engineering based on AutoCAD) a few weeks ago. The target is the edge of a road. Previously, the road edge could only be a data structure called Alignment in Civil. My task was to support other data structures, such as Polyline in AutoCAD.
Interviewer: Is it possible to add new data structures for road edges in the future?
Candidate: It was a requirement to support new data structures during development. A new road edge named Pipeline was added in the second version of the specification. Since my design took scalability into consideration, it was only necessary to add new classes for Pipeline, and little existing code was modified.
Interviewer: It sounds interesting. How did you do it?
The candidate draws a UML figure to show the hierarchy of several classes. (The figure has been omitted here.)
Candidate: (Explaining while pointing to the figure) According to the class hierarchy, it was only necessary to add a new class for Pipeline when it was to support a new target type, and it had no impact on other classes.
Interviewer: (Nods) Yeah, it is cool. OK, let’s change topics and try a coding problem. The requirement is to find the lowest common ancestor with two given nodes in a tree.
Candidate: Is the tree a binary search tree?
Interviewer: Why do you ask such a question?
Candidate: If it is binary search tree, there is a solution available.
Interviewer: OK, let’s suppose it is a binary search tree. How do you get the lowest common ancestor?
Candidate: (A bit excited and speaking quickly) A binary search tree is sorted where value in a parent node is greater than values in the left subtree and less than values in the right subtree. We begin to traverse the tree from the root node and compare the value of the visited node with the values in the two given nodes. If the value of the current visited node is greater than the values of two given nodes, the lowest common ancestor should be in the left subtree, so it moves to the left child node for the next round of comparison. Similarly, it moves to the right child node if the value of the current visited node is less than the values of the two given nodes. The first node whose value is between the values of two given nodes is the lowest common ancestor.
Interviewer: It seems that you are quite familiar with this problem. Did you see it before?
Candidate: (Embarrassed) Uh, I happened to see it …
Interviewer: (Smiles) Let’s modify the requirement a little bit. How do you solve it when the tree is a normal tree rather than a binary search tree or a binary tree?
Candidate: (Thinks for dozens of seconds) Do nodes have links to their parents?
Interviewer: Why do you need links to parent nodes?
The candidate draws a tree, as shown in Figure 9-1.

Figure 9-1. Nodes in a tree have links to parents, which are drawn with dashed arrows._

Candidate: (Explaining while pointing to her drawing) If all nodes except the root in a tree have links to their parents, this problem is equivalent to finding the first common node in two intersected lists. A path in the tree can be viewed as a list connected by links to parents, starting from a leaf to the root. For example, if the input two nodes are the
nodes h and f, the node h is on the path though h → e → b → a, and the node f is on the path though f → c → a. Node a is the first common node on these two paths, and it is also the lowest ancestor of the nodes h and f.
Interviewer: Where did you see the problem to get the first common node in two lists?
Candidate: (Smiles with embarrassment) Uh, it was by accident …
Interviewer: No problem. Let’s modify the requirement again. How do you get the lowest ancestor in a normal tree, where every node does not have a link to its parent?
Candidate: (Disappointed and depressed) OK, give me a few minutes.
Interviewer: It is only a bit more difficult than the previous two problems, and I believe you can solve it.
Candidate: (Thinking silently) Let’s traverse the tree from the root. When a node is visited, we check whether the two input nodes are in its subtrees. If both nodes are in the subtrees, it moves to the children nodes for the next round. The first node whose subtrees contain two input nodes, but its children nodes do not, is the lowest common ancestor.
Interviewer: Can you explain your ideas with an example?
Candidate: (Explaining while drawing Figure 9-2) Let’s assume the two given nodes are d and i. The tree is scanned with the pre-order traversal algorithm. Note that the subtrees of node a contain both node d and i, so we move on to check whether the subtrees of node b and c contain the given nodes. Since both nodes d and i are in the subtree of
node b, we continue to check whether these two nodes are contained in the subtrees of nodes d and e, which are children of b. The subtree rooted at node d does not contain node i, and the subtree rooted at node e does not contain node d. Therefore, node b is the first node whose subtrees contain two input nodes but its children nodes do not, and it is the lowest ancestor of d and i.

2

Figure 9-2. Nodes in a tree do not have links to parents.

Interviewer: It seems that your solution visits nodes multiple times. For instance, when you check whether the subtree root at a contains node i, nodes h, i, and j will be visited. When you check whether the subtree root at b contains i, nodes h, i, and j will be visited again. Is it possible to visit each node only once?
Candidate: (Ponders for more than two minutes) Can I use auxiliary space?
Interviewer: How much space do you want?
Candidate: I’m going to utilize two lists for two paths from the root node to the two given nodes. The lowest ancestor is equivalent to the last common node on the two paths.
Interviewer: (Nods) It sounds interesting. Give me more details about your solution.
Candidate: A path from the root is stored while the tree is traversed. For example, the process to get the path from the root to node i can be described as follows. (1) Node a is visited, and inserted into the path. Now there is a node a in the path. (2) Node b is visited and inserted into the path. The path is a → b. (3) Node d is visited and inserted into the path. The path is a → b → d at this time. (4) Since d is a leaf node, we have to return back to node b, and node d is removed from the path. The path becomes a → b again. (5) Node e is visited and inserted into the path. The path is a → b → e now. (6) Node h is
visited and inserted into the path, which becomes a → b → e → h. (7) Since node h is a leaf, we have to return back to its parent node e. Node h is removed from the path, and the path becomes a → b → e. (8) The target node i is visited and inserted into the path. The path from the root to node i is a → b → e → i.
Interviewer: And then?
Candidate: Similarly, the path from the root to node d is a → b → d. The last common nodes on these two paths are node b, and it is also the lowest ancestor of the nodes d and i. Interviewer: What is the time and space complexity?
Candidate: We have to traverse the tree twice, so it costs O(n) time in a tree with n nodes. Additionally, we utilize two lists to store paths. The length of a path is O(log_n_) on average, and it is O(n) for worst cases.
Interviewer: (Nods and smiles) Pretty good. Can you implement your code in C/C++?
Candidate: No problem.
The candidate writes the three functions in Listing 9-6.

Listing 9-6. C++ Code to Get the Lowest Ancestor of Two Tree Nodes

TreeNode* GetLowestAncestor(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2) {

	if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
        return NULL;
 	list<TreeNode*> path1;
 	GetNodePath(pRoot, pNode1, path1);
 	list<TreeNode*> path2;
 	GetNodePath(pRoot, pNode2, path2);

 	return GetLastCommonNode(path1, path2);
}


bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>& path) {

	if(pRoot == pNode)
 		return true;

	path.push_back(pRoot);
 	bool found = false;
	vector<TreeNode*>::iterator i = pRoot->m_vChildren.begin();
	while(!found && i < pRoot->m_vChildren.end()) {
		found = GetNodePath(*i, pNode, path);
 		++i;
	}

 	if(!found)
 		path.pop_back();
 	return found;
 }

TreeNode* GetLastCommonNode(const list<TreeNode>& path1, const list<TreeNode>& path2) {

	list<TreeNode*>::const_iterator iterator1 = path1.begin();
 	list<TreeNode*>::const_iterator iterator2 = path2.begin();
 	TreeNode* pLast = NULL;
	
    while(iterator1 != path1.end() && iterator2 != path2.end()) {
		if(*iterator1 == *iterator2)
          	pLast = *iterator1;
 		iterator1++;
 		iterator2++;
	}
    
 	return pLast;
}

Candidate: The function GetNodePath gets a path from the root node pRoot to the node pNode. The function GetLastCommonNode gets the last common node of two paths path1 and path2. The function GetLowestAncestor calls the function GetNodePath twice in order to get the paths from the root node to the two given nodes respectively, and then calls the function GetLastCommonNode to get the lowest ancestor.
Interviewer: That is good. I do not have any more questions. Do you have any questions for me?
Candidate: Would you please introduce me to your project briefly?
Interviewer: We are developing a UI framework named Winforms on .NET, with which others can develop a UI for desktop applications. Our Winforms framework provides traditional windows controls such as the ListBox and TreeView, as well as new controls such as the TableLayoutPanel for flexible layout.
Interviewer: Any more questions?
Candidate: (Thinks for a while) No more.
Interviewer: OK. That is the end of this interview. Thank you.
The Interviewer’s Comments
There are a series of problems about the lowest ancestor of two nodes in a tree and the solutions are quite different with various requirements. I did not provide enough detail about the tree intentionally. I expected the candidate to ask for more clarification.
The candidate performed well during the interview. She asked me whether the tree was a binary search tree and then whether there were links to parents in each node. These questions showed her proactive attitude and strong communication skills.
Once I specified my requirements, she found solutions in a very short period of time. When I told her there was a link to the parent node in each node, she converted the problem to find the first common node in two lists. When I removed the link to the parent, she converted the problem to find the last common node in two paths. She demonstrated her deep understanding of data structures as well as strong competence in problem solving.
Additionally, her code was clean and complete, which indicated that she was a professional programmer.
She showed her interests in joining our team in the Q & A phase. Actually, I am looking forward to working with her. In general, my recommendation is to hire her because of her competence in problem solving, programming, and communication.

(863) 267-5815

Database Interview Questions

1. What is database or database management systems (DBMS)? and – What’s the difference between file and database? Can files qualify as a database?

Answer : Database provides a systematic and organized way of storing, managing and retrieving from 1 collection of logically related information. Secondly the information has to be persistent, that means even after the application is closed the information should be persisted.

Finally it should provide an independent way of accessing data and should not be dependent on the application to access the information.

Main difference between a simple file and database that database has independent way (SQL) of accessing information while simple files do not File meets the storing, managing and retrieving part of a database but not the independent way of accessing data. Many experienced programmers think that the main difference is that file can not provide multi-user capabilities which a DBMS provides. But if we look at some old COBOL and C programs where file where the only means of storing data, we can see functionalities like locking, multi-user etc provided very efficiently. So it’s a matter of debate if some interviewers think this as a main difference between files and database accept it… going in to debate is probably loosing a job.

2. What is SQL ?

Answer : SQL stands for Structured Query Language.SQL is an ANSI (American National Standards Institute) standard computer language for accessing and manipulating database systems. SQL statements are used to retrieve and update data in a database.

3. What’s difference between DBMS and RDBMS ?

Answer : DBMS provides a systematic and organized way of storing, managing and retrieving from collection of logically related information. RDBMS also provides what DBMS provides but above that it provides relationship integrity. So in short we can say

RDBMS = DBMS + REFERENTIAL INTEGRITY

These relations are defined by using “Foreign Keys” in any RDBMS.Many DBMS companies claimed there DBMS product was a RDBMS compliant, but according to industry rules and regulations if the DBMS fulfills the twelve CODD rules it’s truly a RDBMS. Almost all DBMS (SQL SERVER, ORACLE etc) fulfills all the twelve CODD rules and are considered as truly RDBMS.

Read more >>

Object Oriented Programming

1. What is OOPS?

OOPS is abbreviated as Object Oriented Programming system in which programs are considered as a collection of objects. Each object is nothing but an instance of a class.

2. Write basic concepts of OOPS?

Following are the concepts of OOPS and are as follows:.

  1. Abstraction.
  2. Encapsulation.
  3. Inheritance.
  4. Polymorphism.

3. What is a class?

A class is simply a representation of a type of object. It is the blueprint/ plan/ template that describe the details of an object.

4. What is an object?

Object is termed as an instance of a class, and it has its own state, behavior and identity.

5. What is Encapsulation?

Read more >>

Design Patterns

1. What are Design Patterns?

Design patterns represent the best practices used by experienced object-oriented software developers. Design patterns are solutions to general problems that software developers faced during software development. These solutions were obtained by trial and error by numerous software developers over quite a substantial period of time.

2. Name types of Design Patterns?

Design patterns can be classified in three categories: Creational, Structural and Behavioral patterns.

Creational Patterns – These design patterns provide a way to create objects while hiding the creation logic, rather than instantiating objects directly using new operator. This gives program more flexibility in deciding which objects need to be created for a given use case.

Structural Patterns – These design patterns concern class and object composition. Concept of inheritance is used to compose interfaces and define ways to compose objects to obtain new functionalities.

Behavioral Patterns – These design patterns are specifically concerned with communication between objects.

3. What are J2EE Patterns?

These design patterns are specifically concerned with the presentation tier. These patterns are identified by Sun Java Center. What is Factory pattern?

Factory pattern is one of most used design pattern in Java. This type of design pattern comes under creational pattern as this pattern provides one of the best ways to create an object.

254-302-6689

905-509-6104

1. What is an operating system?

An operating system is a program that acts as an intermediary between the user and the computer hardware. The purpose of an OS is to provide a convenient environment in which user can execute programs in a convenient and efficient manner.

2. What are the different operating systems?

  1. Batched operating systems
  2. Multi-programmed operating systems
  3. Time sharing operating systems
  4. Distributed operating systems
  5. Real-time operating systems

3. What are the basic functions of an operating system?

Operating system controls and coordinates the use of the hardware among the various applications programs for various uses. Operating system acts as resource allocator and manager. Also operating system is control program which controls the user programs to prevent errors and improper use of the computer. It is especially concerned with the operation and control of I/O devices.

4. What is kernel?

Kernel is the core and essential part of computer operating system that provides basic services for all parts of OS.

5. What is difference between micro kernel and macro kernel?

Micro kernel is a kernel which run services those are minimal for operating system performance. In this kernel all other operations are performed by processor.

Read more >>

Eclipse, OpenCV, C++ and Ubuntu

Configuring OpenCV with Visual Studio seemed painful to me and Visual Studio sucks RAM which makes your PC slow. Some people try codeblocks which is faster as it is a lightweight IDE. But trying something different is not that bad! I will share ins and outs of configuring OpenCV with Eclipse CDT bundle (C/C++ Development Tool) in Ubuntu.

Step 1: Install JDK

1.1 (603) 480-9240and extract wherever you want to to keep. Let’s assume the path is something like “/home/user/jdk1.7.0_80” where ‘user’ is your pc user name.

1.2 Set path variable by editing bashrc file:

$ gedit .bashrc

Copy the following lines any where in the file (I usually put at the bottom) and do the changes as for your path.

export JAVA_HOME="/home/user/jdk1.7.0_80" `

export PATH=${JAVA_HOME}/bin:$PATH

This change will be effective after running the following command.

$ source .bashrc
Read more >>

Linked List Basics

A linked list is a data structure for storing, searching, manipulating and doing many more with a list of data. ‘Array’ data structure has some limitations that can be overcome easily by the linked list having some dynamic features. Let’s see what a linked list can do –

  • Successive elements are connected by pointers.
  • Last element points to NULL.
  • It can grow or shrink in size during execution of a program.
  • It can be made just as long as required.
  • It does not waste memory space.

1

Fig: Liked List Structure

We must know the pointer to the first element of the list (called start, head, etc.).
**Insertion and Deletion in linked list:
**
For insertion:

  • A record is created holding the new item.
  • The nextpointer of the new record is set to link it to the item which is to follow it in the list.
  • The nextpointer of the item which is to precede it must be modified to point to the new item.

linked list insertionFig: Linked List Insertion

For deletion:

  • The nextpointer of the item immediately preceding the one to be deleted is altered, and made to point to the item following the deleted item.
Read more >>

Therap Fresher Recruitment 2015 @CSEDU

Development

  1. Write a code to print 1 to 100 , if multiple of 3 print Fizz, if multipe of 5 print Buzz, if multiple of both print FizzBuzz, else print the number.
  2. Write a code to print the following configuration:
 *
 **
 ***
 **
 *
  1. Write regular expression of any mobile number of Bangladesh.
  2. Write a code to convert a string to integer.
  3. Explain HTTP session and cookie.
  4. Given a procedural programming to get area of square and rectangle. Convert it in the form of OOP.
  5. Relational Database Design from the following table.
  1. If you could do anything, what is your dream job?
  2. How to remove collision from hashtable?
  3. Write Linux command to show running Java processes.
  4. Will these code run and compile?
	Class test
	{
	        int a=10, b=100;
			private static void main(String a[])
			{
				Jobexam t = new Jobexam();
				System.out.println(t.getTest());
			}
			private int getTest()
			{
				return a*b;
			}
	}
  1. Given a graph. Express it with 1)Adjacency Matrix and 2) Adjacency list

SQA

  1. Write the output of the following code snippet.
4315568713

(207) 873-7955

This is a simple collection of problems for interview from the basic knowledge of C programming.

Part 1: Write Short Procedure or Pseudo-code

  1. Write a program to print numbers from 1 to 100 without using loops.
  2. Write a C program to swap two variables without using a temporary variable.
  3. What is the 8 queens problem? Write a C program to solve it?
  4. Write a C program to print a square matrix helicaly.
  5. Write a C program to reverse a string.
  6. Write a C program generate permutations.
  7. Write a C program for calculating the factorial of a number.
  8. Write a C program to calculate pow(x,n)?
  9. How do you calculate the maximum sum of a list of numbers?
  10. How to generate fibonacci numbers with recurison? Can you optimize it?
  11. Solve the Rat In A Maze problem using backtracking.
  12. Write C code to solve the Tower of Hanoi problem (generalize form).
  13. Write a C program which produces its own source code as its output.
  14. Write a C program to convert from decimal to any base (binary, hex, oct etc…).
  15. Write C code to check if an integer is a power of 2 or not in a single line?
  16. Write a C program to find the GCD of two numbers.
  17. Write code to remove duplicates in a sorted array.
  18. Find the maximum of three integers using the ternary operator.
  19. Write C code to dynamically allocate one, two and three dimensional arrays (using malloc()).
  20. How would you find the size of structure without using sizeof()?
  21. Write a C program to multiply two matrices.
  22. Write a C program to check for palindromes.
  23. Write a C program to convert a decimal number into a binary number.
  24. Write C code to implement the Binary Search algorithm.
  25. How do you compare floating point numbers?
  26. Write a program to check if a given year is a leap year or not?
  27. Is there something we can do in C but not in C++?
  28. Can you write general sieve method for finding prime numbers?
  29. What is the difference between scanf(“%s”, str) and gets(str)?
  30. Write your own sqrt() function in C.
  31. How can we sum the digits of a given number in single statement?

Part 2: Find The Output

1. Find the output –

int counter = 0, i;

for(i=0;;i++) {
  if (i<100) continue;
      counter ++;
  if (counter == 100) break;
}

printf(%d%d”,i, counter);

2. what is the value of EOF..?? ans=-1

3. What is the output?

class test{ };

int main()
{
  cout<<sizeof(test);
  return 0;
}
Read more >>

Data Structure Questions

1. What is data structure?

A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.

2. List out the areas in which data structures are applied extensively?

  1. Compiler Design,
  2. Operating System,
  3. Database Management System,
  4. Statistical analysis package,
  5. Numerical Analysis,
  6. Graphics,
  7. Artificial Intelligence,
  8. Simulation

3. What are the major data structures used in the following areas : RDBMS, Network data model and Hierarchical data model.

  1. RDBMS = Array (i.e. Array of structures)
  2. Network data model = Graph
  3. Hierarchical data model = Trees

4. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

5. Minimum number of queues needed to implement the priority queue?

Two. One queue is used for actual storing of data and another for storing priorities.

910-825-1070

8062393653

Interviewer: You mentioned in your résumé that you are proficient on C/C++. How many years have you used these two languages?
Candidate: It has been six or seven years since I learned them at my university.
Interviewer: Cool, it sounds like you are a veteran. Let’s discuss some C++ problems. (The interviewer hands a piece of paper with the source code from Listing 9-1 to the candidate.) What is the output when this piece of code executes?

Listing 9-1: C++ Code for the Member Initialization Order

class A {
  private:
   int n1;
   int n2;
   public:
   A(): n2(0), n1(n2 + 2) {   
 }

  void Print() {
      std::cout << "n1: " << n1 << ", n2: " << n2 << std::endl;
    }
 };

 int main(int argc, char* argv[]) {
   	A a;
    a.Print();
    return 0;
}

Candidate: (Reads code for a while) n1 is 2, and n2 is 0.
Interviewer: Why?
Candidate: In the initialization list of the constructor, n2 is initialized as 0, so the result of n2 is 0. And then n1 is initialized with n2+2, so it is 2.
[ Note: This answer is NOT correct. Please refer to the comments at the end of this section for more details.]
Interviewer: Are members initialized according to their order in the initialization list?
Candidate: (Confused) I am not quite sure.
Interviewer: No problem. Let’s move on to another problem. What is the usage for the function atoi in the C library?
Candidate: It converts a numeric string to an integer. For example, if the input string is “123”, it returns 123.
Interviewer: That’s right. Please write a function StrToInt to convert a string to an integer. Of course, it is not allowed to call atoi or other similar functions in the library. Are there any questions?
Candidate: (Smiles with confidence) No problem.
The candidate writes down the code in Listing 9-2 on paper in a short period of time.

Listing 9-2. C++ Code to Convert a String to an Integer (Version 1)

int StrToInt(char* string) {
  	int number = 0;
   	while(*string != 0) {
    	number = number * 10 + *string - '0';
     	++string;
  	}
 	return number;
}

Candidate: I have finished.
Interviewer: Oh, that was quick. (Reads the code quickly) Do you think it is complete? Scrutinize your code.
Candidate: (Reads the code from the beginning) Sorry that I forgot to verify the NULL pointer for the input string.
The candidate adds two lines of code. The revised code is shown in Listing 9-3.

Listing 9-3. C++ Code to Convert a String to an Integer (Version 2)

int StrToInt(char* string) {
  if(string == NULL)
     return 0;
  int number = 0;
  while(*string != 0) {
  	number = number * 10 + *string - '0';
  	++string;
  }
  return number;
}

Interviewer: Have you finished? (Reads the code again) Your output is 0 when the input string is
NULL. What is the output when the input is a string “0”?
Candidate: It is also 0.
Interviewer: It returns 0 for two different cases. How do you distinguish these cases when its caller
gets a 0?
Candidate: (Confused) I do not know.
Interviewer: Similar to the library function atoi, we may distinguish them with a global variable. When the input is invalid, the variable is set to a special value. However, it is not set when the input is “0”. When the caller gets a 0 from the function StrToInt, it knows what happens according to the global variable.
Candidate: Oh, I see. (Picks up the pen) Let me rewrite that.
Interviewer: Wait. Are there any other invalid inputs besides the NULL pointer?
Candidate: (Thinking, with sweat on forehead) If a string has some characters beyond the range from ‘0’ to ‘9’, it is invalid.
Interviewer: Are all characters beyond the range from ‘0’ to ‘9’ invalid?
Candidate: The positive sign (‘+’) and negative sign (‘-’) should be valid.
Interviewer: Correct. Think carefully before you start to write code.
The candidate thinks for a few minutes, and writes down the code shown in Listing 9-4.

Read more >>

Sorting Algorithms

There are many types of Sorting techniques, differentiated by their efficiency and space requirements. Following are some sorting techniques which we will be covering in next sections.

  1. Bubble Sort
  2. versus
  3. Selection Sort
  4. Quick Sort
  5. 5198551195
  6. (709) 987-1875

The following chart compares sorting algorithms on the various criteria outlined above; the algorithms with higher constant terms appear first, though this is clearly an implementation-dependent concept and should only be taken as a rough guide when picking between sorts of the same big-O efficiency.


Bubble Sort

Bubble Sort is an algorithm which is used to sort N elements that are given in a memory for eg: an Array with N number of elements. Bubble Sort compares all the element one by one and sort them based on their values.

It is called Bubble sort, because with each iteration the smaller element in the list bubbles up towards the first place, just like a water bubble rises up to the water surface.

Sorting takes place by stepping through all the data items one-by-one in pairs and comparing adjacent data items and swapping each pair that is out of order.

Bubble SortingFig: Bubble Sorting

8702980478

intracanonical

Assignment details

This is the first assignment of a series of assignments on constructing a compiler for a programming language. We will call out language SubC. Given the grammar of SubC you are to write the F(LEX) and YACC/BISON specification file that parses code written in SubC. In this assignment, you are to generate a parser for only assignment statements. Following is the grammar for assignment statements for SubC.

Stmt_list → Stmt | Stmt_list ; Stmt Stmt → Variable assignop Expression Variable → id | id [Expression] Expression → Simple_expression | Simple_expression relop Simple_expression Simple_expression → Term | Simple_expression addop Term Term → Factor | Term mulop Factor Factor → id | num | ( Expression) | id [Expression] | not Factor

Tokens/Terminal symbols of this grammar are in BOLD font. Below are the specifications for the tokens

  • If successful in parsing a list of statements the parser prints “success” otherwise prints appropriate error message
  • You code will be evaluated based on the appropriateness & correctness of the error messages that it produces

Implementation

You are to write (F)LEX and YACC/BISON specification files(e.g., subc.l and subc.y). The parser that yacc/bison generates should be able to call the lexical analyzer generated by lex/flex and perform parsing of the code (i.e., list of assignment statements) generated by the given grammar. Your LEX specification should be able to remove any white space from the code. All ids should be stored in a symbol table and printed out as output.

Sample input#1

b= b + 1; input[b+2] = b; a = input [i+2]

Read more >>