Microsoft Interview Question Applications Developers
Country: India
Interview Type: Written Test
Sample Input : [1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 16, 20, 23, 30,31,32]
Sample Linked List : [1] -> [3,4,5] -> [8,9] -> [11] -> [13,14,15,16]->[20]->[23]->[30,31,32]
#include <iostream>
using namespace std;
struct list
{
char *value;
list * next;
}*first=NULL;
void JoinList(int A[],int size)
{
char *tempString = new char(15);
int i=0;list *currentNode;
while(i<size)
{
list *temp=new list;
temp->value=new char(15);
strcpy(temp->value,"");
temp->next=NULL;
do
{
itoa(A[i],tempString,10); //convert array element to string
strcat(temp->value,tempString); //concatenate to current node
i++;
if(i>=size)
break;
}while(A[i]==(A[i-1]+1)); // till the next element is one greater than the current element
if(first==NULL)
{
first=temp;
currentNode=temp;
}
else
{
currentNode->next=temp;
currentNode=temp;
}
}
}
void display(list * node)
{
while(node!=NULL)
{cout<<node->value<<" ";
node=node->next;
}
}
int main()
{
int A[12]= {2,3,4,5,6,9,10,12,13};
JoinList(A,9);
display(first);
system("pause");
return 0;
}
Steps :-
1) convert current array element to string & add to list
2) read & concatenate further elements provided the next element = previous element + 1
3) repeat 1 & 2 to form the linked list till you run out of array elements
Just see the comments in Join List Function. You will understand
Hi
If you observe the input there are some numbers followed by consecutive numbers. For eg:
1 does not have consecutive number 2. So, add 1 in Linked list node.
Add next element in input, i.e 3 to another node of Linked List, then check in the input array for 3 consecutive, i.e 4, it is available. So, add 4 to the same node of Linked list. Like that 5 also to the same node of Linked List.
Now, the linked list contains the [1]->[3,4,5]
Next element in 8 not consecutive to 5. So, add 8 to another node of Linked list.
Like that will have to create Linked List.
Hope you understand the sequence.
Final Sequence is : [1 ]-> [3,4,5]-> [8,9] -> [11] -> [13,14,15,16] -> [20] -> [23] -> [30,31,32].
String[] sa = new String[] { "A", "B", "C" };
LinkedList ll = new LinkedList(Arrays.asList(sa));
// iterate over each element in LinkedList
Iterator iterator = ll.iterator();
while (iterator.hasNext()) {
// Print element to console
System.out.println((String) iterator.next());
}
Hoping that it will help you.
I didn't get the question. It is always a good idea to add an example use case with the question
Integer[] sa ={1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 16, 20, 23, 30,31,32};
LinkedList aa = new LinkedList();
aa.addFirst(sa[0]);
for(int i=1;i<sa.length-1;i++){
if(sa[i-1]+1==sa[i]){
aa.removeLast();
String temp="";
for(int j=i-1;j<sa.length-1;j++){
int a=sa[j];
int b=sa[j+1];
if(a+1==b){
temp=temp+Integer.toString(sa[j])+":";
if(j==sa.length-2){
temp=temp+Integer.toString(sa[j+1]);
aa.addLast(temp);
i=j;
break;
}
}else{
temp=temp+Integer.toString(sa[j]);
aa.addLast(temp);
i=j;
break;
}
}
}else{
aa.addLast(sa[i]);
}
}
Iterator iterator = aa.iterator();
while (iterator.hasNext()) {
// Print element to console
System.out.print(iterator.next()+" ");
}
It works.
This is tested code in Java
/*
* Input array = [1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 16, 20, 23, 30, 31 32]
* Output = [1]->[3,4,5]->[8,9]->[11]->[13,14,15,16]->[20]->[23]->[30,31,32]
*/
public static void arrangeList(int[] arr)
{
List<Object[]> l = new LinkedList<Object[]>();
ArrayList internalArr = new ArrayList();
for(int i = 0; i < arr.length; i++)
{
if(l.isEmpty() && i == 0)
{
internalArr.add(arr[i]);
}
if(i > 0)
{
if(arr[i] - arr[i-1] != 1)
{
l.add(internalArr.toArray());
internalArr =new ArrayList();
internalArr.add(arr[i]);
}
else
{
internalArr.add(arr[i]);
}
}
}
l.add(internalArr.toArray());
/*
* Print Output
*/
for(int i = 0 ; i < l.size(); i++)
{
Object[] objArr = l.get(i);
int count = 0;
for(Object ob : objArr)
{
if(count != 0)
System.out.print("->");
Integer printer = new Integer((Integer) ob);
System.out.print(printer.intValue());
count++;
}
System.out.println();
}
}
public static List<String> continousInt(int a[]){
if(a.length == 0)
return null;
List <String > l = new LinkedList<String>();
int i = 0;
String s = ""+a[i];
int last = a[i];
i++;
while(i<a.length){
if(last+1 ==a[i]){
s = s +a[i];
}else{
l.add(s);
s= ""+a[i];
}
last = a[i];
i++;
}
l.add(s);
return l;
}
public static void main(String[] args) {
Integer[] input = {1,3,4,5,8,9,11,13,14,15,16,20,23,30,31,32};
LinkedList outputList = new LinkedList();
List<Integer> nodes = new ArrayList<Integer>();
for (int i = 1 ; i < input.length ; i++) {
nodes.add(input[i-1]);
if(input[i] == input[i-1] + 1 ) {
continue;
}
else {
int j = outputList.size();
outputList.add(j,nodes);
nodes = new ArrayList<Integer>();
j--;
}
}
System.out.println(outputList);
}
public static void main(String[] args) {
Integer[] input = {1,3,4,5,8,9,11,13,14,15,16,20,23,30,31,32};
LinkedList outputList = new LinkedList();
List<Integer> nodes = new ArrayList<Integer>();
for (int i = 1 ; i < input.length ; i++) {
nodes.add(input[i-1]);
if(input[i] == input[i-1] + 1 ) {
continue;
}
else {
int j = outputList.size();
outputList.add(j,nodes);
nodes = new ArrayList<Integer>();
j--;
}
}
System.out.println(outputList);
}
Hi please find the java code to convert the input array into a linkedlist each node containing a sequence.
Please reply if you find any mistakes .
class LinkedListNode {
String sequeunce;
LinkedListNode next;
}
public class IntegerArrayToSequenceList {
public static void main(String[] args) {
int[] inputArray = { 1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 16, 20, 23, 30,
31, 32 };
LinkedListNode head = null;
LinkedListNode current = new LinkedListNode();
head = current;
StringBuffer strBuf = new StringBuffer();
for (int i = 0; i < inputArray.length; i++) {
if (i + 1 < inputArray.length
&& inputArray[i] == inputArray[i + 1] - 1)
strBuf.append(inputArray[i] + ",");
else {
strBuf.append(inputArray[i]);
current.sequeunce = strBuf.toString();
strBuf.delete(0, strBuf.length());
LinkedListNode temp = new LinkedListNode();
current.next = temp;
current = temp;
}
}
while (head != null) {
if (head.sequeunce != null)
System.out.println(head.sequeunce);
head = head.next;
}
}
}
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int a[]= {1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 16, 20, 23, 30,31,32};
struct node
{
char data[10];
struct node *next;
};
struct node* createnode(int x)
{
struct node* temp;
temp=(struct node*)malloc(sizeof(struct node));
char s[10];
itoa(x,s,10);
strcpy(temp->data,s);
temp->next=NULL;
return temp;
}
void insert(struct node**p)
{
int i;
struct node *temp,*link;
char s1[10];
for(i=0;i<16;i++)
{
if(a[i]+1!=a[i+1])
{
temp=createnode(a[i]);
if(*p==NULL)
{
*p=temp;
link=temp;
}
else
{
link->next=temp;
link=link->next;
}
}
else
{
temp=createnode(a[i]);
while(a[i]+1==a[i+1])
{
itoa(a[i+1],s1,10);
strcat(temp->data,",");
strcat(temp->data,s1);
i++;
}
link->next=temp;
link=link->next;
}
}
}
void show(struct node *p)
{
while(p!=NULL)
{
printf("\n%s",p->data);
p=p->next;
}
}
int main()
{
int i;
struct node *p=NULL;
insert(&p);
show(p);
getch();
return 0;
}
This is tested code in C++, making use of the STL.
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
struct sequence {
int start_num;
int sequence_length;
};
void sequencify(int *input,int length,list<sequence> &first_seq) {
list<sequence> retval;
if (input == NULL || length < 1) {
return;
}
sequence s;
s.start_num = *input;
s.sequence_length = 1;
first_seq.push_back(s);
for (int *i = input + 1;i < input + length;i++) {
if (*(i - 1) == (*i) - 1) {
first_seq.back().sequence_length++;
}
else {
sequence s;
s.start_num = *i;
s.sequence_length = 1;
first_seq.push_back(s);
}
}
}
int main(int argc, const char * argv[])
{
vector<int> vecint;
for (int i = 0;i < 100;i++) {
vecint.push_back((int) rand()%100);
}
sort(vecint.begin(),vecint.end());
for (int j : vecint) {
cout << j << " ";
}
cout << endl;
list<sequence> result;
sequencify( vecint.data(), vecint.size(), result);
for (auto j : result) {
cout << "Start: " << j.start_num << " Length " << j.sequence_length << "\n";
}
return 0;
}
Try this one......Above code are not correct (posted by Rahul)....That's not printing last sequence of Numbers
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class IntArrayToLinkedListSequence {
public static void main(String[] args) {
int[] input = { 1, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15, 16, 20, 23, 30,
31, 32, 45, 66, 58, 98, 45, 23, 24, 25, 55, 56 };
List<List> outputList = new LinkedList<List>();
ArrayList<Integer> nodes = new ArrayList<Integer>();
for (int i = 0; i < input.length; i++) {
nodes.add(input[i]);
if (i + 1 < input.length && input[i] == input[i + 1] - 1) {
continue;
}
else {
int j = outputList.size();
outputList.add(j, nodes);
nodes = new ArrayList<Integer>();
}
}
System.out.println(outputList);
}
}
Output:
[[1], [3, 4, 5, 6], [8, 9], [11], [13, 14, 15, 16], [20], [23], [30, 31, 32], [45], [66], [58], [98], [45], [23, 24, 25], [55, 56]]
wat do you mean by containing one sequence??
- sahil.bathla1 November 15, 2012