Interview question compilation 2

Chong Wang Lv6
  2017-03-15 23:08:43 2017-03-15 23:08:43 Created   2026-10-09 14:32:01 2026-10-09 14:32:01 Updated

Continuing my notes on Cracking the Coding Interview.

17.4 Maximum Without Comparison

Write a method to find the larger of two numbers without using comparison or conditional operators such as if-else.

Given two integers a and b, return the larger one. If they are equal, return either.

Use the sign of a-b to choose the result, while accounting for overflow. Overflow can only occur when the values have different signs, so handle each case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Max {
public:
	int flag(int x)
	{
		return (x >> 31) & 1;
	}
	int getMax(int a, int b)
	{
		int fa = flag(a);
		int fb = flag(b);
		int fc = flag(a - b);

		int k = fa^fb;
		int ans = 0;
		if (k == 0)// Same sign
		{
			ans = 1 ^ fc;
		}
		else// Different signs
		{
			ans = 1 ^ fa;
		}
		return ans*a + (1 ^ ans)*b;
	}
}wc;

17.5 Master Mind

There are four slots, each containing a red (R), yellow (Y), green (G), or blue (B) ball. For example, RGGB means red in slot 1, green in slots 2 and 3, and blue in slot 4. A player guesses a combination such as YRGB. A correct color in the correct slot is a “hit”; a correct color in the wrong slot is a “pseudo-hit”. A hit must not also count as a pseudo-hit.

Given strings A and guess, representing the color combination and a guess, return an int array: hits first, then pseudo-hits.

A LeetCode problem. First count the hits, then count the unmatched colors. Watch the edge cases.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Result {
public:
	vector<int> calcResult(string A, string guess)
	{
		int A_len = A.length();
		int g_len = guess.length();

		vector<int>res;
		if (A_len != g_len)return res;
		int ans1 = 0, ans2 = 0;

		map<char, int>hax;
		for (int i = 0; i < A_len; i++)
		{
			if (A[i] == guess[i])ans1++;
			else
			{
				hax[A[i]]++;
			}
		}
		for (int i = 0; i < g_len; i++)
		{
			if (A[i] == guess[i])continue;
			else
			{
				if (hax[guess[i]])
				{
					ans2++;
					hax[guess[i]]--;
				}
			}
		}
		res.push_back(ans1);
		res.push_back(ans2);
		return res;
	}
};

17.6 Minimal Sort

Given an integer array, find indices m and n such that sorting only the elements between them sorts the entire array. Minimize n-m; in other words, find the shortest such subsequence.

Given an int array A and its size n, return a pair representing the target subsequence’s start and end. Indices start at 0; if the array is already sorted, return [0,0]. All values are positive integers.

First find the middle interval that violates the ordering, record its minimum and maximum, and extend it outward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Rearrange
{
public:

	int find_left(vector<int>&A)
	{
		int sz = A.size();
		for (int i = 0; i+1 < sz; i++)
		{
			if (A[i] > A[i + 1])return i;
		}
		return sz - 1;
	}
	int find_right(vector<int>&A)
	{
		int sz = A.size();
		for (int i = sz - 1; i - 1 >= 0; i--)
		{
			if (A[i] < A[i - 1])return i;
		}
		return 0;
	}
	vector<int> findSegment(vector<int> A, int n) 
	{
		int left = find_left(A);
		int right = find_right(A);
        if (left >= right)
		{
			vector<int>ans = { 0,0 };
			return ans;
		}
		int minn = A[left], maxx = A[right];
		for (int i = left; i <= right; i++)
		{
			minn = min(minn, A[i]);
			maxx = max(maxx, A[i]);
		}
		while (left >= 0)
		{
			if (A[left] <= minn)
			{
				break;
			}
			left--;
		}
		left++;
		while (right < A.size())
		{
			if (A[right] >= maxx)
			{
				break;
			}
			right++;
		}
		right--;
		vector<int>res;
		res.push_back(left);
		res.push_back(right);
		return res;
	}
};

17.7 Number to English

Given a nonnegative integer, write an algorithm that prints its English description.

Given an integer x, return a string containing its English description.

This is also an original LeetCode problem. It is fiddly mainly because spaces require careful handling in every case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class ToString 
{
public:
	vector<string> bigs = { "","Thousand","Million" };
	vector<string>digits = { "One","Two","Three","Four","Five","Six","Seven","Eight","Nine" };
	vector<string>teens = { "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen" };
	vector<string>tens = { "Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety" };
	string toString(int x) 
	{
		if (x == 0)
		{
			return "Zero";
		}
		else if (x < 0)
		{
			return "Negative " + toString(-1 * x);
		}

		string res = "";
		int cnt = 0;
		while (x > 0)
		{
			if (x % 1000 != 0)
			{
                if(res.length())
					res = num_to_string(x % 1000) + " " + bigs[cnt] + "," + res;
                else
                    res = num_to_string(x % 1000) + " " + bigs[cnt];
			}
			x /= 1000;
			cnt++;
		}
        while (*res.begin() == ' ')res.erase(res.begin());
		while (*(res.end() - 1) == ' ')res.erase(res.end() - 1);
		return res;
	}
	string num_to_string(int x)
	{
		string res = "";
		if (x >= 100)
		{
			res = digits[x / 100 - 1] + " Hundred";
			x = x % 100;
		}
		if (x >= 11 && x <= 19)
		{
            if(res.length())
				res = res + " " + teens[x % 10 - 1];
			else
                res = teens[x % 10 - 1];
            return res;
		}
		else if (x == 10 || x >= 20)
		{
			int num = x / 10;
			x %= 10;
            if(res.length())
				res = res + " " + tens[num - 1];
            else
                res = tens[num - 1];
		}
		if (x)
        {
            if(res.length())
				res = res + " " + digits[x - 1];
            else
                res = digits[x - 1];
        }
        return res;
	}
};

17.13 Tree to Linked List

TreeNode is a node-like data structure with a val field and pointers to other nodes. It represents a binary search tree (left is the left child and right is the right child). Convert this tree, implemented with TreeNode, into a linked list implemented with ListNode.

Given a pointer root to the root of a binary search tree, return a pointer to the head of the converted linked list.

Use recursive in-order traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Converter
{
public:
	ListNode *head = new ListNode(-1);
	ListNode *pre = head;
	ListNode* treeToList(TreeNode* root) 
	{
		if (root)
		{
			treeToList(root->left);
			pre->next = new ListNode(root->val);
			pre = pre->next;
			treeToList(root->right);
		}
		return head->next;
		// write code here
	}
};
On this page
Interview question compilation 2