Coding Interview Questions in C++

Q.1 Write a method to print last K lines of the input file using C++.

Solution :- A brute force method might be to count the number of lines (N) and then print from N-K to the Nth line. But this requires two reads of the file, which is unnecessarily expensive. We need a solution that enables us to read only once and print the last K lines.

We can allocate an array for all the K lines and previous K lines that we have read in the array and so on. Every time we read a new line, we purge the oldest line from the array.

Code:

The code below implements this algorithm.


void printLast10Lines (char* fileName) {
const int k = 10;
ifstream file (fileName);
string L[K];
int size = @;
/* read file line by line into circular array */
/* peek() so an EOF following a line ending is not considered a separate line */
while (file.peek() != EOF) {
getline(file, L[size % K]);
size++;
}
/* compute start of circular array, and the size of it */
int start - size > K? (size % K) : 0;
int count = min(K, size);
/* print elements in the order they were read */
for (int i = 0; i < count; i++) {
cout << L[(start + i) % K] << endl;
}
}

Q.2 Implement the function void reverse(char* str) in c++ which reverse a Null-terminated string.

Solution :- This is a classic interview question. The only "gotcha" is to try to do it in place, and be careful for the infirm character.

Code:

void reverse(char *str) {
char* end = str;
char tmp:
if (str) {
while (end) { / find end of the string */
++end;
}
--end; /* set one char back, since last char is null */
/* Swap characters from start of string with the end of the string, until the
* pointers meet in middle. */
while ( str < end  ) {
tmp = *str:
*str++ = "end;
*end-- = tmp;
}
}
}

Q.3 Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed in data structure. The Node data structure contains two pointers to other Nodes.

Solution :- The algorithm will maintain the mapping from the node address in the original structure to the corresponding node in the new structure. This mapping will allow us to search for nodes already copied during a conventional depth-first traversal of the structure. Traversals often mark visited nodes - traces can take many forms and do not necessarily have to be stored in a node.

Code:

typedef map< Node*, Node*> NodeMap;
Node * copy_recursive ( Node * cur, NodeMap & nodeMap) {
if (cur == NULL) {
return NULL;
}
NodeMap::iterator i = nodeMap.find(cur);
if (i != nodeMap.end()) {
// we've been here before, return the copy
return i->second;
}
Node * node = new Node;
nodeMap[cur] = node; // map current before traversing links
node->ptrl = copy_recursive(cur->ptr1, nodeMap):
node->ptr2 = copy_recursive(cur->ptr2, nodeMap);
return node;
}
Node * copy_structure(Node * root) {
NodeMap nodeMap; // we will need an empty map
return copy_recursive(root, nodeMap);
}

Q.4 Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2.

Solution :- The problem can also be solved using hashing. We can use a hash map to mark all the values ​​of a given array. Using two ends, we can iterate for all possible combinations of A and B, and then check if a third value exists. If such a value exists, then there is a Pythagoras triple.

-> arr [] is an array of n element and the bool function is used to return the output Yes or No.Yes means an array satisfy the condition of Pythagorean Triplet and No means an array does not satisfy the condition of Pythagorean Triplet.

Code:

bool checkTriplet(int arr[], int n) 
{ 
int maximum = 0; 
// Find the maximum element 
for (int i = 0; i < n; i++) { 
maximum = max(maximum, arr[i]); 
} 
// Hashing array 
int hash[maximum + 1] = { 0 }; 
// Increase the count of array elements 
// in hash table 
for (int i = 0; i < n; i++) 
hash[arr[i]]++; 
// Iterate for all possible a 
for (int i = 1; i < maximum + 1; i++) { 
// If a is not there 
if (hash[i] == 0) 
continue; 
// Iterate for all possible b 
for (int j = 1; j < maximum + 1; j++) { 
// If a and b are same and there is only one a 
// or if there is no b in original array 
if ((i == j && hash[i] == 1) || hash[j] == 0) 
continue; 
// Find c 
int val = sqrt(i * i + j * j); 
// If c^2 is not a perfect square 
if ((val * val) != (i * i + j * j)) 
continue; 
// If c exceeds the maximum value 
if (val > maximum) 
continue; 
// If there exists c in the original array, 
// we have the triplet 
if (hash[val]) { 
return true; 
} 
} 
} 
return false; 
} 

Q.5 Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Solution :- Use two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by the outer loop. If a greater element is found then that element is printed as next, otherwise -1 is printed.

Code:

void printNGE(int arr[], int n) 
{ 
int next, i, j; 
for (i = 0; i < n; i++) 
{ 
next = -1; 
for (j = i + 1; j < n; j++) 
{ 
if (arr[i] < arr[j]) 
{ 
next = arr[j]; 
break; 
} 
} 
cout << arr[i] << " -- " 
<< next << endl; 
} 
} 

---

Visit :

---

Discussion