akshaycj47
BAN USERIf you are doing it in Python, might as well do it in Pythonic way :P
(Use collections.Counter)
import collections
def findDup(a):
d = collections.Counter(a)
for key, value in d.items():
if value > 1:
return True
return False
a = [1, 2, 34, 545, 334, 53, 534, 56, 7, 4, 3, 1]
print findDup(a)
This can be done using a double ended queue. T = O(n), S = O(k)
#include <iostream>
#include <deque>
using namespace std;
void maxSubarraySlidingWindow(int* arr, int n, int k) {
// Create a deque to simulate a sliding window
deque<int> dq(k);
// Fill out the initial window
for (int i = 0; i < k; i++) {
// Removing all the elements that are greater than current element
while (!dq.empty() && arr[dq.back()] >= arr[i]) {
dq.pop_back();
}
// Pushing the index of the current element
dq.push_back(i);
}
// Sliding the window for all the remaining array elements
for (int i = k + 1; i < n; i++) {
// Printing the smallest element (element at the front)
cout << arr[dq.front()] << " ";
// Removing elements that are out of the window
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// Removing all the elements that are greater than current element
while (!dq.empty() && arr[dq.back()] >= arr[i]) {
dq.pop_back();
}
// Pushing the index of the current element
dq.push_back(i);
}
// Printing for the final window element
cout << arr[dq.front()] << " ";
cout << endl;
}
int main() {
int arr[] = { 2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
maxSubarraySlidingWindow(arr, n, k);
}
Implementation in C++:
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct Item {
string name;
int quantity;
int price;
};
class ShoppingCart {
private:
vector<Item> item;
int total_price;
public:
ShoppingCart();
void addItem(string name, int quantity, int price);
void removeItem(string name, int quantity);
int getTotal();
};
ShoppingCart::ShoppingCart() {
cout << "Creating a new shopping cart" << endl;
total_price = 0;
}
void ShoppingCart::addItem(string name, int quantity, int price) {
for (int i = 0; i < item.size(); i++) {
if (item[i].name == name) {
item[i].quantity += quantity;
return;
}
}
Item temp;
temp.name = name;
temp.quantity = quantity;
temp.price = price;
item.push_back(temp);
}
void ShoppingCart::removeItem(string name, int quantity) {
for (int i = 0; i < item.size(); i++) {
if (item[i].name == name) {
if (item[i].quantity >= quantity) {
item[i].quantity -= quantity;
return;
}
cout << "Not enough items present in the cart to be removed" << endl;
return;
}
}
cout << "This item is not present in the cart" << endl;
}
int ShoppingCart::getTotal() {
total_price = 0;
for (int i = 0; i < item.size(); i++) {
total_price += item[i].quantity * item[i].price;
}
return total_price;
}
int main() {
ShoppingCart cart;
cart.addItem("Maggi", 10, 5);
cart.addItem("Biryani", 2, 15);
cart.addItem("Ketchup", 1, 5);
cout << "Total cost: " << cart.getTotal() << endl;
cart.addItem("Football", 2, 15);
cart.removeItem("Maggi", 4);
cart.removeItem("Ketchup", 2);
cout << cart.getTotal() << endl;
cart.addItem("Candy", 15, 2);
cart.removeItem("Bat", 1);
cout << "Total cost: " << cart.getTotal() << endl;
}
How about traversing the string in a reverse order?
Have a variable, result which will get modified when the character is encountered for the first time. The number of occurrences of characters can be stored in a hash table.
Yes, I always use this trick.
- akshaycj47 November 10, 2015It won't work when a and b are huge numbers. It will cause overflow.
The correct solution will be: a + (b - a) / 2
Because we should use a string literal instead of string variable.
- akshaycj47 November 09, 2015#include <iostream>
#include <climits>
using namespace std;
int findSecondLargest(int* arr, int n) {
int first = INT_MIN;
int second = INT_MIN;
for(int i = 0; i < n; i++) {
if(first < arr[i]) {
second = first;
first = arr[i];
}
else if(second < arr[i] && arr[i] != first) {
second = arr[i];
}
}
return second;
}
int main() {
int arr[] = {3, 5, 9, 6, 4, 2, 11};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSecondLargest(arr, n);
}
#include <iostream>
using namespace std;
bool isPartition(int* arr, int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
}
if (sum & 1) {
return false;
}
sum = sum / 2;
bool** T = new bool*[n + 1];
for (int i = 0; i < n + 1; i++) {
T[i] = new bool[sum + 1];
}
// Initializing the first row as false
for (int j = 0; j < sum + 1; j++) {
T[0][j] = false;
}
// Initializing the first column as true
for (int i = 0; i < n + 1; i++) {
T[i][0] = true;
}
// Computing the T matrix
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < sum + 1; j++) {
if (j < arr[i - 1]) {
T[i][j] = T[i - 1][j];
}
else {
T[i][j] = T[i - 1][j] || T[i - 1][j - arr[i - 1]];
}
}
}
return T[n][sum];
}
int main() {
int arr[] = { 3, 1, 1, 2, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << isPartition(arr, n) << endl;
}
Linked list can be implemented using two stacks.
We can make one of the operations costly: inserting at tail.
Correction:
1. Suppose we have trees p and q.
2. Find the mirror of q.
3. Check is p and q are structurally equivalent
4. Find the mirror of q to get the original tree back.
1. Suppose we have trees p and q.
2. Swap the left and right nodes of q.
3. Check is p and q are structurally equivalent
4. Swap the left and right nodes of q to get the original tree back.
What is k?
- akshaycj47 November 06, 2015How do you assign int to a char*??
- akshaycj47 November 02, 2015
I think he is trying to return whether array can be partitioned in terms of subsets having sum / 2
- akshaycj47 November 18, 2015