# Sum of Three Numbers Less than Target - Google Top Interview Questions

### Problem Statement :

```Given a list of integers nums and an integer target, return the number of triples i < j < k that exist such that nums[i] + nums[j] + nums[k] < target.

Constraints

n ≤ 1,000 where n is the length of nums

Example 1

Input

nums = [-3, 5, 3, 2, 7]

target = 9

Output

5

Explanation

Here are the different triples' values:

-3 + 5 + 3 = 5
-3 + 5 + 2 = 4
-3 + 3 + 2 = 2
-3 + 3 + 7 = 7
-3 + 2 + 7 = 6```

### Solution :

```                        ```Solution in C++ :

int solve(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1, k = nums.size() - 1; j < k;) {
if (nums[i] + nums[j] + nums[k] < target) {
ans += k - j;
j++;
} else {
k--;
}
}
}
return ans;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int[] nums, int target) {
int res = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) res += twoSum(nums, target, i);
return res;
}

// Two pointer function to find all triplets less than target
public int twoSum(int[] nums, int target, int i) {
int j = i + 1, k = nums.length - 1, res = 0;

// Do not do i <= j because the same index cannot be used twice
while (j < k) {
int total = nums[i] + nums[j] + nums[k];
if (total >= target)
k--;

// The array is sorted so all triplets using a smaller k can be added
else {
res += k - j;
j++;
}
}
return res;
}
}```
```

```                        ```Solution in Python :

class Solution:
def two_sum(self, nums, start, val, target):
a, b = start, len(nums) - 1

ans = 0

while a < b:
if nums[a] + nums[b] + val < target:
a += 1
ans += b - a + 1
else:
b -= 1

return ans

def solve(self, nums, target):
nums.sort()

return sum(self.two_sum(nums, i + 1, nums[i], target) for i in range(len(nums)))```
```

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio