This C++ Algorithms and SQL Online Test Separates Good From Bad Hires

Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.

Write a function that, efficiently with respect to time used, checks if a given binary search tree contains a given value.

For example, for the following tree:

• n1 (Value: 1, Left: null, Right: null)
• n2 (Value: 2, Left: n1, Right: n3)
• n3 (Value: 3, Left: null, Right: null)

Call to contains(n2, 3) should return true since a tree with root at n2 contains number 3.

App usage data are kept in the following table:

TABLE sessions
  id INTEGER PRIMARY KEY,
  userId INTEGER NOT NULL,
  duration DECIMAL NOT NULL

Write a query that selects userId and average session duration for each user who has more than one session.

See the example case for more details.

The following data definition defines an organization's employee hierarchy.

An employee is a manager if any other employee has their managerId set to this employee's id. That means John is a manager if at least one other employee has their managerId set to John's id.

TABLE employees
  id INTEGER NOT NULL PRIMARY KEY
  managerId INTEGER
  name VARCHAR(30) NOT NULL
  FOREIGN KEY (managerId) REFERENCES employees(id)

Write a query that selects only the names of employees who are not managers.

See the example case for more details.

Given the following data definition, write a query that returns the number of students whose first name is John.

TABLE students
   id INTEGER PRIMARY KEY,
   firstName VARCHAR(30) NOT NULL,
   lastName VARCHAR(30) NOT NULL

A table containing the students enrolled in a yearly course has incorrect data in records with ids between 20 and 100 (inclusive).

TABLE enrollments
  id INTEGER NOT NULL PRIMARY KEY
  year INTEGER NOT NULL
  studentId INTEGER NOT NULL

Write a query that updates the field 'year' of every faulty record to 2015.

Information about pets is kept in two separate tables:

TABLE dogs
  id INTEGER NOT NULL PRIMARY KEY,
  name VARCHAR(50) NOT NULL

TABLE cats
  id INTEGER NOT NULL PRIMARY KEY,
  name VARCHAR(50) NOT NULL

Write a query that select all distinct pet names.

See the example case for more details.

A new social network site has the following data tables:

users
id	name	sex
1	Ann	null
2	Steve	m
3	Mary	f
4	Brenda	f

friends
user1	user2
1	2
1	3
2	3

Select data that will be returned by the following SQL query:

SELECT users.name, COUNT(*) as count FROM users
LEFT JOIN friends
ON users.id = friends.user1 OR users.id = friends.user2
WHERE users.sex = 'f'
GROUP BY users.id, users.name;

Each item in a web shop belongs to a seller. To ensure service quality, each seller has a rating.

The data are kept in the following two tables:

TABLE sellers
  id INTEGER PRIMARY KEY,
  name VARCHAR(30) NOT NULL,
  rating INTEGER NOT NULL

TABLE items
  id INTEGER PRIMARY KEY,
  name VARCHAR(30) NOT NULL,
  sellerId INTEGER
  FOREIGN KEY (sellerId) REFERENCES sellers(id)

Write a query that selects the item name and the name of its seller for each item that belongs to a seller with a rating greater than 4. The query should return the name of the item as the first column and name of the seller as the second column.

See the example case for more details.

Implement the unique_names method. When passed two vectors of names, it will return a vector containing the names that appear in either or both vectors. The returned vector should have no duplicates.

For example, calling unique_names(std::vector<std::string>{"Ava", "Emma", "Olivia"}, std::vector<std::string>{"Olivia", "Sophia", "Emma"}) should return a vector containing Ava, Emma, Olivia, and Sophia in any order.

Implement the function findRoots to find the roots of the quadratic equation: ax² + bx + c = 0.  The function should return a pair containing both roots in any order. If the equation has only one solution, the function should return that solution as both elements of the pair. The equation will always have at least one solution.

The roots of the quadratic equation can be found with the following formula:

For example, findRoots(2, 10, 8) should return a pair containing (-1, -4) or (-4, -1) as the roots of the equation 2x² + 10x + 8 = 0 are -1 and -4.

A playlist is considered a repeating playlist if any of the songs contain a pointer to a previous song in the playlist. Otherwise, the playlist will end with the last song which points to NULL.

Implement a function isRepeatingPlaylist that, efficiently with respect to time used, returns true if a playlist is repeating or false if it is not.

For example, the following code prints "true" as both songs point to each other.

Song* first = new Song("Hello");
Song* second = new Song("Eye of the tiger");
    
first->next(second);
second->next(first);

std::cout << std::boolalpha << first->isRepeatingPlaylist();

