Compilation of interview questions 1

Chong Wang Lv6
  2017-03-12 14:03:14 2017-03-12 14:03:14 Created   2026-10-09 14:32:01 2026-10-09 14:32:01 Updated

I was reading Cracking the Coding Interview. Some of its 150 questions are excellent, and my submissions are here. Here are my notes:

5.3 Closest Numbers

Given a positive integer, find the two closest numbers with the same number of 1s in their binary representation—one slightly larger and one slightly smaller.

For the slightly larger number, change the rightmost suitable 0 to 1, then move the remaining 1s as far left as possible. Scan past zeroes, then ones, find the next zero, and turn it into one.

For the slightly smaller number, change the rightmost suitable 1 to 0, then move the remaining 1s as far right as possible. Scan past ones, then zeroes, find the next one, and turn it into zero.

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
class CloseNumber
{
public:
	int find_min(int x)
	{
		int res = x;
		int p = 0;
		int cnt1 = 0, cnt0 = 0;
		while ((1 << p)&res)
		{
			res ^= (1 << p);
			p++;
			cnt1++;
		}
		cnt0++;
		p++;
		while (((1 << p)&res) == 0)
		{
			p++;
			cnt0++;
		}
		cnt1++;
		res ^= (1 << p);
		res ^= ((1 << cnt1) - 1) << (cnt0 - 1);
		return res;
	}
	int find_max(int x)
	{
		int res = x;
		int p = 0;
		int cnt1 = 0, cnt0 = 0;
		while (((1 << p)&res)==0)
		{
			p++;
			cnt0++;
		}
		res ^= (1 << p);
		p++;
		while (((1 << p)&res))
		{
			res ^= (1 << p);
			p++;
			cnt1++;
		}
		res ^= (1 << p);
		cnt0++;
		res ^= ((1 << cnt1) - 1);
		return res;
	}
	vector<int> getCloseNumber(int x)
	{
		vector<int>ans;
		ans.push_back(find_min(x));
		ans.push_back(find_max(x));
		return ans;
	}
}wc;

5.7 Draw a Horizontal Line

A monochrome screen is stored in a one-dimensional array, where each element represents eight consecutive pixels. Implement a function that colors pixels $x$ through $y$ (indexed from zero) as efficiently as possible.

Given the screen array (each element represents eight consecutive pixels, whose left-to-right positions correspond to its binary bits from low to high) and integers x and y as described above, return the recolored screen array. The input is valid.

There are quite a few implementation traps, so it is rather fiddly.

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
class Render 
{
public:
	vector<int> renderPixel(vector<int> screen, int x, int y)
	{
		int rx = x / 8, cx = x % 8;
		int ry = y / 8, cy = y % 8;

		if (rx < ry)
		{
			for (int k = rx + 1; k < ry; k++)
			{
				screen[k] = 0xff;
			}
			int num = 8 - cx;
			screen[rx] |= (((1 << (num)) - 1) << cx);
			screen[ry] |= ((1 << (cy + 1)) - 1);
		}
		else
		{
			screen[rx] |= 0xff & ~((1 << cx) - 1)&((1 << (cy + 1)) - 1);
		}
		return screen;
	}
};

9.3 Magic Index (1)

In an array $A[0..n-1]$, a magic index satisfies $A[i]=i$. Given a strictly increasing array with distinct values, determine whether a magic index exists in better than $O(n)$ time.

Given an int array A and its size n, return a bool indicating whether it contains a magic index.

With distinct values, compare A[mid] with mid and binary-search directly.

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
class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n)
    {
        int sz = A.size();
        int le = 0, ri = sz - 1;
        while (le < ri)
        {
            int mid = (le + ri) >> 1;
            if (A[mid] == mid)
            {
                return true;
            }
            else if (A[mid] > mid)
            {
                ri = mid - 1;
            }
            else
            {
                le = mid + 1;
            }
        }
        return A[le]==le;
    }
};

Magic Index (2)

In an array $A[0..n-1]$, a magic index satisfies $A[i]=i$. Given a nondecreasing array whose values may repeat, determine whether a magic index exists in better than $O(n)$ time.

Given an int array A and its size n, return a bool indicating whether it contains a magic index.

When values may repeat, a single binary-search decision is no longer enough. Recursively search the left and right halves, skipping values where possible; see the code for the details.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MagicIndex {
public:
	bool findMagicIndex(vector<int> A, int n)
	{
		return find(A, 0, n, n);
	}
	bool find(vector<int>&A, int st, int en, int n)
	{
		if (st > en || st<0 || en>n)return false;
		int mid = (st + en) >> 1;
		if (A[mid] == mid)return true;
		int le = min(mid - 1, A[mid]);
		int ri = max(mid + 1, A[mid]);

		return find(A, st, le, n) || find(A, ri, en, n);
	}
}wc;

9.10 Stack of Boxes

Given boxes with width $w_i$, depth $d_i$, and height $h_i$, stack them so that each upper box is narrower and shorter than the box below it. Find the greatest possible total stack height.

Given three int arrays w, l, and h for each box’s width, length, and height, and the number of boxes n, return the maximum stack height. $n \le 500$.

Use the same DP idea as longest increasing subsequence, after an initial bubble sort.

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
class Box 
{
public:
	int getHeight(vector<int> w, vector<int> l, vector<int> h, int n)
	{
		for (int i = 0; i < w.size(); i++)
		{
			for (int j = 0; j < w.size() - i - 1; j++)
			{
				if (w[j] > w[j + 1])
				{
					swap(w[j], w[j + 1]);
					swap(l[j], l[j + 1]);
					swap(h[j], h[j + 1]);
				}
			}
		}
		for (int i = 0; i < w.size(); i++)
		{
			cout << w[i] << " " << l[i] << " " << h[i] << endl;
		}
		vector<int>res(w.size(), 0);
		for (int i = w.size()-1; i >= 0 ; i--)
		{
			int ans = 0;
			for (int j = w.size()-1; j > i; j--)
			{
				if (w[i] < w[j] && l[i] < l[j])
				{
					ans = max(ans, res[j]);
				}
			}
			res[i] = ans + h[i];
		}
		int ans = 0;
		for (auto it : res)
		{
			ans = max(ans, it);
		}
		return ans;
	}
};
On this page
Compilation of interview questions 1