6. Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Solution:
int Solution::longestConsecutive(const vector<int> &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
int ans = 0, temp = 0, prev = -99;
set<int> st;
for (int i = 0; i < A.size(); i++) {
st.insert(A[i]);
}
set<int>::iterator it;
for (it = st.begin(); it != st.end(); it++) {
if (prev == -99) {
prev = *it;
} else {
if (*it - prev == 1) {
temp++;
} else {
temp = 0;
}
ans = max(ans, temp);
prev = *it;
}
}
return ans + 1;
}
5. Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Solution:
void helper(vector<vector<int> > &sol, vector<int> A, int st) {
if (st == A.size()) {
sol.push_back(A);
} else {
for (int i = st; i < A.size(); i++) {
// Processing required for not doing repetetive permutations.
int iter_back = i - 1;
bool dup_exist = false;
while (iter_back >= st) {
if (A[iter_back] == A[i]) {
dup_exist = true;
break;
}
iter_back--;
}
if (dup_exist) {
continue;
}
iter_swap(A.begin() + st, A.begin() + i);
helper(sol, A, st + 1);
iter_swap(A.begin() + i, A.begin() + st);
}
}
}
vector<vector<int> > Solution::permute(vector<int> &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
vector<vector<int> > sol;
sort(A.begin(), A.end());
int st = 0;
helper(sol, A, st);
return sol;
}
1. Find the kth smallest element in an unsorted array of non-negative integers.
Solution:
int Solution::kthsmallest(const vector<int> &A, int k) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
// base check.
int size = A.size();
int ans;
if (k > size || size == 0) {
return ans; // garbage.
}
// create a max heap of k elements.
vector<int> hp(A.begin(), A.begin() + k);
make_heap(hp.begin(), hp.end());
// for remaining elements, iterate one by one and check if encounter less than top of heap.
// If yes, insert into heap and heapify.
for (int i = k; i < size; i++) {
if (A[i] <= hp.front()) {
pop_heap(hp.begin(), hp.end());
hp.pop_back();
hp.push_back(A[i]);
push_heap(hp.begin(), hp.end());
}
}
return hp.front();
// return the top element.
}
2. Given an array of non negative integers
Solution:
int Solution::numRange(vector<int> &A, int B, int C) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
int size = A.size();
int sol = 0;
int sum_so_far = 0;
int starting_index = 0, i = 0;
while (starting_index < size) {
sum_so_far += A[i];
if (B <= sum_so_far && sum_so_far <= C) {
sol++;
}else if (sum_so_far > C) {
sum_so_far = 0;
i = starting_index++;
}
i++;
// Start again from starting_index + 1.
if (i == size) {
sum_so_far = 0;
starting_index++;
i = starting_index;
}
}
return sol;
}
Example:
Given
The longest consecutive elements sequence is
Given
[100, 4, 200, 1, 3, 2],The longest consecutive elements sequence is
[1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in
O(n) complexity.Solution:
int Solution::longestConsecutive(const vector<int> &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
int ans = 0, temp = 0, prev = -99;
set<int> st;
for (int i = 0; i < A.size(); i++) {
st.insert(A[i]);
}
set<int>::iterator it;
for (it = st.begin(); it != st.end(); it++) {
if (prev == -99) {
prev = *it;
} else {
if (*it - prev == 1) {
temp++;
} else {
temp = 0;
}
ans = max(ans, temp);
prev = *it;
}
}
return ans + 1;
}
5. Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example :
[1,1,2] have the following unique permutations:[1,1,2]
[1,2,1]
[2,1,1]
NOTE : No 2 entries in the permutation sequence should be the same.
Warning : DO NOT USE LIBRARY FUNCTION FOR GENERATING PERMUTATIONS.
Example : next_permutations in C++ / itertools.permutations in python.
If you do, we will disqualify your submission retroactively and give you penalty points.
Solution:
void helper(vector<vector<int> > &sol, vector<int> A, int st) {
if (st == A.size()) {
sol.push_back(A);
} else {
for (int i = st; i < A.size(); i++) {
// Processing required for not doing repetetive permutations.
int iter_back = i - 1;
bool dup_exist = false;
while (iter_back >= st) {
if (A[iter_back] == A[i]) {
dup_exist = true;
break;
}
iter_back--;
}
if (dup_exist) {
continue;
}
iter_swap(A.begin() + st, A.begin() + i);
helper(sol, A, st + 1);
iter_swap(A.begin() + i, A.begin() + st);
}
}
}
vector<vector<int> > Solution::permute(vector<int> &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
vector<vector<int> > sol;
sort(A.begin(), A.end());
int st = 0;
helper(sol, A, st);
return sol;
}
1. Find the kth smallest element in an unsorted array of non-negative integers.
Definition of kth smallest element
kth smallest element is the minimum possible n such that there are at least k elements in the array <= n.
In other words, if the array A was sorted, then A[k - 1] ( k is 1 based, while the arrays are 0 based )
NOTE
You are not allowed to modify the array ( The array is read only ).
Try to do it using constant extra space.
You are not allowed to modify the array ( The array is read only ).
Try to do it using constant extra space.
Example:
A : [2 1 4 3 2]
k : 3
answer : 2int Solution::kthsmallest(const vector<int> &A, int k) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
// base check.
int size = A.size();
int ans;
if (k > size || size == 0) {
return ans; // garbage.
}
// create a max heap of k elements.
vector<int> hp(A.begin(), A.begin() + k);
make_heap(hp.begin(), hp.end());
// for remaining elements, iterate one by one and check if encounter less than top of heap.
// If yes, insert into heap and heapify.
for (int i = k; i < size; i++) {
if (A[i] <= hp.front()) {
pop_heap(hp.begin(), hp.end());
hp.pop_back();
hp.push_back(A[i]);
push_heap(hp.begin(), hp.end());
}
}
return hp.front();
// return the top element.
}
2. Given an array of non negative integers
A, and a range (B, C),
find the number of continuous subsequences in the array which have sum
S in the range [B, C] or B <= S <= C
Continuous subsequence is defined as all the numbers
where
A[i], A[i + 1], .... A[j]where
0 <= i <= j < size(A)
Example :
A : [10, 5, 1, 0, 2]
(B, C) : (6, 8)
ans = 3
as
as
[5, 1], [5, 1, 0], [5, 1, 0, 2] are the only 3 continuous subsequence with their sum in the range [6, 8]
NOTE : The answer is guranteed to fit in a 32 bit signed integer.
Solution:
int Solution::numRange(vector<int> &A, int B, int C) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
int size = A.size();
int sol = 0;
int sum_so_far = 0;
int starting_index = 0, i = 0;
while (starting_index < size) {
sum_so_far += A[i];
if (B <= sum_so_far && sum_so_far <= C) {
sol++;
}else if (sum_so_far > C) {
sum_so_far = 0;
i = starting_index++;
}
i++;
// Start again from starting_index + 1.
if (i == size) {
sum_so_far = 0;
starting_index++;
i = starting_index;
}
}
return sol;
}
3. Print concentric rectangular pattern in a 2d matrix.
Let us show you some examples to clarify what we mean.
Example 1:
Input: A = 4.
Output:
Output:
4 4 4 4 4 4 4
4 3 3 3 3 3 4
4 3 2 2 2 3 4
4 3 2 1 2 3 4
4 3 2 2 2 3 4
4 3 3 3 3 3 4
4 4 4 4 4 4 4
Example 2:
Input: A = 3.
Output:
Output:
3 3 3 3 3
3 2 2 2 3
3 2 1 2 3
3 2 2 2 3
3 3 3 3 3
The outermost rectangle is formed by A, then the next outermost is formed by A-1 and so on.
You will be given A as an argument to the function you need to implement, and you need to return a 2D array.
Solution:
vector<vector<int> > Solution::prettyPrint(int A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
vector<vector<int> > ans;
int size = 2*(A - 1) + 1;
if (A < 1) {
return ans;
}
vector<vector<int> > sol(size, vector<int>(size, A));
for (int i = 0; i <= size/2; i++) {
int j = size/2;
int to_print = A - i;
int count_to_print = (size/2 - i);
int count = 0;
while (to_print != A) {
while (count <= count_to_print) {
sol[i][j - count] = to_print;
sol[i][j + count] = to_print;
sol[size - i - 1][j - count] = to_print;
sol[size - i - 1][j + count] = to_print;
count++;
}
to_print++;
count_to_print++;
}
}
return sol;
}
4. What is the time complexity of the following code :
int j = 0;
for(i = 0; i < n; ++i) {
while(j < n && arr[i] < arr[j]) {
j++;
}
}o(n)
No comments:
Post a Comment