User interface contains two types of user input controls: TextInput, which accepts all characters and NumericInput, which accepts only digits.

Implement the following methods:

• add on class TextInput - adds the given character to the current value
• getValue on class TextInput - returns the current value
• add on class NumericInput - overrides the base class method so that each non-numeric character is ignored

For example, the following code should output "10":

TextInput* input = new NumericInput();
input->add('1');
input->add('a');
input->add('0');
std::cout << input->getValue();

Write a function that, when passed a list and a target sum, returns, efficiently with respect to time used, two distinct zero-based indices of any two of the numbers, whose sum is equal to the target sum. If there are no two numbers, the function should return (-1, -1).

For example, findTwoSum({ 3, 1, 5, 7, 5, 9 }, 10) should return a std::pair<int, int> containing any of the following pairs of indices:

• 0 and 3 (or 3 and 0) as 3 + 7 = 10
• 1 and 5 (or 5 and 1) as 1 + 9 = 10
• 2 and 4 (or 4 and 2) as 5 + 5 = 10

As part of a data processing pipeline, complete the implementation of the makePipeline method:

• The method should accept a vector of functions, and it should return a new function that accepts one parameter arg.
• The returned function should call the first function in the makePipeline with the parameter arg, and call the second function with the result of the first function.
• The returned function should continue calling each function in the makePipeline in order, following the same pattern, and return the value from the last function.

For example,

std::vector<std::function<int (int)>> functions;
functions.push_back([] (int x) -> int { return x * 3; });
functions.push_back([] (int x) -> int { return x + 1; });
functions.push_back([] (int x) -> int { return x / 2; });
std::function<int (int)> func = makePipeline(functions);

calling the func(3) should return 5.

The following two tables are used to define users and their respective roles:

TABLE users
  id INTEGER NOT NULL PRIMARY KEY,
  userName VARCHAR(50) NOT NULL

TABLE roles
  id INTEGER NOT NULL PRIMARY KEY,
  role VARCHAR(20) NOT NULL

The users_roles table should contain the mapping between each user and their roles. Each user can have many roles, and each role can have many users.

Modify the provided SQL create table statement so that:

• Only users from the users table can exist within users_roles.
• Only roles from the roles table can exist within users_roles.
• A user can only have a specific role once.

See the example case for more details.

Multiple choice test has several multiple choice questions. Each question can have only one correct answer. Additionally, timed multiple choice test can specify the time allowed for solving each question in the test.

The code below satisfies this specification, but the customer complained that the memory usage of the program constantly increases. Fix this problem.

Implement function countNumbers that accepts a sorted vector of unique integers and, efficiently with respect to time used, counts the number of vector elements that are less than the parameter lessThan.

For example, for vector v containing { 1, 3, 5, 7 }, countNumbers(v, 4) should return 2 because there are two vector elements less than 4.

A TrainComposition is built by attaching and detaching wagons from the left and the right sides, efficiently with respect to time used.

For example, if we start by attaching wagon 7 from the left followed by attaching wagon 13, again from the left, we get a composition of two wagons (13 and 7 from left to right). Now the first wagon that can be detached from the right is 7 and the first that can be detached from the left is 13.

Implement a TrainComposition that models this problem.

An insurance company maintains records of sales made by its employees. Each employee is assigned to a state. States are grouped under regions. The following tables contain the data:

TABLE regions
  id INTEGER PRIMARY KEY
  name VARCHAR(50) NOT NULL

TABLE states
  id INTEGER PRIMARY KEY
  name VARCHAR(50) NOT NULL
  regionId INTEGER NOT NULL
  FOREIGN KEY (regionId) REFERENCES regions(id)

TABLE employees
  id INTEGER PRIMARY KEY
  name VARCHAR(50) NOT NULL
  stateId INTEGER NOT NULL
  FOREIGN KEY (stateId) REFERENCES states(id)

TABLE sales
  id INTEGER PRIMARY KEY
  amount INTEGER NOT NULL
  employeeId INTEGER NOT NULL
  FOREIGN KEY (employeeId) REFERENCES employees(id)  

Management requires a comparative region sales analysis report.

Write a query that returns:

• The region name.
• Average sales per employee for the region (Average sales = Total sales made for the region / Number of employees in the region).
• The difference between the average sales of the region with the highest average sales, and the average sales per employee for the region (average sales to be calculated as explained above).

Employees can have multiple sales. A region with no sales should be also returned. Use 0 for average sales per employee for such a region when calculating the 2nd and the 3rd column.

See the example case for more details.