Change

Never thought people (me for that matter) change so quickly. Not long ago I posted here about how I don’t enjoy computers much but just barely make up with them. Yesterday I had to travel to my parents and I was shocked at how badly I was bored when I was not coding. I had to stop listening to music and open a terminal and start coding. I guess when one does something everyday, it becomes difficult to hate it (arranged marriages? :P). Wanted to start on a task which I could complete so wrote the complete code for reversing all the words in a given string (ya ya … I know .. I know its too easy :D).
Re-wrote all the library functions, have to confirm their behaviour though :P. Do let me know if there are any obvious/major bugs.

#include <stdio.h>
#include <stdlib.h>

#define _DEBUG_HAULT_ scanf("%*d");
#define STR_TERM '\0'
#define MAX_INPUT_LENGTH 1000
#define DELIMITERS " ,.':;"

int my_strlen(const char* str) {
  register int len = -1;
  for (;*(str + ++len););
  return len;
}

char* my_strchr(const char* s, int ch) {
  if (NULL == s) return NULL;
  for (; STR_TERM != *s && *s != ch; ++s);
  return STR_TERM == *s ? NULL : (char *)s;
}

char* my_strrev(const char* str, register int l) {
  register int i = -1;
  char *retVal = (char *)malloc(sizeof(char) * l);
  retVal[0] = retVal[l] = STR_TERM;
  for (; l; retVal[++i] = str[--l]);
  return retVal;
}

char* my_strtok(char *buf, const char* delim) {
  static char* record;
  record = (buf == NULL) ? record : buf;
  if (*record == STR_TERM || NULL == record) return NULL;
  char* temp = record;
  while ((STR_TERM != *record) && (NULL == my_strchr(delim, *record))) {
    ++record;
  }
  if (STR_TERM == *record) return temp;
  while ((STR_TERM != *record) && (NULL != my_strchr(delim, *record))) {
    *record = STR_TERM;
    ++record;
  }
  return temp;
}

// Removes all the punctuations (marked in constant DELIMITERS) and inserts
// only 1 space between words.
int main(int argc, char *argv[]) {
  char input[MAX_INPUT_LENGTH], output[MAX_INPUT_LENGTH];
  input[0] = output[0] = STR_TERM;
  scanf("%[^\n]", input);
  register int len = 0, temp = 0;
  register char* ptr = NULL;
  for (ptr = my_strtok(input, DELIMITERS);
       ptr;
       ptr = my_strtok(NULL, DELIMITERS)) {
    temp = my_strlen(ptr);
    sprintf(output + len, "%s ", my_strrev(ptr, temp));
    len += (temp + 1);
  }
  output[len - 1] = STR_TERM;
  printf("%s\n", output);
  printf("%s\n", my_strrev(output, my_strlen(output)));
  return 0;
}

After I was done, I found out about strsep 😛

Advertisements

Interview Problems 23

1. A question set is given to you and you have to generate (question numbers are in an array) generate different set of question paper for k students.

2. Given an array of integers, find out number of ways in which you can select increasing subsequences of length k(k “abcababceced” (2 ‘c’ are removed)
After removing repeated substring of length 2: “abcababceced” –> “abcabceced” (substring “ab” is removed) and so on.

3. You are given a 1D array of integers, such as:
int[] array = [3,4,7,2,2,6,0,9];
Suppose you need to treat this array as a 2D table with a given number of rows.
You want to sum the columns of the table.
One value of numRows is 4..in that case the resultant array would look like
what if numRows==4?
3 4
7 2
2 6
0 9
—-
12 21

4. Given an unsorted array, find the longest consecutive elements sequence.
Ex: 5 7 3 4 9 10 1 15 12
Ans: 3 4 5

5. You have to create a graph in most efficient way from relationship of nodes read from txt file.
text file contains information like:
node_id weight node_id
node_id weight node_id
…..
// which means two nodes are connected with some weight. (undirected)
There are around 600K such information for about 65000 nodes.
Aim is to create a a subgraph for a given node_id. i.e for that node_id find ALL successor nodes with level mentioned i.e form a subgraph for that node.

6. Given ‘n’ no of sets and each set is of a variable size. Find out the cross product of these ‘n’ of sets.
For eg. {1,2} , {3,4} , {5,6,7} these are the three sets.The cross product of these sets would be as below.
{1,3,5},{1,3,6},{1,3,7},{1,4,5},{1,4,6},{1,4,7},{2,3,5},{2,3,6},{2,3,7},{2,4,5},{2,4,6},{2,4,7}.

7. Given an array of integers, find out number of ways in which you can select increasing subsequences of length k(k<=n).
eg array is 1 4 6 2 5 & k=3
Output: 3
Sequences: 1 4 6, 1 4 5, 1 2 5

8. Sorry posted this question as a repetition of question 1.

9. Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays
eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0

10. Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1).

Interview Questions 22

1. Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141

2. I have a card pack of 313 cards. I remove the topmost card from card pack and place it on desk and I remove the next one and put it below the pack of cards(that you are holding). keep doing this till all the cards are on desk. Pick up the card stack from desk and repeat these steps till you find retrieve the original cards order.

3. [Design + Graph Traversal] Assume you have a set of 1500 independent pieces of code. We’ll call them projects. Each project can either be:
1) completely independent
2) dependent on other projects
3) dependent on other projects and have other projects dependent on it
The combined build times of all 1500 projects is 24 hours(so build project 1, when it finished, build project 2, etc). A build consists of compiling and linking all the requisite code. You can assume you don’t have to worry about a budget. If there’s a tool that would help you out, you can use it if you can describe how it works. How would you speed up the build process?

4. Given a BST in a language where memory must be handled manually, how do you completely remove BST from memory? Recursion is not allowed. [O(N), O(1)]

5. [Don’t vomit out TRIE] You are developing a system for a cell phone which will automatically predict what word a user is typing. Talk about the data structures and algorithms you would use to make this, keeping in mind that cell phones have limited memory/CPU power.

6. There are N web servers. Each web server has a huge file containing random 1 million numbers (numbers can repeat). Find the median of these N million numbers given that only 1 million numbers can be brought into memory at a time.

7. Many irregular shape objects are moving in random direction. provide data structure and algo to detect collision. Remember that objects are in million.

8. A complete ternary tree is a tree in which each and every node has either 0 or 3 children . Given preorder of a complete ternary tree , construct the tree . Preorder will be a string containing characterd i and l where i represents an internal node and l represent a leaf node .

9. [Math] Find the number of strings of length n having u distinct uppercase letters , l distinct lowercase letters and d distinct digits.

10. Given a sorting order string, sort the input string based on the given sorting order string.
Ex. sorting order string -> dfbcae
Input string -> abcdeeabc
output -> dbbccaaee

%d bloggers like this: