ashot madatyan
BAN USERThis is basically swapping odd and even bits, which is done using bitmasks. Implementation provided below:
unsigned char swap_bits(unsigned char ch)
{
return ((ch & 0xAA)>>1 ) | ( (ch & 0x55) << 1);
}
If you try to trace the algorithm, you will see that each element in the array is visited exactly once. Since I have provided a complete working solution, I think you can copy-n-paste it into your favourite C++ IDE and see the output for any given input. BTW, when providing a comment, would you please provide not the bare "it is not O(N)"-like something, but instead base your reasoning on the facts - this way all the posters will have some stuff to discuss. Moreover, I would also ebcourage you to sign up and use some name/nick, since communicating to an "anonymous" user is not a so good idea for stuff like this.
Cheers,
Ashot Madatyan
If you try to trace the algorithm, you will see that each element in the array is visited exactly once. Since I have provided a complete working solution, I think you can copy-n-paste it into your favourite C++ IDE and see the output for any given input. BTW, when providing a comment, would you please provide not the bare "it is not O(N)"-like something, but instead base your reasoning on the facts - this way all the posters will have some stuff to discuss. Moreover, I would also ebcourage you to sign up and use some name/nick, since communicating to an "anonymous" user is not a so good idea for stuff like this.
Cheers,
Ashot Madatyan
This question seems to has been double posted. Anyway, please see my complete solution at the link below:
w w w .careercup.com/question?id=13580673
Time complexity O(N), space O(1)
This implementation handles all the input values for Count of Groups(a b c ... x) and Count of Elements in the group (a1 a2 a3 a4 ... an).
Below is the solution with O(N) time and O(1) space complexities.
#include <stdio.h>
/*
Given the current index, count of groups and count of elements within each group,
return the destination index where the current element should be placed to form
the series [a1, b1, c1,...an, bn, cn] out of array
[a1, a2, a3, b1, b2, b3, c1, c2, c3 ... an, bn, cn]
@idx -
@gc - count of groups
@rc - count of elements within each group
*/
int get_idx(int idx, int gc, int rc)
{
// gc = 3 (abc), rc = 4 (a1 a2 a3 a4)
// 0 1 2 3 4 5 6 7 8 9 10 11
// a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4
// a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4
// 0 4 8 1 5 9 2 6 10 3 7 11
int ogc, orc, didx = -1;
ogc = idx / rc;
orc = idx % rc;
didx = orc * gc + ogc;
#if 0
printf("IDX: %-2d DIDX: %-2d OGC: %-2d ORC: %-2d\n", idx, didx, ogc, orc);
#endif
return didx;
}
void test_get_idx(int gc, int rc)
{
int tot = gc * rc;
int didx;
for (int i = 0; i < tot; i++){
didx = get_idx(i, gc, rc);
//printf("IDX: %-2d DIDX: %-2d\n", i, didx);
}
}
void swap(int arr[], int f, int s)
{
int tmp;
if(f == s)
return;
tmp = arr[f];
arr[f] = arr[s];
arr[s] = tmp;
}
/*
Given an array of series like [a1,a2,...an, b1, b2,...bn, c1, c2, ...cn]
do an in-place merge like [a1, b1, c1,... an, bn, cn].
@cnt - array length. Is equal to (@gc * @rc)
@gc - count of groups (a, b, c...)
@rc - count of elements in each group (a1, b1, c1,...an)
*/
void merge_groups(int arr[], int cnt, int gc, int rc)
{
int tc = cnt - 2;
int i;
int didx, cidx;
int count = 1;
for (i = 1; i < cnt; i++) {
if (tc <= 0)
break;
cidx = i;
didx = get_idx(cidx, gc, rc);
while (i != didx){
printf("ID: %-2d I: %-2d CIDX: %-2d DIDX: %-2d\n", count++, i, cidx, didx);
swap(arr, i, didx);
--tc;
if (i == didx)
break;
cidx = didx;
didx = get_idx(didx, gc, rc);
}
--tc; // Count the last too
}
}
void print_array(int arr[], int cnt, const char* cslabel)
{
if (cslabel)
printf("%s\n", cslabel);
for (int i = 0; i < cnt; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
int main(int argc, char *argv[])
{
int arr[] = {1, 4, 7, 10, 2, 5, 8, 11, 3, 6, 9, 12};
int cnt = sizeof(arr)/sizeof(arr[0]);
int gc = 3;
int rc = 4;
if (gc * rc != cnt){
printf("Count of groups (%d) and rank count(%d) do not match "
"the array size (%d)", gc, rc, cnt);
return 1;
}
print_array(arr, cnt, "Before:");
merge_groups(arr, cnt, gc, rc);
print_array(arr, cnt, "After:");
return 0;
}
The original problem says " Given a sorted list ... "
I presume that the "list" here is just a loose semantics for an array, which is iterable randomly. If the input is nevertheless a LinkedList, then yes, you cannot use BS on it efficiently (though it is implementable).
Hey folks. I think you are all missing a very important hint that the array is sorted and rotated by some K positions. In that case we should use the binary search principle to find the reset point, which will be the minimum element in the array. Below is the complete code to demonstarte this technique that runs in O(Log N) time:
#include <iostream>
using namespace std;
/* Find the reset point, i.e. the minimum element's index in
a sorted array that has been rotated (left or right) by some
number of positions.
*/
int find_reset_point(int arr[], int sidx, int eidx)
{
int midx;
if (eidx - sidx <= 0)
return -1;
while (sidx < eidx){
if (eidx - sidx <= 1){
if (arr[sidx] > arr[eidx])
return eidx;
}
midx = sidx + (eidx - sidx) / 2;
if (arr[midx] > arr[sidx])
sidx = midx;
else
eidx = midx;
}
return -1; // No reset point detected, array is sorted ascending
}
int main(int argc, char *argv[])
{
//int arr[] = {4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3};
int arr[] = {10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
//int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
int cnt = sizeof(arr)/sizeof(arr[0]);
int idx;
idx = find_reset_point(arr, 0, cnt - 1);
cout << "IDX: " << idx << endl;
}
- ashot madatyan May 13, 2012struct SLNode {
SLNode *next;
int data;
};
void SL_delete_node(SLNode *head, int value)
{
SLNode *prev = NULL;
while (head){
if (head->data) { // found
if (NULL == prev) { // this is the only node
printf("The value is in head of SLL\n");
return;
}
else { // we have a previous node
prev->next = head->next;
//Delete the current node
delete head;
break;
}
}
prev = head;
head = head->next;
}
}
- ashot madatyan May 11, 20121. Divide all 25 racers into 5 groups, each containg 5 persons and make them race (5 races up to now).
2. From these 5 groups, merge into a list of 3 top performers by picking the first topper
in each group - very much like merging sorted arrays in the merge sort algorithm.
So, there are only 5 races required to identify the top 3 performers
BTW, the original problem seems to be like below:
There are 25 horses. At most, 5 horses can race together at a time. You must
determine the fastest, second fastest, and third fastest horses.
Find the minimum number of races in which this can be done.
Hi dear posters. First of all, I would like to mention that this is not a problem with permutation, but a problem of combinations with a set of possible values for each position in the number. Below is a complete application that generates all the possible words/word combinations for the given number map and the number. Hope the inline comments are quite self-descriptive.
#include <stdio.h>
#include <string.h>
static const int NUM_MAX_CHARS = 5;
struct char_keys {
int key;
int count;
char chrs[NUM_MAX_CHARS];
};
/* Phone pad key mappings */
static char_keys s_keys[10] = {
{0, 1, {'0',} },
{1, 1, {'1',} },
{2, 3, {'A','B','C'} },
{3, 3, {'D','E','F'} },
{4, 3, {'G','H','I'} },
{5, 3, {'J','K','L'} },
{6, 3, {'M','N','O'} },
{7, 4, {'P','Q','R','S'}},
{8, 3, {'T','U','V'} },
{9, 4, {'W','X','Y','Z'}},
};
void print_key_map(int keystart, int keyend)
{
int i, cnt;
if (keystart > keyend)
return;
if (keystart < 0 || keyend < 0 || keystart > 9 || keyend > 9)
return;
for (i = keystart; i <= keyend; i++){
char_keys *chk = &s_keys[i];
printf("KEY %d: COUNT %d: ", i, chk->count);
for (cnt = 0; cnt < chk->count; cnt++) {
printf("%c", chk->chrs[cnt]);
}
printf("\n");
}
}
inline char get_char_key(int key, int pos)
{
char ret = 0;
if (key < 0 || key > 9)
return ret;
if (pos < 0 || pos >= NUM_MAX_CHARS)
return ret;
ret = s_keys[key].chrs[pos];
return ret;
}
void print_word(int num[], int idx[], int cnt)
{
int i;
char chrval;
for (i = 0; i < cnt; i++) {
chrval = get_char_key(num[i], idx[i]);
printf("%c", chrval);
}
printf("\n");
}
int get_key_max_idx(int key)
{
int rv;
rv = s_keys[key].count - 1;
return rv;
}
void gen_phone_words(int *nums, int cnt)
{
int i, uidx, mxidx;
int *pidx = NULL;
bool bFinished = false;
pidx = new int[cnt];
if (NULL == pidx)
return;
for (i = 0; i < cnt; i++)
pidx[i] = 0;
uidx = cnt - 1;
print_word(nums, pidx, cnt);
while (!bFinished) {
/* Increment the last number's index */
pidx[uidx]++;
int carry = 0;
for (i = uidx; i >= 0; i--){
pidx[i] += carry;
mxidx = get_key_max_idx(nums[i]);
if (pidx[i] > mxidx){
carry = 1;
pidx[i] = 0; // On overflow, reset this index to its lowest value
if (i == 0)
bFinished = true;
}
else {
break;
}
}
if (bFinished)
break;
print_word(nums, pidx, cnt);
}
delete [] pidx;
}
int* str_to_int_arr(char *str, int& cnt)
{
int *ret, *tmp, i;
int len;
if (NULL == str)
return NULL;
len = (int) strlen(str);
ret = new int[len];
if (NULL == ret)
return NULL;
tmp = ret;
for (i = 0; i < len; i++){
*tmp++ = static_cast<int>(str[i] - '0');
cnt++;
}
return ret;
}
int main(int argc, char* argv[])
{
int *dat = NULL, cnt = 0;
char num[100];
if (argc > 1)
strcpy(num, argv[1]);
else
strcpy(num, "363138");
printf("================\n");
dat = str_to_int_arr(num, cnt);
gen_phone_words(dat, cnt);
delete [] dat;
return 0;
}
- ashot madatyan May 09, 2012It can be implemented w/o any additional DS's in O(n Log n) time and with O(1) storage.
The below code and the driver app will find all the valid pairs, also included are the inlined comments:
#include <stdio.h>
#include <algorithm>
/*
Given an array of integers in the range INT_MIN to INT_MAX,
find all the pairs of elements that sum up to the given number @sum
Algorithm:
- Sort the input array
- Keep summing up the elements at the lowest and the highest current indices
- If the sum is > than the result, decrement the upper index
- If the sum is < than the result, increment the lower index
- If the sum = result, then
- found a valid pair; print the numbers
- converge the lower and upper indices (++lower, --upper)
- Loop until both indices meet
The above algorithm will find all the valid pairs, including positive,
negative and 0.
*/
bool find_sum(int arr[], int cnt, int sum)
{
int l, u, k;
bool bret = false;
/* Sort the input array */
std::sort(&arr[0], &arr[cnt]);
u = cnt - 1;
l = 0;
while (l < u) {
k = arr[l] + arr[u];
if (k == sum) { // found the two elements
printf("SUM: %-3d ELEMENTS (%d %d): %d %d\n",
sum, l, u,
arr[l], arr[u]);
bret = true;
l++;
u--;
}
else if (k < sum)
++l;
else
--u;
}
return bret;
}
int main(int argc, char* argv[])
{
int arr[] = {7, -4, 1, 0, -2, 3, 8, -9, 10, 1, 0, 20, 2};
int cnt = sizeof(arr)/sizeof(arr[0]);
for (int i = -10; i < 20; i++)
find_sum(arr, cnt, i);
return 0;
}
}}}
Set the range of bits from #L (least) to #H(highest)
1. Set the bit #(H-L+1)
2. Subtract 1 from the result
3. Shift the result by L bits to right
Just omitting the corner case checks to make the code clean.
#include <stdio.h>
int set_bits_range(int start, int end)
{
return ( (1 << (end - start + 1)) - 1 ) << start;
}
int main (int argc, char *argv[])
{
int rv = 0;
rv = set_bits_range(3, 5);
printf("%d\n", rv);
return 0;
}
Below is a simple implementation of the level order scan application using a single queue along with the driver program.
Also pasting the output.
#include <stdio.h>
#include <queue>
struct Node {
Node* left;
Node* right;
int data;
};
static Node g_Nodes[] = {
{NULL, NULL, 17},
{NULL, NULL, 5},
{NULL, NULL, 9},
{NULL, NULL, 12},
{NULL, NULL, 28},
{NULL, NULL, 1 },
{NULL, NULL, 20},
{NULL, NULL, 40},
{NULL, NULL, 38},
{NULL, NULL, 8 },
};
void bst_add(Node *pRoot, Node *pNew)
{
if (pNew->data < pRoot->data) {
if (NULL == pRoot->left)
pRoot->left = pNew;
else
bst_add(pRoot->left, pNew);
}
else {
if (NULL == pRoot->right)
pRoot->right = pNew;
else
bst_add(pRoot->right, pNew);
}
}
Node* bst_init()
{
Node *pRoot = &g_Nodes[0];
int cnt, i;
cnt = sizeof(g_Nodes)/sizeof(g_Nodes[0]);
for (i = 1; i < cnt; i++){
Node *pTmp = &g_Nodes[i];
bst_add(pRoot, pTmp);
}
return pRoot;
}
void bfs_scan_tree(Node *pNode)
{
int cur, nxt;
if (NULL == pNode)
return;
std::queue<Node*> Q;
Q.push(pNode);
cur = 1;
nxt = 0;
while (! Q.empty()) {
Node *ptmp = Q.front();
Q.pop();
/* Add the children of this node to the queue */
if (ptmp->left){
Q.push(ptmp->left);
nxt++;
}
if (ptmp->right){
Q.push(ptmp->right);
nxt++;
}
/* Process the current node and decrement the current counter */
printf("%-2d ", ptmp->data);
cur--;
/* Check if we have completed printing all the
nodes of the current level and process that case.
*/
if (0 == cur) {
cur = nxt;
nxt = 0;
printf("\n");
}
}
}
int main(int argc, char *argv[])
{
Node *pRoot = bst_init();
bfs_scan_tree(pRoot);
return 0;
}
17
5 28
1 9 20 40
8 12 38
#include <stdio.h>
void print_array(int arr[], int cnt, const char* hdr)
{
printf("%s\n", hdr);
for (int i = 0; i < cnt; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
void rearrange(int arr[], int cnt)
{
int cn[3] = {0};
int k = 0;
/* Count the number of integers */
for (int i = 0; i < cnt; i++){
cn[arr[i]]++;
}
print_array(arr, cnt, "Array before:");
/* Now fill back the array with the count of consecutive ints */
for (int i = 0; i < 3; i++){
for (int j = 0; j < cn[i]; j++) {
arr[k] = i;
k++;
}
}
print_array(arr, cnt, "Array after:");
return;
}
/*
Re-arrange an array containing only 0s,1s and 2s,
so that all 1s follow all 0s and all 2s follow 1s.
e.g. 00000011111111222222. Linear time algorithm.
*/
int main(int argc, char *argv[])
{
int arr[] = {0,0,0,0,2,1,2,0,2,1,2,1,2,0,1,0,1,0,2,0,1};
int cnt = sizeof(arr)/sizeof(arr[0]);
rearrange(arr, cnt);
return 0;
}
Use the QuickSelect algorithm (look it up at Wiki, (O(N) time complexity)) for the randomly distributed elements in the matrix or, if the columns and rows are sorted, do an in-place merge in O(N) time of columns (or rows) and just return the element at index "k".
- ashot madatyan April 29, 2012Just do a simple XOR of both strings, resulting in a O(N) time complexity.
bool anagrams(char *s1, char *s2)
{
int l1, l2, xv;
int i;
xv = 0;
if (NULL == s1 || NULL == s2)
return false;
l1 = strlen(s1);
l2 = strlen(s2);
if (0 == l1 || 0 == l2)
return false;
if (l1 != l2)
return false;
/* All corner cases verfied, start XOR'ing two strings */
for(i = 0; i < l1; i++){
xv ^= s1[i];
xv ^= s2[i];
}
/* If the two strings did not cancel each other out then they are not anagrams */
if (xv)
return false;
return true;
}
- ashot madatyan April 18, 2012This is the solution to your question, plus it returns the total count of nodes for the given node. Hope that the code is self explaining. :)
struct Node {
Node *left;
Node *right;
int leftcount;
int rightcount;
};
int node_count(Node *pNode)
{
int l = 0;
int r = 0;
if (NULL == pNode)
return 0;
if (pNode->left) {
l = 1 + node_count(pNode->left);
pNode->leftcount = l;
}
else {
pNode->leftcount = 0;
}
if (pNode->right) {
r = 1 + node_count(pNode->right);
pNode->rightcount = r;
}
else {
pNode->rightcount = 0;
}
return l + r;
}
Below I am producing the code that generates any length of words based on the given conversion map (number to possible characters). Though filtering out all the meaningful words is not implemented (leaving this to make the code base as concise as possible), I think the main algorithm for generating the combinations (please note, this is not a permutation) of all the possible words is quite straightforward.
#include <stdio.h>
#include <string.h>
static const int NUM_MAX_CHARS = 5;
struct char_keys {
int key;
int count;
char chrs[NUM_MAX_CHARS];
};
static char_keys s_keys[10] = {
{0, 1, {'0',} },
{1, 1, {'1',} },
{2, 3, {'A','B','C'} },
{3, 3, {'D','E','F'} },
{4, 3, {'G','H','I'} },
{5, 3, {'J','K','L'} },
{6, 3, {'M','N','O'} },
{7, 4, {'P','Q','R','S'}},
{8, 3, {'T','U','V'} },
{9, 4, {'W','X','Y','Z'}},
};
void print_key_map(int keystart, int keyend)
{
int i, cnt;
if (keystart > keyend)
return;
if (keystart < 0 || keyend < 0 || keystart > 9 || keyend > 9)
return;
for (i = keystart; i <= keyend; i++){
char_keys *chk = &s_keys[i];
printf("KEY %d: COUNT %d: ", i, chk->count);
for (cnt = 0; cnt < chk->count; cnt++) {
printf("%c", chk->chrs[cnt]);
}
printf("\n");
}
}
inline char get_char_key(int key, int pos)
{
char ret = 0;
if (key < 0 || key > 9)
return ret;
if (pos < 0 || pos >= NUM_MAX_CHARS)
return ret;
ret = s_keys[key].chrs[pos];
return ret;
}
void print_word(int num[], int idx[], int cnt)
{
int i;
char chrval;
for (i = 0; i < cnt; i++) {
chrval = get_char_key(num[i], idx[i]);
printf("%c", chrval);
}
printf("\n");
}
int get_key_max_idx(int key)
{
int rv;
rv = s_keys[key].count - 1;
return rv;
}
void gen_phone_words(int *nums, int cnt)
{
int i, uidx, mxidx;
int *pidx = NULL;
bool bFinished = false;
pidx = new int[cnt];
if (NULL == pidx)
return;
for (i = 0; i < cnt; i++)
pidx[i] = 0;
uidx = cnt - 1;
print_word(nums, pidx, cnt);
while (!bFinished) {
/* Increment the last number's index */
pidx[uidx]++;
int carry = 0;
for (i = uidx; i >= 0; i--){
pidx[i] += carry;
mxidx = get_key_max_idx(nums[i]);
if (pidx[i] > mxidx){
carry = 1;
pidx[i] = 0; // On overflow, reset this index to its lowest value
if (i == 0)
bFinished = true;
}
else {
break;
}
}
if (bFinished)
break;
print_word(nums, pidx, cnt);
}
delete [] pidx;
}
int* str_to_int_arr(char *str, int& cnt)
{
int *ret, *tmp, i;
int len;
if (NULL == str)
return NULL;
len = (int) strlen(str);
ret = new int[len];
if (NULL == ret)
return NULL;
tmp = ret;
for (i = 0; i < len; i++){
*tmp++ = static_cast<int>(str[i] - '0');
cnt++;
}
return ret;
}
int main(int argc, char* argv[])
{
int *dat = NULL, cnt = 0;
char *num = NULL;
if (argc > 1)
num = argv[1];
else
num = "+37491210701";
dat = str_to_int_arr(num, cnt);
gen_phone_words(dat, cnt);
delete [] dat;
return 0;
}
Just please notice that the find utility uses a 0-based logic. So, if the K=1, then this will actually request the second largest item. For the rest of the logic, you can use the code and have it run with any data you find appropriate.
- ashot madatyan March 16, 2012JAR A(5L) JAR B(3L)
5 0
-> (Pour to B)
2 3
-> (Empty the B)
2 0
-> (Pour to B)
0 2
->(Fill 5 L into A )
5 2
->(Pour 1L to B to get 3 L in the B)
4 3
void reverse(Node *pRoot)
{
if (NULL == pRoot)
return;
Node *ptmp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = pTmp;
reverse(pRoot->left);
reverse(pRoot->right);
}
- ashot madatyan March 15, 2012I am fixing my previous wrong implementation here:
struct Node {
Node *left;
Node *right;
int data;
};
Node* find_kth_largest(Node *pNode, int& K)
{
Node *pTmp = NULL;
if (pNode == NULL)
return NULL;
if (pNode->right){
pTmp = find_kth_largest(pNode->right, K);
if (pTmp) {
return pTmp;
}
}
if (0 == K) {
return pNode;
}
else {
K--;
if (pNode->left){
pTmp = find_kth_largest(pNode->left, K);
if (pTmp)
return pTmp;
}
}
return NULL;
}
- ashot madatyan March 12, 2012Smart solution and well done ! This is what interviewers most probably are looking for during technical interviews. As for accounting for the negative numbers, I think it's just a matter of checking the sign before starting extracting the individual digits and keeping a flag for that.
- ashot madatyan March 11, 2012Dear Free Bird, what if one of the arrays (suppose the smaller one) contains duplicate values? Should the duplicates be considered as a part of intersection?
If the intersection is to contain only unique values, those algos are not going to produce valid results.
In best case It takes (2*N + N*logN ) time.
Moreover, the initial order of the non-zero values will be broken, which may not be the intent of the interview question if you sort the elements in the array.
Thanks for noting that, hitman. I just somehow missed that. Anyway, below is the implementation required. Anyway, the idea in this algorithm is just using a single index of the last position where the zero was encountered.
Below is the implementation for groupping zeros to right:
void group_zeros_right(int dat[], int count)
{
int i;
int zidx = count; // Initially set to a non-valid value
for(i = 0; i < count; i++) {
if (0 == dat[i] ){
if (count == zidx )
zidx = i;
}
else { // the current item is not a zero
if (zidx != count) { // if we had a hole in between
swap_ints(dat, zidx, i);
zidx++; // Increment to next index, since it is the next hole
}
}
}
}
- ashot madatyan March 10, 2012Thanks for noting that, hitman. I just somehow missed that. Anyway, below is the implementation required. Anyway, the idea in this algorithm is just using a single index of the last position where the zero was encountered.
Below is the implementation for groupping zeros to right:
void group_zeros_right(int dat[], int count)
{
int i;
int zidx = count; // Initially set to a non-valid value
for(i = 0; i < count; i++) {
if (0 == dat[i] ){
if (count == zidx )
zidx = i;
}
else { // the current item is not a zero
if (zidx != count) { // if we had a hole in between
swap_ints(dat, zidx, i);
zidx++; // Increment to next index, since it is the next hole
}
}
}
}
- ashot madatyan March 10, 2012Here is an implementation with O(N) time complexity and O(1) storage.
inline void swap_ints(int dat[], int idx1, int idx2)
{
dat[idx1] = dat[idx1] ^ dat[idx2];
dat[idx2] = dat[idx1] ^ dat[idx2];
dat[idx1] = dat[idx1] ^ dat[idx2];
}
void group_zeros(int dat[], int count)
{
int i;
int zidx = count; // Initially set to a non-valid value
for(i = count - 1; i >= 0; i--) {
if (0 == dat[i] ){
if (count == zidx )
zidx = i;
}
else { // the current item is not a zero
if (zidx != count) { // if we had a hole in between
swap_ints(dat, zidx, i);
zidx--; // Decrement to next index, since it is the next hole
}
}
}
}
void print_array_spiral(int mat[4][5])
{
int j, i;
int min_row, max_row;
int min_col, max_col;
min_row = 0;
max_row = 3;
min_col = 0;
max_col = 4;
while (min_col < max_col && min_row < max_row) {
// Move rightwards and print
for (i = min_col; i <= max_col; i++)
printf("%2d ", mat[min_row][i]);
min_row++;
// Move downwards and print
for (i = min_row; i <= max_row; i++)
printf("%2d ", mat[i][max_col]);
max_col--;
// Move leftwards and print
for (i = max_col; i >= min_col; i--)
printf("%2d ", mat[max_row][i]);
max_row--;
// Move upwards and print
for (i = max_row; i >= min_row; i--)
printf("%2d ", mat[i][min_col]);
min_col++;
printf("\n");
}
printf("\n"); // one round is over, proceed to the next
}
In-place implementation of the reverse sentence words. Algorithm description inlined in s/c.
#include <stdio.h>
#include <string.h>
void rev_string(char *dat, int len)
{
char *ps, *pe, tmp;
if (1 == len)
return;
ps = dat; // the start of the data
pe = dat + len - 1; // the end (last char) of the data
while (ps < pe) {
tmp = *ps;
*ps = *pe;
*pe = tmp;
ps++;
pe--;
}
}
/**
Do an in-place reversing of the words in sentence,eg.
"1234 56 78 9" -> "9 78 56 1234"
Algorithm:
1. Reverse the whole string
2. Scan the resulting sentence from left to right and:
a) Find each token (word delimited by whitespace)
b) Reverse each token
c) Loop back to a) while there are more tokens
*/
void rev_sentence_words(char dat[], int len)
{
int i, j;
char *ps;
rev_string(dat, len);
for (i = 0; i < len; i++) {
if (dat[i] == ' ')
continue;
j = i;
ps = &dat[j];
/* Find the next whitespace */
while (dat[i] && dat[i] != ' ')
i++;
rev_string(ps, i - j);
}
}
int main(int argc, char* argv[])
{
char dat[] = " the careercup just rocks ";
printf("Before: <%s>\n", dat);
rev_sentence_words(dat, strlen(dat));
printf("After: <%s>\n", dat);
return 0;
}
I think one of the patterns here is the "not repeating double of the value" solution by Naseer, so the two lines are:
ACE HIKL...
BDE GJOP...
Sort in-place and wo additional storage. For the sake of brevity, some checkings are omitted.
void sort_zeros_n_ones(int dat[], int count)
{
int s, e;
s = 0;
e = count - 1;
/* We want values to be sorted in ascending order, i.e. like "000..11..1" */
while (s < e) {
while(dat[s] == 0) {
s++;
}
while(dat[e] == 1) {
e--;
}
if (s < e) {
swap(dat, s, e);
s++;
e--;
}
}
}
When the interviewer said "wo loops", I presume he meant wo nested loops. Anyway, below is the single loop solution, though we could also implement it with recursion, which as noted earlier, would be an overkill.
void print_bl_tr_diag(int a[][], int n)
{
for (int j = n - 1; j >= 0; j--)
printf("%d\n", a[j][n - j - 1]);
}
/**
@shpos - how many positions to shift (left or right)
@dir - left (-1) or right(1) shift
*/
int cyclic_shift(int num, int shpos, int dir)
{
int retv;
if ((0 == shpos) || (sizeof(int) * CHAR_BIT == shpos))
return num;
/* Prevent losing any bit of the original value */
shpos = shpos % (sizeof(int) * CHAR_BIT);
if (dir > 0) // the right cyclic shift
retv = (num >> shpos) | ( num << (sizeof(int) * CHAR_BIT - shpos));
else // the left cyclic shift
retv = (num >> ( sizeof(int) * CHAR_BIT - shpos )) | (num << shpos);
return retv;
}
If the matrix is sorted both on its columns and rows (and assuming the sort order is ascending for both columns and rows), you can process the matrix as a simple linear array of sorted values and use a simple binary (O(logN)) search to find the sought value or confirm that the values is missing from the matrix.
- ashot madatyan February 08, 2012Below is the implementation of the algorithm in c++ with all the descriptions inlined as comments:
template <class T>
void __swap(T& left, T& right)
{
T tmp;
tmp = left;
left = right;
right = tmp;
}
bool digs_to_int(char dat[], int elcount, int& val)
{
int retv = 0;
if (0 == elcount)
return false;
val = -1;
for (int i = 0; i < elcount; i++){
retv = retv * 10 + dat[i];
}
val = retv;
return true;
}
/**
- start scanning from the right at position (elcount - 1) and find the digit
with index @i such that d[i] < d[i+1];
- sort the array from @i+1 to @elcount
- from position @i+1 find the smallest digit such that d[i]<d[smallest_digit_pos]
- swap(d[i], d[smallest_digit_pos])
@dat - the array of chars with the number digits
@elcount - count of elements in the array
*/
bool next_max_val(char dat[], int elcount, int& nxtmax)
{
int i;
int minidx; // index of the first value on the right of the pivot that is greater than the pivot value
int pividx; // the pivot index
int eidx; // the last index of the array
nxtmax = -1;
eidx = elcount - 1;
pividx = -1; // initially set to invalid index (not found)
minidx = -1;
/* Find the digit that is less than its successor digit. */
for (i = eidx - 1; i >= 0; i--) {
if (dat[i] < dat[i + 1]) {
pividx = i;
break;
}
}
/* If there is no such digit then this is the maximum value */
if (-1 == pividx) {
digs_to_int(dat, elcount, nxtmax);
printf("This is the maximum number: %d\n", nxtmax);
return true;
}
/* Sort the array starting from the element next to the pivot */
std::sort(dat + pividx + 1, dat + eidx + 1);
/* Find the first digit in the rest of the sorted digits that is > than
the pivot value at dat[pividx]*/
for (i = pividx + 1; i < elcount; i++) {
if (dat[pividx] < dat[i]) {
minidx = i;
break;
}
}
/* Swap the pivot value and the minimal value in the rest of the
* sorted array. */
__swap(dat[i], dat[pividx]);
digs_to_int(dat, elcount, nxtmax);
return true;
}
1. Reserve 3 bits for the count of payload bits, thus allowing numbers 0-7
2. Use the rest of the 5 bits in the <char> to communicate the payload
This solution enables transferring 5 different combinations in a single char,
as well as communicating the actual size of the payload.
1. Reserve 3 bits for the count of payload bits, thus allowing numbers 0-7;
2. Use the rest of the 5 bits in the <char> to transfer the payload;
This solution enables transferring 5 different combinations in a single char,
as well as communicating the actual size of the payload.
@salvo: This does not do what is required - swap every two bits. Instead, it does two lower BYTES.
- ashot madatyan May 16, 2012