Samsung | Senior SDE | Bangalore | November 2021 | Offer
Anonymous User
1075
Interview

Question: Given a sorted array which may contain duplicate elements, find the first and the last index of the target integer. If the target is not present, return -1. The only constraint was that we had to implement every library function.

Code

//This function returns the -1 if element is not found else
//it returns the index of that element
int upper_bound(vector<int> &arr, int target) {
	int n = arr.size();
	int l = 0, r = n - 1;
	int ansIndex = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		// 1, 2, 3, 3, 3, 4, 4, 5, target = 3
		if (arr[mid] == target) {
			//have found the needed element
			ansIndex = mid;
			l = mid + 1;
		} else if (arr[mid] > target) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return ansIndex;
}

//This function returns the -1 if element is not found else
//it returns the index of that element
int lower_bound(vector<int> &arr, int target) {
	int n = arr.size();
	int l = 0, r = n - 1;
	int ansIndex = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		// 1, 2, 3, 3, 3, 4, 4, 5, target = 3
		if (arr[mid] == target) {
			//have found the needed element
			ansIndex = mid;
			r = mid - 1;
		} else if (arr[mid] > target) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return ansIndex;
}
pair<int, int> getTheIndices (vector<int> &arr, int target) {
	int n = arr.size();
	int upperIndex = upper_bound(arr, target);
	int lowerIndex = lower_bound(arr, target);
	return {lowerIndex, upperIndex};
}

Question: There is a salesman named Alex. Alex was able to predict the profits he can earn in next N days in two different cities A and B. But Doesn't know how he can maximize the profits if Alex can only sell his goods in one of the cities on a particular day. The cost of travelling between cities is also known. Please help alex so that he can maximize the profit.

Code

Int func(lastCity, currentCost, currentDay) {
	if (currentDay >= A.size())  return currentCost;
	//1 - A city, 2 - B city
	if (lastCity == 1) {
		int ans = max(func(1, A[currentDay] + currentCost, currentDay + 1), func(2, B[currentDay] - Cost + currentCost, currentDay + 1));
	} else {
		int ans = max(func(1, A[currentDay] + currentCost - Cost, currentDay + 1), func(2, B[currentDay] + currentCost, currentDay + 1));
	}
	Return ans;
}

Q3: Given a linked list, we want to reverse the linked list in the group of size ‘k’.

Ex -  1, 2, 3, 4, 5, 6, K = 3
After reversal - 3, 2, 1, 6, 5, 4


struct Node {
	struct Node *next;
	Int val;
};

//current Example
//1, 2, 3, 4, 5, 6, k = 3
//3, 2, 1->nullptr helper(4, 5, 6, k = 3)
// 6, 5, 4
//3, 2, 1, 6, 5, 4
Node *helper(Node *head, int k) {
	int  nodeCnt  = 0;
	Node *ptr = head, prev = nullptr;
	//reversed the current block
	while (nodeCnt < k && ptr->next) {
		Node *next = ptr->next;
		ptr->next = prev;
		Prev = ptr;
		Ptr = next;
		++nodeCnt;
	}

	ptr->next = helper(prev->next, k);
	return prev;
}

Node *reverseInBlocks(Node *head, int k) {
	helper(head, k);
}
Comments (4)